Критерий независимости клонов - Independence of clones criterion

В системы голосования теория, критерий независимости клонов измеряет устойчивость метода выборов к стратегическая номинация. Николай Тайдман был первым, кто сформулировал этот критерий, согласно которому победитель не должен меняться из-за добавления не выигравшего кандидата, который похож на уже присутствующего кандидата.^[1]Чтобы быть более точным, подмножество кандидатов, называемое набором клонов, существует, если ни один избиратель не ранжирует любого кандидата вне набора между (или равным) любым кандидатам, которые находятся в наборе. Если набор клонов содержит не менее двух кандидатов, критерий требует, чтобы удаление одного из клонов не увеличивало или не уменьшало шанс на победу любого кандидата, не входящего в набор клонов.

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

Клонировать отрицательный и клонировать положительный

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

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

В Граф Борда является примером метода положительного клонирования. Множественное голосование является примером метода отрицательного клонирования из-за разделение голосов. Метод Коупленда является примером метода, демонстрирующего скученность.

Соответствующие методы

Мгновенное голосование и некоторые методы выборов, которые соответствуют Критерий Кондорсе Такие как ранжированные пары и Метод Шульце^[2] также встречаются независимость от клонов.

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

Некоторые из других методов, не соответствующих критерию, - это Граф Борда, минимакс, то Метод Кемени – Янга, Метод Коупленда, Баклин голосование, то большинство голосов, а двухходовая система. Варианты Мгновенное голосование которые исключают несколько кандидатов за раунд (например, условное голосование ) или запретить избирателям ранжировать всех кандидатов (например, дополнительное голосование ) также не соответствуют критерию.

Примеры

Граф Борда

Основная статья: Граф Борда

Рассмотрим выборы, в которых участвуют два кандидата, A и B. Предположим, избиратели имеют следующие предпочтения:

66%: A> B

34%: B> A

Кандидат А получит 66% баллов Борда (66% × 1 + 34% × 0), а Б получит 34% (66% × 0 + 34% × 1). Таким образом, кандидат А выиграет с перевесом в 66%.

Теперь предположим, что сторонники B выдвигают дополнительного кандидата B.₂, который очень похож на B, но считается второстепенным всеми избирателями. Для 66%, предпочитающих A, B по-прежнему остается вторым выбором. Для 34% тех, кто предпочитает B, A продолжает оставаться наименее предпочтительным кандидатом. Теперь предпочтения избирателей таковы:

66%: A> B> B2

34%: B> B2> А

Кандидат А теперь имеет 132% очков Борда (66% × 2 + 34% × 0). B имеет 134% (66% × 1 + 34% × 2). B₂ имеет 34% (66% × 0 + 34% × 1). Номинация B₂ меняет победителя с А на Б, опрокидывая оползень, даже несмотря на то, что дополнительная информация о предпочтениях избирателей является избыточной из-за схожести Б.₂ к Б.

Можно построить аналогичные примеры, чтобы показать, что учитывая подсчет Борда, любой сколь угодно большой оползень можно отменить, добавив достаточное количество кандидатов (при условии, что по крайней мере один избиратель предпочитает проигравшего). Например, чтобы отменить 90% -ное предпочтение оползня для A над B, добавьте 9 альтернатив, аналогичных / уступающих B. Тогда оценка A будет 900% (90% × 10 + 10% × 0), а оценка B будет 910% ( 90% × 9 + 10% × 10).

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

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

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

Copeland

Основная статья: Метод Коупленда

Эти примеры показывают, что метод Коупленда нарушает критерий независимости клонов.

Теснота

Метод Коупленда уязвим для переполнения, то есть результат выборов изменяется путем добавления (не выигравших) клонов не выигравшего кандидата. Предположим пять кандидатов A, B, B₂, B₃ и избиратели C и 4 со следующими предпочтениями:

# проголосовавших	Предпочтения
1	А> В3 > B> B2 > C
1	B3 > B> B2 > С> А
2	С> А> В2 > B> B3

Обратите внимание, что B, B₂ и B₃ сформировать набор клонов.

Клоны не номинированы

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

# проголосовавших	Предпочтения
1	А> В> С
1	В> С> А
2	С> А> В

Результаты будут представлены в следующей таблице:

Парные предпочтения

		Икс
		А	B	C
Y	А		[X] 1 [Y] 3	[X] 3 [Y] 1
	B	[X] 3 [Y] 1		[X] 2 [Y] 2
	C	[X] 1 [Y] 3	[X] 2 [Y] 2
Парные результаты выборов (выиграл-ничья-проиграл):		1-0-1	0-1-1	1-1-0

• [X] обозначает избирателей, которые предпочли кандидата, указанного в заголовке столбца, кандидату, указанному в заголовке строки.
• [Y] обозначает избирателей, которые предпочли кандидата, указанного в заголовке строки, кандидату, указанному в заголовке столбца.

Результат: У C одна победа и нет поражений, у A одна победа и одно поражение. Таким образом, C избран победителем Copeland.

Клоны номинированы

Предположим, все три клона будут соревноваться. Предпочтения будут следующими:

# проголосовавших	Предпочтения
1	А> В3 > B> B2 > C
1	B3 > B> B2 > С> А
2	С> А> В2 > B> B3

Результаты будут представлены в следующей таблице:

Парные предпочтения

		Икс
		А	B	B2	B3	C
Y	А		[X] 1 [Y] 3	[X] 1 [Y] 3	[X] 1 [Y] 3	[X] 3 [Y] 1
	B	[X] 3 [Y] 1		[X] 2 [Y] 2	[X] 2 [Y] 2	[X] 2 [Y] 2
	B2	[X] 3 [Y] 1	[X] 2 [Y] 2		[X] 2 [Y] 2	[X] 2 [Y] 2
	B3	[X] 3 [Y] 1	[X] 2 [Y] 2	[X] 2 [Y] 2		[X] 2 [Y] 2
	C	[X] 1 [Y] 3	[X] 2 [Y] 2	[X] 2 [Y] 2	[X] 2 [Y] 2
Парные результаты выборов (выиграл-ничья-проиграл):		3-0-1	0-3-1	0-3-1	0-3-1	1-3-0

Результат: Тем не менее, у C одна победа и ни одного поражения, но теперь у A три победы и одно поражение. Таким образом, А избран победителем Copeland.

Вывод

A получает выгоду от клонов кандидата, которого он побеждает, в то время как C не может получить выгоду от клонов, потому что C связан со всеми из них. Таким образом, добавив два клона не выигравшего кандидата B, победитель изменился. Таким образом, метод Коупленда уязвим для скученности и не соответствует критерию независимости клонов.

Объединение

Метод Коупленда также уязвим для объединения, то есть добавление клонов увеличивает шансы на победу набора клонов. Снова предположим, что пять кандидатов A, B, B₂, B₃ и избиратели C и 2 со следующими предпочтениями:

# проголосовавших	Предпочтения
1	А> С> В> В3 > B2
1	B> B2 > B3 > А> С

Обратите внимание, что B, B₂ и B₃ сформировать набор клонов.

Клоны не номинированы

Предположим, что только один из клонов будет соревноваться. Предпочтения будут следующими:

# проголосовавших	Предпочтения
1	А> С> В
1	В> А> С

Результаты будут представлены в следующей таблице:

Парные предпочтения

		Икс
		А	B	C
Y	А		[X] 1 [Y] 1	[X] 0 [Y] 2
	B	[X] 1 [Y] 1		[X] 1 [Y] 1
	C	[X] 2 [Y] 0	[X] 1 [Y] 1
Парные результаты выборов (выиграл-ничья-проиграл):		1-1-0	0-2-0	0-1-1

Результат: У A одна победа и нет поражений, у B нет побед или поражений, поэтому А избран победителем Copeland.

Клоны номинированы

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

# проголосовавших	Предпочтения
1	А> С> В> В3 > B2
1	B> B2 > B3 > А> С

Результаты будут представлены в следующей таблице:

Парные предпочтения

		Икс
		А	B	B2	B3	C
Y	А		[X] 1 [Y] 1	[X] 1 [Y] 1	[X] 1 [Y] 1	[X] 0 [Y] 2
	B	[X] 1 [Y] 1		[X] 0 [Y] 2	[X] 0 [Y] 2	[X] 1 [Y] 1
	B2	[X] 1 [Y] 1	[X] 2 [Y] 0		[X] 1 [Y] 1	[X] 1 [Y] 1
	B3	[X] 1 [Y] 1	[X] 2 [Y] 0	[X] 1 [Y] 1		[X] 1 [Y] 1
	C	[X] 2 [Y] 0	[X] 1 [Y] 1	[X] 1 [Y] 1	[X] 1 [Y] 1
Парные результаты выборов (выиграл-ничья-проиграл):		1-3-0	2-2-0	0-3-1	0-3-1	0-3-1

Результат: A имеет одну победу и ни одного поражения, но теперь у B две победы и ни одного поражения. Таким образом, B избран победителем Copeland.

Вывод

B получает выгоду от добавления низших клонов, в то время как A не может получить выгоду от клонов, потому что он связан со всеми из них. Итак, добавив два клона B, B превратился из проигравшего в победителя. Таким образом, метод Коупленда уязвим для объединения и не соответствует критерию независимости клонов.

Множественное голосование

Основная статья: Система множественного голосования

Предположим, есть два кандидата, A и B, и 55% избирателей предпочитают A, а не B. A победит на выборах, от 55% до 45%. Но предположим, что сторонники B также выдвигают альтернативу, аналогичную A, с именем A₂. Предположим, что значительное число избирателей, предпочитающих А, а не Б, также предпочитают А.₂ над A. Когда они голосуют за A₂, это снижает общую сумму A ниже 45%, в результате чего B выигрывает.

55%	30%
А2 нет	А2 25%
В 45%	В 45%

Голосование по диапазону

Основная статья: Голосование по диапазону

Голосование по диапазону удовлетворяет критерию независимости клонов.

Избиратели меняют свое мнение

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

При голосовании по диапазону, чтобы повысить влияние бюллетеня, избиратель может дать максимально возможную оценку своей наиболее предпочтительной альтернативе и минимально возможную оценку своей наименее предпочтительной альтернативе.^[3] Фактически, присвоение максимально возможной оценки всем кандидатам, которые превышают некоторый порог, и присвоение минимально возможной оценки другим кандидатам, максимизирует влияние бюллетеня на результат.^[4] Однако для этого примера необходимо, чтобы избиратель использовал первое простое правило, а не второе.

Начнем с предположения, что есть 3 альтернативы: A, B и B.₂, где B₂ похож на B, но считается нижестоящим среди сторонников A и B. Избиратели, поддерживающие A, будут иметь порядок предпочтения "A> B> B₂"чтобы они дали максимально возможную оценку, они поставят B₂ минимально возможный балл, и они дают B балл, который находится где-то посередине (больше минимального). У сторонников B будет порядок предпочтения "B> B.₂> A ", поэтому они дают B максимально возможную оценку, A минимальную оценку и B₂ оценка где-то посередине. Предположим, что B с небольшим преимуществом выигрывает выборы.

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

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

Строго интерпретируемое определение ранговых клонов

Определение набора клонов по критерию Независимости клонов создано для ранжированных систем голосования. Для систем голосования по очкам это определение неточно. Это можно увидеть на следующем примере:

Предположим, что три кандидата A, B и C имеют следующие оценки:

	Очки
# проголосовавших	А	B	C
1	10	8	0
1	0	8	9

Набор {A, B} - это набор клонов, поскольку нет избирателя, который дал бы C оценку между оценками A и B.

Кроме того, набор {B, C} является набором клонов, поскольку нет избирателя, который дал бы A оценку между оценками B и C.

Набор {A, C} не является набором клонов, поскольку оба избирателя дают B оценку между оценками A и C.

Итак, A является клоном B, а B - клоном C, но A не является клоном C.

Теперь, если выборы проводятся между A и C (без B), то A победит. Если добавить B, выиграет B. B - клон A, победитель в первую очередь. Но B также является клоном C, проигравшего в первую очередь. Таким образом, используя определение в его строгой форме, B не должен выигрывать, потому что подчиненный C не может выиграть.

Однако даже в этой строгой версии определения клонов добавление невыигрывающего клона не меняет шансы на победу всех кандидатов.

Обратите внимание, что методы Кондорсе приведут к равенству между всеми кандидатами в этом примере. Удовлетворение независимости клонов зависит от решающего момента. Используя метод Шульце или ранжированные пары, простой выбор одного из связанных кандидатов наугад повысит вероятность набора клонов {A, B} с 50%, если B не соревнуется, до 67%, если B конкурирует и, таким образом, нарушают критерий.

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

Метод Кемени – Янга

Основная статья: Метод Кемени – Янга

Этот пример показывает, что метод Кемени – Янга нарушает критерий независимости клонов. Предположим, пять кандидатов A, B₁, B₂, B₃ а также избиратели C и 13 со следующими предпочтениями:

# проголосовавших	Предпочтения
4	А> В1 > B2 > B3 > C
5	B1 > B2 > B3 > С> А
4	С> А> В1 > B2 > B3

Отметим, что B₁, B₂ и B₃ сформировать набор клонов.

Клоны не номинированы

Предположим, что участвует только один из клонов. Предпочтения будут такими:

# проголосовавших	Предпочтения
4	А> В1 > C
5	B1 > С> А
4	С> А> В1

Метод Кемени – Янга упорядочивает счетчики парных сравнений в следующей таблице подсчета:

Все возможные пары избранных имен		Количество голосов с указанным предпочтением
		Предпочитайте X, а не Y	Равное предпочтение	Предпочитайте Y, а не X
Х = А	Y = B1	8	0	5
Х = А	Y = C	4	0	9
X = B1	Y = C	9	0	4

Рейтинговые баллы всех возможных рейтингов:

Предпочтения	1. против 2.	1. против 3.	2. против 3.	Общий
А> В1 > C	8	4	9	21
А> С> В1	4	8	4	16
B1 > А> С	5	9	4	18
B1 > С> А	9	5	9	23
С> А> В1	9	4	8	21
C> B1 > А	4	9	5	18

Результат: Рейтинг B₁ > C> A имеет наивысший рейтинг. Таким образом, B₁ побеждает впереди C и A.

Клоны номинированы

Предположим, все три клона соревнуются. Предпочтения будут такими:

# проголосовавших	Предпочтения
4	А> В1 > B2 > B3 > C
5	B1 > B2 > B3 > С> А
4	С> А> В1 > B2 > B3

Метод Кемени – Янга упорядочивает счетчики парных сравнений в следующей таблице подсчета (с ${displaystyle iin {1,2,3}}$) :

Все возможные пары избранных имен		Количество голосов с указанным предпочтением
		Предпочитайте X, а не Y	Равное предпочтение	Предпочитайте Y, а не X
Х = А	Y = Bя	8	0	5
Х = А	Y = C	4	0	9
X = Bя	Y = C	9	0	4
X = B1	Y = B2	13	0	0
X = B1	Y = B3	13	0	0
X = B2	Y = B3	13	0	0

Поскольку клоны имеют идентичные результаты по сравнению со всеми другими кандидатами, их необходимо расположить один за другим в оптимальном рейтинге. Более того, оптимальный рейтинг среди клонов однозначен: B₁ > B₂ > B₃. Фактически, для вычисления результатов три клона можно рассматривать как одного объединенного кандидата B, чьи победы и поражения в три раза сильнее, чем у каждого отдельного клона. Рейтинговые баллы всех возможных рейтингов по этому поводу следующие:

Предпочтения	1. против 2.	1. против 3.	2. против 3.	Общий
А> В> С	24	4	27	55
А> С> В	4	24	12	40
В> А> С	15	27	4	46
В> С> А	27	15	9	51
С> А> В	9	12	24	45
С> В> А	12	9	15	36

Результат: Рейтинг A> B₁ > B₂ > B₃ > C имеет наивысший рейтинг. Таким образом, А побеждает впереди клонов B_я и С.

Вывод

Преимущества двух клонов B₁ потому что выигрыш А умножается на три. Итак, добавив два клона B, B превратился из победителя в проигравшего. Таким образом, метод Кемени – Янга уязвим для спойлеров и не соответствует критерию независимости клонов.

Минимакс

Основная статья: Минимакс Кондорсе

Этот пример показывает, что минимаксный метод нарушает критерий независимости клонов. Предположим, четыре кандидата A, B₁, B₂ и B₃ и 9 избирателей со следующими предпочтениями:

# проголосовавших	Предпочтения
3	А> В1 > B2 > B3
3	B2 > B3 > B1 > А
2	B3 > B1 > B2 > А
1	А> В3 > B1 > B2

Отметим, что B₁, B₂ и B₃ сформировать набор клонов.

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

Клоны не номинированы

Предположим, что только один из клонов будет соревноваться. Предпочтения будут такими:

# проголосовавших	Предпочтения
4	А> В1
5	B1 > А

Результаты будут представлены в следующей таблице:

Парные результаты выборов

		Икс
		А	B1
Y	А		[X] 5 [Y] 4
	B1	[X] 4 [Y] 5
Парные результаты выборов (выиграл-ничья-проиграл):		0-1	1-0
худшее попарное поражение (выигрыш голосов):		5	0
худшее попарное поражение (маржа):		1	0
худшее попарное противостояние:		5	4

• [X] обозначает избирателей, которые предпочли кандидата, указанного в заголовке столбца, кандидату, указанному в заголовке строки.
• [Y] обозначает избирателей, которые предпочли кандидата, указанного в заголовке строки, кандидату, указанному в заголовке столбца.

Результат: B - победитель Кондорсе. Таким образом, B избран победителем минимакса.

Клоны номинированы

Теперь предположим, что все три клона будут соревноваться. Предпочтения будут следующими:

# проголосовавших	Предпочтения
3	А> В1 > B2 > B3
3	B2 > B3 > B1 > А
2	B3 > B1 > B2 > А
1	А> В3 > B1 > B2

Результаты будут представлены в следующей таблице:

Парные результаты выборов

		Икс
		А	B1	B2	B3
Y	А		[X] 5 [Y] 4	[X] 5 [Y] 4	[X] 5 [Y] 4
	B1	[X] 4 [Y] 5		[X] 3 [Y] 6	[X] 6 [Y] 3
	B2	[X] 4 [Y] 5	[X] 6 [Y] 3		[X] 3 [Y] 6
	B3	[X] 4 [Y] 5	[X] 3 [Y] 6	[X] 6 [Y] 3
Парные результаты выборов (выиграл-ничья-проиграл):		0-0-3	2-0-1	2-0-1	2-0-1
худшее попарное поражение (выигрыш голосов):		5	6	6	6
худшее попарное поражение (маржа):		1	3	3	3
худшее попарное противостояние:		5	6	6	6

Результат: A имеет ближайшее самое крупное поражение. Таким образом, А избран победителем минимакса.

Вывод

Добавляя клонов, победитель Кондорсе B₁ становится побежденным. Все три клона победили друг друга с явным поражением. А выгода от этого. Итак, добавив два клона B, B превратился из победителя в проигравшего. Таким образом, минимаксный метод уязвим для спойлеров и не соответствует критерию независимости клонов.

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

• Стратегическая номинация

Рекомендации

1. Т. Николаус Тидеман, «Независимость клонов как критерий правил голосования», Социальный выбор и благосостояние Vol. 4, № 3 (1987), стр. 185–206.
2. М. Шульце, "Новый монотонный и независимый от клонов метод выборов единственного победителя", Вопросы голосования 17 (2003), стр. 9–19.
3. http://www.rangevoting.org/RVstrat3.html
4. http://scorevoting.net/RVstrat7.html