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

Совместная серия «Политика и экономика»
Социальный выбор и избирательные системы
Социальный выбор Конструкция механизма Сравнительная политология Сравнение Список  ( по странам )
Методы с одним победителем Методы голосования по принципу «единого голоса» и « плюрализма» Первое предпочтение относительного большинства (FPP) Two-round (US: Jungle primary) Partisan primary Instant-runoff UK: Alternative vote (AV) US: Ranked-choice (RCV) Condorcet methods Condorcet-IRV Round-robin voting Minimax Schulze Ranked pairs Maximal lottery Positional voting Plurality (el. IRV) Borda count (el. Baldwin) Antiplurality (el. Coombs) Cardinal voting Score voting Approval voting Majority judgment STAR voting
Proportional representation Party-list Apportionment Highest averages Largest remainders National remnant Biproportional List type Closed list Open list Panachage List-free PR Localized list Quota-remainder methods Hare STV Schulze STV CPO-STV Quota Borda Approval-based committees Thiele's method Phragmen's method Expanding approvals rule Method of equal shares Fractional social choice Direct representation Interactive representation Liquid democracy Fractional approval voting Maximal lottery Random ballot Semi-proportional representation Cumulative SNTV Limited voting
Mixed systems By results of combination Mixed-member majoritarian Mixed-member proportional By mechanism of combination Non-compensatory Parallel (superposition) Coexistence Conditional Fusion (majority bonus) Compensatory Seat linkage system UK: 'AMS' NZ: 'MMP' Vote linkage system Negative vote transfer Mixed ballot Supermixed systems Dual-member proportional Rural–urban proportional Majority jackpot By ballot type Single vote Double simultaneous vote Dual-vote
Paradoxes and pathologies Spoiler effects Spoiler effect Cloning paradox Frustrated majorities paradox Center squeeze Pathological response Perverse response Best-is-worst paradox No-show paradox Multiple districts paradox Strategic voting Lesser evil voting Exaggeration Truncation Turkey-raising Paradoxes of majority rule Tyranny of the majority Discursive dilemma Conflicting majorities paradox
Social and collective choice Impossibility theorems Arrow's theorem Majority impossibility Moulin's impossibility theorem McKelvey–Schofield chaos theorem Gibbard's theorem Positive results Median voter theorem Condorcet's jury theorem May's theorem Condorcet dominance theorems Harsanyi's utilitarian theorem VCG mechanism Quadratic voting
Politics portal Economics portal Mathematics portal
v t e

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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