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

Избирательная система с несколькими победителями

Пропорциональное одобрительное голосование ( PAV ) — это пропорциональная избирательная система для выборов с несколькими победителями . Это метод одобрения с несколькими победителями , который расширяет метод распределения Д'Ондта , обычно используемый для расчета распределения для пропорционального представительства по партийным спискам . ^[1] Однако PAV позволяет избирателям поддерживать только тех кандидатов, которых они одобряют, вместо того, чтобы быть вынужденными одобрять или отклонять всех кандидатов в данном партийном списке . ^[2]

В PAV избиратели подают одобрительные бюллетени, отмечая всех кандидатов, которых они одобряют; затем бюллетень каждого избирателя рассматривается так, как если бы все кандидаты в бюллетене были в его собственном «партийном списке». Затем места распределяются между кандидатами таким образом, чтобы обеспечить пропорциональное представительство всех коалиций.

История

PAV — это особый случай правила голосования Тиле , предложенного Торвальдом Н. Тиле . ^{[3] [4]} Оно использовалось в сочетании с рейтинговым голосованием на шведских выборах с 1909 по 1921 год для распределения мест внутри партий и на местных выборах. ^[4] PAV было заново открыто Форестом Симмонсом в 2001 году, ^[5] который дал ему название «пропорциональное одобрительное голосование».

Метод

Как и его близкий родственник, голосование по одобрению удовлетворения , PAV можно рассматривать как выбор комитета путем тестирования всех возможных комитетов, а затем выбора комитета с наибольшим количеством голосов. При голосовании по одобрению удовлетворения бюллетень каждого избирателя делится поровну между всеми кандидатами, которых они одобряют, давая каждому голос. Если избиратели идеально стратегически мыслят и поддерживают только столько кандидатов, сколько имеет право их партия, SAV создает пропорциональный результат. ${\displaystyle r}$ ${\displaystyle 1/r}$

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

Таким образом, если бюллетень одобряет избранных кандидатов, этот бюллетень добавляет -ое гармоническое число к общему числу голосов этого комитета. Другими словами: ^{[5] [6]} ${\displaystyle r}$ ${\displaystyle r}$

${\displaystyle \mathrm {H} (r)=1+{\frac {1}{2}}+{\frac {1}{3}}+\cdots +{\frac {1}{r}}}$

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

Формально предположим, что у нас есть набор кандидатов , набор избирателей и размер комитета . Пусть обозначает набор кандидатов, одобренных избирателем . Оценка PAV комитета с размером определяется как . PAV выбирает комитет с максимальной оценкой. ${\displaystyle C=\{c_{1},c_{2},\ldots ,c_{m}\}}$ ${\displaystyle N=\{1,2,\ldots ,n\}}$ ${\displaystyle k}$ ${\displaystyle A_{i}}$ ${\displaystyle i\in N}$ ${\displaystyle W\subseteq C}$ ${\displaystyle |W|=k}$ ${\displaystyle \textstyle \mathrm {sc} _{\mathrm {PAV} }(W)=\sum _{i=1}^{n}\mathrm {H} (|A_{i}\cap W|)}$ ${\displaystyle W}$

Пример 1

Предположим, что нужно заполнить 2 места, и есть четыре кандидата: Андреа (A), Брэд (B), Картер (C) и Делайла (D), и 30 избирателей. Бюллетени следующие:

• 5 избирателей проголосовали за A и B
• 17 избирателей проголосовали за A и C
• 8 избирателей проголосовали за D

Возможны 6 результатов: AB, AC, AD, BC, BD и CD.

Избраны Андреа и Картер.

Обратите внимание, что Simple Approval показывает, что у Андреа 22 голоса, у Картера 17 голосов, у Делайлы 8 голосов и у Брэда 5 голосов. В этом случае выбор PAV Андреа и Картера совпадает с последовательностью Simple Approval. Однако, если голоса выше немного изменить так, чтобы A и C получили 16 голосов, а D получил 9 голосов, то Андреа и Делайла будут избраны, поскольку счет A и C теперь равен 29, а счет A и D остается равным 30. Кроме того, последовательность, созданная с помощью Simple Approval, остается неизменной. Это показывает, что PAV может давать результаты, несовместимые с методом, который просто следует последовательности, подразумеваемой Simple Approval.

Пример 2

Предположим, что нужно выбрать 10 мест и есть три группы кандидатов: красные , синие и зеленые кандидаты. Есть 100 избирателей:

• 60 избирателей проголосовали за всех синих кандидатов,
• 30 избирателей проголосовали за всех красных кандидатов,
• За всех зеленых кандидатов проголосовали 10 избирателей .

В этом случае PAV выберет 6 синих , 3 красных и 1 зеленого кандидата. Оценка такого комитета будет Все остальные комитеты получат более низкий балл. Например, оценка комитета, состоящего только из синих кандидатов, будет $${\displaystyle 60\cdot \mathrm {H} (6)+30\cdot \mathrm {H} (3)+10\cdot \mathrm {H} (1)=60\cdot \left(1+{\tfrac {1}{2}}+\ldots +{\tfrac {1}{6}}\right)+30\cdot \left(1+{\tfrac {1}{2}}+{\tfrac {1}{3}}\right)+10\cdot 1=147+55+10=212{\text{.}}}$$

${\displaystyle 60\cdot \mathrm {H} (10)+30\cdot \mathrm {H} (0)+10\cdot \mathrm {H} (0)=60\cdot \left(1+{\tfrac {1}{2}}+\ldots +{\tfrac {1}{10}}\right)\approx 175.73{\text{.}}}$

В этом примере результат PAV пропорционален : количество кандидатов, выбранных из каждой группы, пропорционально количеству избирателей, голосующих за группу. Это не совпадение: если кандидаты образуют непересекающиеся группы, как в приведенном выше примере (группы можно рассматривать как политические партии), и каждый избиратель голосует исключительно за всех кандидатов в пределах одной группы, то PAV будет действовать так же, как метод Д'Ондта пропорционального представительства партийных списков . ^[1]

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

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

Комитеты размером один

На выборах с единственным победителем PAV действует точно так же, как и одобрительное голосование . То есть, он выбирает комитет, состоящий из кандидата, одобренного большинством избирателей.

Пропорциональность

Большинство систем пропорционального представительства используют партийные списки . PAV была разработана для того, чтобы иметь как пропорциональное представительство, так и персональные голоса (избиратели голосуют за кандидатов, а не за партийный список). Она заслуживает того, чтобы ее называли «пропорциональной» системой, потому что если голоса распределяются по партийной схеме (каждый избиратель голосует за всех кандидатов от одной партии и ни за кого другого), то система выбирает количество кандидатов в каждой партии, пропорциональное количеству избирателей, выбравших эту партию (см. Пример 2). ^[1] Кроме того, при умеренных предположениях (симметрия, непрерывность и эффективность по Парето ), PAV является единственным расширением метода Д'Ондта , которое допускает персональные голоса и удовлетворяет критерию согласованности . ^[2]

Даже если избиратели не следуют партийной схеме, правило обеспечивает гарантии пропорциональности. Например, PAV удовлетворяет свойству сильной справедливости, называемому расширенным оправданным представлением , ^[6] , а также связанному свойству пропорциональное оправданное представление . ^[7] Он также имеет оптимальную степень пропорциональности. ^{[8] [9]} Все эти свойства гарантируют, что любая группа избирателей со сплоченными (похожими) предпочтениями будет представлена ​​числом кандидатов, которое по крайней мере пропорционально размеру группы. PAV является единственным методом, удовлетворяющим таким свойствам среди всех методов оптимизации, подобных PAV (которые могут использовать в своем определении числа, отличные от гармонических чисел). ^[6]

Комитеты, возвращаемые PAV, могут не входить в ядро . [ ^{жаргон ] [ 6] [10]} Однако он гарантирует 2-аппроксимацию ядра, ^{[ жаргон ]} что является оптимальным отношением аппроксимации, которое может быть достигнуто с помощью правила, удовлетворяющего принципу переносов Пигу-Дальтона . ^[10] Кроме того, PAV удовлетворяет свойству ядра, если в выборах участвует достаточно много похожих кандидатов. ^[11]

PAV не удовлетворяет требованиям ценовой доступности (то есть выбор PAV не всегда можно объяснить с помощью процесса, в котором избиратели наделены фиксированной суммой виртуальных денег и тратят эти деньги на покупку кандидатов, которые им нравятся) и не удовлетворяет требованиям ламинарной пропорциональности. ^[10] Два альтернативных правила, которые удовлетворяют требованиям ценовой доступности и ламинарной пропорциональности и которые имеют сравнительно хорошие свойства, связанные с пропорциональностью, по сравнению с PAV, — это метод равных долей и последовательные правила Фрагмена . ^[12] Эти два альтернативных метода также вычислимы за полиномиальное время , однако они не удовлетворяют требованиям эффективности по Парето .

Другие свойства

Помимо свойств, относящихся к пропорциональности, PAV удовлетворяет следующим аксиомам:

• эффективность по Парето
• Последовательность
• Монотонность поддержки (если поддержка победившего кандидата увеличивается, т.е. за этого кандидата голосует больше избирателей, то этот кандидат остается победителем) ^[13]
• Принцип Пигу–Дальтона ^[10]

PAV не соответствует следующим свойствам:

• Монотонность дома . ^[12] Два альтернативных метода, которые удовлетворяют монотонности дома и которые имеют сравнительно хорошие свойства, связанные с пропорциональностью, по сравнению с PAV, — это последовательное пропорциональное голосование по одобрению и последовательные правила Фрагмена . ^[12] Эти два альтернативных метода также вычислимы за полиномиальное время , но они не соответствуют эффективности Парето , согласованности и принципу Пигу–Дальтона . ^[12]

Вычисление

Формулировка целочисленного линейного программирования для вычисления комитетов-победителей согласно PAV. Переменная указывает, выбран ли кандидат или нет. Переменная указывает, одобряет ли избиратель по крайней мере выбранных кандидатов. ^{[12] [14]} ${\displaystyle y_{c}}$ ${\displaystyle c}$ ${\displaystyle x_{i,\ell }}$ ${\displaystyle i}$ ${\displaystyle \ell }$

Решения PAV и их качество можно проверить за полиномиальное время , ^{[15] [16]} что упрощает прозрачность. Однако в худшем случае временная сложность является NP-полной , что означает, что для некоторых выборов может быть сложно или невозможно найти точное решение, гарантирующее все теоретические свойства PAV.

На практике результат PAV может быть точно вычислен для комитетов среднего размера (<50 кандидатов) с использованием решателей целочисленного программирования (например, тех, что предоставлены в пакете Python abcvoting). Поиск точного решения имеет временную сложность при k местах и ​​n избирателях. ${\displaystyle O(nm^{k})}$

С точки зрения параметризованной сложности , проблема вычисления PAV теоретически сложна за исключением нескольких исключительных простых случаев. ^{[15] [17] [18]} К счастью, такие случаи часто являются хорошими приближениями реальных выборов, что позволяет использовать их в качестве эвристик, которые значительно сокращают вычислительные усилия по поиску правильного решения. Например, точные результаты выборов могут быть решены за полиномиальное время в случае, когда избиратели и кандидаты находятся вдоль одномерного политического спектра, ^[14] и за линейное время, когда избиратели являются сильными сторонниками (т. е. голосуют за партийные списки, а не за кандидатов).

Детерминированные аппроксимации

Последовательное пропорциональное голосование по одобрению является жадным приближением для PAV с наихудшим коэффициентом приближения , поэтому оценка PAV результирующего комитета составляет не менее 63% от оптимального. ^[16] Этот метод может быть вычислен за полиномиальное время, и исход выборов потенциально может быть определен вручную. Другой подход, включающий дерандомизированное округление (с методом условных вероятностей ), дает наихудший коэффициент приближения 0,7965; ^[19] при стандартных предположениях в теории сложности это наилучший коэффициент приближения, который может быть достигнут для PAV за полиномиальное время. ^[19] Задача приближения PAV может быть также сформулирована как задача минимизации (вместо максимизации мы хотим минимизировать ), в этом случае наилучший известный коэффициент приближения равен 2,36. ^[20] ${\displaystyle 1-1/e\approx 0.63}$ ${\displaystyle \textstyle \mathrm {sc} _{\mathrm {PAV} }(W)}$ ${\displaystyle \textstyle \sum _{i\in N}\mathrm {H} (k)-\mathrm {sc} _{\mathrm {PAV} }(W)}$

Дальнейшее чтение

• Lackner, Martin; Skowron, Piotr (2023). Голосование с несколькими победителями и предпочтениями одобрения . SpringerBriefs in Intelligent Systems. arXiv : 2007.01795 . doi : 10.1007/978-3-031-09016-5. ISBN 978-3-031-09015-8. S2CID  244921148.
• Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, Nimrod Talmon (2017-10-26). "Multiwinner Voting: A New Challenge for Social Choice Theory". В Endriss, Ulle (ред.). Trends in Computational Social Choice . AI Access. ISBN 978-1-326-91209-3.{{cite book}}: CS1 maint: multiple names: authors list (link)

Смотрите также

• Метод равных долей
• Метод Д'Ондта
• Последовательное пропорциональное голосование по одобрению
• Правила голосования Фрагмена

Ссылки

1. Brill, Markus; Laslier, Jean-François; Skowron, Piotr (2018). «Правила одобрения для нескольких победителей как методы распределения». Journal of Theoretical Politics . 30 (3): 358–382. arXiv : 1611.08691 . doi : 10.1177/0951629818775518. S2CID  10535322.
2. Лакнер, Мартин; Сковрон, Петр (2021). «Последовательные правила для нескольких победителей, основанные на одобрении». Журнал экономической теории . 192 : 105173. arXiv : 1704.02453 . doi : 10.1016/j.jet.2020.105173. S2CID  232116881.
3. Тиле, Торвальд Н. (1895). «Ом Флерфолдсвальг». Надзор над Det Kongelige Danske Videnskabernes Selskabs Forhandlinger : 415–441.
4. Janson, Svante (2016). «Методы выборов Фрагмена и Тиле». arXiv : 1611.08826 [math.HO].
5. Килгур, Д. Марк (2010). «Голосование по одобрению выборов с несколькими победителями». У Жана-Франсуа Ласлье; М. Ремзи Санвер (ред.). Руководство по голосованию за одобрение . Спрингер. стр. 105–124. ISBN 978-3-642-02839-7.
6. Азиз, Харис; Брилл, Маркус; Конитцер, Винсент; Элкинд, Эдит; Фримен, Руперт; Уолш, Тоби (2017). «Оправданное представительство при голосовании в комитете на основе одобрения». Social Choice and Welfare . 48 (2): 461–485. arXiv : 1407.8269 . doi : 10.1007/s00355-016-1019-3. S2CID  8564247.
7. Санчес-Фернандес, Луис; Элкинд, Эдит; Лакнер, Мартин; Фернандес, Норберто; Фистеус, Иисус; Вэл, Пабло Басанта; Сковрон, Петр (10 февраля 2017 г.). «Пропорциональное обоснованное представительство». Материалы конференции AAAI по искусственному интеллекту . 31 (1). дои : 10.1609/aaai.v31i1.10611 . hdl : 10016/26166 . ISSN  2374-3468. S2CID  17538641.
8. Азиз, Харис; Элкинд, Эдит; Хуан, Шэньвэй; Лакнер, Мартин; Санчес Фернандес, Луис; Сковрон, Петр (2018). «О сложности расширенного и пропорционального обоснованного представления». Труды конференции AAAI по искусственному интеллекту . 32 (1): 902–909. doi : 10.1609/aaai.v32i1.11478 . S2CID  19124729.
9. Сковрон, Петр (2021). «Степень пропорциональности правил Multiwinner». Труды 22-й конференции ACM по экономике и вычислениям . EC-21. стр. 820–840. arXiv : 1810.08799 . doi : 10.1145/3465456.3467641. ISBN 9781450385541. S2CID  53046800.
10. Peters, Dominik; Skowron, Piotr (2020). «Пропорциональность и пределы велфаризма». Труды 21-й конференции ACM по экономике и вычислениям . EC'20. С. 793–794. arXiv : 1911.11747 . doi :10.1145/3391403.3399465. ISBN 9781450379755. S2CID  208291203.
11. Брилл, Маркус; Гёльц, Пауль; Петерс, Доминик; Шмидт-Крепелин, Ульрике; Вилькер, Кай (2019). «Распределение на основе одобрения». Труды конференции AAAI по искусственному интеллекту . 34 (2): 1854–1861. arXiv : 1911.08365 . doi : 10.1609/aaai.v34i02.5553. S2CID  208158445.
12. Лакнер, Мартин; Сковрон, Петр (2023). Голосование с несколькими победителями с предпочтениями одобрения . SpringerBriefs in Intelligent Systems. arXiv : 2007.01795 . doi : 10.1007/978-3-031-09016-5. ISBN 978-3-031-09015-8. S2CID  244921148.
13. Санчес Фернандес, Луис; Фистеус, Хесус (2019). «Аксиомы монотонности в правилах голосования с несколькими победителями, основанных на одобрении» (PDF) : 485–493. arXiv : 1710.04246 . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
14. Peters, Dominik (2018). «Одновершинность и полная унимодулярность: новые полиномиальные алгоритмы для выборов с несколькими победителями»: 1169–1176. arXiv : 1609.03537 . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
15. Азиз, Харис; Гасперс, Серж; Гудмундссон, Иоахим; Маккензи, Саймон; Маттей, Николас; Уолш, Тоби (2015). Вычислительные аспекты голосования за одобрение с участием нескольких победителей . стр. 107–115. arXiv : 1407.3247 . ISBN 978-1-4503-3413-6.
16. Сковрон, Петр; Фалишевский, Петр; Ланг, Жером (2016). «Поиск коллективного набора элементов: от пропорционального множественного представления к групповой рекомендации». Искусственный интеллект . 241 : 191–216. arXiv : 1402.3044 . doi : 10.1016/j.artint.2016.09.003. S2CID  11313941.
17. Бредерек, Роберт; Фалишевский, Петр; Качмарчик, Анджей; Кноп, Душан; Нидермейер, Рольф (2020). «Параметризованные алгоритмы поиска коллективного набора элементов». Труды конференции AAAI по искусственному интеллекту . 34 (2): 1838–1845. doi : 10.1609/aaai.v34i02.5551 . S2CID  213963505.
18. Годзишевский, Михал; Батько, Павел; Сковрон, Петр; Фалишевский, Петр (2021). «Анализ правил комитета на основе одобрения для 2D-евклидовых выборов». Труды конференции AAAI по искусственному интеллекту . 35 (6): 5448–5455. doi : 10.1609/aaai.v35i6.16686 . S2CID  235306592.
19. Dudycz, Szymon; Manurangsi, Pasin; Marcinkowski, Jan; Sornat, Krzysztof (2020). «Точная аппроксимация для пропорционального одобрительного голосования». Труды Двадцать девятой Международной совместной конференции по искусственному интеллекту . IJCAI-20. стр. 276–282. doi : 10.24963/ijcai.2020/39 . ISBN 978-0-9992411-6-5. S2CID  220484671.
20. Бирка, Ярослав; Сковрон, Петр; Сорнат, Кшиштоф (2017). Пропорциональное одобрительное голосование, гармоническая k-медиана и отрицательная ассоциация . Том 107. С. 26:1–26:14. arXiv : 1704.02183 . doi : 10.4230/LIPIcs.ICALP.2018.26 . ISBN 9783959770767. S2CID  3839722.

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

• Онлайн-инструмент для расчета PAV и других методов многопобедителей на основе одобрения
• Пакет Python abcvoting, содержащий реализацию PAV (pypi)