Голосование по нескольким вопросам

Не путать с голосованием по вопросу .

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

Первым соображением является достижение справедливости как для большинства, так и для меньшинства. В качестве иллюстрации рассмотрим группу друзей, которые каждый вечер решают, пойти ли им в кино или ресторан. Предположим, что 60% друзей предпочитают кино, а 40% — рестораны. В результате единовременного голосования группа, вероятно, примет предпочтение большинства и пойдет в кино. Однако принимать одно и то же решение снова и снова каждый день несправедливо, поскольку оно удовлетворяет 60% друзей в 100% случаев, а остальные 40% никогда не бывают удовлетворены. Если рассматривать эту задачу как голосование по нескольким вопросам, то можно добиться справедливой последовательности решений, проводя 60% вечеров в кино и 40% вечеров в ресторан. Изучение механизмов справедливого голосования по нескольким вопросам иногда называют справедливым принятием публичных решений. Особый случай, когда разные вопросы принимаются в разные периоды времени, а количество периодов времени заранее неизвестно, называется вечным голосованием.

Второе соображение – это потенциальная зависимость между различными проблемами. Например, предположим, что речь идет о двух предложениях по финансированию государственных проектов. Избиратель может поддержать финансирование каждого проекта в отдельности, но возражать против финансирования обоих проектов одновременно из-за негативного влияния на городской бюджет. Если вопросов всего несколько, можно попросить каждого избирателя оценить все возможные комбинации кандидатов. Однако количество комбинаций увеличивается экспоненциально с увеличением количества проблем, поэтому это непрактично, когда проблем много. Исследование этой ситуации иногда называют комбинаторным голосованием .

Определения

несколько вопросов Предстоит решить проблемы t существует набор C _t кандидатов или . Для каждой альтернатив на выбор. По каждому вопросу t должен быть избран один кандидат от C _t . Избиратели могут иметь разные предпочтения относительно кандидатов. Предпочтения могут быть числовыми ( кардинальные бюллетени ), ранжированными ( порядковые бюллетени ) или двоичными ( одобрительные бюллетени ). В комбинаторных условиях избиратели могут иметь предпочтения по отношению к комбинациям кандидатов.

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

• В автономном режиме предпочтения агентов по всем вопросам заранее известны. Поэтому выбор по всем вопросам может быть сделан одновременно. Эту настройку часто называют принятием публичных решений .
• В онлайн- режиме проблемы представляют собой решения, принятые в разное время; каждая проблема t возникает в момент времени t. Предпочтения избирателей по вопросу t становятся известны только в момент времени t . Эту настройку часто называют вечным голосованием . Правило бессрочного голосования — это правило, которое в каждом туре t принимает в качестве входных данных предпочтения избирателей, а также последовательность победителей в турах 1,..., t -1 и возвращает элемент C _t, который избранный во время t .
  • Некоторые авторы различают полуонлайн- режим, в котором количество раундов известно заранее и неизвестны только предпочтения в каждом раунде, и полностью онлайн-режим , в котором неизвестно даже количество раундов.

Кардинальные предпочтения

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

Оффлайн кардинальные голосования

Конитцер, Фриман и Шах изучили голосование по нескольким вопросам с использованием кардинальных бюллетеней в автономном режиме (они ввели термин публичное принятие решений ). Они сосредоточены на справедливости по отношению к отдельным агентам. Естественным требованием справедливости в этой ситуации является пропорциональное деление , при котором каждый агент должен получить по крайней мере 1/ n своей максимальной полезности. Поскольку пропорциональность может оказаться недостижимой, они предлагают три послабления:

• Пропорциональность до одного вопроса (PROP1) : для каждого избирателя существует такой раунд, что, если решение в этом раунде изменится в пользу лучшего кандидата избирателя в этом раунде, избиратель получит свою справедливую долю.
• Доля по круговой системе (RRS) : каждый избиратель получает по крайней мере столько полезности, сколько он мог бы получить, если бы раунды были разделены по принципу распределения элементов по круговой системе , и он играл бы последним.
• Пессимистическая пропорциональная доля (PPS) .

Эти послабления имеют смысл, когда число избирателей невелико, а количество вопросов велико, поэтому разница в один вопрос невелика по отношению к 1/ n . Они показывают, что решение максимального благосостояния Нэша (максимизирующее произведение полезностей всех агентов) удовлетворяет или приближается ко всем трем релаксациям. Они также предоставляют алгоритмы с полиномиальным временем и результаты по сложности для поиска распределений, удовлетворяющих этим аксиомам, с эффективностью по Парето или без нее .

Кардинальное голосование онлайн

Фриман, Захеди и Конитцер изучить голосование по нескольким вопросам с помощью кардинальных бюллетеней онлайн . Они представляют два жадных алгоритма, целью которых является максимизация долгосрочного благосостояния Нэша (произведение полезностей всех агентов). Они оценивают свои алгоритмы на основе данных, собранных из приложений компьютерных систем.

Настройки одобрения

Офлайн-голосование за одобрение: один кандидат в туре

Простейшая настройка голосования по нескольким вопросам заключается в том, что существует набор вопросов, и каждый агент голосует либо за, либо против каждого вопроса (фактически в каждом раунде есть один кандидат). Аманатидис, Барро, Ланг, Маркакис и Райс представьте несколько правил голосования для этой настройки, основанных на расстоянии Хэмминга :

• Утилитарное правило (которое они называют «минимум») просто следует большинству голосов по каждому вопросу независимо от других. Это правило может быть несправедливым по отношению к меньшинствам, но оно не является стратегическим .
• Эгалитарное правило (которое они называют «минимакс») принимает подмножество вопросов, которое сводит к минимуму максимальное расстояние Хэмминга до бюллетеней избирателей (то есть минимизирует разногласия). Возможно, это правило может дать меньшинствам слишком много власти; кроме того, это не является стратегией.
• Семейство правил, основанное на упорядоченном взвешенном усреднении, может использоваться для интерполяции между утилитарным и эгалитарным правилом. Эта семья позволяет достичь компромисса между справедливостью по отношению к меньшинствам и устойчивостью к стратегии.

Барро, Ланг и Йоку изучите возможность манипулирования этими правилами на основе OWA. Они доказывают, что единственным устойчивым к стратегии правилом OWA с невозрастающими весами является утилитарное правило. Они также эмпирически изучают подсемейство правил, основанных на OWA. Их семейство характеризуется параметром p , который представляет свойство, называемое « орнесс » правила OWA. p = 0,5 дает утилитарный AV, тогда как p = 1 дает эгалитарный AV. Они эмпирически показывают, что увеличение p приводит к увеличению доли случайных профилей, которыми может манипулировать хотя бы один избиратель.

Фриман, Кан и Пеннок изучите голосование за одобрение нескольких победителей с переменным числом победителей. Фактически, они рассматривают каждого кандидата как бинарный вопрос (да/нет), поэтому их настройку можно рассматривать как голосование по нескольким вопросам с одним кандидатом в туре. Они адаптируют концепции обоснованного представления к этим условиям следующим образом:

• Каждый избиратель получает удовлетворение не только от избранного кандидата, которого он одобряет, но и от неизбранного кандидата, которого он не одобряет (это делает проблему похожей на голосование по нескольким вопросам, где каждый кандидат представляет собой бинарный вопрос).
• Группа называется 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.

Сковрон и Горецкий изучите аналогичную ситуацию: голосование по нескольким вопросам с автономным голосованием за одобрение, где в каждом туре t есть один кандидат (единственное решение «да/нет»). Их главная аксиома справедливости — пропорциональность : каждая группа размера k должна иметь возможность влиять хотя бы на долю k / n решений. Это контрастирует с аксиомами обоснованного представления, которые рассматривают только сплоченные группы. Это различие важно, поскольку эмпирические исследования показывают, что сплоченные группы встречаются редко. Формально они определяют два понятия справедливости для голосования без воздержавшихся :

• Пропорциональность : в каждой группе размером k полезность хотя бы одного избирателя должна быть больше, чем ( m /2)*( k / n )-1. Мультипликативный коэффициент 1/2 имеет важное значение; В качестве простого примера предположим, что n/2 избирателей всегда голосуют «за», а остальные n/2 избирателей всегда голосуют «нет». Тогда любое справедливое правило должно решить «да» ровно m /2 раз, так что полезность каждого избирателя будет равна m /2. Следовательно, для группы всех избирателей ( k = n ) мы не можем гарантировать более высокую полезность, чем ( m /2)*( k / n ).
• Пропорциональное среднее представительство : функция d ( * ), такая, что в каждой группе избирателей размером k среднее удовлетворение составляет не менее d ( k / n ).

Для голосования с воздержавшимися определения необходимо адаптировать (поскольку, если все избиратели воздержатся по всем вопросам, их полезность обязательно будет равна 0): вместо m коэффициент меняется на количество вопросов, по которым не воздерживаются все члены группы.

Они изучают два правила:

• Пропорциональное голосование за одобрение (PAV) – без воздержавшихся гарантирует максимально возможное среднее представительство, которое составляет d(r)=(m/2)*r-1; это означает, что оно пропорционально. Более того, для сплоченных групп оно имеет среднее представление d(L) > 3L/4-1. Пропорционально оно также при голосовании с воздержавшимися.
• и метод равных долей (МОН) – без воздержавшихся, он пропорционален и имеет среднее представительство d(r)>((m+1)/3)*r-1. При воздержавшихся наивное внедрение MES не является пропорциональным; но есть вариант - пропорциональный (метод согласованных аукционов с равными долями).

Автономное голосование за одобрение: несколько кандидатов за раунд

Брилл, Маркакис, Папасотиропулос и Янник Петерс расширил результаты Сковрона и Горецкого на проблемы с несколькими кандидатами в раунде и возможные зависимости между проблемами; см. ниже подраздел « Справедливость при комбинаторном голосовании» .

Пейдж, Шапиро и Талмон изучил частный случай, в котором «проблемами» являются кабинеты министров. На каждую должность существует набор кандидатов; все множества попарно не пересекаются. Каждый избиратель должен голосовать за одного кандидата на каждую должность. Цель состоит в том, чтобы избрать по одному министру на каждую должность. В отличие от публичного принятия решений, здесь число избирателей велико, а количество вопросов мало. Они представляют два обобщения свойства обоснованного представления :

• Более слабое обобщение — это Глобальное пропорциональное обоснованное представительство (G-PJR) : для каждой группы S агентов размера Ln / k , множества одобрений которых во всех должностях имеют непустое пересечение, существует не менее L должностей, в которых избранный кандидат одобрено хотя бы одним S. членом Распределение G-PJR существует всегда (с использованием связно-жадного алгоритма суперполиномиального времени), и оно регулируется с фиксированными параметрами в зависимости от количества избирателей.
• Более сильное обобщение — это частичное пропорциональное обоснованное представительство (P-PJR) : для каждой группы S агентов размера Ln / x , наборы одобрений которых в некоторых x из k офисов имеют непустое пересечение, существует как минимум L офисов, в которых избранный кандидат одобрен хотя бы одним S. членом Распределение P-PJR существует всегда (с использованием суперполиномиального по времени связно-жадного алгоритма).

Они обобщают ситуацию, считая, что разные вопросы (должности) имеют разный вес (важность, власть). Они рассматривают как объективную степенную функцию , так и субъективные степенные функции . Для функции объективной власти они определяют обобщение обоснованного представления, которое они называют наиболее важным распределением власти . Затем они представляют жадную версию PAV и с помощью моделирования показывают, что во многих случаях она гарантирует меньшинствам оправданное представительство.

Онлайн-голосование за одобрение: несколько кандидатов в туре

При онлайн-голосовании принято предполагать, что в каждом туре t имеется несколько кандидатов; набор кандидатов обозначается C _t . Каждый избиратель j одобряет подмножество A _t,j из C _t .

Мартин Лакнер изучал вечное голосование с помощью онлайн -бюллетеней для одобрения. Он определил следующие понятия:

• Удовлетворенность . избирателя – это количество туров, в которых избирается один из одобренных им кандидатов
• Поддержка избирателя в каком-то туре — это доля избирателей, поддержавших одного из одобренных им кандидатов.
• Квота . избирателя – это сумма его голосов за весь предыдущий тур

Основываясь на этих концепциях, он определил три аксиомы справедливости:

1. Простая пропорциональность – в любом простом случае, когда каждый агент каждый раз голосует за одного и того же кандидата, удовлетворение каждого агента должно быть не менее его квоты (это означает, что каждая группа избирателей, поддерживающих одного и того же кандидата, должна иметь свои кандидат избирается число раз, пропорциональное размеру группы).
2. Независимость единогласных решений: если есть вопрос, по которому согласны все избиратели, то решение по этому вопросу не должно влиять на будущие решения (эта аксиома предотвращает явные манипуляции путем внесения в повестку дня непротиворечивых вопросов).
3. Ограниченные периоды засухи: каждый избиратель должен быть удовлетворен хотя бы одним решением в заданный (ограниченный) период времени. Граница может зависеть от числа избирателей.

Он также определяет два количественных свойства:

1. Постоянное соблюдение нижней/верхней квоты – вероятность того, что избиратель будет удовлетворен пропорциональной долей решений;
2. Джини Коэффициент влияния – неравенство в степени влияния разных избирателей.

Он определил класс правил постоянного голосования, названный взвешенным голосованием за одобрение . Каждому избирателю присваивается вес, который обычно инициализируется значением 1. В каждом туре избирается кандидат с наибольшей суммой одобряющих весов (разрыв связей в фиксированном, заранее определенном порядке). Вес избирателей, поддержавших победившего кандидата, уменьшается, а вес остальных избирателей увеличивается. Несколько распространенных схем взвешивания:

• Вечный PAV — как и при последовательном пропорциональном голосовании за одобрение : вес избирателя с текущим удовлетворением k равен 1/( k +1). Он удовлетворяет простой пропорциональности, но не ограничивает засушливые периоды и не соблюдает какие-либо квоты.
• Постоянная стоимость единицы — вес удовлетворенного избирателя остается прежним, в то время как вес неудовлетворенного избирателя увеличивается на 1. Таким образом, вес избирателя с текущим удовлетворением k во времени t равен t - k .
• Вечный сброс — вес удовлетворенного избирателя падает до 1, а вес неудовлетворенного увеличивается на 1.
• Вечное равенство – вес избирателя, удовлетворенного k, равен n. ^-к . Таким образом, голос избирателя с удовлетворением k больше, чем все голоса избирателей с удовлетворением, превышающим k .
• Вечный консенсус – вес неудовлетворенного избирателя увеличивается на 1. Вес всех избирателей увеличивается на 1; затем общий вес довольных избирателей уменьшается n (вес каждого удовлетворенного избирателя уменьшается на n / s , где s — количество довольных избирателей). Это правило дает наилучшие результаты в аксиоматическом анализе: это единственное правило, которое удовлетворяет всем трем аксиомам (простая пропорциональность, независимость единогласных решений и ограниченные периоды засухи: ни один агент не имеет периода засухи длиной ( n ² +3 н )/4. связано с методом распределения Фреге Это правило .
• Вечные фрагмены. В каждом туре бюджет каждого избирателя постоянно увеличивается до тех пор, пока какая-то группа избирателей не сможет «купить» кандидата. Он удовлетворяет простой пропорциональности и ограниченным периодам засухи: ни у одного агента нет периода засухи длиной 2 n -1. Это правило связано с правилами голосования Phragmen . Его можно вычислить за полиномиальное время.
• Бессрочная квота – вес избирателя – это разница между удовлетворенностью этого избирателя и его квотой. Это правило удовлетворяет простой пропорциональности и независимости единогласных решений, а не ограниченному периоду засухи. Тем не менее, он показал лучшие результаты в экспериментальной оценке по двум показателям: постоянному соблюдению более низких квот и коэффициенту влияния Джини.
• Perpetual Nash — максимизирует произведение оценок удовлетворенности избирателей.

Мали и Лакнер обсудите общие классы простых правил бессрочного голосования для онлайн-голосования и проанализируйте аксиомы, которым могут удовлетворять правила каждого класса. В частности, они обсуждают Perpetual Phragmen , Perpetual Quota и Perpetual Consensus.

Булто, Хазон, Пейдж, Розенфельд и Талмон сосредоточить внимание на понятиях справедливости по отношению к группам избирателей, а не к отдельным избирателям. Они адаптируют некоторые свойства обоснованного представления к этой настройке. В частности, они определяют два варианта пропорционального обоснованного представительства (PJR). В обоих вариантах мы говорим, что группа агентов согласилась в раунде t есть хотя бы один кандидат , если в C _t , которого они все одобряют.

• Более слабый вариант — all- periods-intersection-PJR . Он требует, чтобы для каждой группы S агентов размера Ln / T договаривающихся во всех T раундах, существовало как минимум L раундов, в которых избранный кандидат одобрялся хотя бы одним членом S. ,
• Более сильный вариант — some- periods-intersection-PJR . Для этого требуется, чтобы для каждой группы S агентов размера Ln / k договаривающихся в некоторых k из T раундов, существовало как минимум L раундов, в которых избранный кандидат одобрялся хотя бы одним членом S. , Этот вариант более сильный, так как не требует согласия группы во всех T раундах. Однако если они согласятся на меньшее количество раундов, то их «право» будет пропорционально меньше.

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

Чандак, Гоэл и Питерс усилить обе аксиомы от PJR до EJR (разница в том, что в EJR должно быть не менее L раундов, в которых избранный кандидат одобряется одним и тем же членом S ). Они называют свои новые аксиомы «EJR» и «strong-EJR». Они также адаптируют к этой ситуации три правила голосования:

• Правило Sequential Phragmen полностью онлайн — оно принимает решения раунд за раундом, и ему не нужно знать общее количество решений. Это работает следующим образом. Для каждого избирателя i переменную x _i , которую мы называем нагрузкой i мы сохраняем . Первоначально все нагрузки установлены равными 0. В каждом туре t для каждого кандидата c в C _t мы проверяем, как разделить общую нагрузку 1 между избирателями, одобрившими c в этом туре, так, чтобы максимальная общая нагрузка, назначенная один избиратель будет как можно меньше (образно, каждого избирателя можно представить как бутылку, наполненную x _i литрами воды; нам нужно налить по 1 литру воды в бутылки, поддерживающие c , так, чтобы максимальная высота воды будет как можно ниже). В каждом раунде t мы выбираем кандидата, у которого максимальная суммарная нагрузка как можно меньше. Правило может быть вычислено за полиномиальное время. Правило может быть вычислено за полиномиальное время. Он удовлетворяет сильному PJR (PJR-пересечение некоторых периодов), но не соответствует даже слабому EJR (EJR-пересечение всех периодов).
• Метод равных долей является полуонлайновым – для него необходимо знать общее количество раундов, но он все равно работает раунд за раундом. Для каждого избирателя i переменную b _i , которую мы называем бюджетом i мы сохраняем . Первоначально для всех бюджетов установлено значение 1. В каждом раунде t для каждого кандидата c в C _t мы проверяем, как разделить общую стоимость n / T между избирателями, которые одобряют c в этом раунде. Мы выбираем кандидата, за которого максимальная цена, которую необходимо заплатить, как можно меньше. Если в каком-то раунде t ни один кандидат не доступен избирателям, которые его одобряют, то мы выбираем кандидата, который минимизирует сумму, которую должны заплатить избиратели, которые его не одобряют, и обнуляют бюджет избирателей, которые его одобряют. Правило может быть вычислено за полиномиальное время. Он удовлетворяет слабому EJR, но не соответствует сильному PJR (и сильному EJR).
• Пропорциональное голосование одобрения проводится в автономном режиме. Он выбирает последовательность решений, которая максимизирует показатель PAV, который представляет собой сумму по всем избирателям i гармонического числа числа избранных кандидатов, одобренных i . Это удовлетворяет сильному EJR. Найти оптимальную последовательность NP-трудно; однако, используя локальный поиск , можно найти локально оптимальную последовательность, которая также удовлетворяет строгому EJR.
• Остается открытым вопрос, существует ли полностью онлайн-правило, удовлетворяющее EJR (это подразумевало бы существование правила EJR, удовлетворяющего монотонности Хауса , что является еще одной открытой проблемой).
• Более сильные варианты этих свойств, при которых группы избирателей могут иметь немного меньший размер или соглашаться на меньшее количество туров, могут оказаться невозможными для удовлетворения.
• Они эмпирически сравнили различные правила для определения их средней полезности ( утилитарной ценности ), 25%-й процентильной полезности (вдохновленной эгалитарной ценностью ) и коэффициента Джини . Для средней полезности утилитарное голосование за одобрение лучше всего ; Порядок пропорциональных правил был следующим: PAV > Seq.Phragmen > MES > Perpetual Quota > Perpetual Consensus, но различия невелики. Что касается эгалитарного значения и коэффициента Джини, утилитарное голосование за одобрение является худшим; между пропорциональными правилами нет последовательной разницы. Наборы данных были (а) случайными, (б) взяты из данных голосования в США, (в) взяты из моделей машинного обучения, обученных на наборе данных Moral Machine .

Постоянное голосование за нескольких победителей

Бредерек, Флюшник и Качмарчик изучите вечное голосование с несколькими победителями : в каждом туре каждый избиратель голосует за одного кандидата. Цель состоит в том, чтобы избрать комитет заданного размера. Кроме того, разница между новым комитетом и предыдущим комитетом должна быть ограничена: в консервативной модели разница ограничена сверху (два последовательных комитета должны иметь небольшую симметричную разницу ), а в революционной модели разница ограничена снизу. (два последовательных комитета должны иметь значительную симметричную разницу). Обе модели являются NP-трудными даже для постоянного числа агентов.

Комбинаторные предпочтения

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

Выявление неразделимых предпочтений

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

1. Если вопросов всего несколько, можно попросить каждого избирателя оценить все возможные комбинации кандидатов. Однако количество комбинаций увеличивается экспоненциально с увеличением количества проблем, поэтому это непрактично, когда проблем много. Есть некоторые исследования языков для краткого представления предпочтений.
2. В каждом номере отдельно можно задать вопрос о понравившейся альтернативе каждому избирателю. Этот вариант проще, но может привести к парадоксам множественных выборов, когда коллективное решение будет наихудшим для всех агентов. Например, предположим, что имеется три задачи, и для каждой задачи есть два кандидата — 1 и 0. Предположим, лучший выбор Алисы — (1, 1, 0), лучший выбор Боба — (1, 0, 1), а лучший выбор Ханы — выбор — (0, 1, 1), а последний выбор всех агентов — (1, 1, 1). Большинство голосов по каждому вопросу в отдельности привело бы к результату (1,1,1), худшему для всех избирателей.
3. При голосовании последовательном вопросы решаются по порядку, так что каждый агент может голосовать по вопросу, основываясь на результатах ранее решенных вопросов. Этот метод полезен, когда существует естественный порядок зависимости от проблем. Однако, если некоторые вопросы будут зависеть от решений в будущих выпусках, избирателям будет трудно решить, за что голосовать.
4. При голосовании итеративном мы просим каждого избирателя указать любимый вариант в каждом выпуске отдельно, но позволяем им пересматривать свой голос на основе голосов других людей. Избирателям разрешено обновлять только один выпуск одновременно. Проблема в том, что итеративная динамика может не сходиться. Однако в некоторых особых случаях равновесие Нэша существует. Итеративное голосование может улучшить социальное благосостояние и предотвратить некоторые парадоксы множественных выборов; это было показано как компьютерным моделированием и лабораторными экспериментами.

Обзор голосования в комбинаторных областях проведен Лангом и Ся, 2016.

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

Брилл, Маркакис, Папасотиропулос и Янник Петерс изучить автономное голосование по нескольким вопросам с небинарным доменом и возможные зависимости между вопросами, где основной целью является справедливое представительство. Они определяют обобщения PAV и MES, которые обрабатывают условные избирательные бюллетени; они называют их условным PAV и условным MES . Они доказывают это:

• При различных предположениях условный-PAV и условный-MES удовлетворяют альфа-пропорциональности, для некоторой альфа, которая зависит от максимальной степени графов зависимостей и максимального количества кандидатов на одну задачу.
• Вычисление победителя условного MES является NP-сложной задачей, даже если все избиратели имеют общий граф зависимостей; и когда избиратели могут иметь разные графы зависимостей, даже если степень входа каждого графа зависимостей постоянна. Но как с общим графом зависимостей , так и с ограниченной степенью результат можно вычислить за полиномиальное время. То же самое справедливо, если каждый связный компонент графа глобальных зависимостей имеет не более постоянного числа вершин.

Обобщения

Совместное бюджетирование

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

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

При справедливом распределении неделимых общественных благ (FAIPG) общество должно выбрать набор неделимых общественных благ, при этом существуют ограничения осуществимости того, какие подмножества элементов могут быть выбраны. Фейн, Мунагала и Шах сосредоточьтесь на трех типах ограничений:

• Ограничения матроида : над элементами существует фиксированный матроид M должны составлять основу M. , и выбранные элементы Эта проблема справедливого принятия общественных решений - это особый случай, в котором каждая проблема является категорией (содержащей всех кандидатов для этой проблемы), и существует ограничение матроида раздела, так что для каждой проблемы должен быть выбран один кандидат.
• Ограничения сопоставления : существует фиксированный граф G =( V , E ), где элементы являются ребрами, а выбранные элементы должны образовывать сопоставление G. в
• Ограничения упаковки : существует фиксированная матрица A и фиксированный вектор b , а индикаторный вектор элементов x должен удовлетворять неравенству A x ≤ b . Проблема совместного составления бюджета представляет собой особый случай, когда матрица A имеет одну строку, содержащую затраты на статьи, а b — бюджет. Ограничения упаковки позволяют использовать более общие настройки бюджета, в которых существуют разные виды ресурсов, каждый из которых имеет свой бюджет.

Фейн, Мунагала и Шах представить понятие справедливости для FAIPG, основанное на ядре . Они предоставляют алгоритмы с полиномиальным временем, находящие аддитивную аппроксимацию ядра с небольшими мультипликативными потерями. При матроидных ограничениях аддитивная аппроксимация равна 2. При согласованных ограничениях существует постоянная аддитивная граница. При ограничениях упаковки и при мягких ограничениях аддитивная аппроксимация является логарифмической по ширине многогранника. Алгоритмы основаны на выпуклой программе максимизации социального благосостояния Нэша.

Гарг, Кулкарни и Мурхекар изучить ФАИПГ в условиях бюджетных ограничений. Они показывают полиномиальное сокращение времени для решений максимального благосостояния Нэша и лексимина между моделями частных благ, общественных благ и принятия общественных решений. Они доказывают, что распределение благосостояния Макса Нэша является Prop1, RRS и Парето-эффективным . Однако найти такие распределения, а также распределения лексиминов NP-трудно даже при постоянном количестве агентов или при двоичных оценках. Они разрабатывают алгоритмы псевдополиномиального времени для вычисления точного MNW или оптимального по лексимину распределения для постоянного количества агентов и для постоянного количества товаров с аддитивными оценками. Они также представляют приближение с коэффициентом O(n) для максимального благосостояния Нэша, которое также удовлетворяет RRS, Prop1 и 1/2-Prop.

Банерджи, Гкацелис, Хоссейн, Джин, Мика и Шах Изучите FAIPG с помощью прогнозов: в каждом раунде поступает общественное благо, каждый агент раскрывает свою ценность для блага, и алгоритм должен решить, сколько инвестировать в благо (с учетом общего бюджетного ограничения). Существуют приблизительные прогнозы общей стоимости всех товаров каждого агента. Цель состоит в том, чтобы добиться пропорциональной справедливости для групп. При использовании двоичных оценок и единичного бюджета пропорциональная справедливость может быть достигнута без прогнозов. При общих оценках и бюджете прогнозы необходимы для достижения пропорциональной справедливости.

Стратегические манипуляции

Правила голосования по нескольким вопросам подвержены стратегическим манипуляциям. Особенно простой формой манипуляции является проблема безбилетника : некоторые избиратели могут неправдиво выступать против общественного мнения по одному вопросу, чтобы получить больше внимания по другим вопросам. Лакнер, Мали и Нарди детально изучить эту проблему. Они показывают, что:

• Почти каждое правило, основанное на упорядоченном взвешенном усреднении или правилах Тиле , либо с использованием глобальной оптимизации, либо с использованием последовательных жадных выборов, склонно к халявному использованию. Единственным исключением является утилитарное правило , которое несправедливо по отношению к меньшинствам.
• Для правила OWA или Тиле, основанного на глобальной оптимизации (за исключением утилитарного правила), вычислить результат NP-трудно; более того, даже когда победитель вопроса известен, NP-трудно определить, возможен ли «безбилетник» (т. е. может ли один агент лишить победителя своего одобрения, не меняя победителя). Однако бесплатное катание никогда не может быть вредным.
• Для последовательных правил OWA и Тиле вычисление победителя в каждом выпуске может быть выполнено за полиномиальное время, и, следовательно, легко узнать, возможен ли «безбилетник». Однако безбилетник в одном вопросе может снизить полезность безбилетника в следующих вопросах; произойдет это или нет, NP-трудно сказать, и требуется полная информация по всем вопросам. Без полной информации невозможно точно знать, полезно или вредно бесплатное катание.
• В симуляционных экспериментах рассматриваются варианты правил OWA и Тиле, параметризованные коэффициентом x ; x =0 — утилитарное правило, а больший x означает, что правило более справедливое. По мере увеличения x доля избирателей, которые могут извлечь выгоду из «безбилетника», увеличивается с 0 примерно до 50%; но увеличивается и доля избирателей, которые могут проиграть от безбилетника, с 0 до более чем 10%.

См. также

• Голосование за нескольких победителей
• Хранимые голоса – еще один способ, с помощью которого меньшинства могут получить справедливую долю власти – стратегически сохраняя голоса и тратя их позже.
• Динамическое голосование - голосование по одному вопросу, при котором предпочтения избирателей меняются с течением времени.
• Дискурсивная дилемма — противоречие между решениями большинства по каждому вопросу в отдельности и решениями большинства по конечному результату.

Внешние ссылки

• Код Python для некоторых правил и экспериментов вечного голосования