Критерий суммируемости

В науке о выборах метод голосования удовлетворяет критерию суммируемости, если можно подсчитать результаты выборов на местном уровне по избирательным участкам , а затем подсчитать результаты путем сложения всех голосов. Более формально, сложность компиляции или суммирования измеряет системы голосования сложность подсчета голосов на отдельных избирательных участках и равна наименьшему количеству битов, необходимых для суммирования всех голосов. ^[1] Метод голосования называется суммируемым, если число битов растет как полиномиальная функция числа кандидатов.

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

Несуммируемые методы, такие как альтернативное голосование (ранговый выбор), могут оказаться непомерно дорогими в реализации, что часто приводит к их отклонению избирателями ( как в Соединенном Королевстве ) или отмене (см. RCV в США ).

Ключевым преимуществом низкой сложности компиляции является упрощение проверки результатов голосования. Низкая сложность составления позволяет суммировать результаты на каждом избирательном участке отдельно, что легко проверить, попросив представителей каждой партии подсчитать бюллетени на каждом избирательном участке. Затем любой избиратель сможет проверить окончательный результат, суммируя результаты с 1000 избирательных участков. Эта проверяемость важна для того, чтобы общественность доверяла и принимала результаты. ^[1] Публично опубликованная информация с каждого избирательного участка может быть использована независимыми аудиторами выборов для выявления любых доказательств фальсификации результатов выборов с помощью статистических методов.

Сложность компиляции также алгоритмически полезна для вычисления победителя по обратной индукции в играх с голосованием по Штакельбергу . ^[2]^{[ нужны разъяснения ]}

Определения

Пусть r — правило голосования : функция, которая принимает на вход список из n ранжированных бюллетеней , представляющих предпочтения n избирателей, и возвращает результат. Есть k < n избирателей, голоса которых известны . Функция компиляции — это функция f , которая принимает на вход список из k бюллетеней с рейтингом и возвращает некоторый результат, такой, что для любого числа u := n - k дополнительных бюллетеней с рейтингом результат r для всего набора бюллетеней может быть вычислил точно.

Сложность компиляции правила r — это наихудшее количество битов в выходных данных наиболее эффективной функции компиляции f . ^[1] Это число обычно является функцией n (количества избирателей), k (количества известных голосов) и c (количества кандидатов). Однако для простоты мы сосредоточимся только на c , поскольку нас обычно интересует случай с очень большим количеством неизвестных голосов.

Сложность составления правил голосования с одним победителем

Число возможных бюллетеней для любого ранжированного голосования равно правила $\Theta (c!)$ , обеспечивая верхнюю границу сложности. Однако большинство правил имеют гораздо меньшую сложность компиляции. ^[1]

Позиционное голосование

В позиционных системах голосования, таких как плюралистическая или Борда , любой набор голосов может быть суммирован путем записи общего балла каждого кандидата (например, сколько раз кандидат появляется первым в множественном числе ). Победителя затем можно найти, сложив баллы на каждом избирательном участке, что дает оценку $\Theta (c)$ . Аналогичный аргумент применим к голосованию по баллам и голосованию за одобрение . ^[1]

Правила голосования на основе графика взвешенного большинства

Граф взвешенного большинства профиля избирателя представляет собой ориентированный граф, в котором вершины являются кандидатами, и существует направленное ребро от x до y тогда и только тогда, когда большинство избирателей предпочитают x вместо y . Вес этого преимущества — это количество избирателей, которые предпочитают x вместо y . Многие правила основаны только на графе большинства; количество классов эквивалентности таких правил не превышает числа возможных графов взвешенного большинства. Это число обозначается T( k , c ) — количество взвешенных турниров на c вершинах, которые можно получить от k избирателей. Следовательно, сложность компиляции не превышает log(T( k , c )). Верхняя граница log(T( k , c )) равна ${\frac {c(c-1)}{2}}$ , поскольку для каждой пары кандидатов x,y достаточно сохранить количество избирателей, предпочитающих x вместо y, и это число находится в диапазоне от 0 до k . ^[1]^[2]

Правила голосования со вторым туром

Сложность составления двухтурового голосования ( условного голосования ) находится в $\Theta (c^{2})$ . Обратите внимание, что это выше, чем сложность компиляции голосования по Борде, хотя сложность коммуникации при двухраундовом голосовании ниже , чем у голосования по Борде. ^[3]

Сложность составления единого передаваемого голоса находится в $\Theta \left(2^{c}c\right)$ , что делает его несуммируемым. ^[1]

STAR-голосование также проводится $\Theta (c^{2})$ . ^[4]

Правило Баклина

Для голосования Баклина сложность компиляции равна $\Theta (c^{2})$ . ^[2] Для тесно связанных правил голосования с наивысшим медианным значением сложность бюллетеня, включая $k$ возможные рейтинги $\Theta (ck)$ .

Сложность составления правил голосования с несколькими победителями

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

Для одного непередаваемого голоса сложность заключается в $\Theta (c)$ .
Для Борды сложность заключается в $\Theta (c\log {kc})$ . ^[5]

Связанные проблемы

Компиляция знаний : компиляция части входных данных в автономном режиме, чтобы при поступлении онлайн-входов выходные данные можно было быстро вычислить. Здесь цель компиляции — сэкономить время , а не сэкономить место .
Сложность прекращения сбора данных: учитывая правило голосования, набор известных голосов и набор новых избирателей, определен ли уже результат голосования на основе известных голосов? Очевидно, что если результат уже определен, сложность компиляции невелика, поскольку нам просто нужно сохранить этот результат.
Подсчет возможных и необходимых победителей: учитывая правило голосования, набор неполных голосов ( частичный порядок набора кандидатов), кто являются кандидатами, которые все еще могут выиграть выборы, и есть ли кандидат, который наверняка их выиграет? Очевидно, что если есть уверенный победитель, то сложность компиляции очень мала: нам просто нужно сохранить личность этого уверенного победителя.
Сложность коммуникации : учитывая правило голосования и набор избирателей, какое наименьшее количество битов должно быть передано между избирателями и центром, чтобы вычислить результат выборов? Конитцер и Сандхольм изучают сложность коммуникации некоторых общих правил голосования. ^[3] Сложность компиляции можно рассматривать как сложность однораундной коммуникации. ^[1]

См. также

Ссылки

^ Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час Шевалейр, Янн; Ланг, Джером; Моде, Николас; Равильи-Абади, Уильям (11 июля 2009 г.). «Подсчет голосов подэлектората » Материалы 21-й Международной совместной конференции по искусственному интеллекту . IJCAI'09. Сан-Франциско, Калифорния, США: Morgan Kaufmann Publishers Inc.: 97–102.
^ Перейти обратно: ^а ^б ^с Ся, Лижун; Конитцер, Винсент (4 июля 2010 г.). «Сложность составления общих правил голосования» . Материалы конференции AAAI по искусственному интеллекту . 24 (1): 915–920. дои : 10.1609/aaai.v24i1.7627 . ISSN 2374-3468 .
^ Перейти обратно: ^а ^б Конитцер, Винсент; Сандхольм, Туомас (5 июня 2005 г.). «Коммуникационная сложность единых правил голосования» . Материалы 6-й конференции ACM по электронной коммерции . ЕС '05. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 78–87. дои : 10.1145/1064009.1064018 . ISBN 978-1-59593-049-1 .
^ «Сравните STAR и IRV — Коалиция равного голосования» . Коалиция равных голосов . Проверено 12 ноября 2018 г.
^ Кария, Нил; Ланг, Жером (18 мая 2021 г.). «Сложность составления правил голосования с несколькими победителями (конспект студента)» . Материалы конференции AAAI по искусственному интеллекту . 35 (18): 15809–15810. дои : 10.1609/aaai.v35i18.17901 . ISSN 2374-3468 .

[:0-1] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час Шевалейр, Янн; Ланг, Джером; Моде, Николас; Равильи-Абади, Уильям (11 июля 2009 г.). «Подсчет голосов подэлектората » Материалы 21-й Международной совместной конференции по искусственному интеллекту . IJCAI'09. Сан-Франциско, Калифорния, США: Morgan Kaufmann Publishers Inc.: 97–102.

[:2-2] Перейти обратно: ^а ^б ^с Ся, Лижун; Конитцер, Винсент (4 июля 2010 г.). «Сложность составления общих правил голосования» . Материалы конференции AAAI по искусственному интеллекту . 24 (1): 915–920. дои : 10.1609/aaai.v24i1.7627 . ISSN 2374-3468 .

[:1-3] Перейти обратно: ^а ^б Конитцер, Винсент; Сандхольм, Туомас (5 июня 2005 г.). «Коммуникационная сложность единых правил голосования» . Материалы 6-й конференции ACM по электронной коммерции . ЕС '05. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 78–87. дои : 10.1145/1064009.1064018 . ISBN 978-1-59593-049-1 .

[4] «Сравните STAR и IRV — Коалиция равного голосования» . Коалиция равных голосов . Проверено 12 ноября 2018 г.

[5] Кария, Нил; Ланг, Жером (18 мая 2021 г.). «Сложность составления правил голосования с несколькими победителями (конспект студента)» . Материалы конференции AAAI по искусственному интеллекту . 35 (18): 15809–15810. дои : 10.1609/aaai.v35i18.17901 . ISSN 2374-3468 .

[1]

[2]

[3]

[4]

[5]