Полностью пропорциональное представительство

Полностью пропорциональное представительство (FPR) является свойством систем голосования с несколькими победителями . Оно расширяет свойство пропорционального представительства (PR), требуя, чтобы представительство основывалось на всех предпочтениях избирателей, а не на их первом выборе. Более того, это требование объединяет PR с требованием подотчетности — каждый избиратель точно знает, какой избранный кандидат его представляет, и каждый кандидат точно знает, каких избирателей он представляет.

Термин был придуман в 1995 году Бертом Л. Монро ^[1], но похожая идея появилась уже в 1983 году в статье Джона Р. Чемберлина и Пола Н. Куранта . ^[2] Известно, что два правила голосования, удовлетворяющие этому свойству, известны — соответственно — как правило голосования Монро и правило голосования Чемберлина-Куранта (CC) .

Фон

Большинство существующих избирательных систем пропорционального представительства (PR) основаны только на первых предпочтениях избирателей, например: если 40% голосуют за партию А в качестве своего первого выбора, то 40% членов парламента должны быть представителями партии А. Это игнорирует тот факт, что избиратели могут иметь другие предпочтения ниже своего первого выбора.

Другим недостатком существующих систем PR, например, систем партийных списков , является отсутствие подотчетности : ^[3] нет прямой связи между избирателями и избранными кандидатами, поскольку кандидаты избираются через свою партию. Такие правила, как правило «Единый передаваемый голос» и «Расширяющееся правило одобрения», направлены на смягчение этой проблемы, позволяя людям напрямую ранжировать кандидатов; однако по-прежнему сложно сказать, какой именно кандидат представляет какого избирателя.

Правила FPR направлены на исправление обоих этих недостатков одновременно: они основаны на предпочтениях избирателей по отношению ко всем кандидатам; и они создают четкую связь между избранными кандидатами и избирателями: каждый избиратель знает своих представителей, а каждый представитель знает, каких избирателей он представляет.

Правила

Пусть k — необходимое число представителей (членов комитета), m — число кандидатов, а n — число избирателей. Каждый избиратель представляет рейтинг кандидатов. Как правило Монро, так и правило CC выбирают k представителей и связывают каждого избирателя с уникальным представителем (другими словами, они вычисляют разделение избирателей среди представителей). Главное различие заключается в следующем:

Правило Монро требует, чтобы каждый кандидат был связан ровно с n / k избирателями (округляя в большую или меньшую сторону, если это не целое число).
В правиле CC такого требования нет — каждый кандидат может представлять разное количество избирателей (но это следует учитывать позже, в ходе работы комитета, например, применяя взвешенное голосование ).

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

Подсчет Борда : если избиратель представлен своим лучшим кандидатом, то его удовлетворенность равна m -1; если избиратель представлен своим худшим кандидатом, то его удовлетворенность равна 0.
Бюллетени одобрения : если избиратель представлен кандидатом, которого он одобряет, то его удовлетворенность равна 1; в противном случае его удовлетворенность равна 0.

Альтернативные варианты этих правил используют функцию неудовлетворенности вместо функции удовлетворения. На основе этих функций оценки оба правила имеют несколько вариантов:

Правило утилитаризма направлено на поиск комитета, который максимизирует сумму уровней удовлетворенности всех избирателей (например, в случае с бюллетенями одобрения: максимизируйте число избирателей, представленных кандидатом, которого они одобряют); альтернативный вариант направлен на минимизацию суммы уровней неудовлетворенности всех избирателей.
Эгалитарные правила направлены на поиск комитета, который максимизирует наименьший уровень удовлетворенности избирателя (например, с помощью подсчета Борда: найти оптимальный ранг r, такой, чтобы у всех избирателей был представитель с рангом r или выше); альтернативный вариант направлен на минимизацию наибольшего уровня неудовлетворенностивсех избирателей.

Вычисление

Прокачча, Розеншайн и Зохар ^[4] доказали, что определение победителя правила голосования Монро является NP-трудной задачей, даже с бюллетенями одобрения . Однако, когда число победителей ( k ) постоянно, задача может быть решена за полиномиальное время.

Бецлер, Слинко и Ульманн ^[3] исследуют параметризованную сложность определения победителя вариантов на основе неудовлетворенности: они доказывают фиксированную параметрическую управляемость для параметра «количество кандидатов», но фиксированную параметрическую неуправляемость для «количества победителей». Они изучают одобрение, Борда и неограниченные функции оценки.

Некоторые проблемы решаются проще для областей ограниченных предпочтений:

Для одновершинных предпочтений Бетцлер, Слинко и Ульманн ^[3] доказывают, что классическое правило Монро все еще NP-трудно, но существует поливременной алгоритм для эгалитарного Монро. Оба варианта CC являются полиномиальными.
Для односторонних перекрестных предпочтений Сковрон, Ю, Файльшевски и Элкинд ^[5] доказывают, что правило CC является поливременным, но Монро остается NP-трудным. Для односторонних перекрестных нарциссических предпочтений (каждый кандидат занимает первое место по крайней мере у одного избирателя) существует эффективный алгоритм для эгалитарного правила Монро.

Лу и Бутилье ^[6] представили поливременной жадный алгоритм аппроксимации с 0,63-фактором для оптимального выполнения правила CC.

Сковрон, Фалишевски и Слинко ^[7] предоставляют алгоритмы аппроксимации и результаты неаппроксимации :

Для утилитарного удовлетворения Монро с оценкой Борда, (0,715-эпсилон)-приближение;
Для утилитарного удовлетворения Монро с произвольной позиционной оценкой , 0,63-приближение;
Для утилитарного удовлетворения CC с оценкой Борда, PTAS .
Для утилитаристских и эгалитарных версий моделей Монро и CC, основанных на неудовлетворенности, а также для эгалитарных версий, основанных на удовлетворенности, не существует приближения с постоянным множителем.

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

Обратите внимание, что после избрания k представителей, определение фактического представительства (какого избирателя представляет какой кандидат) может быть выполнено в поливремени с использованием алгоритмов сетевого потока . ^[3]

Обобщения

Лу и Бутилье ^[6] обобщили правило CC для бюджетного общественного выбора .

Ссылки

^ Монро, Берт Л. (1995-12-01). «Полностью пропорциональное представительство». American Political Science Review . 89 (4): 925–940 . doi :10.2307/2082518. ISSN 1537-5943. JSTOR 2082518. S2CID 121059560.
^ Чемберлин, Джон Р.; Курант, Пол Н. (1983-09-01). «Представительские обсуждения и представительские решения: пропорциональное представительство и правило Борда». American Political Science Review . 77 (3): 718– 733. doi :10.2307/1957270. ISSN 0003-0554. JSTOR 1957270. S2CID 147162169.
^ abcd Betzler, N.; Slinko, A.; Uhlmann, J. (2013-07-22). «О вычислении полностью пропорционального представления». Журнал исследований искусственного интеллекта . 47 : 475–519 . arXiv : 1402.0580 . doi : 10.1613/jair.3896 . ISSN 1076-9757.
^ Прокачча, Ариэль Д.; Розеншайн, Джеффри С.; Зохар, Авив (2008-04-01). «О сложности достижения пропорционального представительства». Социальный выбор и благосостояние . 30 (3): 353– 362. doi :10.1007/s00355-007-0235-2. ISSN 1432-217X. S2CID 18126521.
^ Сковрон, Петр; Ю, Лан; Фалишевский, Петр; Элкинд, Эдит (2013). «Сложность полностью пропорционального представительства для электоратов с одним пересечением». В Vöcking, Бертольд (ред.). Алгоритмическая теория игр . Конспект лекций по информатике. Том 8146. Берлин, Гейдельберг: Springer. стр. 1– 12. arXiv : 1307.1252 . doi :10.1007/978-3-642-41392-6_1. ISBN 978-3-642-41392-6.
^ ab Lu, Tyler; Boutilier, Craig (2011-07-16). "Бюджетный социальный выбор: от консенсуса к персонализированному принятию решений". Труды Двадцать второй Международной совместной конференции по искусственному интеллекту - Том Том первый . IJCAI'11. Барселона, Каталония, Испания: AAAI Press: 280–286 . ISBN 978-1-57735-513-7.
^ Сковрон, Петр; Фалишевский, Петр; Слинько, Аркадий (2015-05-01). «Достижение полностью пропорционального представления: результаты аппроксимации». Искусственный интеллект . 222 : 67–103 . arXiv : 1312.4026 . doi : 10.1016/j.artint.2015.01.003 . ISSN 0004-3702. S2CID 467056.

[1] Монро, Берт Л. (1995-12-01). «Полностью пропорциональное представительство». American Political Science Review . 89 (4): 925–940 . doi :10.2307/2082518. ISSN 1537-5943. JSTOR 2082518. S2CID 121059560.

[2] Чемберлин, Джон Р.; Курант, Пол Н. (1983-09-01). «Представительские обсуждения и представительские решения: пропорциональное представительство и правило Борда». American Political Science Review . 77 (3): 718– 733. doi :10.2307/1957270. ISSN 0003-0554. JSTOR 1957270. S2CID 147162169.

[:0-3] Betzler, N.; Slinko, A.; Uhlmann, J. (2013-07-22). «О вычислении полностью пропорционального представления». Журнал исследований искусственного интеллекта . 47 : 475–519 . arXiv : 1402.0580 . doi : 10.1613/jair.3896 . ISSN 1076-9757.

[4] Прокачча, Ариэль Д.; Розеншайн, Джеффри С.; Зохар, Авив (2008-04-01). «О сложности достижения пропорционального представительства». Социальный выбор и благосостояние . 30 (3): 353– 362. doi :10.1007/s00355-007-0235-2. ISSN 1432-217X. S2CID 18126521.

[5] Сковрон, Петр; Ю, Лан; Фалишевский, Петр; Элкинд, Эдит (2013). «Сложность полностью пропорционального представительства для электоратов с одним пересечением». В Vöcking, Бертольд (ред.). Алгоритмическая теория игр . Конспект лекций по информатике. Том 8146. Берлин, Гейдельберг: Springer. стр. 1– 12. arXiv : 1307.1252 . doi :10.1007/978-3-642-41392-6_1. ISBN 978-3-642-41392-6.

[:2-6] Lu, Tyler; Boutilier, Craig (2011-07-16). "Бюджетный социальный выбор: от консенсуса к персонализированному принятию решений". Труды Двадцать второй Международной совместной конференции по искусственному интеллекту - Том Том первый . IJCAI'11. Барселона, Каталония, Испания: AAAI Press: 280–286 . ISBN 978-1-57735-513-7.

[:1-7] Сковрон, Петр; Фалишевский, Петр; Слинько, Аркадий (2015-05-01). «Достижение полностью пропорционального представления: результаты аппроксимации». Искусственный интеллект . 222 : 67–103 . arXiv : 1312.4026 . doi : 10.1016/j.artint.2015.01.003 . ISSN 0004-3702. S2CID 467056.