?
Вычислительная сложность манипулирования в задаче голосования
.
В ситуациях, когда коллективу требуется принять решение на основе множества индивидуальных предпочтений, применяется тот или иной метод агрегирования, в частности, голосование. Одной из главных проблем для любой недиктаторской процедуры выбора является манипулирование - возможность у избирателей добиться более выгодного для себя исхода голосования при помощи искажения своих предпочтений. Один из подходов, используемых для сравнения процедур по степени манипулируемости, – выявление класса сложности задачи манипулирования при том или ином методе агрегирования. В настоящей работе представлен обзор литературы по исследованию классов сложности задач манипулирования при различных предположениях и ограничениях в модели.
Язык:
русский
Ключевые слова: коллективный выборsocial choiceвычислительная сложностьманипулированиеsocial choice rulesmanipulationправила коллективного выбораComputational Complexity
ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА:
В книге
Красноярск: Сибирский федеральный университет, 2014.
Дудаков С. М., Карлов Б. Н., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2025 Т. 524 № 1 С. 11–18
В работе изучается проблема тотальной выводимости в контекстно-свободных, неукорачивающих и контекстно-зависимых грамматиках. Для фиксированного терминального слова проблема состоит в том, чтобы по грамматике определить, существует ли вывод этого слова, в котором каждое правило используется не менее некоторого заданного числа раз. Доказывается, что проблема тотальной выводимости пустого слова в контекстно-свободной грамматике является NP-полной. Для неукорачивающих и ...
Добавлено: 18 марта 2026 г.
Сперанский С. О., Алгебра и логика 2013 Т. 52 № 2 С. 236–254
Изучаются иерархии проблем общезначимости для префиксных фрагментов вероятностной логики с кванторами по пропозициональным формулам, обозначаемой QPL, и её вариантов. Доказывается: если подполе F вещественных чисел определимо в стандартной модели арифметики посредством формулы второго порядка, не содержащей кванторов по множествам, то проблема общезначимости над F-значными вероятностными структурами для $\Sigma_4$-QPL-предложений является $\Pi^1_1$-полной и, как следствие, соответствующая иерархия проблем общезначимости схлопывается. Более того, при ...
Добавлено: 27 декабря 2025 г.
Дахно Г. С., Малышев Д. С., Математические заметки 2026 Т. 119 № 3 С. 360–376
Наследственный класс — множество графов, замкнутое относительно удаления вершин. Каждый такой класс имеет каноническое описание посредством минимальных запрещенных порожденных фрагментов. Задача о вершинной 3-раскраске (задача 3-ВР) для заданного графа состоит в том, чтобы определить, а можно ли множество его вершин разбить на три подмножества попарно несмежных вершин. Известна дихотомия сложности этой задачи для всех наследственных ...
Добавлено: 26 ноября 2025 г.
Оноприенко А. А., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2025 № 527 С. 206–216
Мы исследуем кооперативную карточную игру “Ханаби” с точки зрения алгоритмической сложности. Особенность “Ханаби” заключается в том, что игроки видят карты других игроков, но не свои, и об- мениваются информацией путем подсказок. Даже в модели с одним игроком, обладающим полной информацией о колоде, “Ханаби” остается NP-трудной. Найдены минимальные параметры игры, при которых сохраняется NP-трудность. В случае ...
Добавлено: 23 ноября 2025 г.
N. L. Polyakov, Shamolin M. V., Journal of Mathematical Sciences 2025 Vol. 292 No. 6 P. 793–803
Добавлено: 8 октября 2025 г.
Рыбаков М. Н., Щербаков М. И., В кн.: Четырнадцатые Смирновские чтения по логике: материалы Междунар. науч. конф., Москва, 19-21 июня 2025 г.: М.: Издатель Александр Воробьев, 2025. С. 46–49.
Логики с аксиомой конвергентности: сложность при малом числе переменных в языке ...
Добавлено: 21 июня 2025 г.
Кудинов А. В., Рыбаков М. Н., В кн.: Четырнадцатые Смирновские чтения по логике: материалы Междунар. науч. конф., Москва, 19-21 июня 2025 г.: М.: Издатель Александр Воробьев, 2025. С. 36–39.
Показано, что каждая модальная логика, содержащая классическую логику высказываний и содержащаяся в слабой логике Гжегорчика, имеет NP-трудную проблему выполнимости для константного фрагмента. В частности, константные фрагменты ненормальных модальных логик E, EM, EN и EMN являются coNP-полными. ...
Добавлено: 21 июня 2025 г.
Сапронов Ю. Ф., Юдин Н. Е., Computational Mathematics and Mathematical Physics 2025 Vol. 65 No. 3 P. 567–581
We continue to develop the concept of studying the ε-optimal policy for Average Reward Markov Decision Processes (AMDP) by reducing it to Discounted Markov Decision Processes (DMDP). Existing research often stipulates that the discount factor must not fall below a certain threshold. Typically, this threshold is close to one, and as is well-known, iterative methods ...
Добавлено: 10 июня 2025 г.
Дахно Г. С., Малышев Д. С., Математические заметки 2025 Т. 117 № 1 С. 62–78
Наследственный класс — множество обыкновенных графов, замкнутое относительно удаления вершин, каждый такой класс задается множеством своих минимальных запрещенных порожденных подграфов. Задача о доминирующем множестве для заданного графа состоит в том, чтобы определить, а имеется ли в нем такое подмножество вершин заданного размера, что каждая вершина вне подмножества имеет хотя бы одного соседа в данном подмножестве. ...
Добавлено: 3 декабря 2024 г.
Kryukov G. M., Сандомирская М. С., Automation and Remote Control 2024 Vol. 85 P. 696–710
In this paper, the disclosure of information about the scoring model is investigated. Some of the company’s customers find out their internal rating in the company. Such customers can change their behavior to increase their internal rating. The customers who are aware of the leakage are represented as players who can choose a strategy: whether ...
Добавлено: 19 ноября 2024 г.
Крюков Г. М., Сандомирская М. С., Автоматика и телемеханика 2024 № 8 С. 54–75
В данной статье моделируется раскрытие информации о скоринговой модели. Некоторые клиенты компании узнают свой внутренний рейтинг в компании. Такие клиенты могут изменить свое поведение, чтобы повысить свой внутренний рейтинг. Клиенты, знающие об утечке информации, являются игроками, которые могут выбирать стратегию: повышать ли свой внутренний рейтинг и если да, то насколько. Главная задача – найти в ...
Добавлено: 28 августа 2024 г.
Kirill V. Kaymakov, Dmitry S. Malyshev, Optimization Letters 2024 Vol. 18 P. 1273–1283
Добавлено: 18 апреля 2024 г.
Осипов Д. В., В кн.: Язык в межкультурном пространстве XXI века: взгляды и научные исследования, перспективы развития : Материалы Международной научно-практической конференцииВып. 1.: Астрахань: [б.и.], 2021. С. 112–118.
В статье рассматриваются стратегии и тактики вербального и невербального воздействия рекламных текстов (на примере китайского языка), даётся анализ манипуляций, применяемых в рекламных продуктах, выделяются национальноспецифические особенности китайской культуры, которые также присутствуют в рекламе. ...
Добавлено: 19 марта 2024 г.
Гаевская М. А., Мошняга Е. В., Чихачева Д. В., Вестник Челябинского государственного университета 2024 № 1 (483) С. 81–91
Исследование посвящено изучению особенностей репрезентации ценностей в мотивационном
дискурсе американских коучей, а также выбора ими речевых стратегий и тактик для завоевания доверия
аудитории и внушения им необходимой информации. В ходе исследования был составлен корпус примеров на основе видеовыступлений общей длительностью 8 часов. В результате исследования было уточне но определение мотивационного дискурса, были выявлены основные ценности американского общества
и ...
Добавлено: 6 марта 2024 г.
Малышев Д. С., Duginov O. I., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2023 Vol. 17 No. 4 P. 791–801
Добавлено: 16 февраля 2024 г.
Иванов А. А., , in: Data Analysis and Optimization. In Honor of Boris Mirkin's 80th Birthday.: Springer, 2023. P. 157–168.
Добавлено: 26 января 2024 г.
Иванов А. А., Журнал Новой экономической ассоциации 2022 № 5(57) С. 14–23
Аннотация: манипулирование – это ситуация, когда при голосовании один или несколько участников вписывают в бюллетень неискренние предпочтения, чтобы достичь более хорошего для себя исхода голосования. Было доказано, что не существует недиктаторской процедуры голосования, которая была бы неманипулируема. Для поиска наименее манипулируемых правил голосования исследователи обычно используют два подхода. Первый – вывод формулы для конкретного индекса ...
Добавлено: 26 января 2024 г.
The problem of query answering over incomplete attributed graph data is a challenging field of database management systems and artificial intelligence. When there are rules on data structure expressed in the form of the ontology, the theoretical complexity of finding exact solution satisfying ontology constraints increases. Logic-based methods use theoretical constructions to obtain efficient rewritings ...
Добавлено: 5 января 2024 г.
Юдина А. В., В кн.: Межвузовская научно-техническая конференция студентов, аспирантов и молодых специалистов им. Е.В. Арменского 2023.: МИЭМ НИУ ВШЭ, 2023. С. 7–11.
В работе рассматриваются способы выбора наилучших альтернатив на основании результатов их попарного сравнения. Подобный выбор является проблемой в ситуации, когда у любого варианта выбора есть более предпочтительный вариант. В литературе предложено много концепций решения поставленной задачи (так называемых турнирных решений). При этом особый интерес представляют обобщения турнирных решений на случай неполных сравнений, так как реальные ...
Добавлено: 5 ноября 2023 г.