Обоснованное представление

Критерий оценки справедливости избирательных систем

Справедливое представительство (JR) является критерием справедливости в многопобедном одобрительном голосовании . Его можно рассматривать как адаптацию критерия пропорционального представительства к одобрительному голосованию.

Фон

Пропорциональное представительство (PR) является важным фактором при разработке избирательных систем. Это означает, что различные группы и секторы населения должны быть представлены в парламенте пропорционально их размеру. Наиболее распространенной системой для обеспечения пропорционального представительства является система партийных списков . В этой системе кандидаты делятся на партии, и каждый гражданин голосует за одну партию. Каждая партия получает количество мест, пропорциональное количеству граждан, которые за нее проголосовали. Например, для парламента с 10 местами, если ровно 50% граждан голосуют за партию A, ровно 30% голосуют за партию B и ровно 20% голосуют за партию C, то пропорциональное представительство требует, чтобы парламент содержал ровно 5 кандидатов от партии A, ровно 3 кандидатов от партии B и ровно 2 кандидатов от партии C. В действительности дроби обычно неточны, поэтому следует использовать какой-либо метод округления, и это можно сделать различными методами распределения .

В последние годы растет недовольство партийной системой. ^[1] Жизнеспособной альтернативой системам партийных списков является предоставление гражданам возможности голосовать напрямую за кандидатов, используя бюллетени для одобрения . Это поднимает новую проблему: как мы можем определить пропорциональное представительство, когда нет заранее определенных групп (партий), которые могут заслуживать пропорционального представительства? Например, предположим, что один избиратель одобряет кандидата 1,2,3; другой избиратель одобряет кандидатов 2,4,5; третий избиратель одобряет кандидатов 1,4. Каково разумное определение «пропорционального представительства» в этом случае? ^[2] Было предложено несколько ответов; они в совокупности известны как оправданное представительство.

Основные понятия

Ниже мы обозначаем количество мест как k , а количество избирателей как n . Квота Хара равна n / k — минимальное количество сторонников, оправдывающее одно место. В системах партийных списков PR каждая группа избирателей с не менее чем L квотами, голосующая за одну и ту же партию, имеет право на L представителей этой партии.

Естественным обобщением этой идеи является L-сплоченная группа , определяемая как группа избирателей с не менее чем L квотами, которые совместно одобряют не менее L кандидатов.

Оправданные свойства представления

В идеале мы хотели бы потребовать, чтобы для каждой L-сплоченной группы каждый член имел по крайней мере L представителей. Это условие, называемое сильным обоснованным представительством (SJR) , может быть недостижимым, как показано в следующем примере. ^[3]

Пример 1. Есть k = 3 места и 4 кандидата {a, b, c, d}. Есть n = 12 избирателей с наборами одобрения: ab, b, b, bc, c, c, cd, d, d, da, a, a. Обратите внимание, что квота Хара равна 4. Группа {ab, b, b, bc} является 1-сплоченной, так как она содержит 1 квоту, и все члены одобряют кандидата b. Strong-JR подразумевает, что кандидат b должен быть избран. Аналогично, Группа {bc, cc, cd} является 1-сплоченной, что требует избрания кандидата c. Аналогично, группа {cd, d, d, da} требует избрания d, а группа {da, a, a, ab} требует избрания a. Таким образом, нам нужно выбрать 4 кандидатов, но размер комитета составляет всего 3. Следовательно, ни один комитет не удовлетворяет сильному JR.

Есть несколько способов смягчить концепцию сильного младшего помощника.

Единогласные группы

Один из способов — гарантировать представительство только L-единогласной группе , определяемой как группа избирателей с квотами не менее L, которая одобряет точно такой же набор из не менее L кандидатов. Это условие называется единогласным обоснованным представительством (UJR) . Однако L-единогласные группы довольно редки в системах одобрительного голосования, поэтому единогласная JR не будет очень полезной гарантией.

Сплоченные группы

Оставаясь с L-сплоченными группами, мы можем ослабить гарантию представительства следующим образом. Определим удовлетворенность избирателя как количество победителей, одобренных этим избирателем. Strong-JR требует, чтобы в каждой L-сплоченной группе минимальное удовлетворение члена группы было не менее L. Вместо этого мы можем потребовать, чтобы среднее удовлетворение членов группы было не менее L. Это более слабое условие называется средним оправданным представительством (AJR) . ^[4] К сожалению, это условие все еще может быть недостижимым. В примере 1 выше, как и Strong-JR, Average-JR требует избрать всех 4 кандидатов, но есть только 3 места. В каждом комитете размером 3 среднее удовлетворение некоторой 1-сплоченной группы составляет всего 1/2.

Пропорциональное одобрительное голосование гарантирует каждой L-сплоченной группе среднее удовлетворение, превышающее L -1. У него есть вариант, называемый Local-Search-PAV, который выполняется за полиномиальное время и также гарантирует среднее удовлетворение, превышающее L -1. ^[5]^{: Теория 1, Предложение 1} Эта гарантия оптимальна: для любой константы c >0 нет правила, гарантирующего среднее удовлетворение, по крайней мере, L -1+ c . ^[5]^{: Предложение 2}
AJR может быть удовлетворена фракционными комитетами — комитетами, в которых члены могут служить часть срока или получать взвешенные голоса. В частности, правило Нэша удовлетворяет AJR. ^[6]

Мы можем еще больше ослабить требование, потребовав, чтобы максимальное удовлетворение члена группы было не менее L. Другими словами, в каждой L-сплоченной группе по крайней мере один член должен иметь L одобренных представителей. Это условие называется расширенным обоснованным представительством (EJR) ; оно было введено и проанализировано Азизом, Бриллом, Конитцером, Элкиндом , Фрименом и Уолшем . ^[3] Существует еще более слабое условие, которое требует, чтобы EJR выполнялось только для L=1 (только для 1-сплоченных групп); оно называется обоснованным представительством. ^[3] Несколько известных методов удовлетворяют EJR:

Каждый комитет со средним удовлетворением больше L -1 удовлетворяет EJR (по принципу ящика ). ^[5] Следовательно, PAV и Local-Search-PAV удовлетворяют EJR. PAV — единственное правило голосования Тиле , которое удовлетворяет EJR. ^[3]
Метод равных долей ^[7] — еще одно вычислимое за полиномиальное время правило, удовлетворяющее EJR.
Другим поливременным алгоритмом, гарантирующим EJR, является EJR-Exact. ^[5]
Простой алгоритм, который находит распределение EJR, называется "Жадный EJR". Цикл L от k вниз до 1, этот алгоритм проверяет, существует ли L-сплоченное подмножество избирателей. Если да, он выбирает наибольшее L-сплоченное подмножество и добавляет несколько L кандидатов, которые одобрены всеми из них. ^[8]^{: Алгоритм 1}
Последовательный PAV удовлетворяет EJR только для 1-сплоченных групп и только при k ≤ 5. При k ≥ 6 он не удовлетворяет EJR даже для 1-сплоченных групп.
Правило Монро не работает EJR
Проверка того, удовлетворяет ли данный комитет условию EJR, является ко-NP-полной .

Дальнейшим ослаблением EJR является пропорциональное оправданное представительство (PJR) . Это означает, что для каждого L ≥ 1 в каждой L -сплоченной группе избирателей объединение их наборов одобрения содержит несколько победителей L. Это было введено и проанализировано Санчесом-Фернандесом, Элкиндом , Лакнером, Фернандесом, Фистеусом, Валом и Сковроном . ^[4]

EJR подразумевает PJR, но не наоборот. Например, ^[9]^{: Раздел 4} рассматривает ситуацию с 2 k кандидатами и k избирателями. Избиратель i одобряет кандидата i , а также кандидатов k +1,...,2 k . Обратите внимание, что квота составляет одного избирателя, и каждые L избирателей являются L -сплоченной группой. Комитет 1,..., k удовлетворяет PJR, поскольку для каждых L избирателей объединение их множеств одобрения содержит L победителей. Но он не удовлетворяет EJR, поскольку у каждого избирателя есть только 1 одобренный победитель. Напротив, комитет k +1,...,2 k удовлетворяет EJR.
PAV удовлетворяет EJR, поэтому он удовлетворяет и PJR; и это также единственное правило голосования на основе веса, которое удовлетворяет PJR. Однако Sequential-PAV нарушает PJR.
Некоторые из правил голосования Phragmen удовлетворяют PJR, а именно: Leximax Phragmen, который является NP-трудным для вычисления, и Sequential Phragmen, который является поливременно вычислимым и, кроме того, удовлетворяет комитетной монотонности . ^[10]
Когда k делит n , Monroe и Greedy Monroe удовлетворяют PJR. Однако, когда k не делит n , и Monroe, и Greedy Monroe могут нарушать PJR, за исключением случая, когда L=1. ^[4]
Другое правило, которое вычисляется как по методу PJR, так и по методу поливремени, — это правило максиминной поддержки . ^[11]
Проверка того, удовлетворяет ли данный комитет PJR, является ко-NP-полной . ^[5]

Частично сплоченные группы

Вышеуказанные условия имеют смысл только для L-сплоченных групп. Но L-сплоченные группы могут быть довольно редкими на практике. ^[12] Вышеуказанные условия вообще ничего не гарантируют группам, которые являются "почти" сплоченными. Это мотивирует поиск более надежных понятий JR, которые гарантируют что-то также и для частично сплоченных групп.

Одним из таких понятий, которое очень распространено в теории кооперативных игр, является стабильность ядра (CS). ^[3] Это означает, что для любой группы избирателей с L квотами (не обязательно сплоченной), если эта группа отклоняется и создает меньший комитет с L местами, то по крайней мере для одного избирателя число членов комитета, которых он одобряет, не больше, чем в исходном комитете. EJR можно рассматривать как слабый вариант CS, в котором отклоняться разрешено только L-сплоченным группам. EJR требует, чтобы для любой L-сплоченной группы по крайней мере один член не хотел отклоняться, поскольку его текущее удовлетворение уже равно L, что является максимально возможным удовлетворением с L представителями.

По состоянию на 2023 год вопрос о том, будет ли существовать комитет CS, остается открытым.

Peters, Pierczyński и Skowron ^[13] представляют другое ослабление сплоченности. При наличии двух целых чисел L и B ≤ L группа избирателей S называется (L,B)-слабосплоченной , если она содержит не менее L квот и существует множество C из L кандидатов, такое, что каждый член S одобряет не менее B кандидатов из C . Обратите внимание, что ( L , L )-слабосплоченность эквивалентна L-сплоченности. Комитет удовлетворяет условию полного обоснованного представительства (FJR), если в каждой (L,B)-слабосплоченной группе есть по крайней мере один член, который одобряет некоторых победителей B. Очевидно, что FJR подразумевает EJR.

FJR всегда может быть удовлетворен с помощью жадного связного правила (которое не является поливременным); остается открытым вопрос о том, существуют ли поливременные алгоритмы, удовлетворяющие FJR.

Брилл и Питерс ^[14] представляют другое ослабление сплоченности. При наличии выборного комитета определим группу как L-депривированную , если она содержит не менее L квот, и, кроме того, по крайней мере один невыборный кандидат одобрен всеми членами. Комитет удовлетворяет EJR+, если для каждой L-депривированной группы избирателей максимальное удовлетворение составляет не менее L (по крайней мере один член группы одобряет не менее L победителей); комитет удовлетворяет PJR+, если для каждой L-депривированной группы объединение их множеств одобрения содержит несколько L победителей. Очевидно, что EJR+ подразумевает EJR и PJR+, а PJR+ подразумевает PJR.

PAV, local-search-PAV и MES удовлетворяют EJR+; доказательства такие же, как и исходные доказательства, поскольку исходные доказательства не используют связность — они используют только тот факт, что один кандидат, одобренный всеми членами группы, не избирается.
Существует также поливременной жадный алгоритм , который находит комитет EJR+: правило жадного обоснованного кандидата.
PJR+ можно проверить за полиномиальное время, сведя к субмодулярной оптимизации — в отличие от PJR, который coNP-трудно проверить.
EJR+ можно проверить за полиномиальное время с помощью следующего простого алгоритма: для каждого L между 1 и k и для каждого неизбранного кандидата c: подсчитать количество избирателей, которые одобряют c, и одобряют менее L победителей. Если количество таких избирателей составляет не менее L квот, то комитет нарушает EJR+.
EJR+ удовлетворяет слабой форме монотонности комитета : для всех k существует комитет EJR+ W размера k и невыбранный кандидат c , такой что добавление c к W дает комитет EJR+ (размера k +1).

Идеальное представление

Другое, не связанное свойство — это Идеальное представление (PER) . Это означает, что существует отображение каждого избирателя на одного победителя, одобренного им, так что каждый победитель представляет ровно n / k избирателей. Хотя идеальное представление может и не существовать, мы ожидаем, что если оно существует, то оно будет выбрано по правилу голосования. ^[4]

PER совместим с PJR и JR: для каждого случая, допускающего совершенное представление, существует комитет, удовлетворяющий PJR. Однако PER несовместим с EJR: существуют случаи, в которых существуют совершенные представления, но ни одно из них не удовлетворяет EJR. PER удовлетворяется правилом Монро и правилом лексимакс- Фрагмена ; ^[10] но оно нарушается жадным Монро, последовательным PAV и PAV. ^[4]

См. также: Полностью пропорциональное представительство .

Подразумеваемое

Следующая диаграмма иллюстрирует импликационные отношения между различными условиями: SJR подразумевает, что AJR подразумевает, что EJR; CS подразумевает, что FJR подразумевает, что EJR; и EJR+ подразумевает, что EJR и PJR+. EJR подразумевает, что PJR, что подразумевает как UJR, так и JR. UJR и JR не подразумевают друг друга.

СЖР	→	АЖР	→	ЭЙР	→	ПЖР	→	УЖР
				↑		↑	→	Дж.Р.
КС	→	ФЙР	→	↑		↑
				↑		↑
		ЭЖР+	→	↑	→	ПЖР+

EJR+ несравним с CS и FJR. ^[14]^{: Rem.2}

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

Проверка

Учитывая предпочтения избирателей и конкретный комитет, можем ли мы эффективно проверить, удовлетворяет ли он какой-либо из этих аксиом? ^[5]

JR можно проверить за полиномиальное время;
PJR и EJR являются coNP-полными для проверки;
Проверка PER является NP-сложной (решение вопроса о существовании идеального представления является NP-полной задачей).

Средняя удовлетворенность - степень пропорциональности

Удовлетворенность избирателя, учитывая определенный комитет, определяется как количество членов комитета, одобренных этим избирателем. Средняя удовлетворенность группы избирателей - это сумма их уровней удовлетворенности, деленная на размер группы. Если группа избирателей L -сплоченная (то есть их размер составляет не менее L * n / k и они одобряют не менее L кандидатов совместно), то:

Каждый комитет JR имеет среднюю удовлетворенность не менее 1 - 1/ L + 1/( Ln ). То же самое справедливо для каждого комитета PJR.
Каждый комитет EJR имеет среднее удовлетворение не менее ( L -1)/2. Эскиз доказательства : EJR гарантирует по крайней мере одному члену в L -сплоченной группе удовлетворение не менее L . После того, как этот член удален, оставшаяся группа становится по крайней мере ( L -1)-сплоченной, поэтому по крайней мере одному оставшемуся члену гарантируется удовлетворение не менее L -1. Продолжая таким образом, получаем среднее удовлетворение L+(L-1)+..., что больше, чем ( L -1)/2.
Таким образом, EJR обеспечивает гораздо более надежную гарантию удовлетворения в худшем случае, чем PJR. ^[4]
Каждый комитет со средним уровнем удовлетворенности больше L -1 удовлетворяет EJR.

Пропорциональное одобрительное голосование гарантирует среднее удовлетворение, большее, чем L -1. У него есть вариант, называемый Local-Search-PAV, который работает за полиномиальное время и также гарантирует среднее удовлетворение, большее, чем L -1 (следовательно, это EJR). ^[5]^{: Теор.1, Предл.1} Эта гарантия оптимальна: для любой константы c >0 нет правила, которое гарантирует среднее удовлетворение, по крайней мере, L -1+ c (см. Пример 1 выше). ^[5]^{: Предл.2}

Скоурон ^[15] изучает степень пропорциональности правил голосования с несколькими победителями — нижнюю границу средней удовлетворенности всех групп определенного размера.

Переменное количество победителей

Фримен, Канг и Пеннок ^[16] адаптируют концепцию среднего удовлетворения к многопобедительному голосованию с переменным числом победителей. Они утверждают, что другие аксиомы JR не привлекательны при переменном числе победителей, тогда как среднее удовлетворение является более надежным понятием. Адаптация включает следующие изменения:

Каждый избиратель получает удовлетворение не только от избранного кандидата, которого он одобряет, но и от неизбранного кандидата, которого он не одобряет (это делает проблему похожей на голосование по нескольким вопросам , где каждый кандидат представляет собой бинарную проблему).
Группа является L-большой , если она содержит не менее L * n / m избирателей (где m — общее число кандидатов), и L-сплоченной , если, кроме того, члены группы соглашаются о размещении не менее L кандидатов (то есть: пересечение A _i плюс пересечение C \ A _i составляет не менее L ).
Комитет является r-AS (r-среднее-удовлетворение), если для каждой L -сплоченной группы среднее значение удовлетворенности членов составляет по крайней мере r*L . Условия JR, PJR и EJR обобщаются аналогичным образом.
Правило PAV выбирает комитет, который максимизирует сумму Harmonic(sat _i ), где sat _i — это удовлетворение избирателя i . Последовательное правило Фрагмена и метод равных долей делят нагрузку каждого избранного кандидата среди избирателей, которые его одобряют, а нагрузку каждого неизбранного кандидата — среди избирателей, которые его не одобряют. Все эти правила удовлетворяют PJR. MES нарушает EJR; неизвестно, удовлетворяют ли ему два других.
Детерминированное правило не может гарантировать r -AS для r = (m-1)/m+epsilon, для любого epsilon>0. PAV, Phragmen и MES не могут гарантировать r -AS для r = 1/2+epsilon. Но есть рандомизированное правило, которое удовлетворяет (29/32)-AS.

Цена обоснованного представительства

Цена оправданного представительства — это потеря среднего удовлетворения из-за требования иметь оправданное представительство. Она аналогична цене справедливости . ^[8]

Эмпирическое исследование

Бредерек, Фалишевски, Качмарчик и Нидермайер ^[12] провели экспериментальное исследование, чтобы проверить, сколько комитетов удовлетворяют различным аксиомам обоснованного представительства. Они обнаружили, что сплоченные группы редки, и поэтому большая часть случайно выбранных комитетов JR также удовлетворяют PJR и EJR.

Адаптации

Аксиомы обоснованного представительства были адаптированы к различным ситуациям, выходящим за рамки простого голосования в комитете.

Голосование по одобрению партии

Brill, Golz, Peters, Schmidt-Kraepelin и Wilker адаптировали аксиомы JR к голосованию с одобрением партии . В этой обстановке вместо одобрения отдельных кандидатов избиратели должны одобрить целые партии. Эта обстановка является промежуточным вариантом между выборами по партийным спискам, в которых избиратели должны выбрать одну партию, и стандартным голосованием с одобрением, в котором избиратели могут выбрать любой набор кандидатов. При голосовании с одобрением партии избиратели могут выбрать любой набор партий, но не могут выбрать отдельных кандидатов внутри партии. Некоторые аксиомы JR адаптированы к этой обстановке следующим образом. ^[17]

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

PJR означает, что для каждого L ≥ 1 в каждой L- сплоченной группе избирателей партии в объединении их наборов одобрения выделяются не менее L мест.
EJR означает, что для каждого целого числа L ≥ 1 в каждой L -сплоченной группе избирателей партии, одобренные хотя бы одним избирателем, получают не менее L мест.
CS означает, что для любой группы избирателей размером L * n / k избирателей (не обязательно сплоченной), если эта группа отклоняется и создает меньший комитет с L местами, то хотя бы для одного избирателя число членов комитета от одобренных им партий не будет больше, чем в первоначальном комитете.

Следующий пример ^[17] иллюстрирует разницу между CS и EJR. Предположим, что есть 5 партий {a, b, c, d, e}, k = 16 мест и n = 16 избирателей со следующими предпочтениями: 4*ab, 3*bc, 1*c, 4*ad, 3*de, 1*e. Рассмотрим комитет с 8 местами для партии a, 4 для партии c и 4 для партии e. Числа представителей избирателей: 8, 4, 4, 8, 4, 4. Это не CS: рассмотрим группу из 14 избирателей, которые одобряют ab, bc, ad, de. Они могут сформировать комитет с 4 местами для партии a, 5 мест для партии b и 5 мест для партии d. Теперь числа представителей составляют: 9, 5, [0], 9, 5, [0], поэтому все члены отклоняющейся коалиции строго счастливее. Однако первоначальный комитет удовлетворяет EJR. Обратите внимание, что квота равна 1. Наибольшее L, для которого существует L -сплоченная группа, составляет L = 8 (избиратели ab и ad), и этой группе выделяется 8 мест.

Выборы на основе ранга

Концепция JR берет свое начало из более ранней концепции, введенной Майклом Дамметом для выборов на основе ранга. Его условие заключается в том, что для каждого целого числа L ≥ 1, для каждой группы размером не менее L * n / k , если они ранжируют одних и тех же L кандидатов наверху, то эти L кандидатов должны быть избраны. ^[18]

Трихотомические бюллетени

Талмон и Пейдж ^[19] распространяют некоторые аксиомы JR с бюллетеней одобрения на трихотомические (с тремя вариантами) бюллетени, позволяя каждому избирателю выражать положительные, отрицательные или нейтральные чувства по отношению к каждому кандидату. Они представляют два класса обобщений: более сильные («Класс I») и более слабые («Класс II»).

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

Дегрессивная и регрессивная пропорциональность

Дегрессивная пропорциональность (иногда прогрессивная пропорциональность) предоставляет меньшим группам больше представителей, чем им пропорционально положено, и используется Европейским парламентом . Например, Пенроуз предположил, что каждая группа должна быть представлена пропорционально квадратному корню ее размера.

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

С другой стороны, регрессивная пропорциональность означает, что большим группам должно быть предоставлено представительство выше пропорционального. Крайностью регрессивной пропорциональности является индивидуальное превосходство , что означает, что комитет должен содержать членов, поддержанных наибольшим числом избирателей. ^[9]^{: Раздел 4.5} Правило голосования по одобрению блока (AV) максимизирует индивидуальное превосходство.

Лакнер и Сковрон ^[20] показывают, что правила голосования Тиле могут быть использованы для интерполяции между регрессивной и дегрессивной пропорциональностью: PAV пропорциональны; правила, в которых наклон функции оценки выше, чем у PAV, удовлетворяют регрессивной пропорциональности; и правила, в которых наклон функции оценки ниже, чем у PAV, удовлетворяют дегрессивной пропорциональности. Более того, ^[21] Если оценка удовлетворения i -го одобренного кандидата равна (1/ p ) ⁱ , для различных значений p , мы получаем весь спектр между CC и AV.

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

Делимые товары

Бэй, Лу и Суксомпонг ^[23] расширяют модель выборов комитета до ситуации, в которой есть континуум кандидатов, представленный действительным интервалом [0, c ], как в честном разрезании торта . Цель состоит в том, чтобы выбрать подмножество этого интервала с общей длиной не более k , где здесь k и c могут быть любыми действительными числами с 0 < k < c . Чтобы обобщить понятия JR для этой ситуации, они рассматривают L -сплоченные группы для любого действительного числа L (не обязательно целого): ^[23]^{: App.A}

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

Они рассматривают два решения: решение лексимина не удовлетворяет ни PJR, ни EJR, но оно истинно . Напротив, правило Нэша, которое максимизирует сумму log(u _i ), удовлетворяет EJR и, следовательно, PJR. Обратите внимание, что правило Нэша можно рассматривать как непрерывный аналог пропорционального одобрительного голосования , которое максимизирует сумму Harmonic(u _i ). Однако Нэш не является истинным. Эгалитарное отношение обоих решений равно k /( n - nk+k ).

Lu, Peters, Aziz, Bei и Suksompong ^[24] расширяют эти определения до настроек со смешанными делимыми и неделимыми кандидатами: есть набор из m неделимых кандидатов, а также торт [0, c ]. Расширенное определение EJR, которое допускает L-сплоченные группы с нецелым L, может быть недостижимым. Они определяют две релаксации:

EJR-M гарантирует любой L-сплоченной группе, когда имеется набор ресурсов общего размера точно L , что по крайней мере один член группы получает полезность не менее L. EJR-M сводится к EJR как в ситуациях, когда есть только неделимые кандидаты, так и в ситуациях, когда есть только делимый кандидат.
EJR-b (для любого действительного числа b) гарантирует любой L-сплоченной группе, что по крайней мере один член группы получит полезность большую, чем Lb.

Они доказывают, что:

Для любого b<1 EJR-b может быть недостижим.
Правило Нэша не удовлетворяет EJR-b ни для какого b.
Правило, называемое Greedy-EJR, удовлетворяет EJR-M, но выполняется за экспоненциальное время и имеет степень пропорциональности ~ L /2.
Обобщение равных долей удовлетворяет EJR-1, но не EJR-M, но удовлетворяет EJR для случаев, когда доли только делимы, и имеет степень пропорциональности ~ L /2.
Обобщение PAV, использующее аналитическое расширение гармонического ряда, удовлетворяет EJR-1, но не EJR-M, не удовлетворяет EJR для случаев, когда числа только делятся, и имеет степень пропорциональности больше L -1.

Другие адаптации

Булто, Хазон, Пейдж, Розенфельд и Талмон ^[25] адаптировали аксиомы JR к многовопросному голосованию (также называемому: постоянное голосование, публичное принятие решений или последовательное принятие решений). Их работа была позже расширена Чандаком, Сашватом и Питерсом. ^[26]
Азиз, Ли и Талмон ^[27] адаптировали аксиомы JR к партисипаторному бюджетированию .
Брилл, Ласлиер и Скоурон ^[28] адаптировали JR к дегрессивной пропорциональности , присвоив больший вес меньшинствам.
Мавров, Мунагала и Шен ^[29] изучают ядро и аксиомы JR, когда на комитет накладываются ограничения.
Мунагала, Шен, Ван и Ван ^[30] изучают мультипликативную аппроксимацию ядра, когда агенты могут иметь неаддитивные функции удовлетворения.

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

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

Ссылки

^ «Недовольство политикой партии достигает новых высот». The New York Times . 21 сентября 2023 г.
^ Петр Фалишевский, Петр Сковрон, Аркадий Слинько, Нимрод Тальмон (26 октября 2017 г.). «Голосование с несколькими победителями: новый вызов теории социального выбора». В Эндриссе, Улле (ред.). Тенденции в вычислительном социальном выборе . Лулу.com. ISBN 978-1-326-91209-3.{{cite book}}: CS1 maint: multiple names: authors list (link)
^ abcde Азиз, Харис; Брилл, Маркус; Конитцер, Винсент; Элкинд, Эдит; Фримен, Руперт; Уолш, Тоби (2017). «Оправданное представительство при голосовании в комитете на основе одобрения». Social Choice and Welfare . 48 (2): 461– 485. arXiv : 1407.8269 . doi : 10.1007/s00355-016-1019-3. S2CID 8564247.
^ abcdef Санчес-Фернандес, Луис; Элкинд, Эдит; Лакнер, Мартин; Фернандес, Норберто; Фистеус, Иисус; Вэл, Пабло Басанта; Сковрон, Петр (10 февраля 2017 г.). «Пропорциональное обоснованное представительство». Материалы конференции AAAI по искусственному интеллекту . 31 (1). arXiv : 1611.09928 . дои : 10.1609/aaai.v31i1.10611 . ISSN 2374-3468. S2CID 17538641.
^ abcdefgh Азиз, Харис; Элкинд, Эдит; Хуан, Шэньвэй; Лакнер, Мартин; Санчес-Фернандес, Луис; Сковрон, Петр (2018-04-25). «О сложности расширенного и пропорционального обоснованного представления». Труды конференции AAAI по искусственному интеллекту . 32 (1). doi : 10.1609/aaai.v32i1.11478 . ISSN 2374-3468. S2CID 19124729.
^ Азиз, Харис; Богомольная, Анна; Мулен, Эрве (2019-06-17). "Справедливое смешивание: случай дихотомических предпочтений" (PDF) . Труды конференции ACM 2019 года по экономике и вычислениям . EC '19. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 753–781 . doi :10.1145/3328526.3329552. ISBN 978-1-4503-6792-9. S2CID 7436482.
^ Гжегож, Перчинский; Петр, Сковрон; Доминик, Петерс (2021-12-06). «Пропорциональное партисипаторное бюджетирование с аддитивными полезностями». Достижения в области нейронных систем обработки информации . 34. arXiv : 2008.13276 .
^ ab Элкинд, Эдит; Фалишевски, Петр; Игараси, Аюми; Манурангси, Пасин; Шмидт-Крепелин, Ульрике; Суксомпонг, Варут (2024). «Цена обоснованного представления». ACM Transactions on Economics and Computation . 12 (3): 1– 27. arXiv : 2112.05994 . doi : 10.1145/3676953.
^ ab Lackner, Martin; Skowron, Piotr (2023). Голосование за нескольких победителей с предпочтениями одобрения. Springer Nature. hdl :20.500.12657/60149. ISBN 978-3-031-09016-5.
^ ab Brill, Markus; Freeman, Rupert; Janson, Svante; Lackner, Martin (2023-03-06). «Методы голосования Фрагмена и обоснованное представление». Математическое программирование . 203 ( 1– 2): 47– 76. arXiv : 2102.12305 . doi : 10.1007/s10107-023-01926-8 . ISSN 1436-4646. PMC 10858002 . PMID 38344413.
^ Санчес-Фернандес, Луис; Фернандес, Норберто; Фистеус, Хесус А.; Брилл, Маркус (05 сентября 2018 г.). «Метод поддержки максимина: расширение метода Д'Ондта для выборов с несколькими победителями, основанных на одобрении». arXiv : 1609.05370 [cs.GT].
^ ab Бредерек, Роберт; Фалишевский, Петр; Качмарчик, Анджей; Нидермайер, Рольф (2019-08-10). «Экспериментальный взгляд на комитеты, обеспечивающие обоснованное представительство». Труды 28-й Международной совместной конференции по искусственному интеллекту . IJCAI'19. Макао, Китай: AAAI Press: 109–115 . ISBN 978-0-9992411-4-1.
^ Питерс, Доминик; Перчинский, Гжегож; Сковрон, Петр (2021). «Пропорциональное партисипаторное бюджетирование с аддитивными полезностями». Достижения в области нейронных систем обработки информации . 34. Curran Associates, Inc.: 12726– 12737. arXiv : 2008.13276 .
^ ab Brill, Markus; Peters, Jannik (2023). «Надежные и проверяемые аксиомы пропорциональности для голосования с несколькими победителями». arXiv : 2302.01989 [cs.GT].
^ Скоурон, Петр (2021-07-18). «Степень пропорциональности правил Multiwinner». Труды 22-й конференции ACM по экономике и вычислениям . EC '21. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 820–840 . arXiv : 1810.08799 . doi : 10.1145 /3465456.3467641. ISBN 978-1-4503-8554-1. S2CID 53046800.
^ Фримен, Руперт; Канг, Энсон; Пеннок, Дэвид М. (2021-01-07). «Пропорциональность в выборах на основе одобрения с переменным числом победителей». Труды Двадцать девятой Международной совместной конференции по искусственному интеллекту . IJCAI'20. Иокогама, Иокогама, Япония: 132–138 . ISBN 978-0-9992411-6-5.
^ ab Brill, Markus; Gölz, Paul; Peters, Dominik; Schmidt-Kraepelin, Ulrike; Wilker, Kai (2020-04-03). «Распределение на основе одобрения». Труды конференции AAAI по искусственному интеллекту . 34 (2): 1854–1861 . arXiv : 1911.08365 . doi : 10.1609/aaai.v34i02.5553. ISSN 2374-3468. S2CID 208158445.
^ Дамметт, Майкл (1984). Процедуры голосования. Oxford University Press UK.
^ Талмон, Нимрод; Пейдж, Рутвик (2021). «Пропорциональность в выборе комитета с негативными чувствами». arXiv : 2101.01435 [cs.GT].
^ Лакнер, Мартин; Сковрон, Петр (2018-06-11). «Последовательные правила одобрения для нескольких победителей». Труды конференции ACM 2018 года по экономике и вычислениям . EC '18. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 47–48 . arXiv : 1704.02453 . doi :10.1145/3219166.3219170. ISBN 978-1-4503-5829-3.
^ Лакнер, Мартин; Сковрон, Петр (2020-11-01). «Утилитарные гарантии благосостояния и представительства правил с несколькими победителями на основе одобрения». Искусственный интеллект . 288 : 103366. arXiv : 1801.01527 . doi : 10.1016/j.artint.2020.103366. ISSN 0004-3702.
^ Яворский, Михал; Сковрон, Петр (2022). «Правила Фрагмена для дегрессивной и регрессивной пропорциональности». arXiv : 2201.04248 [cs.GT].
^ ab Bei, Xiaohui; Lu, Xinhang; Suksompong, Warut (2022-06-28). «Искренний обмен тортами». Труды конференции AAAI по искусственному интеллекту . 36 (5): 4809– 4817. arXiv : 2112.05632 . doi : 10.1609/aaai.v36i5.20408. ISSN 2374-3468.
^ Лу, Синьхан; Питерс, Янник; Азиз, Харис; Бэй, Сяохуэй; Суксомпонг, Варут (2023-06-26). «Голосование на основе одобрения со смешанными товарами». Труды конференции AAAI по искусственному интеллекту . 37 (5): 5781– 5788. arXiv : 2211.12647 . doi : 10.1609/aaai.v37i5.25717 . ISSN 2374-3468.
^ Булто, Лоран; Хазон, Ноам; Пейдж, Рутвик; Розенфельд, Ариэль; Талмон, Нимрод (2021). «Обоснованное представительство для бессрочного голосования». IEEE Access . 9 : 96598– 96612. Bibcode : 2021IEEEA...996598B. doi : 10.1109/ACCESS.2021.3095087 . ISSN 2169-3536. S2CID 235966019.
^ Чандак, Нихил; Гоэль, Шашват; Питерс, Доминик (2023-06-26). «Пропорциональное агрегирование предпочтений для последовательного принятия решений». arXiv : 2306.14858 [cs.GT].
^ Азиз, Харис; Ли, Бартон Э.; Талмон, Нимрод (2018-07-09). «Пропорционально представительное партисипаторное бюджетирование: аксиомы и алгоритмы». Труды 17-й Международной конференции по автономным агентам и многоагентным системам . AAMAS '18. Ричленд, Южная Каролина: Международный фонд автономных агентов и многоагентных систем: 23–31 . arXiv : 1711.08226 .
^ Brill, Markus; Laslier, Jean-François; Skowron, Piotr (2018-07-01). «Правила одобрения для нескольких победителей как методы распределения». Journal of Theoretical Politics . 30 (3): 358–382 . arXiv : 1611.08691 . doi : 10.1177/0951629818775518. ISSN 0951-6298. S2CID 10535322.
^ Мавров, Иван-Александар; Мунагала, Камеш; Шен, Ихэн (2023). «Честные выборы с несколькими победителями и ограничениями в распределении средств». arXiv : 2305.02868 [cs.GT].
^ Мунагала, Камеш; Шен, Ихэн; Ван, Каннинг; Ван, Чжии (2021). «Приблизительное ядро для выбора комитета с помощью многолинейного расширения и рыночного клиринга». arXiv : 2110.12499 [cs.GT].

[1] «Недовольство политикой партии достигает новых высот». The New York Times . 21 сентября 2023 г.

[2] Петр Фалишевский, Петр Сковрон, Аркадий Слинько, Нимрод Тальмон (26 октября 2017 г.). «Голосование с несколькими победителями: новый вызов теории социального выбора». В Эндриссе, Улле (ред.). Тенденции в вычислительном социальном выборе . Лулу.com. ISBN 978-1-326-91209-3.{{cite book}}: CS1 maint: multiple names: authors list (link)

[:0-3] Азиз, Харис; Брилл, Маркус; Конитцер, Винсент; Элкинд, Эдит; Фримен, Руперт; Уолш, Тоби (2017). «Оправданное представительство при голосовании в комитете на основе одобрения». Social Choice and Welfare . 48 (2): 461– 485. arXiv : 1407.8269 . doi : 10.1007/s00355-016-1019-3. S2CID 8564247.

[:1-4] Санчес-Фернандес, Луис; Элкинд, Эдит; Лакнер, Мартин; Фернандес, Норберто; Фистеус, Иисус; Вэл, Пабло Басанта; Сковрон, Петр (10 февраля 2017 г.). «Пропорциональное обоснованное представительство». Материалы конференции AAAI по искусственному интеллекту . 31 (1). arXiv : 1611.09928 . дои : 10.1609/aaai.v31i1.10611 . ISSN 2374-3468. S2CID 17538641.

[:5-5] Азиз, Харис; Элкинд, Эдит; Хуан, Шэньвэй; Лакнер, Мартин; Санчес-Фернандес, Луис; Сковрон, Петр (2018-04-25). «О сложности расширенного и пропорционального обоснованного представления». Труды конференции AAAI по искусственному интеллекту . 32 (1). doi : 10.1609/aaai.v32i1.11478 . ISSN 2374-3468. S2CID 19124729.

[6] Азиз, Харис; Богомольная, Анна; Мулен, Эрве (2019-06-17). "Справедливое смешивание: случай дихотомических предпочтений" (PDF) . Труды конференции ACM 2019 года по экономике и вычислениям . EC '19. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 753–781 . doi :10.1145/3328526.3329552. ISBN 978-1-4503-6792-9. S2CID 7436482.

[:6-7] Гжегож, Перчинский; Петр, Сковрон; Доминик, Петерс (2021-12-06). «Пропорциональное партисипаторное бюджетирование с аддитивными полезностями». Достижения в области нейронных систем обработки информации . 34. arXiv : 2008.13276 .

[:4-8] Элкинд, Эдит; Фалишевски, Петр; Игараси, Аюми; Манурангси, Пасин; Шмидт-Крепелин, Ульрике; Суксомпонг, Варут (2024). «Цена обоснованного представления». ACM Transactions on Economics and Computation . 12 (3): 1– 27. arXiv : 2112.05994 . doi : 10.1145/3676953.

[:9-9] Lackner, Martin; Skowron, Piotr (2023). Голосование за нескольких победителей с предпочтениями одобрения. Springer Nature. hdl :20.500.12657/60149. ISBN 978-3-031-09016-5.

[:22-10] Brill, Markus; Freeman, Rupert; Janson, Svante; Lackner, Martin (2023-03-06). «Методы голосования Фрагмена и обоснованное представление». Математическое программирование . 203 ( 1– 2): 47– 76. arXiv : 2102.12305 . doi : 10.1007/s10107-023-01926-8 . ISSN 1436-4646. PMC 10858002 . PMID 38344413.

[:7-11] Санчес-Фернандес, Луис; Фернандес, Норберто; Фистеус, Хесус А.; Брилл, Маркус (05 сентября 2018 г.). «Метод поддержки максимина: расширение метода Д'Ондта для выборов с несколькими победителями, основанных на одобрении». arXiv : 1609.05370 [cs.GT].

[:2-12] Бредерек, Роберт; Фалишевский, Петр; Качмарчик, Анджей; Нидермайер, Рольф (2019-08-10). «Экспериментальный взгляд на комитеты, обеспечивающие обоснованное представительство». Труды 28-й Международной совместной конференции по искусственному интеллекту . IJCAI'19. Макао, Китай: AAAI Press: 109–115 . ISBN 978-0-9992411-4-1.

[13] Питерс, Доминик; Перчинский, Гжегож; Сковрон, Петр (2021). «Пропорциональное партисипаторное бюджетирование с аддитивными полезностями». Достижения в области нейронных систем обработки информации . 34. Curran Associates, Inc.: 12726– 12737. arXiv : 2008.13276 .

[:8-14] Brill, Markus; Peters, Jannik (2023). «Надежные и проверяемые аксиомы пропорциональности для голосования с несколькими победителями». arXiv : 2302.01989 [cs.GT].

[15] Скоурон, Петр (2021-07-18). «Степень пропорциональности правил Multiwinner». Труды 22-й конференции ACM по экономике и вычислениям . EC '21. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 820–840 . arXiv : 1810.08799 . doi : 10.1145 /3465456.3467641. ISBN 978-1-4503-8554-1. S2CID 53046800.

[16] Фримен, Руперт; Канг, Энсон; Пеннок, Дэвид М. (2021-01-07). «Пропорциональность в выборах на основе одобрения с переменным числом победителей». Труды Двадцать девятой Международной совместной конференции по искусственному интеллекту . IJCAI'20. Иокогама, Иокогама, Япония: 132–138 . ISBN 978-0-9992411-6-5.

[:3-17] Brill, Markus; Gölz, Paul; Peters, Dominik; Schmidt-Kraepelin, Ulrike; Wilker, Kai (2020-04-03). «Распределение на основе одобрения». Труды конференции AAAI по искусственному интеллекту . 34 (2): 1854–1861 . arXiv : 1911.08365 . doi : 10.1609/aaai.v34i02.5553. ISSN 2374-3468. S2CID 208158445.

[18] Дамметт, Майкл (1984). Процедуры голосования. Oxford University Press UK.

[19] Талмон, Нимрод; Пейдж, Рутвик (2021). «Пропорциональность в выборе комитета с негативными чувствами». arXiv : 2101.01435 [cs.GT].

[20] Лакнер, Мартин; Сковрон, Петр (2018-06-11). «Последовательные правила одобрения для нескольких победителей». Труды конференции ACM 2018 года по экономике и вычислениям . EC '18. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 47–48 . arXiv : 1704.02453 . doi :10.1145/3219166.3219170. ISBN 978-1-4503-5829-3.

[21] Лакнер, Мартин; Сковрон, Петр (2020-11-01). «Утилитарные гарантии благосостояния и представительства правил с несколькими победителями на основе одобрения». Искусственный интеллект . 288 : 103366. arXiv : 1801.01527 . doi : 10.1016/j.artint.2020.103366. ISSN 0004-3702.

[22] Яворский, Михал; Сковрон, Петр (2022). «Правила Фрагмена для дегрессивной и регрессивной пропорциональности». arXiv : 2201.04248 [cs.GT].

[:10-23] Bei, Xiaohui; Lu, Xinhang; Suksompong, Warut (2022-06-28). «Искренний обмен тортами». Труды конференции AAAI по искусственному интеллекту . 36 (5): 4809– 4817. arXiv : 2112.05632 . doi : 10.1609/aaai.v36i5.20408. ISSN 2374-3468.

[24] Лу, Синьхан; Питерс, Янник; Азиз, Харис; Бэй, Сяохуэй; Суксомпонг, Варут (2023-06-26). «Голосование на основе одобрения со смешанными товарами». Труды конференции AAAI по искусственному интеллекту . 37 (5): 5781– 5788. arXiv : 2211.12647 . doi : 10.1609/aaai.v37i5.25717 . ISSN 2374-3468.

[:12-25] Булто, Лоран; Хазон, Ноам; Пейдж, Рутвик; Розенфельд, Ариэль; Талмон, Нимрод (2021). «Обоснованное представительство для бессрочного голосования». IEEE Access . 9 : 96598– 96612. Bibcode : 2021IEEEA...996598B. doi : 10.1109/ACCESS.2021.3095087 . ISSN 2169-3536. S2CID 235966019.

[26] Чандак, Нихил; Гоэль, Шашват; Питерс, Доминик (2023-06-26). «Пропорциональное агрегирование предпочтений для последовательного принятия решений». arXiv : 2306.14858 [cs.GT].

[27] Азиз, Харис; Ли, Бартон Э.; Талмон, Нимрод (2018-07-09). «Пропорционально представительное партисипаторное бюджетирование: аксиомы и алгоритмы». Труды 17-й Международной конференции по автономным агентам и многоагентным системам . AAMAS '18. Ричленд, Южная Каролина: Международный фонд автономных агентов и многоагентных систем: 23–31 . arXiv : 1711.08226 .

[28] Brill, Markus; Laslier, Jean-François; Skowron, Piotr (2018-07-01). «Правила одобрения для нескольких победителей как методы распределения». Journal of Theoretical Politics . 30 (3): 358–382 . arXiv : 1611.08691 . doi : 10.1177/0951629818775518. ISSN 0951-6298. S2CID 10535322.

[29] Мавров, Иван-Александар; Мунагала, Камеш; Шен, Ихэн (2023). «Честные выборы с несколькими победителями и ограничениями в распределении средств». arXiv : 2305.02868 [cs.GT].

[30] Мунагала, Камеш; Шен, Ихэн; Ван, Каннинг; Ван, Чжии (2021). «Приблизительное ядро для выбора комитета с помощью многолинейного расширения и рыночного клиринга». arXiv : 2110.12499 [cs.GT].