Jump to content

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

(Перенаправлено с выборов в комитет )

Мультипобедитель , [1] в целом или комитет [2] [3] Голосование относится к избирательным системам , которые избирают нескольких кандидатов одновременно. Такие методы могут использоваться для избрания парламентов или комитетов .

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

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

Семейства методов

[ редактировать ]

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

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

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

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

[ редактировать ]

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

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

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

Существуют правила, основанные на других принципах, например минимаксное голосование за одобрение. [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 кандидатов должны быть избраны. Этот принцип легко реализовать, когда избиратели голосуют за партии (в системах партийных списков ), но его также можно адаптировать к одобрительному голосованию или рейтинговому голосованию; см. обоснованное представительство и пропорциональность для прочных коалиций .

См. также

[ редактировать ]
  1. ^ Jump up to: а б с д и Элкинд, Эдит; Фалишевский, Петр; Сковрон, Петр; Слинько, Аркадий (01.03.2017). «Свойства правил голосования с несколькими победителями» . Социальный выбор и благосостояние . 48 (3): 599–632. дои : 10.1007/s00355-017-1026-z . ISSN   1432-217X . ПМК   7089675 . ПМИД   32226187 .
  2. ^ Jump up to: а б Азиз, Харис; Брилл, Маркус; Конитцер, Винсент; Элкинд, Эдит; Фриман, Руперт; Уолш, Тоби (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. дои : 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. ^ Jump up to: а б Прокачча, Ариэль Д.; Розеншайн, Джеффри С.; Зоар, Авив (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. ^ Фишберн, Питер К. (1 октября 1981 г.). «Комитеты большинства» . Журнал экономической теории . 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. дои : 10.1007/s00355-003-0209-y . ISSN   1432-217X . S2CID   36949675 .
  18. ^ Jump up to: а б с д Барбера, Сальвадор; Коэльо, Данило (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. ^ Камва, Эрик (01 мая 2017 г.). «Об устойчивых правилах отбора комиссий» . Журнал математической экономики . 70 : 36–44. дои : 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 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 52592ea5d51312ffc288bb3e0a5a8128__1720922460
URL1:https://arc.ask3.ru/arc/aa/52/28/52592ea5d51312ffc288bb3e0a5a8128.html
Заголовок, (Title) документа по адресу, URL1:
Multiwinner voting - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)