Голосование за одобрение нескольких победителей

Семейство методов пропорциональных выборов

Голосование с одобрением нескольких победителей ^[1] , иногда также называемое голосованием комитета на основе одобрения (ABC) , ^[2] относится к семейству избирательных систем с несколькими победителями , которые используют бюллетени одобрения . Каждый избиратель может выбрать («одобрить») любое количество кандидатов, и избирается несколько кандидатов.

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

Голосование по утверждению блока

При голосовании блоком одобрения (также называемом неограниченным голосованием ) каждый избиратель либо одобряет, либо не одобряет каждого кандидата, и побеждают k кандидатов с наибольшим количеством голосов одобрения (где k — заранее определенный размер комитета). Это не обеспечивает пропорционального представительства .

Пропорциональное одобрительное голосование

Пропорциональное одобрительное голосование относится к методам голосования, которые направлены на обеспечение пропорционального представительства в случае, если все сторонники партии одобряют всех кандидатов этой партии. Такие методы включают пропорциональное одобрительное голосование , ^{[3] [4]} последовательное пропорциональное одобрительное голосование , правила голосования Фрагмена и метод равных долей . ^{[5] [6]} В общем случае пропорциональное представительство заменяется более общим требованием, называемым оправданным представительством .

В этих методах избиратели заполняют стандартный бюллетень одобрения, но бюллетени подсчитываются особым образом, который обеспечивает пропорциональное представительство. Точная процедура зависит от того, какой метод используется.

Голосование по одобрению партии

Голосование по одобрению партии (также называемое распределением на основе одобрения) ^[7] — это метод, при котором каждый избиратель может одобрить одну или несколько партий , а не одобрять отдельных кандидатов. Это комбинация голосования по одобрению нескольких победителей с голосованием по партийным спискам .

Другие методы

Другие способы распространения одобрительного голосования на выборы с несколькими победителями — это голосование по удовлетворению , ^[8] избыточный метод ^[9] и минимаксное одобрение. ^[10] Эти методы используют одобрительные бюллетени, но подсчитывают их по-разному.

Стратегическое голосование

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

Пример

Наиболее распространенной формой манипуляции является манипуляция подмножеством , при которой избиратель сообщает только строгое подмножество своих одобренных кандидатов. Такая манипуляция называется безбилетным проездом Хилланда ^{[ требуется ссылка ]} : манипулятор безбилетничает за счет одобрения кандидата другими и притворяется, что ему хуже, чем на самом деле. Затем правило побуждается «компенсировать» манипулятора, выбирая больше одобренных им кандидатов.

В качестве примера предположим, что мы используем правило PAV с k=3, есть 4 кандидата (a, b, c, d) и 5 ​​избирателей, из которых трое поддерживают a, b, c и двое поддерживают a, b, d. Затем PAV выбирает a, b, c. Но если последний избиратель сообщает только d, то PAV выбирает a, b, d, что строго лучше для него.

свойства стратегической устойчивости

Правило голосования с несколькими победителями называется стратегически устойчивым, если ни один избиратель не может увеличить свое удовлетворение, сообщая о ложных предпочтениях. Существует несколько вариантов этого свойства в зависимости от потенциального результата манипуляции:

• Устойчивость к стратегии включения означает, что никакая манипуляция не может привести к избранию строгого надмножества одобренных манипулятором кандидатов (как в примере PAV выше).
• Неуязвимость к кардинальности и стратегическому превосходству — более сильное свойство: оно означает, что никакая манипуляция не может привести к избранию большего числа одобренных манипулятором кандидатов.

Свойства стратегической защищенности также можно классифицировать по типу потенциальных манипуляций: ^[11]

• Независимость нерелевантных альтернатив означает, что относительная заслуга двух комитетов не зависит от кандидатов за пределами этих двух комитетов. Это предотвращает определенную форму стратегического голосования: изменение своего голоса в отношении нерелевантных кандидатов для манипулирования результатом.
• Монотонность означает, что избиратель никогда не проигрывает, раскрывая свой истинный набор одобренных кандидатов. ^{[ сомнительный – обсудить ]} Это предотвращает другую форму стратегического голосования: сокрытие некоторых одобренных кандидатов.

Лакнер и Скоурон ^[11] фокусируются на классе правил подсчета ABC (расширение правил позиционного подсчета до голосования с несколькими победителями). Среди этих правил правила Тиле — единственные, удовлетворяющие IIA, а правила подсчета неудовлетворенности — единственные, удовлетворяющие монотонности. ^{[ требуется разъяснение ]} Утилитаристское одобрительное голосование — единственное нетривиальное правило подсчета ABC, удовлетворяющее обеим аксиомам. ^{[ сомнительно — обсудить ]} Это также единственное нетривиальное правило подсчета ABC, удовлетворяющее SD-стратегической устойчивости — расширению кардинальности-стратегической устойчивости до нерешительных правил. Если утилитаристское одобрительное голосование сделать решительным с помощью плохого правила разрешения ничьей, оно может стать нестратегически устойчивым.

Стратегическая устойчивость и пропорциональность

Требования к кардинальности-стратегии и к инклюзивности-стратегии удовлетворяются утилитаристским одобрительным голосованием (правило мажоритарного одобрительного голосования с неограниченным количеством голосов), но не удовлетворяются никаким другим известным правилом, удовлетворяющим пропорциональности.

Это поднимает вопрос о том, существует ли правило, которое одновременно является и стратегически защищенным, и пропорциональным. Ответ — нет: Доминик Питерс доказал, что ни одно правило голосования с несколькими победителями не может одновременно удовлетворять слабой форме пропорциональности, слабой форме стратегической защищенности и слабой форме эффективности. ^[12] В частности, следующие три свойства несовместимы, когда k ≥ 3, n кратно k , а число кандидатов не менее k +1:

• Subset-inclusion-strategyproofness : если агент i с одобренными кандидатами A _i сообщает о подмножестве A _i (и все остальные отчеты такие же), то ни один ранее неизбранный кандидат из A _i не избирается. Это свойство слабее, чем include-strategyproofness, поскольку оно учитывает только один тип манипуляции: сообщение о подмножестве своего истинного множества одобрения.
• Пропорциональность партийного списка : Мы определяем профиль партийного списка как характеристику профиля голосования по партийному списку , то есть: существует разделение избирателей на k групп и разделение проектов на k подмножеств, так что каждый избиратель из группы i голосует только за все проекты в группе i . Пропорциональность партийного списка означает, что в профиле партийного списка, если некоторый одноэлементный бюллетень { x } появляется по крайней мере B / n раз, то x избирается. Это свойство слабее, чем свойство более низкой квоты от распределения , и слабее, чем свойство оправданного представительства .
  • Альтернативное свойство, для которого выполняется невозможность, — это непересекающееся разнообразие . Это означает, что в профиле партийного списка с максимум k различными партиями правило выбирает по крайней мере одного члена из каждой партии.
• Слабая эффективность : если кандидата x никто не поддерживает, а есть по крайней мере k кандидатов, которые поддерживаются, то x не избирается.

Доказательство основано на индукции; базовый случай ( k =3) был найден решателем SAT . Для k =2 невозможность сохраняется с немного более сильной аксиомой стратегической устойчивости.

Степень манипулируемости

Лакнер и Скоурон ^[11] количественно оценили компромисс между стратегической устойчивостью и пропорциональностью, эмпирически измерив долю случайно сгенерированных профилей, для которых некоторые избиратели могут выиграть, предоставив ложные данные. Примеры результатов, когда каждый избиратель одобряет 2 кандидатов, следующие: Последовательное правило Фрагмена поддается манипулированию в 66% профилей; Последовательное PAV - 68%; PAV - 71%; Удовлетворение AV и Максимин AV - 86%; Одобрение Монро - 92%; Чемберлен-Курант - 95%. Они также проверили манипулируемость правил Тиле с p -геометрической функцией оценки (где оценки являются степенями 1/ p для некоторого фиксированного p ). Обратите внимание, что p = 1 дает утилитарное AV, тогда как p→∞ дает Чемберлен-Курант. Они обнаружили, что увеличение p приводит к увеличению манипулируемости: правила, которые больше похожи на утилитарный AV, менее манипулируемы, чем правила, которые больше похожи на CC, а пропорциональные правила находятся посередине.

Барро, Ланг и Йоку ^[13] представляют похожее исследование другого семейства правил, основанного на упорядоченном взвешенном усреднении и расстоянии Хэмминга . Их семейство также характеризуется параметром p , где p = 0,5 дает утилитарное AV, тогда как p = 1 дает эгалитарное AV. Они приходят к похожему выводу: увеличение p приводит к большей доле случайных профилей, которыми можно манипулировать.

Ограниченные предпочтительные домены

Один из способов преодоления результатов невозможности — рассмотреть ограниченные области предпочтений. Ботан ^[14] рассматривает предпочтения партийных списков , то есть профили, в которых избиратели разделены на непересекающиеся подмножества, каждое из которых голосует за непересекающееся подмножество кандидатов. Она доказывает, что правила Тиле (такие как PAV) противостоят некоторым распространенным формам манипуляций, и они являются стратегической защитой для «оптимистичных» избирателей.

Нерешительные правила

Свойства strategyproofness могут быть расширены до нерешительных правил (правил, которые возвращают несколько связанных комитетов). Лакнер и Скоурон ^[11] определяют сильное расширение, называемое stochastic-dominance -strategyproofness , и доказывают, что оно характеризует утилитаристское правило голосования одобрения .

Клюивинг, Врис, Врейберген, Бойксель и Эндрисс ^[15] дают более полное обсуждение стратегической устойчивости нерешительных правил; в частности, они распространяют результат невозможности Петерса на нерешительные правила. Дадди ^[16] представляет результат невозможности, используя другой набор аксиом.

Недихотомические предпочтения

Существует даже более сильный вариант стратегической защищенности, называемый недихотомической стратегической защищенностью : он предполагает, что у агентов есть базовое недихотомическое отношение предпочтений, и они используют одобрения только в качестве приближения. Это означает, что никакая манипуляция не может привести к избранию комитета, который ранжируется манипулятором выше. Недихотомическая стратегическая защищенность не удовлетворяется никаким нетривиальным правилом голосования с несколькими победителями. ^[17]

Шейерман, Харман, Маттей и Венейбл представляют поведенческие исследования того, как ведут себя люди с недихотомическими предпочтениями, когда им необходимо предоставить бюллетень для голосования по одобрению, когда результат решается с помощью утилитарного голосования по одобрению. ^{[18] [19]}

Расширения

Переменное количество победителей

Фримен, Канг и Пеннок изучают многопобедное одобрительное голосование, в котором число победителей не фиксируется заранее, а определяется голосами. Например, при выборе кандидатов для собеседования, если есть много сильных кандидатов, то число кандидатов, выбранных для собеседования, может быть больше. Они распространяют понятие средней удовлетворенности на эту настройку. ^[20]

Разделимые комитеты

Бэй, Лу и Суксомпонг ^[21] расширяют модель выборов комитета до ситуации, в которой имеется континуум кандидатов, представленных действительным интервалом [0, c ], как в справедливом разрезании торта . Цель состоит в том, чтобы выбрать подмножество этого интервала с общей длиной не более k , где здесь k и c могут быть любыми действительными числами с 0 < k < c . Они обобщают понятие обоснованного представления для этой ситуации. Лу, Петерс, Азиз, Бэй и Суксомпонг ^[22] расширяют эти определения до ситуаций со смешанными делимыми и неделимыми кандидатами (см. обоснованное представление ).

Использование

Одобрительное голосование с несколькими победителями, хотя и менее распространено, чем стандартное одобрительное голосование , используется в нескольких местах.

Блокировать голосование по утверждению

• Корейские деревни использовали голосование по принципу одобрения блока для конкурентных выборов после капитуляции Японии, согласно наблюдениям, сделанным журналисткой Анной Луизой Стронг в 1946 году: «В одной деревне было двенадцать кандидатов, из которых пятеро должны были быть выбраны в деревенский комитет. Каждому избирателю выдавалось двенадцать карточек с именами кандидатов. Затем он бросал выбранных им кандидатов в белый ящик, а отвергнутых — в черный». ^[23]
• Несколько швейцарских кантонов избирают свое правительство, используя такие же методы, как и французские города с населением менее 1000 человек. ^[24]
• В 1963 году система пропорционального представительства в Восточной Германии была заменена процедурой, в которой кандидаты должны были получить более 50% голосов. Если бы больше кандидатов, чем мест в этом избирательном округе, получили большинство, порядок списка определял бы, кто вступит в Народную палату .

Внешние ссылки

• Голосование за нескольких победителей с возможностью одобрения

• Реализация на Python множества правил голосования с несколькими победителями, основанных на одобрении
• Демонстрация Javascript многих правил на сайте pref.tools

Ссылки

1. Азиз, Харис; Гасперс, Серж; Гудмундссон, Иоахим; Маккензи, Саймон; Маттей, Николас; Уолш, Тоби (11 июля 2014 г.). «Вычислительные аспекты голосования за одобрение с участием нескольких победителей». arXiv : 1407.3247 [cs.GT].
2. Азиз, Харис; Брилл, Маркус; Конитцер, Винсент; Элкинд, Эдит; Фримен, Руперт; Уолш, Тоби (2017). «Оправданное представительство при голосовании в комитете на основе одобрения». Social Choice and Welfare . 48 (2): 461–485. arXiv : 1407.8269 . doi : 10.1007/s00355-016-1019-3. S2CID  8564247.
3. http://www2.math.uu.se/~svante/papers/sjV9.pdf ^{[ пустой URL-адрес PDF ]}
4. Брилл, Маркус; Ласлье, Жан-Франсуа; Сковрон, Петр (2016). «Правила одобрения нескольких победителей как методы распределения». arXiv : 1611.08691 [cs.GT].
5. Питерс, Доминик; Сковрон, Петр (2020). «Пропорциональность и пределы благосостояния». Труды 21-й конференции ACM по экономике и вычислениям . EC'20. С. 793–794. arXiv : 1911.11747 . doi : 10.1145/3391403.3399465. ISBN 9781450379755. S2CID  208291203.
6. Перчинский, Гжегож; Петерс, Доминик; Сковрон, Петр (2020). «Пропорциональное партисипаторное бюджетирование с аддитивными полезностями». Труды конференции 2021 года по системам обработки нейронной информации . NeurIPS'21. arXiv : 2008.13276 .
7. Брилл, Маркус; Гёльц, Пауль; Петерс, Доминик; Шмидт-Крепелин, Ульрике; Вилькер, Кай (2020-04-03). «Распределение на основе одобрения». Труды конференции AAAI по искусственному интеллекту . 34 (2): 1854–1861. arXiv : 1911.08365 . doi : 10.1609/aaai.v34i02.5553. ISSN  2374-3468. S2CID  208158445.
8. Плаза, Энрик. Технологии политического представительства и подотчетности (PDF) . CiteSeerX 10.1.1.74.3284 . Получено 2011-06-17 . 
9. https://as.nyu.edu/content/dam/nyu-as/faculty/documents/Excess%20Method%20(final).pdf ^{[ пустой URL-адрес PDF ]}
10. LeGrand, Rob; Markakis, Evangelos; Mehta, Aranyak (2007). Труды 6-й международной совместной конференции по автономным агентам и многоагентным системам - AAMAS '07 (PDF) . стр. 1. doi :10.1145/1329125.1329365. ISBN 9788190426275. S2CID  13870664 . Получено 2011-06-17 .
11. Лакнер, Мартин; Сковрон, Петр (2018-07-13). «Правила одобрения с несколькими победителями и стратегическое голосование». Труды 27-й Международной совместной конференции по искусственному интеллекту . IJCAI'18. Стокгольм, Швеция: AAAI Press: 340–346. ISBN 978-0-9992411-2-7.
12. Питерс, Доминик (2021). «Пропорциональность и стратегическая защищенность в выборах с несколькими победителями». arXiv : 2104.08594 [cs.GT].
13. Барро, Натанаэль; Ланг, Жером; Йоку, Макото (2017-05-08). «Манипуляция голосованием на основе одобрения Хэмминга для множественных референдумов и выборов комитетов». Труды 16-й конференции по автономным агентам и многоагентным системам . AAMAS '17. Ричленд, Южная Каролина: Международный фонд автономных агентов и многоагентных систем: 597–605.
14. Ботан, Сирин (2021-05-03). «Манипулируемость методов Тиле на профилях партийных списков». Труды 20-й Международной конференции по автономным агентам и многоагентным системам . AAMAS '21. Richland, SC: Международный фонд автономных агентов и многоагентных систем: 223–231. ISBN 978-1-4503-8307-3.
15. Клювинг, Боас; де Врис, Адриан; Врейберген, Пепейн; Бойксель, Артур; Эндрисс, Улле (2020), «Анализ нерешительных правил голосования с несколькими победителями с помощью бюллетеней для одобрения посредством решения SAT», ECAI 2020 , IOS Press, стр. 131–138, doi :10.3233/faia200085 , получено 27 октября 2023 г.
16. Дадди, Конал (01.07.2014). «Выборы представительного комитета путем голосования по утверждению: невозможный результат». Economics Letters . 124 (1): 14–16. doi :10.1016/j.econlet.2014.04.009. ISSN  0165-1765.
17. Ниеми, Ричард Г. (1984). «Проблема стратегического поведения при голосовании за одобрение». The American Political Science Review . 78 (4): 952–958. doi :10.2307/1955800. ISSN  0003-0554. JSTOR  1955800. S2CID  146976380.
18. Шейерман, Джаэль; Харман, Джейсон Л.; Маттей, Николас; Венейбл, К. Брент (2020-05-13). «Эвристические стратегии в неопределенных средах голосования при одобрении». Труды 19-й Международной конференции по автономным агентам и многоагентным системам . AAMAS '20. Ричленд, Южная Каролина: Международный фонд автономных агентов и многоагентных систем: 1993–1995. arXiv : 1912.00011 . ISBN 978-1-4503-7518-4.
19. Шейерман, Джаэль; Харман, Джейсон; Маттей, Николас; Венейбл, К. Брент (18.05.2021). «Моделирование избирателей при голосовании с одобрением нескольких победителей». Труды конференции AAAI по искусственному интеллекту . 35 (6): 5709–5716. arXiv : 2012.02811 . doi : 10.1609/aaai.v35i6.16716 . ISSN  2374-3468. S2CID  227335243.
20. Фримен, Руперт; Канг, Энсон; Пеннок, Дэвид М. (2021-01-07). «Пропорциональность в выборах на основе одобрения с переменным числом победителей». Труды Двадцать девятой Международной совместной конференции по искусственному интеллекту . IJCAI'20. Иокогама, Иокогама, Япония: 132–138. ISBN 978-0-9992411-6-5.
21. Бэй, Сяохуэй; Лу, Синьхан; Суксомпонг, Варут (28.06.2022). «Правдивый раздел торта». Труды конференции AAAI по искусственному интеллекту . 36 (5): 4809–4817. arXiv : 2112.05632 . doi : 10.1609/aaai.v36i5.20408. ISSN  2374-3468.
22. Лу, Синьхан; Петерс, Янник; Азиз, Харис; Бэй, Сяохуэй; Суксомпонг, Варут (2023-06-26). «Голосование на основе одобрения со смешанными товарами». Труды конференции AAAI по искусственному интеллекту . 37 (5): 5781–5788. arXiv : 2211.12647 . doi : 10.1609/aaai.v37i5.25717 . ISSN  2374-3468.
23. Стронг, Анна. «В Северной Корее: первый отчет очевидца». Архив Marxists Internet . Получено 14 мая 2019 г.
24. Вандер Стратен, Карин; Лаша, Ромен; Ласлье, Жан-Франсуа (2018). Стивенсон, Лора Б.; Олдрич, Джон Х.; Блэйс, Андре (ред.). Глава 9: Стратегическое голосование на выборах с несколькими победителями с баллотированием по принципу одобрения: применение к выборам регионального правительства 2011 года в Цюрихе . Энн-Арбор, Мичиган: Издательство Мичиганского университета. С. 178–202. {{cite encyclopedia}}: |work=проигнорировано ( помощь )