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