Механизм диктатуры

В теории социального выбора механизм диктатуры — это правило, согласно которому среди всех возможных альтернатив результаты голосования отражают предпочтения одного заранее определенного человека без учета интересов других избирателей. Диктатура сама по себе не считается хорошим механизмом на практике, но теоретически она важна: согласно теореме Эрроу о невозможности , когда существует по крайней мере три альтернативы, диктатура является единственной ранговой избирательной системой , которая удовлетворяет неограниченной области действия , эффективности по Парето и независимости неактуальные альтернативы . Аналогичным образом, согласно теореме Гиббарда , когда существует по крайней мере три альтернативы, диктатура является единственным правилом , не допускающим стратегии .

Недиктатура — это свойство более распространенных правил голосования , в которых на результаты влияют предпочтения всех людей. Это свойство удовлетворяется, если нет ни одного избирателя i с индивидуальным порядком предпочтений P, так что P всегда является общественным («победящим») порядком предпочтений. Другими словами, предпочтения индивида i не всегда должны преобладать. Системы анонимного голосования (с минимум двумя избирателями) автоматически удовлетворяют свойству недиктатуры.

У правила диктатуры есть варианты, полезные на практике: серийная диктатура , случайная диктатура и случайная серийная диктатура (см. ниже).

Формальное определение

Недиктатура — одно из необходимых условий теоремы невозможности Эрроу . ^[1] В книге «Социальный выбор и индивидуальные ценности » Кеннет Эрроу определяет недиктатуру как:

Не существует избирателя i в { 1 , ..., n } такого, что для любого набора порядков в области конституции и каждой пары социальных состояний x и y , x $P_{i}$ y подразумевает x P y .

Естественно, диктатура — это правило, которое не удовлетворяет недиктатуре.

Серийная диктатура

Механизм диктатуры четко определен только тогда, когда у диктатора есть единственный наиболее предпочтительный вариант. Когда диктатору безразлично два или более наиболее предпочтительных варианта, можно выбрать один из них произвольно/случайно, но это не будет эффективно по Парето . Более эффективное решение — назначить второго диктатора, который имеет право выбирать из всех лучших вариантов первого диктатора тот, который они больше всего предпочитают. Если второму диктатору также безразлично два или более вариантов, то третий диктатор выбирает один из них и так далее. Это правило называется серийной диктатурой . ^[2]^: 6 Другое его название — механизм приоритетов .

Механизм приоритета часто используется в вопросах распределения жилья . Например, при выделении студентам комнат в общежитии обычно студенты упорядочиваются в заранее заданном порядке приоритета (например, по возрасту, классам, расстоянию и т. д.), и каждый из них, в свою очередь, выбирает наиболее предпочтительную комнату из доступные.

Случайная диктатура и случайная серийная диктатура

Диктатурное правление явно несправедливо, но у него есть вариант, справедливый в ожидании. В правиле случайной диктатуры (RD) один из избирателей выбирается равномерно случайным образом, и выбирается альтернатива, наиболее предпочтительная для этого избирателя. Это одно из общих правил случайного социального выбора . При использовании в органах с несколькими округами его иногда называют случайным голосованием .

Подобно диктатуре, случайная диктатура также должна учитывать возможность безразличия; общее решение состоит в том, чтобы распространить его на случайную серийную диктатуру (RSD), ^[2]^: 6 также называется случайным приоритетом . В этом механизме выбирается случайная перестановка избирателей, и каждый избиратель, в свою очередь, сужает существующие альтернативы до тех, которые ему больше всего нравятся, из тех, которые еще доступны. Это общий механизм распределения неделимых объектов между агентами; см. случайное распределение предметов по приоритету .

Характеристики

Аллан Гиббард доказал теорему о случайной диктатуре . ^[3] В нем говорится, что когда предпочтения строгие, RD является единственным правилом, которое удовлетворяет следующим трем свойствам:

Анонимность: лотерея не делает заранее различий между разными избирателями.
Сильная устойчивость к SD-стратегии: каждое ложное сообщение агента приводит к результату, который слабо стохастически доминирует .
Эффективность по Парето ex-post: результат эффективен по Парето.
- Фактически, при строгих предпочтениях RD удовлетворяет более сильному свойству эффективности, называемому SD-эффективностью : в результате лотерея не доминирует стохастически. При слабых предпочтениях RSD удовлетворяет фактической эффективности, но нарушает SD-эффективность.
- Даже при строгих предпочтениях RD нарушает более сильное свойство, называемое эффективностью ПК: результирующая лотерея может доминировать в смысле попарных сравнений (для каждого агента вероятность того, что другая лотерея даст лучшую альтернативу, чем лотерея RD, больше, чем наоборот).

RD также удовлетворяет свойству, называемому согласованностью повестки дня. Это единственное правило, удовлетворяющее следующим свойствам: ^[4]

Сильная согласованность сокращения («регулярность»): вероятности не могут уменьшаться при удалении произвольных альтернатив.
Эффективность по факту.
Вероятностная версия независимости нерелевантных альтернатив .

Последующие исследования предоставили альтернативные доказательства, а также различные расширения. ^[2]^: 15 Один результат о невозможности относится к распространению теоремы на слабые предпочтения. В нем говорится, что при слабых предпочтениях свойства анонимности, СД-эффективности и СД-стратегической устойчивости несовместимы при наличии хотя бы 4 агентов и 4 альтернатив. Доказательство было получено с использованием решателя SMT и проверено интерактивным средством доказательства теорем Isabelle/HOL . ^[5]

RD удовлетворяет аксиоме, называемой согласованностью популяции , и аксиоме, называемой согласованностью клонирования , но нарушает согласованность композиции .

Вычисление

На практике легко реализовать механизмы как RD, так и RSD: просто выберите случайного избирателя или случайную перестановку, и позвольте каждому диктатору по очереди выбрать лучший вариант. Однако иногда хочется заранее вычислить, какова вероятность того, что будет выбрана определенная альтернатива. При RD (когда предпочтения строгие) это тоже легко: вероятность того, что альтернатива x будет выбрана, равна количеству избирателей, которые занимают x первое место, разделенной на общее количество избирателей. А вот с ОСБ ситуация другая (когда есть безразличия):

Вычисление вероятностей #P -сложно; ^[6]
Имеется эффективный алгоритм вычисления носителя (альтернативы, выбранные с положительной вероятностью); ^[6]
Существуют алгоритмы с управляемой параметризованной сложностью , где параметрами являются: количество объектов, количество альтернатив и количество типов избирателей. ^[7]
Существует алгоритм экспоненциального времени для вычисления вероятностей в контексте дробного голосования . ^[8]^{: Приложение}

Ссылки

^ Теория игр, второе издание, Гильермо Оуэн, глава 6, стр. 124-5, Аксиома 5, Academic Press, 1982. ISBN 0-12-531150-8
↑ Перейти обратно: Перейти обратно: ^а ^б ^с Феликс Брандт (26 октября 2017 г.). «Вероятностный социальный выбор» . В Эндриссе, Улле (ред.). Тенденции в вычислительном социальном выборе . Лулу.com. ISBN 978-1-326-91209-3 .
^ Гиббард, Аллан (1977). «Манипулирование схемами, смешивающими голосование со случайностью» . Эконометрика . 45 (3): 665–681. дои : 10.2307/1911681 . hdl : 10419/220534 . ISSN 0012-9682 . JSTOR 1911681 .
^ Паттанаик, Прасанта К.; Пелег, Бецалель (1986). «Распределение власти по правилам стохастического социального выбора» . Эконометрика . 54 (4): 909–921. дои : 10.2307/1912843 . ISSN 0012-9682 . JSTOR 1912843 .
^ Брандл, Флориан; Брандт, Феликс; Эберл, Мануэль; Гейст, Кристиан (31 января 2018 г.). «Доказательство несовместимости эффективности и стратегической устойчивости с помощью SMT-решений» . Журнал АКМ . 65 (2): 6:1–6:28. arXiv : 1604.05692 . дои : 10.1145/3125642 . ISSN 0004-5411 . S2CID 1135734 .
↑ Перейти обратно: Перейти обратно: ^а ^б Азиз, Харис; Брандт, Феликс; Брилл, Маркус (1 декабря 2013 г.). «Вычислительная сложность случайной серийной диктатуры» . Письма по экономике . 121 (3): 341–345. arXiv : 1304.3169 . дои : 10.1016/j.econlet.2013.09.006 . ISSN 0165-1765 . S2CID 14384249 .
^ Азиз, Харис; Местре, Хулиан (01 ноября 2014 г.). «Параметризованные алгоритмы для случайной серийной диктатуры» . Математические социальные науки . 72 : 1–6. arXiv : 1403.0974 . doi : 10.1016/j.mathsocsci.2014.07.002 . ISSN 0165-4896 . S2CID 6719832 .
^ Богомольная, Анна; Мулен, Эрве; Стонг, Ричард (1 июня 2005 г.). «Коллективный выбор при дихотомических предпочтениях» . Журнал экономической теории . 122 (2): 165–184. дои : 10.1016/j.jet.2004.05.005 . ISSN 0022-0531 .

[1] Теория игр, второе издание, Гильермо Оуэн, глава 6, стр. 124-5, Аксиома 5, Academic Press, 1982. ISBN 0-12-531150-8

[:0-2] Перейти обратно: Перейти обратно: ^а ^б ^с Феликс Брандт (26 октября 2017 г.). «Вероятностный социальный выбор» . В Эндриссе, Улле (ред.). Тенденции в вычислительном социальном выборе . Лулу.com. ISBN 978-1-326-91209-3 .

[3] Гиббард, Аллан (1977). «Манипулирование схемами, смешивающими голосование со случайностью» . Эконометрика . 45 (3): 665–681. дои : 10.2307/1911681 . hdl : 10419/220534 . ISSN 0012-9682 . JSTOR 1911681 .

[4] Паттанаик, Прасанта К.; Пелег, Бецалель (1986). «Распределение власти по правилам стохастического социального выбора» . Эконометрика . 54 (4): 909–921. дои : 10.2307/1912843 . ISSN 0012-9682 . JSTOR 1912843 .

[5] Брандл, Флориан; Брандт, Феликс; Эберл, Мануэль; Гейст, Кристиан (31 января 2018 г.). «Доказательство несовместимости эффективности и стратегической устойчивости с помощью SMT-решений» . Журнал АКМ . 65 (2): 6:1–6:28. arXiv : 1604.05692 . дои : 10.1145/3125642 . ISSN 0004-5411 . S2CID 1135734 .

[:1-6] Перейти обратно: Перейти обратно: ^а ^б Азиз, Харис; Брандт, Феликс; Брилл, Маркус (1 декабря 2013 г.). «Вычислительная сложность случайной серийной диктатуры» . Письма по экономике . 121 (3): 341–345. arXiv : 1304.3169 . дои : 10.1016/j.econlet.2013.09.006 . ISSN 0165-1765 . S2CID 14384249 .

[7] Азиз, Харис; Местре, Хулиан (01 ноября 2014 г.). «Параметризованные алгоритмы для случайной серийной диктатуры» . Математические социальные науки . 72 : 1–6. arXiv : 1403.0974 . doi : 10.1016/j.mathsocsci.2014.07.002 . ISSN 0165-4896 . S2CID 6719832 .

[:02-8] Богомольная, Анна; Мулен, Эрве; Стонг, Ричард (1 июня 2005 г.). «Коллективный выбор при дихотомических предпочтениях» . Журнал экономической теории . 122 (2): 165–184. дои : 10.1016/j.jet.2004.05.005 . ISSN 0022-0531 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]