Правила голосования Фрагмена

Совместная серия «Политика и экономика»
Социальный выбор и избирательные системы
Социальный выбор Конструкция механизма Сравнительная политология Сравнение Список  ( по странам )
Методы с одним победителем Методы голосования по принципу «единого голоса» и « плюрализма» Первое предпочтение относительного большинства (FPP) Двухтуровый ( США : праймериз в джунглях ) Партийные праймериз Мгновенный сток Великобритания : Альтернативное голосование (AV) США : рейтинговый выбор (RCV) Методы Кондорсе Кондорсе-ИРВ Круговое голосование Минимакс Шульце Ранжированные пары Максимальная лотерея Позиционное голосование Множественность ( эл. IRV ) граф Борда ( эл. Болдуин ) Антиплюральность ( эл. Кумбс ) Кардинальское голосование Оценка голосования Одобрительное голосование Решение большинства ЗВЕЗДНОЕ голосование
Пропорциональное представительство партийный список Распределение Самые высокие средние показатели Наибольшие остатки Национальный остаток Бипропорциональный Тип списка Закрытый список Открытый список Паначаж PR без списков Локализованный список Методы квотирования остатка Заяц СТВ Шульце СТВ CPO-STV Квота Борда Комитеты, работающие на основе одобрения Метод Тиле Метод Фрагмена Расширение правила одобрения Метод равных долей Частичный социальный выбор Прямое представительство Интерактивное представление Текучая демократия Фракционное голосование по одобрению Максимальная лотерея Случайное голосование Полупропорциональное представительство Накопительный СНТВ Ограниченное голосование
Смешанные системы По результатам совмещения смешанное большинство Смешанная пропорциональная избирательная система По механизму сочетания Некомпенсаторный​ Параллельно (суперпозиция) Сосуществование Условный Fusion (бонус большинства) Компенсаторный Система крепления сиденья Великобритания : «АМС» Новая Зеландия : «ММП» Система привязки голосов Отрицательный перенос голоса Смешанное голосование Суперсмешанные системы Двухчленная пропорциональная Пропорционально село-город Джекпот большинства По типу бюллетеня Единый голос Double simultaneous vote Dual-vote
Paradoxes and pathologies Spoiler effects Spoiler effect Cloning paradox Frustrated majorities paradox Center squeeze Pathological response Perverse response Best-is-worst paradox No-show paradox Multiple districts paradox Strategic voting Lesser evil voting Exaggeration Truncation Turkey-raising Paradoxes of majority rule Tyranny of the majority Discursive dilemma Conflicting majorities paradox
Social and collective choice Impossibility theorems Arrow's theorem Majority impossibility Moulin's impossibility theorem McKelvey–Schofield chaos theorem Gibbard's theorem Positive results Median voter theorem Condorcet's jury theorem May's theorem Condorcet dominance theorems Harsanyi's utilitarian theorem VCG mechanism Quadratic voting
Politics portal Economics portal Mathematics portal
v t e

Правила голосования Фрагмена — это правила для голосования с несколькими победителями . Они позволяют избирателям голосовать за отдельных кандидатов, а не за партии, но при этом гарантируют пропорциональное представительство . Они были опубликованы Ларсом Эдвардом Фрагменом на французском и шведском языках между 1893 и 1899 годами ^[1] и переведены на английский язык Сванте Янсоном в 2016 году. ^[2]

При голосовании с одобрением нескольких победителей каждый избиратель может проголосовать за одного или нескольких кандидатов, и цель состоит в том, чтобы выбрать фиксированное число победителей k (где k может быть, например, числом членов парламента). Вопрос в том, как определить множество победителей?

• Самый простой метод — множественное непередаваемое голосование , в котором избираются k кандидатов с наибольшим числом одобрений. Но этот метод имеет тенденцию выбирать k кандидатов из самой большой партии, оставляя меньшие партии вообще без представительства.
• В 19 веке было много дискуссий относительно избирательных систем, которые могли бы гарантировать пропорциональное представительство . Одним из решений, предложенных, например, Д'Ондтом в 1878 году, было голосование за партийные списки, а не за отдельных кандидатов. Это решение все еще очень распространено сегодня.

Фрагмен хотел сохранить голосование за отдельных кандидатов, чтобы избиратели могли одобрять кандидатов на основе их личных заслуг. В особом случае, когда каждый избиратель одобряет всех и только кандидатов одной партии, методы Фрагмена дают те же результаты, что и метод Д'Ондта. ^{[2] : Раздел 11} Однако метод Фрагмена может обрабатывать более общие ситуации, в которых избиратели могут голосовать за кандидатов из разных партий (фактически, метод игнорирует информацию о том, какой кандидат принадлежит к какой партии).

Метод Фрагмена для неупорядоченных (одобрительных) бюллетеней может быть представлен несколькими эквивалентными способами. ^{[2] : Раздел 3}

Каждый избранный кандидат создает "нагрузку" в 1 единицу. Нагрузку кандидата должны нести избиратели, которые его поддерживают. Цель состоит в том, чтобы найти комитет, для которого нагрузка может быть разделена между избирателями наиболее "сбалансированным" образом.

В зависимости от точного определения «сбалансированного» возможны несколько правил: ^[3]

• Leximax-Phragmen: минимизация максимальной нагрузки и, в зависимости от этого, второй по максимуму нагрузки и т. д. (используя лексикографическую оптимизацию по максимуму-мину ).
• Leximin-Phragmen : максимизация минимальной нагрузки и, в зависимости от этого, вторая минимальная нагрузка и т. д.
• Метод Вар-Фрагмена или Эберта : минимизация дисперсии нагрузки.

Каждый из этих вариантов имеет два подварианта:

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

Оригинальный метод Фрагмена — это последовательный метод, минимизирующий максимальную нагрузку, который в настоящее время известен как Seq-Phragmen . ^[3]

На практике правила, которые имеют наилучшие аксиоматические гарантии в категории глобальной оптимизации, это leximax-Phragmen и var-Phragmen. Среди последовательных вариантов наилучшие гарантии дает Seq-Phragmen.

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

Seq-Phragmen можно альтернативно описать как следующий непрерывный процесс:

• Каждый избиратель начинает с 0 виртуальных денег и получает деньги по постоянной ставке 1 в день.
• В каждый момент времени t мы определяем еще не избранного кандидата x как доступного, если общая сумма денег, имеющихся у избирателей, одобривших x, составляет не менее 1.
• В первый раз, когда какой-то кандидат доступен, мы выбираем одного доступного кандидата y произвольно. Мы добавляем y в комитет и обнуляем виртуальные деньги избирателей, которые одобряют y (поскольку они теперь «использовали» свои виртуальные деньги для финансирования y ).
• Избиратели продолжают зарабатывать виртуальные деньги и финансировать кандидатов до тех пор, пока не будут избраны все k членов комитета.

Следующий простой пример напоминает голосование по партийному списку. Есть k=6 мест и 9 кандидатов, обозначенных a, b, c, d, e, f, g, h, i. Есть 63 избирателя со следующими предпочтениями: 31 избиратель одобряет a, b, c; 21 избиратель одобряет d, e, f; и 11 избирателей одобряют g, h, i.

• Избиратели начинают зарабатывать деньги по фиксированной ставке 1 в день. Через 1/31 дня (~0,0323 дня) у 31 избирателя abc есть по 0,0323 каждый, поэтому вместе они могут финансировать одного из одобренных ими кандидатов. Один из a, b, c выбирается произвольно; предположим, это a.
• Через 1/21 дня (~0,0476 дня) у 31 избирателя abc есть только ~0,015 у каждого, но у 21 избирателя def есть 0,0476 у каждого, поэтому вместе они могут финансировать одного из одобренных ими кандидатов. Один из d,e,f выбирается произвольно; предположим, это d.
• Через ~0,0646 дня у избирателей abc снова будет по 0,0323, поэтому они покупают еще одного из одобренных ими кандидатов, скажем, b.
• Через 1/11 дня (~0,091 дня) у избирателей ghi будет по 0,091, поэтому вместе они могут профинансировать одного из одобренных ими кандидатов, скажем, g (в этот момент у избирателей abc будет только по 0,0264, а у избирателей def — по 0,0434, поэтому никто из них не сможет профинансировать другого кандидата).
• Через 0,0952 дня у избирателей, проголосовавших за отказ от голосования , снова будет по 0,0476, поэтому они могут купить другого кандидата, скажем, e.
• Через 0,0969 дня у избирателей abc снова будет по 0,0323, поэтому они могут купить другого кандидата, скажем, c.

Окончательный состав комитета: a, b, c; d, e; g. Обратите внимание, что каждая «партия» представлена ​​примерно пропорционально ее размеру: 3 кандидата на 31 избирателя, 2 кандидата на 21 избирателя и 1 кандидат на 11 избирателей.

Вот более сложный пример. Есть k = 3 места и 6 кандидатов, обозначенных как A, B, C, P, Q, R. Бюллетени следующие: 1034 голоса за ABC, 519 голосов за PQR, 90 голосов за ABQ, 47 голосов за APQ. Победители выбираются последовательно следующим образом:

• Сначала мы вычисляем для каждого кандидата требуемое значение t , чтобы кандидат мог получить общее количество голосов, равное 1. Это значение составляет 1/1171 для A (так как A появляется в 1171 бюллетене); 1/1124 для B; 1/1034 для C; 1/566 для P; 1/656 для Q; 1/519 для R. Таким образом, A избирается первым.
• Теперь мы пересчитываем для каждого кандидата требуемое значение t так, чтобы кандидат мог получить общую силу голоса 1, имея в виду вычесть 1/1171 из каждого избирателя, одобрившего A. Требуемое значение для B составляет 1/1124+1/1171, поскольку есть 1124 избирателя, которые одобряют B, и все они уже одобрили A. Аналогично, требуемое значение для C составляет 1/1034+1/1171; для Q оно составляет 1/656+(137/656)/1171, поскольку 137 из 656 избирателей за Q уже проголосовали за A; для P оно составляет 1/566+(47/566)/1171; а для R оно составляет 1/519. Наименьшее значение имеет Q, поэтому он избирается вторым победителем.
• Аналогично, B избирается третьим победителем.

Var-Phragmen и Leximax-Phragmen являются NP-трудными для вычисления, даже когда каждый агент одобряет 2 кандидатов и каждый кандидат одобрен 3 избирателями. Доказательство заключается в сокращении от максимального независимого множества на кубических графах . ^[3]

Leximax-Phragmen можно вычислить с помощью последовательности не более 2 n смешанно-целочисленных линейных программ с O( nm + n ² ) переменными каждая (где n — число избирателей, а m — число кандидатов); см. Лексикографическая оптимизация по максимуму и минимуму .

Var-Phragmen можно вычислить, решив одну смешанную целочисленную квадратичную программу с O( nm ) переменными.

Seq-Phragmen можно вычислить за полиномиальное время. Наивное вычисление показывает, что время выполнения составляет O( kmn ): есть k шагов (по одному для каждого избранного кандидата); на каждом шаге мы должны проверить всех кандидатов, чтобы увидеть, кто из них может быть профинансирован; и для каждого кандидата мы должны проверить всех избирателей, чтобы увидеть, кто из них может его профинансировать. Однако, чтобы быть точными, нам нужно работать с рациональными числами, и их величина должна расти до k log n . Поскольку вычисления в b битах могут потребовать O( b ² ) времени, общее время выполнения составляет O( k ³ mn log ² n).

Правила Phragmén обычно используются с бюллетенями одобрения (то есть, голосование одобрения с несколькими победителями ), но у них есть варианты, использующие ранжированные бюллетени (то есть, ранжированное голосование с несколькими победителями ). Адаптация для Seq-Phragmen была предложена в 1913 году Королевской комиссией по пропорциональному методу выборов. Этот метод использовался на шведских выборах для распределения мест внутри партий с 1921 года. ^{[2] : Sec.9}

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

Можно использовать метод Фрагмена для партий. Каждый избиратель может одобрить одну или несколько партий. Процедура та же, что и раньше, за исключением того, что теперь каждая партия может быть выбрана несколько раз — от 0 до общего числа кандидатов в партии. ^[4]

Правило Seq-Phragmen было адаптировано к более общим условиям комбинаторного партисипативного бюджетирования . ^[5]

Яворски и Сковрон ^[6] построили класс правил, которые обобщают seq-Phragmen для дегрессивной и регрессивной пропорциональности. Интуитивно:

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

Последовательный метод Фрагмена может быть использован не только для выбора подмножества, но и для создания рейтинга альтернатив в соответствии с порядком, в котором они были выбраны. Брилл и Израэль ^[7] расширяют этот метод до динамических рейтингов . Мотивированные онлайн-приложениями вопросов и ответов, ^[8] они предполагают, что некоторые кандидаты уже были выбраны, и используют эту информацию при вычислении рейтинга. Они предлагают две адаптации правила Фрагмена:

• Динамический Phragmen: на каждом шаге перебирайте последовательность уже избранных кандидатов и делите их «стоимость» между их сторонниками. Это создает для каждого пользователя потенциальный «долг» — отрицательный баланс. Вычисление долгов может быть выполнено за время O( mn ² ), где m — количество кандидатов, а n — количество пользователей. Затем пользователи начинают накапливать деньги как обычно, при этом пользователь может начать покупать новых кандидатов только после выплаты своего «долга». Пользователи покупают кандидатов последовательно, пока не будет вычислен новый рейтинг. Новый рейтинг пропорционален. Вычисление новой последовательности может быть выполнено за время O( m ² n ² ).
• Myopic Phragmen: «долг» каждого пользователя вычисляется так же, как в Dynamic Phragmen. Затем, вместо создания полного рейтинга путем запуска Sequential Phragmen, кандидаты ранжируются по размеру «долга», который они создадут для пользователей. То есть: кандидаты ранжируются по их пригодности для следующего избрания. Результирующий рейтинг не обязательно пропорционален (в частности, когда последовательность пуста, Myopic Phragmen совпадает с утилитарным голосованием по одобрению ). Вычисление новой последовательности может быть выполнено за время O( mn ² ).

Они анализируют свойства монотонности и справедливости этих адаптаций как теоретически, так и эмпирически.

Для каждого возможного бюллетеня b пусть v _b будет числом избирателей, которые проголосовали ровно за b (например: одобрили точно тот же набор кандидатов). Пусть p _b будет долей избирателей, которые проголосовали ровно за b (= v _b / общее число голосов). Метод голосования называется однородным , если он зависит только от долей p _b . Таким образом, если все числа голосов умножаются на одну и ту же константу, метод возвращает тот же результат. Методы Фрагмена однородны в этом смысле. ^{[2] : Rem.2.1}

Если в бюллетень добавляется любое количество кандидатов, но ни один из них не избирается (даже если за некоторых из них проголосовали), то результат не меняется. ^{[2] : Раздел 6} Это снижает один стимул для стратегической манипуляции: добавление «фиктивных» кандидатов для привлечения голосов.

Seq-Phragmén распределяет места по одному, поэтому он удовлетворяет свойству монотонности комитета : при добавлении большего количества мест набор победителей увеличивается (ни один победитель не теряет места). ^{[2] : Раздел 5}

Они также удовлетворяют нескольким другим критериям монотонности . ^{[2] : Раздел 14}

Для метода одобрения-голосования Фрагмена : если некий кандидат C избран, а затем кандидат C получает некоторое одобрение либо от новых избирателей, которые голосуют за C , либо от существующих избирателей, которые добавляют C в свои бюллетени, и никаких других изменений не происходит, то C все равно избирается. Однако эта монотонность не выполняется для пар кандидатов, даже если они всегда появляются вместе. Например, возможно, что кандидаты C, D появляются вместе во всех бюллетенях и получают два места, но если еще один бюллетень добавляется за C, D, то они получают вместе только одно место (поэтому один из них теряет место). ^{[2] : Пример 14.4, 14.5} Аналогично монотонность не выполняется в варианте с партиями: партия может получить больше одобрений, но все равно получить меньше мест. Например: ^[4]

• Предположим, что есть k = 3 места и 3 кандидата: a, b, c. Бюллетени таковы: 4 за a, 7 за b, 1 за a+b, 16 за a+c, 4 за b+c. Тогда избранный комитет — {a, b, a}. Но если один из избирателей b тоже одобряет a (так что бюллетени таковы: 4 за a, 6 за b, 2 за a+b, 16 за a+c, 4 за b+c), то избранный комитет — {a, c, b}. Таким образом, партия a получила одобрение, но потеряла место.

Для метода ранжированного голосования Фрагмена : если некий кандидат C избран, а затем кандидат C повышен в некоторых бюллетенях или получил несколько новых голосов, и никаких других изменений не произошло, то C все равно избран. Однако если одновременно произойдут некоторые другие изменения, то C может потерять свое место. Например, возможно, что некоторые избиратели изменят свое мнение и вместо того, чтобы голосовать за A и B, они проголосуют за C и D, и это изменение приведет к тому, что C потеряет свое место. ^{[2] : Пример 13.16}

Правило последовательного Фрагмена удовлетворяет аксиоме, известной как пропорциональное обоснованное представление (PJR). ^[3] Это делает его одним из немногих методов, удовлетворяющих как PJR, так и монотонности.

Однако это не соответствует более сильной аксиоме, известной как Extended Justified Representation (EJR). Один пример приведен здесь: ^[3]

• Кандидатов 14: a, b, c1, ..., c12. Необходимо заполнить 12 мест.
• Имеется 24 избирателя: двое избирателей одобряют {a,b,c1}; двое избирателей одобряют {a,b,c2}; 6 избирателей одобряют {c1,c2,...,c12}; 5 избирателей одобряют {c2,c3,...,c12); 9 избирателей одобряют {c3,c4,...,c12}.
• Seq-Phragmen выбирает c1,...,c12. Это нарушает EJR для четырех избирателей, которые одобряют {a,b,c1} и {a,b,c2}: у этой группы 2 квоты, и она 2-сплоченная, но ни у одного из членов нет 2 одобренных победителей.

Другой пример приведен здесь (для установления партий): ^[9]

• Необходимо заполнить 10 мест, баллотирующихся на выборах, от 3 партий-кандидатов.
• Имеется 10 избирателей с наборами одобрения ab,ab,ab; ac,ac,ac,ac; bc,bc; b.
• Seq-Phragmen выбирает a (в момент времени 1/7); затем b; затем a,b,a,b,a,b,a,b.
• Избиратели 1,2,3 одобряют всех 10 кандидатов, но избиратели 4,...,10 одобряют только 5 кандидатов. Однако группа избирателей 4,5,6,7,8,9 все согласны с партией c, поэтому EJR требует, чтобы по крайней мере один из них одобрил 6 кандидатов, поэтому EJR нарушается (обратите внимание, что PJR не нарушается для этой группы, поскольку все 10 кандидатов одобрены по крайней мере одним членом группы).

Seq-Phragmen также не соответствует другой, несовместимой аксиоме, называемой совершенным представлением (PER).

Var-Phragmen удовлетворяет PER, но не удовлетворяет PJR и EJR (за исключением случая L=1).

Leximan-Phragmen удовлетворяет требованиям PJR и PER, но по-прежнему не соответствует требованиям EJR.

Методы Фрагмена не удовлетворяют критерию согласованности . Более того, они не игнорируют полные бюллетени: добавление избирателей, которые голосуют за всех кандидатов (и, таким образом, совершенно безразличны), может повлиять на результат. ^{[2] : Пример 15.4, 15.6, 15.8, 15.9}

Когда есть одно место ( k =1):

• Метод одобрения-голосования Фрагмена сводится к голосованию по одобрению — он всегда выбирает кандидата с наибольшим числом одобрений.
• Метод ранжированного голосования Фрагмена сводится к относительному голосованию — он всегда выбирает кандидата, занявшего первое место по наибольшему числу голосов.

• Более подробную информацию о методах Фрагмена можно найти на сайте. ^[10]
• Математические свойства методов Фрагмена против методов Тиле. ^[11]
• Методы Энестрома и Фрагмена. ^[12]

• Некоторые правила голосования Phragmén реализованы в пакете Python abcvoting.
• Некоторые правила голосования Фрагмена можно опробовать онлайн на сайте pref.tools.
• В основе криптовалюты Polkadot используются как простые, так и сложные версии ^{[13] [14]} . ^[15]

Мотамед, Соетеман, Рей и Эндрисс ^[16] представляют последовательный механизм балансировки нагрузки , который обобщает правило Фрагмена для партисипаторного бюджетирования с несколькими ресурсами.

• Закон Архимеда и история « Эврика! » — аналогичны идее балансировки нагрузки
• Расширение правила одобрения
• Метод равных долей
• Единый передаваемый голос
• Правила голосования Тиле