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

Процесс избрания более чем одного победителя на одних и тех же выборах/округах

Голосование с несколькими победителями , ^[1] также называемое голосованием в комитете ^[2] или выборами в комитете , ^[3] представляет собой избирательную систему , в которой избирается несколько кандидатов. Число избранных кандидатов обычно фиксируется заранее. Например, это может быть количество мест в парламенте страны или необходимое количество членов комитета .

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

1. Превосходство . Здесь каждый избиратель выражает свое мнение о том, какой кандидат/ы «лучше» справляется с той или иной задачей. Цель – найти «лучших» кандидатов. Примером применения является составление короткого списка : выбор из списка кандидатов на работу небольшой группы финалистов, которые перейдут к заключительному этапу оценки (например, с помощью собеседования). Здесь каждый кандидат оценивается независимо от других кандидатов. Если два кандидата похожи, то, вероятно, оба будут избраны (если они оба хороши) или оба будут отклонены (если оба плохи).
2. Разнообразие . Здесь избранные кандидаты должны быть максимально разными . Например, предположим, что кандидатами являются возможные места для строительства объекта, например пожарной части. Большинство горожан, естественно, предпочитают пожарную станцию ​​в центре города. Однако нет необходимости иметь две пожарные части в одном месте; лучше разнообразить выбор и поставить вторую станцию ​​в более отдаленном месте. В отличие от настройки «отлично», если два кандидата одинаковы, то, вероятно, будет избран ровно один из них. Другой сценарий, в котором разнообразие важно, — это когда поисковая система выбирает результаты для отображения или когда авиакомпания выбирает фильмы для показа во время полета.
3. Пропорциональность . Здесь избранные кандидаты должны, насколько это возможно, научно-сбалансированно представлять различные мнения, которых придерживается население избирателей, измеряемое количеством отданных ими голосов. Это общая цель на парламентских выборах ; см. пропорциональное представительство .

Базовые концепты

Основная задача при изучении голосования с несколькими победителями — найти разумную адаптацию концепций голосования с одним победителем. Их можно классифицировать по типу голосования: голосование за одобрение и рейтинговое голосование .

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

В других системах кандидаты группируются в комитеты (списки), и избиратели отдают голоса за комитеты (или списки). Эти системы на основе комитетов описаны здесь:

Утверждающее голосование в комитетах

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

При голосовании с несколькими победителями существует множество способов решить, какой кандидат должен быть избран. В некоторых случаях каждый избиратель ранжирует кандидатов; в других они отдали Х голосов. Кроме того, каждый избиратель может отдать один или несколько голосов.

Уже в 1895 году Тиле предложил семейство правил, основанных на весе, названных правилами голосования Тиле . ^{[2] [5]} Каждое правило в семействе определяется последовательностью k слабо положительных весов, w ₁ ,..., w _k (где k — размер комитета). Каждый избиратель присваивает каждому комитету, состоящему из p кандидатов, одобренных избирателем, балл, равный w ₁ +...+ w _p . Избирается комитет, набравший наибольшее количество баллов. Некоторые общие правила голосования в семье Тиле:

• Множественный непередаваемый голос (MNTV): вектор веса равен (1,1,...,1). Это также называется голосованием за одобрение большинством голосов .
• Утверждение-Чемберлен-Куран (ACC): вектор веса равен (1,0,...,0). То есть каждый избиратель дает комитету 1 балл тогда и только тогда, когда в нем есть один из одобренных им кандидатов.
• Пропорциональное голосование за одобрение (PAV): вектор веса представляет собой гармоническую прогрессию (1, 1/2, 1/3, ..., 1/ k ).

Существуют правила, основанные на других принципах, такие как минимаксное одобрительное голосование ^[6] и его обобщения, ^[7], а также правила голосования Фрагмена ^[8] и метод равных долей . ^{[9] [10]}

Сложность определения победителей различается: победителей MNTV можно найти за полиномиальное время, тогда как Чемберлен-Куран ^[11] и PAV оба являются NP-сложными.

Правила позиционного подсчета очков для комитетов

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

При голосовании с несколькими победителями, проводимом с использованием этих систем, нам необходимо присваивать баллы комитетам, а не отдельным кандидатам. Это можно сделать разными способами, например: ^[1]

• Одиночный непередаваемый голос : каждый избиратель дает 1 балл комитету, если в нем есть его наиболее предпочтительный кандидат. Другими словами: каждый избиратель голосует за одного кандидата в конкурсе, в котором выбираются несколько победителей, и избираются k кандидатов, набравших наибольшее количество голосов. Это обобщает принцип голосования «первым прошедшим» . Его можно вычислить за полиномиальное время.

• Множественное голосование без права передачи (также называемое блоковым голосованием ): каждый избиратель дает комитету 1 балл за каждое открытое место в его топ- k . Другими словами: каждый избиратель голосует за k кандидатов, где k мест открыто, и избираются k кандидатов, набравших наибольшее количество голосов.

• k -Борда: каждый избиратель дает каждому члену комитета свой счет Борды . Каждый избиратель ранжирует кандидатов, и рейтинги подсчитываются вместе. Избираются k кандидатов с наибольшим общим баллом Борда.
• Борда-Чемберлен-Куран (BCC): каждый избиратель сообщает каждому комитету подсчет Борда своего наиболее предпочтительного кандидата в комитете. ^[12] Вычисление победителя с помощью BCC является NP-сложной задачей. ^[11]

Комитеты Кондорсе

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

• Первая адаптация была сделана Питером Фишберном : ^{[13] [14]} комитет является комитетом Кондорсе , если большинство избирателей предпочитает его любому другому возможному комитету. Фишберн предположил, что избиратели ранжируют комитеты по количеству членов в их наборе одобрения (т. е. у них есть дихотомические предпочтения ). В более поздних работах предполагалось, что избиратели ранжируют комитеты по другим критериям, например, по подсчету голосов в Борде . CoNP-полно проверить, удовлетворяет ли комитет этому критерию, и coNP-трудно решить, существует ли комитет Кондорсе. ^[15]
• Другая адаптация была предложена Герляйном ^[16] и Рэтлифом ^[17] : комитет представляет собой набор Кондорсе тогда и только тогда, когда каждый кандидат в нем предпочитается большинством избирателей каждому кандидату за его пределами. Правило голосования с несколькими победителями иногда называется стабильным , если оно выбирает множество Кондорсе всякий раз, когда оно существует. ^[18] Вот некоторые стабильные правила: ^[19]
  • Метод мультипобедителя Коупленда : каждый комитет оценивается по «количеству внешних поражений»: количеству пар ( c , d ), где c есть в комитете, d нет, и большинство избирателей предпочитают c d .
  • Минимаксный метод Кондорсе с несколькими победителями : каждый комитет оценивается по «размеру внешней оппозиции»: минимальному по всем парам ( c , d ) числу избирателей, предпочитающих c .
  • Варианты с несколькими выигрышами некоторых других правил Кондорсе. ^[20]
• Третья адаптация была сделана Элкиндом , Лангом и Саффидином: ^[21] Набор -выигрыш Кондорсе — это набор, в котором для каждого члена d, не входящего в набор, большинство членов набора предпочитается некоторому члену c перед d . Основываясь на этом определении, они представляют другой многопобедный вариант минимаксного метода Кондорсе .

Выборы превосходства

Превосходство означает, что в состав комитета должны входить «лучшие» кандидаты. Правила голосования, основанные на превосходстве, часто называют правилами отбора. ^[18] Их часто используют в качестве первого шага в выборе единственного лучшего кандидата, то есть в качестве метода создания короткого списка . Основным свойством, которому должно удовлетворяться такое правило, является монотонность комитета (также называемая монотонностью дома , вариант монотонности ресурсов ): если по правилу избираются некоторые k кандидатов, а затем размер комитета увеличивается до k +1 и правило применяется повторно, то первые k кандидатов все равно должны быть избраны. Некоторые семейства комитетно-монотонных правил:

• Последовательные правила: ^[18] используя любое правило голосования с одним победителем, выберите одного кандидата и добавьте его в комитет. Повторите процедуру k раз.
• Правила Best -k : ^[1] используя любое правило подсчета очков, присвойте балл каждому кандидату. Выберите k кандидатов с наибольшим количеством баллов.

Свойство монотонности комитета несовместимо со свойством устойчивости (частная адаптация критерия Кондорсе): существует единый профиль голосования, который допускает уникальное множество Кондорсе размера 2 и уникальное множество Кондорсе размера 3, и они не пересекаются. (набор размера 2 не содержится в наборе размера 3). ^[18]

С другой стороны, существует семейство правил позиционного подсчета очков - раздельных правил позиционного подсчета очков - которые являются монотонными для комитета. Эти правила также вычислимы за полиномиальное время (если их основные функции подсчета очков с одним победителем таковы). ^[1] Например, k -Borda является отделимым, а множественный непередаваемый голос - нет.

Разнообразные выборы

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

• Критерий узкой вершины: ^[1] если существует комитет размера k , содержащий кандидата с самым высоким рейтингом от каждого избирателя, то он должен быть избран.
• Монотонность высшего члена: ^[22] если избирается комитет и какой-то избиратель повышает ранг своего наиболее предпочтительного победителя, то должен быть избран тот же комитет.

Пропорциональные выборы

Пропорциональность означает, что каждая сплоченная группа избирателей (то есть: группа избирателей со схожими предпочтениями) должна быть представлена ​​количеством победителей, пропорциональным ее численности. Формально, если размер комитета k , имеется n избирателей и некоторые L * n / k избирателей ставят на первое место одних и тех же L кандидатов (или одобряют одних и тех же L кандидатов), то эти L кандидатов должны быть избраны. Этот принцип легко реализовать, когда избиратели голосуют за партии (в системах партийных списков ), но его также можно адаптировать к одобрительному голосованию или рейтинговому голосованию; см. обоснованное представительство и пропорциональность для прочных коалиций .

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

• Партисипаторное составление бюджета - можно рассматривать как продолжение голосования с несколькими победителями, при котором у каждого кандидата есть «стоимость». При голосовании с несколькими победителями цена каждого кандидата равна 1, а бюджет равен k .

Рекомендации

1. Элкинд, Эдит; Фалишевский, Петр; Сковрон, Петр; Слинько, Аркадий (01.03.2017). «Свойства правил голосования с несколькими победителями». Социальный выбор и благосостояние . 48 (3): 599–632. doi : 10.1007/s00355-017-1026-z. ISSN  1432-217X. ПМК  7089675 . ПМИД  32226187.
2. Азиз, Харис; Брилл, Маркус; Конитцер, Винсент; Элкинд, Эдит; Фриман, Руперт; Уолш, Тоби (2017). «Оправданное представительство при голосовании в комитете на основе одобрения». Социальный выбор и благосостояние . 48 (2): 461–485. arXiv : 1407.8269 . дои : 10.1007/s00355-016-1019-3. S2CID  8564247.
3. Бок, Ганс-Германн; Дэй, Уильям Х.Э.; МакМоррис, Франция (1 мая 1998 г.). «Правила консенсуса для выборов в комитеты». Математические социальные науки . 35 (3): 219–232. дои : 10.1016/S0165-4896(97)00033-4. ISSN  0165-4896.
4. Петр Фалишевский, Петр Сковрон, Аркадий Слинько, Нимрод Тальмон (26 октября 2017 г.). «Голосование с несколькими победителями: новый вызов теории социального выбора». В Эндриссе, Улле (ред.). Тенденции в вычислительном социальном выборе . Лулу.com. ISBN 978-1-326-91209-3.{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
5. Санчес-Фернандес, Луис; Элкинд, Эдит; Лакнер, Мартин; Фернандес, Норберто; Фистеус, Иисус; Вэл, Пабло Басанта; Сковрон, Петр (10 февраля 2017 г.). «Пропорциональное обоснованное представительство». Материалы конференции AAAI по искусственному интеллекту . 31 (1). дои : 10.1609/aaai.v31i1.10611 . hdl : 10016/26166 . ISSN  2374-3468. S2CID  17538641.
6. Брамс, Стивен Дж.; Килгур, Д. Марк; Санвер, М. Ремзи (1 сентября 2007 г.). «Минимаксная процедура избрания комитетов». Общественный выбор . 132 (3): 401–420. doi : 10.1007/s11127-007-9165-x. ISSN  1573-7101. S2CID  46632580.
7. Аманатидис, Георгиос; Барро, Натанаэль; Ланг, Жером; Маркакис, Евангелос; Райс, Бернард (4 мая 2015 г.). «Множественные референдумы и выборы с несколькими победителями с использованием расстояний Хэмминга: сложность и возможность манипулирования». Материалы Международной конференции по автономным агентам и мультиагентным системам 2015 года . ААМАС '15. Стамбул, Турция: Международный фонд автономных агентов и мультиагентных систем: 715–723. ISBN 978-1-4503-3413-6.
8. Брилл, Маркус; Фриман, Руперт; Янсон, Сванте; Лакнер, Мартин (10 февраля 2017 г.). «Методы голосования Фрагмена и оправданное представительство». Материалы конференции AAAI по искусственному интеллекту . 31 (1). arXiv : 2102.12305 . дои : 10.1609/aaai.v31i1.10598 . ISSN  2374-3468. S2CID  2290202.
9. Петерс, Доминик; Сковрон, Петр (2020). «Пропорциональность и пределы благосостояния». Материалы 21-й конференции ACM по экономике и вычислениям . ЕС'20. стр. 793–794. arXiv : 1911.11747 . дои : 10.1145/3391403.3399465. ISBN 9781450379755. S2CID  208291203.
10. Перчинский, Гжегож; Петерс, Доминик; Сковрон, Петр (2021). «Пропорциональное совместное бюджетирование с аддитивными утилитами». Материалы конференции 2021 года по нейронным системам обработки информации . НейрИПС'21. arXiv : 2008.13276 .
11. Прокачча, Ариэль Д.; Розеншайн, Джеффри С.; Зоар, Авив (19 апреля 2007 г.). «О сложности достижения пропорционального представительства». Социальный выбор и благосостояние . 30 (3): 353–362. дои : 10.1007/s00355-007-0235-2. S2CID  18126521.
12. Чемберлин, Джон Р.; Курант, Пол Н. (1983). «Представительские обсуждения и представительные решения: пропорциональное представительство и правило Борды». Американский обзор политической науки . 77 (3): 718–733. дои : 10.2307/1957270. ISSN  0003-0554. JSTOR  1957270. S2CID  147162169.
13. Фишберн, Питер К. (1981-10-01). «Комитеты большинства». Журнал экономической теории . 25 (2): 255–268. дои : 10.1016/0022-0531(81)90005-3. ISSN  0022-0531.
14. Фишберн, Питер К. (1 декабря 1981). «Анализ простых систем голосования для избирательных комитетов». SIAM Journal по прикладной математике . 41 (3): 499–502. дои : 10.1137/0141041. ISSN  0036-1399.
15. Дарманн, Андреас (1 ноября 2013 г.). «Насколько сложно определить, что такое комитет Кондорсе?». Математические социальные науки . 66 (3): 282–292. doi :10.1016/j.mathsocsci.2013.06.004. ISSN  0165-4896. ПМК 4376023 . ПМИД  25843993. 
16. Герляйн, Уильям В. (1 декабря 1985 г.). «Критерий Кондорсе и выбор комитета». Математические социальные науки . 10 (3): 199–209. дои : 10.1016/0165-4896(85)90043-5. ISSN  0165-4896.
17. Рэтлифф, Томас К. (1 декабря 2003 г.). «Некоторые поразительные несоответствия при избрании комитетов». Социальный выбор и благосостояние . 21 (3): 433–454. doi : 10.1007/s00355-003-0209-y. ISSN  1432-217X. S2CID  36949675.
18. Барбера, Сальвадор; Коэльо, Данило (2008). «Как выбрать непротиворечивый список из k имен». Социальный выбор и благосостояние . 31 (1): 79–96. дои : 10.1007/s00355-007-0268-6. ISSN  0176-1714. JSTOR  41107910. S2CID  16974573.
19. Коэльо, Данило; Барбера, Сальвадор (2005). Понимание, оценка и выбор правил голосования посредством игр и аксиом. Беллатерра: Автономный университет Барселоны. ISBN 978-84-689-0967-7.
20. Камва, Эрик (1 мая 2017 г.). «Об устойчивых правилах отбора комиссий». Журнал математической экономики . 70 : 36–44. doi : 10.1016/j.jmateco.2017.01.008. ISSN  0304-4068. S2CID  125508393.
21. Элкинд, Эдит; Ланг, Жером; Саффидин, Абдалла (2015). «Наборы победы Кондорсе». Социальный выбор и благосостояние . 44 (3): 493–517. дои : 10.1007/s00355-014-0853-4. ISSN  0176-1714. JSTOR  43662603. S2CID  31128109.
22. Фалишевский, Петр; Сковрон, Петр; Слинько, Аркадий; Талмон, Нимрод (9 июля 2016 г.). «Правила оценки комитетов: аксиоматическая классификация и иерархия». Материалы двадцать пятой Международной совместной конференции по искусственному интеллекту . IJCAI'16. Нью-Йорк, Нью-Йорк, США: AAAI Press: 250–256. ISBN 978-1-57735-770-4.