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

Оправданное представительство (JR) является критерием справедливости при голосовании за одобрение нескольких победителей . Это можно рассматривать как адаптацию критерия пропорционального представительства к одобрительному голосованию.

Фон

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

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

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

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

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

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

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

Пример 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.

Есть несколько способов ослабить понятие сильного JR.

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

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

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

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

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

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

• Каждый комитет со средним уровнем удовлетворенности, превышающим L -1, удовлетворяет требованиям EJR (по принципу «ячейки» ). Следовательно, PAV и Local-Search-PAV удовлетворяют EJR. PAV — единственное правило голосования Тиле , удовлетворяющее требованиям EJR.
• Метод равных долей — еще одно правило, вычислимое за полиномиальное время, удовлетворяющее EJR.
• Другой политаймовый алгоритм, гарантирующий EJR, — это EJR-Exact.
• Простой алгоритм поиска распределения EJR называется «Жадный EJR». Прокручивая L от k вниз до 1, этот алгоритм проверяет, существует ли L-сплоченное подмножество избирателей. Если да, то он выбирает самое большое L-сплоченное подмножество и добавляет несколько L-кандидатов, одобренных всеми из них.
• Последовательный-PAV удовлетворяет EJR только для 1-сплоченных групп и только для k ≤ 5. Для k ≥ 6 он не соответствует EJR даже для 1-сплоченных групп.
• Правило Монро не работает EJR
• является со-NP-полной . Проверка того, удовлетворяет ли данный комитет EJR,

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

• EJR подразумевает PJR, но не наоборот. Например, рассмотрим ситуацию с 2k кандидатами и k избирателями. Избиратель i одобряет кандидата i , а также кандидатов k +1,...,2 k . Обратите внимание, что квота составляет один избиратель, и каждые L избирателей представляют собой L -сплоченную группу. Комитет 1,..., k удовлетворяет PJR, поскольку для каждых L избирателей объединение их наборов одобрений содержит L победителей. Но это не удовлетворяет EJR, поскольку у каждого избирателя есть только один утвержденный победитель. Напротив, комитет k +1,...,2 k удовлетворяет EJR.
• PAV удовлетворяет EJR, поэтому он также удовлетворяет PJR; и это также единственное правило голосования на основе веса, которое удовлетворяет PJR. Однако Sequential-PAV нарушает PJR.
• Некоторые правила голосования Phragmen удовлетворяют PJR, а именно: Leximax Phragmen — который NP-трудно вычислить, и Sequential Phragmen — который вычислим в политайме и, кроме того, удовлетворяет монотонности комитета .
• Когда k делит n , Монро и Жадная Монро удовлетворяют PJR. Однако, когда k не делит n , и Монро, и Жадная Монро могут нарушить PJR, за исключением случая L=1.
• Еще одно правило, которое вычислимо как PJR, так и политаймом, — это правило поддержки максимина .
• является со-NP-полной . Проверка того, удовлетворяет ли данный комитет PJR,

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

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

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

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

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

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

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

• PAV, 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 избирателей. Хотя идеального представительства может не существовать, мы ожидаем, что, если оно существует, то оно будет избрано по правилу голосования.

• PER совместим с PJR и JR: для каждого случая, допускающего идеальное представительство, существует комитет, удовлетворяющий PJR. Однако PER несовместим с EJR: бывают случаи, когда идеальные представления существуют, но ни одно из них не удовлетворяет EJR. PER удовлетворяется правилом Монро и правилом лексимакса-Фрагмена ; но это нарушается Greedy Monroe, Sequential PAV и PAV.

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

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

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

SJR	→	ВОЗДУХ	→	ЭДЖР	→	ПДжР	→	УЮР
				↑		↑	→	младший
CS	→	ФЕДР	→	↑		↑
				↑		↑
		EJR+	→	↑	→	PJR+

EJR+ несравним ни с CS, ни с FJR.

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

Проверка

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

• 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.
• Каждый комитет, средний уровень удовлетворенности которого превышает L -1, удовлетворяет требованиям EJR.

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

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

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

Фриман, Кан и Пеннок адаптировать концепцию среднего удовлетворения к голосованию с несколькими победителями с переменным числом победителей. Они утверждают, что другие аксиомы 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. МЧС нарушает EJR; неизвестно, удовлетворяют ли ему два других.
• Детерминированное правило не может гарантировать r -AS для r = (m-1)/m+epsilon, для любого epsilon>0. PAV, Phragmen и MES не могут гарантировать r -AS для r = 1/2+эпсилон. Но существует рандомизированное правило, удовлетворяющее (29/32)-AS.

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

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

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

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

Адаптации

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

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

Брилл, Гольц, Петерс, Шмидт-Крепелин и Вилкер адаптировали аксиомы Дж.Р. к голосованию за одобрение партии . В таких условиях избирателям необходимо одобрить не отдельных кандидатов, а целые партии. Этот вариант представляет собой нечто среднее между выборами по партийным спискам, при которых избиратели должны выбрать одну партию, и стандартным голосованием за одобрение, при котором избиратели могут выбрать любой набор кандидатов. При голосовании по одобрению партии избиратели могут выбирать любой набор партий, но не могут выбирать отдельных кандидатов внутри партии. Некоторые аксиомы JR адаптированы к этой ситуации следующим образом.

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

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

Следующий пример иллюстрирует разницу между CS и EJR. Предположим, имеется 5 партий {a, b, c, d, e}, k =16 мест и n =16 избирателей со следующими предпочтениями: 4*ab, 3*bc, 1*c, 4*ad, 3* де, 1*е. Рассмотрим комитет с 8 местами для партии А, 4 для партии С и 4 для партии Е. Числа представителей избирателей: 8, 4, 4, 8, 4, 4. Это не CS: рассмотрим группу из 14 избирателей, которые одобряют ab, bc, ad, de. Они могут сформировать комитет с 4 местами для партии А, 5 местами для партии Б и 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 кандидатов должны быть избраны.

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

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

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

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

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

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

С другой стороны, регрессивная пропорциональность означает, что большим группам должно быть предоставлено сверхпропорциональное представительство. Крайним проявлением регрессивной пропорциональности является индивидуальное превосходство , а это означает, что комитет должен состоять из членов, поддерживаемых наибольшим числом избирателей. Правило блочного голосования (AV) максимизирует индивидуальное мастерство.

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

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

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

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

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

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

Лу, Питерс, Азиз, Бэй и Суксомпонг распространите эти определения на настройки со смешанными делимыми и неделимыми кандидатами: существует набор из 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.

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

• Булто, Хазон, Пейдж, Розенфельд и Талмон адаптировал аксиомы JR к голосованию по нескольким вопросам (также называемому вечным голосованием, публичным принятием решений или последовательным принятием решений). Позже их работу расширили Чандак, Сашват и Питерс.
• Азиз, Ли и Талмон адаптировали аксиомы JR к совместному бюджетированию .
• Брилл, Ласьер и Скоурон адаптировал JR к дегрессивной пропорциональности - придавая больший вес меньшинствам.
• Мавров, Мунагала и Шен изучайте ядро ​​и аксиомы JR, когда есть ограничения на комитет.
• Мунагала, Шен, Ван и Ван изучить мультипликативную аппроксимацию ядра, когда агенты могут иметь неаддитивные функции удовлетворения.

См. также

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