?
Вычислительная сложность манипулирования в задаче голосования
.
В ситуациях, когда коллективу требуется принять решение на основе множества индивидуальных предпочтений, применяется тот или иной метод агрегирования, в частности, голосование. Одной из главных проблем для любой недиктаторской процедуры выбора является манипулирование - возможность у избирателей добиться более выгодного для себя исхода голосования при помощи искажения своих предпочтений. Один из подходов, используемых для сравнения процедур по степени манипулируемости, – выявление класса сложности задачи манипулирования при том или ином методе агрегирования. В настоящей работе представлен обзор литературы по исследованию классов сложности задач манипулирования при различных предположениях и ограничениях в модели.
Язык:
русский
Ключевые слова: коллективный выборsocial choiceвычислительная сложностьманипулированиеsocial choice rulesmanipulationправила коллективного выбораComputational Complexity
ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА:
В книге
Красноярск : Сибирский федеральный университет, 2014
Веселова Ю. А., Автоматика и телемеханика 2016 Т. 77 № 3 С. 7-32
В ситуациях, когда коллективу требуется принять решение на основе множества индивидуальных предпочтений, применяется тот или иной метод агрегирования, в частности голосование. Одной из главных проблем для любого недиктаторского правила коллективного выбора является возможность у избирателей добиться более выгодного для себя исхода голосования при помощи искажения своих предпочтений. Такие действия со стороны избирателей называются манипулированием или ...
Добавлено: 25 октября 2014 г.
Веселова Ю. А., Automation and Remote Control 2016 Vol. 77 No. 3 P. 369-388
In situations when a group of people has to make a decision based on the set of individual preferences, they use a certain aggregation method, in particular, voting. One of the main problems for any non-dictatorial social choice rule is the possibility for the voters to achieve a more preferable outcome of the voting by ...
Добавлено: 8 июня 2016 г.
Веселова Ю. А., , in : Clusters, orders, trees: methods and applications. In Honor of Boris Mirkin's 70th Birthday. Vol. 92.: Berlin : Springer, 2014. P. 391-404.
Procedures aggregating individual preferences into a collective choice differ in their vulnerability to manipulations. To measure it, one may consider the share of preference profiles where manipulation is possible in the total number of profiles, which is called Nitzan-Kelly's index of manipulability. The problem of manipulability can be considered in different probability models. There are ...
Добавлено: 24 октября 2013 г.
Субочев А. Н., Журнал Новой экономической ассоциации 2016 № 2(30) С. 181-192
С помощью коэффициента корреляции Кендалла три рейтинга российских научных журналов по экономике и менеджменту (рейтинг Муравьева, рейтинг НИУ ВШЭ и рейтинг Балацкого) сравниваются друг с другом и с ранжированиями входящих в них журналов по значениям библиометрических показателей НЭБ/РИНЦ. Оказывается, что эти рейтинги кор-релируют слабо, а степень их отличия от рейтингов НЭБ/РИНЦ сопоставима со степенью их ...
Добавлено: 26 июня 2016 г.
Субочев А. Н., В кн. : XVII Апрельская международная научная конференция по проблемам развития экономики и общества: в 4 кн. Кн. 1.: М. : Издательский дом НИУ ВШЭ, 2017. С. 111-120.
Основной задачей теории коллективного выбора является описание способов определения альтернатив, которые должны быть выбраны из числа имеющихся в наличии вариантов на основании мнения о них индивидуальных участников процесса принятия коллективных решений.
Математически выбор моделируется функцией выбора. В настоящем докладе рассматриваются три схожие функции, зависящие от коллективных предпочтений, моделируемых мажоритарным отношением: объединение минимальных Р-доминирующих множеств MPD, объединения ...
Добавлено: 26 июня 2016 г.
Fuad Aleskerov, Карабекян Д. С., Иванов А. А. и др., , in : Evaluating Voting Systems with Probability Models. : Cham : Springer, 2021. P. 231-249.
Добавлено: 14 апреля 2021 г.
Малышев Д. С., Дискретный анализ и исследование операций 2012 Т. 19 № 3 С. 58-64
В работе предлагается алгоритм, который определяет число независимости n-вершинного графа из класса Free({P5,C5, Kp}) за время O(np+O(1)). ...
Добавлено: 6 июня 2012 г.
Шитов Я. Н., St Petersburg Mathematical Journal 2014 Vol. 26 No. 2 P. 216-228
Добавлено: 24 мая 2014 г.
Алескеров Ф. Т., Субочев А. Н., Доклады Академии Наук. Информатика 2009 Т. 426 № 3 С. 318-320
Ординальная задача группового выбора определяется конечным множеством альтернатив и тем, что мнения участников относительно альтернатив выражается в виде бинарных отношений предпочтений; решение задачи ищется в виде выбора наилучшей альтернативы. В теории в качестве такой альтернативы обычно принимается победитель Кондорсе – альтернатива, более предпочтительная по сравнению с другими альтернативами для большинства участников при парном сравнении. Однако ...
Добавлено: 25 сентября 2014 г.
Малышев Д. С., Discrete Mathematics and Applications 2010 Vol. 19 No. 6 P. 625-630
Понятие граничного класса — полезный инструмент изучения сложности экстремальных задач на графах. В настоящее время известны один граничный класс для задачи о независимом множестве и три граничных класса для задачи о доминирующем множестве. В настоящей работе доказывается бесконечность множества граничных классов для задачи о 3-раскраске. ...
Добавлено: 25 ноября 2012 г.
Сироткин Д. В., Журнал Средневолжского математического общества 2018 Т. 20 № 2 С. 199-205
Задача о вершинной 3-раекраеке для заданного графа состоит в том, чтобы проверить, можно ли множество его вершин разбить на три подмножества попарно несмежных вершин. Известно, что эта задача является NР-полной в классе планарных графов и что она становится полиномиально разрешимой для плоских триангуляций — планарных графов, у которых все грани (включая и внешнюю) являются треугольниками. ...
Добавлено: 2 июля 2018 г.
Малышев Д. С., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2013 Vol. 7 No. 2 P. 221-228
Добавлено: 23 июня 2013 г.
Алексеев В. Е., Лозин В. В., Малышев Д. С. и др., Lecture Notes in Computer Science 2008 Vol. 5162 No. 4 P. 96-107
В работе изучается вычислительная сложность нахождения наибольшего независимого множества вершин в планарных графах. В общем случае данная задача является NP-полной. Однако, при определенных ограничениях она становится полиномиально разрешимой. В работе выявляется графовый параметр, к изменению которого чувствительна сложность задачи и предлагаем несколько отрицательных (об NP-полноте) и положительных (о полиномиальной разрешимости) результатов, обобщающих несколько ранее известных ...
Добавлено: 7 ноября 2012 г.
Веселова Ю. А., В кн. : Управление развитием крупномасштабных систем (MLSD’2019): материалы Двенадцатой международной конференции, 1–3 окт. 2019 г. : Институт проблем управления им. В.А. Трапезникова РАН, 2019. С. 1185-1187.
При манипулировании со стороны коалиций существует опасность получить результат худший,
чем был изначально, если не все члены коалиции решают манипулировать. В этом случае манипулирование
небезопасно. В докладе рассматривается вопрос о том, для каких правил и при каких условиях
манипулирование небезопасно. ...
Добавлено: 1 ноября 2019 г.
Гольденгорин Б. И., Малышев Д. С., Пардалос П. О., Doklady Mathematics 2013 Vol. 87 No. 3 P. 368-371
The notion of a tolerance of an element of a combinatorial optimization problem is often used for stability analysis of an optimal solution and it is a base for design branch-and-bound algorithms solving such problems. In this paper we show that for the weighted independent set problem on trees with n vertices all upper and ...
Добавлено: 23 июня 2013 г.
Карабекян Д. С., Экономический журнал Высшей школы экономики 2009 Т. 13 № 1 С. 19-34
Рассматриваются предпочтения на множествах альтернатив (расширенные предпочтения). Анализируется ряд известных свойств, которым должны удовлетворять алгоритмы получения расширенных предпочтений из предпочтений на множестве альтернатив. Затем описываются существующие и предлагаются новые методы расширения предпочтений. Выделено три группы методов: лексико-графические, вероятностные и усреднения рангов, которые исследуются на соответствие известным свойствам. Если лексикографические и вероятностные методы для любого числа ...
Добавлено: 15 октября 2012 г.
Шитов Я. Н., American Mathematical Monthly 2016 Vol. 123 No. 1 P. 71-77
We present an infinite sequence of pairs (An, Bn) of chess positions on an n × n board such that (1) there is a legal sequence of chess moves leading from An to Bn and (2) any legal sequence leading from An to Bn contains at least exp(n + o(n)) moves. ...
Добавлено: 23 февраля 2016 г.
Сироткин Д. В., Малышев Д. С., Lobachevskii Journal of Mathematics 2021 Vol. 42 No. 4 P. 760-766
Добавлено: 5 июня 2021 г.
Васильев В. А., Moscow Mathematical Journal 2017 Vol. 17 No. 4 P. 825-836
Добавлено: 27 декабря 2017 г.
Швыдун С. В., / Высшая школа экономики. Series WP7 "Математические методы анализа решений в экономике, бизнесе и политике". 2015. No. WP7/2015/07.
Исследуются двухступенчатые процедурывыбора, которые представляют собой суперпозицию двух процедур выбора. Показано, какие из рассматриваемых процедур выбора удовлетворяют существующим нормативным условиям, описывающим, каким образом изменяется конечный выбор при изменении предъявляемого множества альтернатив и оценок альтернатив по критериям. Особое внимание уделяется двухступенчатым процедурам, в основе которых лежат позиционные правила, а также правила, использующие мажоритарное отношение, вспомогательную числовую ...
Добавлено: 20 октября 2015 г.
Алескеров Ф. Т., Карабекян Д. С., Иванов А. А. и др., , in : Procedia Computer Science. Vol. 139: 6th International Conference on Information Technology and Quantitative Management.: Elsevier, 2018. P. 212-220.
Добавлено: 24 октября 2018 г.
Малышев Д. С., Дискретный анализ и исследование операций 2012 Т. 19 № 6 С. 37-48
Понятие граничного класса графов является полезным инструментом для анализа вычислительной сложности задач на графах в семействе наследственных классов. В предыдущих работах автора исследовались общие черты и особенности семейств граничных классов графов для задачи о вершинной k-раскраске и ее «предельного варианта» - задачи о хроматическом числе. В данной работе эта проблематика рассматривается применительно к реберному варианту ...
Добавлено: 30 ноября 2012 г.
Алескеров Ф. Т., Мещерякова Н. Г., Швыдун С. В. и др., , in : 6th International Conference on Computers Communications and Control (ICCCC) 2016. : Oradea : Agora University, 2016. P. 118-123.
Добавлено: 8 июня 2016 г.