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

Метод Кемени -Янга — это избирательная система , в которой используются ранжированные бюллетени и подсчет попарных сравнений для определения наиболее популярных вариантов на выборах. Это метод Кондорсе , потому что, если есть победитель Кондорсе, он всегда будет считаться самым популярным выбором.

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

Метод Кемени-Янга также известен как правило Кемени , рейтинг популярности VoteFair , максимального правдоподобия метод и медианное отношение .

Описание

Метод Кемени-Янга использует избирательные бюллетени , в которых избиратели ранжируют выбор в соответствии со своими предпочтениями. Избирателю разрешено ранжировать более одного варианта на одном и том же уровне предпочтений. ^{[ нужна ссылка ]} Варианты без ранжирования обычно интерпретируются как наименее предпочтительные.

Расчеты Кемени-Янга обычно выполняются в два этапа. Первым шагом является создание матрицы или таблицы, которая подсчитывает попарные предпочтения избирателей. Второй шаг — протестировать все возможные рейтинги , подсчитать балл для каждого такого рейтинга и сравнить результаты. Каждый рейтинговый балл равен сумме попарных оценок, применимых к этому рейтингу.

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

Другой способ просмотреть порядок состоит в том, что он минимизирует сумму тау-расстояний Кендалла ( расстояние пузырьковой сортировки ) до списков избирателей.

Чтобы продемонстрировать, как индивидуальный порядок предпочтений преобразуется в итоговую таблицу, стоит рассмотреть следующий пример. Предположим, что один избиратель имеет выбор среди четырех кандидатов (т. е. Эллиота, Мередита, Роланда и Селдена) и имеет следующий порядок предпочтений:

Предпочтение заказ	Выбор
Первый	Эллиот
Второй	Роланд
Третий	Мередит или Селден (равные предпочтения)

Эти предпочтения могут быть выражены в сводной таблице. Таблица подсчета голосов, в которой все результаты попарного подсчета расположены в трех столбцах, полезна для подсчета (подсчета) предпочтений в избирательных бюллетенях и расчета рейтинговых баллов. В центральном столбце отслеживаются случаи, когда избиратель указывает более одного варианта на одном и том же уровне предпочтений. Вышеупомянутый порядок предпочтений можно выразить в виде следующей таблицы: ^{[ нужна ссылка ]}

Все возможные пары избранных имен	Количество голосов с указанным предпочтением
Все возможные пары избранных имен	Предпочитайте X, а не Y	Равные предпочтения	Предпочитайте Y, а не X
X = Селден Y = Мередит	0	+1 голос	0
X = Селден Y = Эллиот	0	0	+1 голос
X = Селден Y = Роланд	0	0	+1 голос
X = Мередит Y = Эллиот	0	0	+1 голос
X = Мередит Y = Роланд	0	0	+1 голос
X = Эллиот Y = Роланд	+1 голос	0	0

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

Все возможные пары избранных имен	Количество голосов с указанным предпочтением
Все возможные пары избранных имен	Предпочитайте X, а не Y	Равные предпочтения	Предпочитайте Y, а не X
X = Селден Y = Мередит	50	10	40
X = Селден Y = Эллиот	40	0	60
X = Селден Y = Роланд	40	0	60
X = Мередит Y = Эллиот	40	0	60
X = Мередит Y = Роланд	30	0	70
X = Эллиот Y = Роланд	30	0	70

Сумма подсчетов в каждой строке должна равняться общему количеству голосов.

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

Эллиот
Роланд
Мередит
Селден

удовлетворяет предпочтениям Эллиот > Роланд, Эллиот > Мередит, Эллиот > Селден, Роланд > Мередит, Роланд > Селден и Мередит > Селден. Соответствующие баллы, взятые из таблицы, равны

Эллиот > Роланд: 30
Эллиот > Мередит: 60
Эллиот > Селден: 60
Роланд > Мередит: 70
Роланд > Селден: 60
Мередит > Селден: 40

давая общий рейтинговый балл 30 + 60 + 60 + 70 + 60 + 40 = 320.

Подсчет общего рейтинга

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

Роланд
Эллиот
Селден
Мередит

с рейтингом 370.

Если есть циклы или ничьи, более чем один возможный рейтинг может иметь один и тот же наибольший балл. Циклы разрешаются путем создания единого общего рейтинга, в котором некоторые варианты выбора связаны между собой. ^{[ нужны разъяснения ]}

Сводная матрица

После расчета общего рейтинга результаты парных сравнений можно сгруппировать в сводную матрицу, как показано ниже, в которой варианты отображаются в выигрышном порядке от самого популярного (сверху и слева) до наименее популярного (снизу и справа). Этот матричный макет не включает парные счетчики с равными предпочтениями, которые появляются в итоговой таблице: ^{[ 1 ]}

	... над Роландом	... над Эллиотом	...о Селдене	... над Мередит
Предпочитаю Роланда ...	-	70	60	70
Предпочитаю Эллиота ...	30	-	60	60
Предпочитаю Селден ...	40	40	-	50
Предпочитаю Мередит ...	30	40	40	-

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

В этой сводной матрице сумма чисел в нижней левой треугольной половине матрицы (показанной здесь на красном фоне) является минимальной. Научные статьи Джона Кемени и Пейтона Янга ^{[ 2 ]}^{[ 3 ]} обратитесь к поиску этой минимальной суммы, которая называется оценкой Кемени и которая основана на том, сколько избирателей выступают против (а не поддерживают) каждый парный порядок:

Метод	Победитель первого места
Кемени-Янг	Роланд
Кондорсе	Роланд
Мгновенное второе голосование	Эллиот или Селден (в зависимости от того, как будет решена ничья во втором раунде)
Множество	Селден

Пример

Предположим, что в Теннесси проводятся выборы по вопросу о местонахождении своей столицы . Население сосредоточено вокруг четырех крупных городов. Все избиратели хотят, чтобы столица была как можно ближе к ним. Возможные варианты:

Мемфис , крупнейший город, но далекий от остальных (42% избирателей)
Нэшвилл , недалеко от центра штата (26% избирателей)
Чаттануга , немного восточнее (15% избирателей)
Ноксвилл , далеко на северо-востоке (17% избирателей)

Предпочтения избирателей каждого региона таковы:

42% избирателей Дальний Запад	26% избирателей Центр	15% избирателей Центр-Восток	17% избирателей Дальний Восток
Мемфис Нэшвилл Чаттануга Ноксвилл	Нэшвилл Чаттануга Ноксвилл Мемфис	Чаттануга Ноксвилл Нэшвилл Мемфис	Ноксвилл Чаттануга Нэшвилл Мемфис

Эта матрица суммирует соответствующие счетчики парных сравнений :

	... над Мемфис	... над Нэшвилл	... над Чаттануга	... над Ноксвилл
Предпочитать Мемфис ...	-	42%	42%	42%
Предпочитать Нэшвилл ...	58%	-	68%	68%
Предпочитать Чаттануга ...	58%	32%	-	83%
Предпочитать Ноксвилл ...	58%	32%	17%	-

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

Все возможные пары избранных имен	Количество голосов с указанным предпочтением
Предпочитайте X, а не Y	Равные предпочтения	Предпочитайте Y, а не X
X = Мемфис Y = Нэшвилл	42%	0	58%
X = Мемфис Y = Чаттануга	42%	0	58%
X = Мемфис Y = Ноксвилл	42%	0	58%
X = Нэшвилл Y = Чаттануга	68%	0	32%
X = Нэшвилл Y = Ноксвилл	68%	0	32%
X = Чаттануга Y = Ноксвилл	83%	0	17%

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

42% (избирателей) предпочитают Мемфис Нэшвиллу

42% предпочитают Мемфис Чаттануге

42% предпочитают Мемфис Ноксвиллу

68% предпочитают Нэшвилл Чаттануге

68% предпочитают Нэшвилл Ноксвиллу

83% предпочитают Чаттанугу Ноксвиллу

В этой таблице перечислены все рейтинговые оценки:

Первый выбор	Второй выбор	Третий выбор	Четвертый выбор	Рейтинг счет
Мемфис	Нэшвилл	Чаттануга	Ноксвилл	345
Мемфис	Нэшвилл	Ноксвилл	Чаттануга	279
Мемфис	Чаттануга	Нэшвилл	Ноксвилл	309
Мемфис	Чаттануга	Ноксвилл	Нэшвилл	273
Мемфис	Ноксвилл	Нэшвилл	Чаттануга	243
Мемфис	Ноксвилл	Чаттануга	Нэшвилл	207
Нэшвилл	Мемфис	Чаттануга	Ноксвилл	361
Нэшвилл	Мемфис	Ноксвилл	Чаттануга	295
Нэшвилл	Чаттануга	Мемфис	Ноксвилл	377
Нэшвилл	Чаттануга	Ноксвилл	Мемфис	393
Нэшвилл	Ноксвилл	Мемфис	Чаттануга	311
Нэшвилл	Ноксвилл	Чаттануга	Мемфис	327
Чаттануга	Мемфис	Нэшвилл	Ноксвилл	325
Чаттануга	Мемфис	Ноксвилл	Нэшвилл	289
Чаттануга	Нэшвилл	Мемфис	Ноксвилл	341
Чаттануга	Нэшвилл	Ноксвилл	Мемфис	357
Чаттануга	Ноксвилл	Мемфис	Нэшвилл	305
Чаттануга	Ноксвилл	Нэшвилл	Мемфис	321
Ноксвилл	Мемфис	Нэшвилл	Чаттануга	259
Ноксвилл	Мемфис	Чаттануга	Нэшвилл	223
Ноксвилл	Нэшвилл	Мемфис	Чаттануга	275
Ноксвилл	Нэшвилл	Чаттануга	Мемфис	291
Ноксвилл	Чаттануга	Мемфис	Нэшвилл	239
Ноксвилл	Чаттануга	Нэшвилл	Мемфис	255

Наибольший рейтинговый балл равен 393, и этот рейтинг связан со следующим возможным рейтингом, поэтому этот рейтинг также является общим рейтингом:

Предпочтение заказ	Выбор
Первый	Нэшвилл
Второй	Чаттануга
Третий	Ноксвилл
Четвертый	Мемфис

Если нужен единственный победитель, выбирается первый вариант - Нэшвилл. (В этом примере Нэшвилл является победителем Кондорсе .)

В приведенной ниже сводной матрице попарные подсчеты расположены в порядке от самого популярного (сверху и слева) к наименее популярному (снизу и справа):

	... над Нэшвиллом ...	... над Чаттанугой ...	... над Ноксвиллем ...	... над Мемфисом ...
Предпочитаю Нэшвилл ...	-	68%	68%	58%
Предпочитаю Чаттанугу ...	32%	-	83%	58%
Предпочитаю Ноксвилл ...	32%	17%	-	58%
Предпочитаю Мемфис ...	42%	42%	42%	-

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

Характеристики

Во всех случаях, которые не приводят к точному совпадению, метод Кемени-Янга определяет наиболее популярный выбор, второй по популярности выбор и так далее.

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

Удовлетворительные критерии для всех методов Кондорсе

Все методы Кондорсе, включая метод Кемени – Янга, удовлетворяют этим критериям:

Ненавязывание ^{[ сломанный якорь ]}: Существуют предпочтения избирателей, которые могут дать любой возможный результат в общем порядке предпочтений, включая равенство при любой комбинации уровней предпочтений.

Критерий Кондорсе: Если есть выбор, который выигрывает все парные состязания, то этот выбор выигрывает.

Критерий большинства: Если большинство избирателей однозначно предпочитают вариант X любому другому выбору, то выбор X считается наиболее популярным.

Недиктатура: Один избиратель не может контролировать результат во всех случаях.

Дополнительные удовлетворенные критерии

Метод Кемени-Янга также удовлетворяет этим критериям:

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

Парето-эффективность: Любое парное предпочтение, выраженное каждым избирателем, приводит к тому, что предпочтительный выбор получает более высокий рейтинг, чем менее предпочтительный выбор.

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

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

Независимость альтернатив, в которых доминирует Смит: Если выбор X отсутствует в наборе Смита , добавление или удаление варианта X не меняет результат, в котором выбор Y считается наиболее популярным.

Армирование: Если все бюллетени разделены на отдельные расы и общий рейтинг для отдельных гонок одинаков, то такой же рейтинг получается и при объединении всех бюллетеней. ^{[ 4 ]}

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

Неудачные критерии для всех методов Кондорсе

Как и все методы Кондорсе, метод Кемени-Янга не соответствует этим критериям (что означает, что описанные критерии не применимы к методу Кемени-Янга):

Независимость нерелевантных альтернатив: Добавление или удаление варианта X не меняет результата, в котором вариант Y считается наиболее популярным.

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

Неуязвимость к компрометации: Избиратель не может сделать свой выбор самым популярным, придавая этому выбору неискренне высокий рейтинг.

Участие: Добавление бюллетеней, в которых выбор X ставится выше выбора Y, никогда не приведет к тому, что выбор Y вместо выбора X станет наиболее популярным.

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

Последовательность: Если все бюллетени разделены на отдельные расы и выбор X определен как наиболее популярный в каждой такой гонке, то вариант X является наиболее популярным, когда все бюллетени объединены.

Искренний любимый критерий: Оптимальная стратегия голосования для отдельного человека всегда должна включать предоставление максимальной поддержки любимому кандидату.

Дополнительные критерии неудачи

Метод Кемени-Янга также не соответствует этим критериям (что означает, что описанные критерии не применимы к методу Кемени-Янга):

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

Неуязвимость к опрокидыванию: Избиратель не может сделать выбор X самым популярным, присвоив варианту Y неискренне высокий рейтинг.

Шварц: Выбор, определенный как самый популярный, является членом множества Шварца.

Полиномиальное время выполнения ^{[ 5 ]}: Известно, что с помощью этого метода определяется алгоритм определения победителя в полиномиальном по числу вариантов времени выполнения.

Методы расчета и сложность вычислений

Алгоритм вычисления рейтинга Кемени-Янга за полиномиальное время от числа кандидатов неизвестен и вряд ли существует, поскольку проблема NP-трудна. ^{[ 5 ]} даже если будет всего 4 избирателя (даже) ^{[ 6 ]}^{[ 7 ]} или 7 избирателей (нечетное). ^{[ 8 ]}

Сообщается, что ^{[ 9 ]} что методы расчета, основанные на целочисленном программировании, иногда позволяли вычислить полный рейтинг голосов по 40 кандидатам за секунды. Однако некоторые выборы Кемени с 40 кандидатами и 5 голосами, сгенерированные случайным образом, не могли быть решены на компьютере Pentium с тактовой частотой 3 ГГц в полезный срок, установленный в 2006 году. ^{[ 9 ]}

Метод Кемени-Янга можно сформулировать как пример более абстрактной задачи поиска взвешенных наборов дуг обратной связи в турнирных графах . ^{[ 10 ]} Таким образом, к этой проблеме можно применить множество методов расчета наборов дуг обратной связи, включая вариант алгоритма Хелда-Карпа , который может вычислять ранжирование Кемени-Янга для $n$ кандидаты вовремя $O(n2^{n})$ , что для многих кандидатов значительно быстрее, чем факторное время проверки всех рейтингов. ^{[ 11 ]}^{[ 12 ]} Существует полиномиальная аппроксимационная схема для вычисления рейтинга Кемени-Янга: ^{[ 13 ]} а также существует параметризованный алгоритм субэкспоненциального времени со временем работы O ^*(2 ^{О( √ ОПТ )}) для вычисления такого рейтинга. ^{[ 10 ]}

История

Метод Кемени-Янга был разработан Джоном Кемени в 1959 году. ^{[ 2 ]}

В 1978 году Пейтон Янг и Артур Левенглик аксиоматически охарактеризовали этот метод, показав, что это уникальный нейтральный метод, удовлетворяющий непротиворечивости и так называемому критерию квазиКондорсе. ^{[ 3 ]} Его также можно охарактеризовать с помощью свойств непротиворечивости и монотонности. ^{[ 14 ]} В других статьях ^{[ 15 ]} ^{[ 16 ]} ^{[ 17 ]} ^{[ 18 ]} Янг принял эпистемический подход к агрегированию предпочтений: он предполагал, что существует объективно «правильный», но неизвестный порядок предпочтения альтернатив, и избиратели получают зашумленные сигналы об этом истинном порядке предпочтений (ср. теорему присяжных Кондорсе ). Модель этих зашумленных сигналов Янг показал, что метод Кемени-Янга является оценкой максимального правдоподобия истинного порядка предпочтений. Янг далее утверждает, что сам Кондорсе знал о правиле Кемени-Янга и его интерпретации максимального правдоподобия, но не смог ясно выразить свои идеи.

В статьях Джона Кемени и Пейтона Янга в оценках Кемени используется подсчет количества избирателей, которые выступают против, а не поддерживают каждое парное предпочтение. ^{[ 2 ]}^{[ 3 ]} но наименьший такой балл соответствует тому же общему рейтингу.

С 1991 года этот метод пропагандируется Ричардом Фобсом под названием «Рейтинг популярности VoteFair». ^{[ 19 ]}

Сравнительная таблица

В следующей таблице метод Кемени-Янга сравнивается с другими методами выборов с одним победителем:

Сравнение систем голосования с одним победителем
Критерий Метод	Большинство	Проигравший большинства	Взаимное большинство	Победитель Кондорсе ^{[ Тн 1 ]}	Кондорсе неудачник	Смит ^{[ Тн 1 ]}	Смит-IIA ^{[ Тн 1 ]}	ТАМ / ЛИЯ ^{[ Тн 1 ]}	Cloneproof	Monotone	Участие	Позже без вреда ^{[ Тн 1 ]}	Позже-без помощи ^{[ Тн 1 ]}	Нет любимого предательства ^{[ Тн 1 ]}	бюллетень тип
Антиплюрализм	Нет	Да	Нет	Нет	Нет	Нет	Нет	Нет	Нет	Да	Да	Нет	Нет	Да	Единая отметка
Одобрение	Да	Нет	Нет	Нет	Нет	Нет	Нет	Да ^{[ Тн 2 ]}	Да	Да	Да	Нет	Да	Да	Approvals
Болдуин	Да	Да	Да	Да	Да	Да	Нет	Нет	Нет	Нет	Нет	Нет	Нет	Нет	Ranking
Черный	Да	Да	Нет	Да	Да	Нет	Нет	Нет	Нет	Да	Нет	Нет	Нет	Нет	Ranking
Край	Нет	Да	Нет	Нет	Да	Нет	Нет	Нет	Нет	Да	Да	Нет	Да	Нет	Ranking
Баклин	Да	Да	Да	Нет	Нет	Нет	Нет	Нет	Нет	Да	Нет	Нет	Да	Нет	Ranking
Кумбс	Да	Да	Да	Нет	Да	Нет	Нет	Нет	Нет	Нет	Нет	Нет	Нет	Да	Ranking
Коупленд	Да	Да	Да	Да	Да	Да	Да	Нет	Нет	Да	Нет	Нет	Нет	Нет	Ranking
Доджсон	Да	Нет	Нет	Да	Нет	Нет	Нет	Нет	Нет	Нет	Нет	Нет	Нет	Нет	Ranking
Самая высокая медиана	Да	Да ^{[ Тн 3 ]}	Нет ^{[ Тн 4 ]}	Нет	Нет	Нет	Нет	Да ^{[ Тн 2 ]}	Да	Да	Нет ^{[ Тн 5 ]}	Нет	Да	Да	Результаты
Мгновенный сток	Да	Да	Да	Нет	Да	Нет	Нет	Нет	Да	Нет	Нет	Да	Да	Нет	Ranking
Кемени-Янг	Да	Да	Да	Да	Да	Да	Да	Только ЛИИА	Нет	Да	Нет	Нет	Нет	Нет	Ranking
Минимакс	Да	Нет	Нет	Да ^{[ Тн 6 ]}	Нет	Нет	Нет	Нет	Нет	Да	Нет	Нет ^{[ Тн 6 ]}	Нет	Нет	Ranking
Нансон	Да	Да	Да	Да	Да	Да	Нет	Нет	Нет	Нет	Нет	Нет	Нет	Нет	Ranking
Множество	Да	Нет	Нет	Нет	Нет	Нет	Нет	Нет	Нет	Да	Да	Да	Да	Нет	Единая отметка
Случайное голосование ^{[ Тн 7 ]}	Нет	Нет	Нет	Нет	Нет	Нет	Нет	Да	Да	Да	Да	Да	Да	Да	Единая отметка
Рейтинговые пары	Да	Да	Да	Да	Да	Да	Да	Только ЛИИА	Да	Да	Нет ^{[ Тн 5 ]}	Нет	Нет	Нет	Ranking
Сток	Да	Да	Нет	Нет	Да	Нет	Нет	Нет	Нет	Нет	Нет	Да	Да	Нет	Единая отметка
Шульце	Да	Да	Да	Да	Да	Да	Да	Нет	Да	Да	Нет ^{[ Тн 5 ]}	Нет	Нет	Нет	Ranking
Счет	Нет	Нет	Нет	Нет	Нет	Нет	Нет	Да ^{[ Тн 2 ]}	Да	Да	Да	Нет	Да	Да	Результаты
Жеребьевка ^{[ Тн 8 ]}	Нет	Нет	Нет	Нет	Нет	Нет	Нет	Да	Нет	Да	Да	Да	Да	Да	Никто
ЗВЕЗДА	Нет	Да	Нет	Нет	Да	Нет	Нет	Нет	Нет	Да	Нет	Нет	Нет	Нет	Результаты
Альтернатива Тайдману	Да	Да	Да	Да	Да	Да	Да	Нет	Да	Нет	Нет	Нет	Нет	Нет	Ranking
Примечания к таблице	^ Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г Критерий Кондорсе несовместим с критериями последовательности , участия , «позже без вреда» , «позже без помощи » и искреннего любимца . ^ Перейти обратно: ^а ^б ^с Голосование за одобрение, голосование по баллам и решение большинства удовлетворяют требованиям IIA, если предположить, что избиратели оценивают кандидатов независимо, используя свою собственную абсолютную шкалу . Чтобы это произошло, на некоторых выборах некоторые избиратели должны использовать меньше своих полномочий, несмотря на наличие значимых предпочтений среди жизнеспособных кандидатов. ^ Решение большинства может избрать кандидата, однозначно наименее предпочитаемого более чем половиной избирателей, но никогда не избирает кандидата с однозначно наименьшим рейтингом более чем половиной избирателей. ^ Решение большинства не соответствует критерию взаимного большинства, но удовлетворяет критерию, если большинство ставит взаимно предпочтительный набор выше заданной абсолютной оценки, а все остальные - ниже этой оценки. ^ Перейти обратно: ^а ^б ^с При голосовании по наивысшей медиане, рейтинговых парах и голосовании Шульце для любого избирателя всегда есть получестное голосование без сожалений, при этом все остальные бюллетени остаются неизменными и при условии, что он достаточно знает о том, как будут голосовать другие. В таких обстоятельствах у избирателя всегда есть хотя бы один способ принять участие, не ставя при этом менее предпочтительного кандидата выше более предпочтительного. ^ Перейти обратно: ^а ^б Вариант Минимакса, который учитывает только парную оппозицию, а не оппозицию минус поддержка, не соответствует критерию Кондорсе и соответствует принципу «позже не будет причинен вред». ^ Победитель определяется случайным образом выбранным бюллетенем. Этот и тесно связанные с ним методы представляют математический интерес и включены сюда, чтобы продемонстрировать, что даже необоснованные методы могут соответствовать критериям метода голосования. ^ Если победитель выбирается случайным образом из кандидатов, проводится жеребьевка, чтобы продемонстрировать, что даже методы без голосования могут соответствовать некоторым критериям.

Примечания

^ Числа в этом примере взяты из образца выборов, использованного в Википедии, заархивировано 30 марта 2017 г. в Wayback Machine .
^ Перейти обратно: ^а ^б ^с Джон Кемени, «Математика без чисел», Дедал 88 (1959), стр. 577–591.
^ Перейти обратно: ^а ^б ^с Х. П. Янг и А. Левенглик, « Последовательное расширение избирательного принципа Кондорсе », SIAM Journal on Applied Mathematics 35 , вып. 2 (1978), стр. 285–300.
^ Джузеппе Мунда, «Социальная многокритериальная оценка устойчивой экономики», стр. 124.
^ Перейти обратно: ^а ^б Дж. Бартольди III, К. А. Тови и М. А. Трик , «Схемы голосования, при которых может быть трудно определить, кто победил на выборах», Social Choice and Welfare , Vol. 6, № 2 (1989), стр. 157–165.
^ К. Дворк, Р. Кумар, М. Наор, Д. Сивакумар. Методы агрегирования рангов для Интернета, WWW10, 2001 г.
^ Бидль, Тереза ; Бранденбург, Франц Дж.; Дэн, Сяоте (12 сентября 2005 г.). Хили, Патрик; Николов, Никола С. (ред.). Пересечения и перестановки . Конспекты лекций по информатике. Шпрингер Берлин Гейдельберг. стр. 1–12. дои : 10.1007/11618058_1 . ISBN 9783540314257 . S2CID 11189107 .
^ Бахмайер, Георг; Брандт, Феликс; Гейст, Кристиан; Харренштейн, Пол; Кардель, Кейван; Петерс, Доминик; Сидиг, Ханс Георг (01 ноября 2019 г.). «К-мажоритарные орграфы и сложность голосования при постоянном числе избирателей» . Журнал компьютерных и системных наук . 105 : 130–157. arXiv : 1704.06304 . дои : 10.1016/j.jcss.2019.04.005 . ISSN 0022-0000 . S2CID 2357131 .
^ Перейти обратно: ^а ^б Винсент Конитцер, Эндрю Давенпорт и Джаянт Каланьянам, « Улучшенные границы для расчета рейтингов Кемени » (2006).
^ Перейти обратно: ^а ^б Карпински М. и Шуди В. «Быстрые алгоритмы для турнира по набору дуг обратной связи, турнира по агрегированию рангов Кемени и турнира по взаимосвязи» , в: Чеонг О., Чва К.-Ю. и Парк К. (ред. ): ISAAC 2010, Часть I, LNCS 6506, стр. 3–14.
^ Лоулер, Э. (1964), «Комментарий к минимальным наборам дуг обратной связи», IEEE Transactions on Circuit Theory , 11 (2): 296–297, doi : 10.1109/tct.1964.1082291
^ Бодлендер, Ганс Л .; Фомин Федор Владимирович; Костер, Арье MCA; Крач, Дитер; Тиликос, Димитриос М. (2012), «Заметка о точных алгоритмах для задач упорядочения вершин на графах», Theory of Computing Systems , 50 (3): 420–432, doi : 10.1007/s00224-011-9312-0 , hdl : 1956/4556 , МР 2885638 , S2CID 253742611
^ «Как ранжировать с небольшим количеством ошибок» . http://cs.brown.edu/~claire/stoc07.pdf
^ Может, Бурак; Сторкен, Тон (01 марта 2013 г.). «Обновить правила монотонного предпочтения» (PDF) . Математические социальные науки . 65 (2): 136–149. doi : 10.1016/j.mathsocsci.2012.10.004 . ISSN 0165-4896 .
^ HP Young, «Теория голосования Кондорсе», American Political Science Review 82 , вып. 2 (1988), стр. 1231–1244.
^ HP Young, «Оптимальное ранжирование и выбор из парных сравнений», в « Объединении информации и принятии групповых решений» под редакцией Б. Грофмана и Г. Оуэна (1986), JAI Press, стр. 113–122.
^ HP Young, «Оптимальные правила голосования», Journal of Economic Perspectives 9 , № 1 (1995), стр. 51–64.
^ HP Young, «Групповой выбор и индивидуальные суждения», Глава 9 « Перспективы общественного выбора: справочник» , под редакцией Денниса Мюллера (1997), Cambridge UP., стр. 181–200.
^ Ричард Фобс, «Набор инструментов творческого решения проблем», ( ISBN 0-9632-2210-4 ), 1993, стр. 223–225.

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

VoteFair.org — сайт, на котором подсчитываются результаты Кемени-Янга. Для сравнения он также вычисляет победителя по множественности, подсчету Кондорсе, Борда и другим методам голосования.
VoteFair_Ranking.cpp — программа на C++, доступная на GitHub под лицензией MIT, которая рассчитывает результаты рейтинга VoteFair, включая расчеты Кондорсе-Кемени.
класса Кондорсе PHP- библиотека , поддерживающая несколько методов Кондорсе, включая метод Кемени-Янга.
Программа C++ для агрегирования предпочтений Кемени-Янга — программа командной строки для быстрого расчета результатов Кемени-Янга в виде исходного кода и скомпилированных двоичных файлов для Windows и Linux. Открытый исходный код, за исключением использования числовых рецептов .
Программа C для агрегирования предпочтений Кемени-Янга — реализует алгоритм Давенпорта без каких-либо других библиотечных зависимостей. Открытый исходный код, лицензия LGPL. Привязка Ruby к библиотеке также имеет открытый исходный код и имеет лицензию LPGL.
Оптимальное агрегирование рангов Кемени-Янга в Python — учебное пособие, в котором используется простая формулировка в виде целочисленной программы и которое можно адаптировать к другим языкам с привязкой к lpsolve.
QuickVote — веб-сайт, на котором рассчитываются результаты Кемени-Янга, а также даются дополнительные объяснения и примеры концепции. Он также вычисляет победителя по множественности, подсчету Борды, мгновенному второму туру и другим методам голосования.

[condorcet-iia-incompatibility-20] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г Критерий Кондорсе несовместим с критериями последовательности , участия , «позже без вреда» , «позже без помощи » и искреннего любимца .

[IIA_rating_methods-21] Перейти обратно: ^а ^б ^с Голосование за одобрение, голосование по баллам и решение большинства удовлетворяют требованиям IIA, если предположить, что избиратели оценивают кандидатов независимо, используя свою собственную абсолютную шкалу . Чтобы это произошло, на некоторых выборах некоторые избиратели должны использовать меньше своих полномочий, несмотря на наличие значимых предпочтений среди жизнеспособных кандидатов.

[22] Решение большинства может избрать кандидата, однозначно наименее предпочитаемого более чем половиной избирателей, но никогда не избирает кандидата с однозначно наименьшим рейтингом более чем половиной избирателей.

[mjmmc-23] Решение большинства не соответствует критерию взаимного большинства, но удовлетворяет критерию, если большинство ставит взаимно предпочтительный набор выше заданной абсолютной оценки, а все остальные - ниже этой оценки.

[semipc-24] Перейти обратно: ^а ^б ^с При голосовании по наивысшей медиане, рейтинговых парах и голосовании Шульце для любого избирателя всегда есть получестное голосование без сожалений, при этом все остальные бюллетени остаются неизменными и при условии, что он достаточно знает о том, как будут голосовать другие. В таких обстоятельствах у избирателя всегда есть хотя бы один способ принять участие, не ставя при этом менее предпочтительного кандидата выше более предпочтительного.

[MinimaxVarient-25] Перейти обратно: ^а ^б Вариант Минимакса, который учитывает только парную оппозицию, а не оппозицию минус поддержка, не соответствует критерию Кондорсе и соответствует принципу «позже не будет причинен вред».

[26] Победитель определяется случайным образом выбранным бюллетенем. Этот и тесно связанные с ним методы представляют математический интерес и включены сюда, чтобы продемонстрировать, что даже необоснованные методы могут соответствовать критериям метода голосования.

[27] Если победитель выбирается случайным образом из кандидатов, проводится жеребьевка, чтобы продемонстрировать, что даже методы без голосования могут соответствовать некоторым критериям.

[1] Числа в этом примере взяты из образца выборов, использованного в Википедии, заархивировано 30 марта 2017 г. в Wayback Machine .

[kemeny-2] Перейти обратно: ^а ^б ^с Джон Кемени, «Математика без чисел», Дедал 88 (1959), стр. 577–591.

[young-3] Перейти обратно: ^а ^б ^с Х. П. Янг и А. Левенглик, « Последовательное расширение избирательного принципа Кондорсе », SIAM Journal on Applied Mathematics 35 , вып. 2 (1978), стр. 285–300.

[4] Джузеппе Мунда, «Социальная многокритериальная оценка устойчивой экономики», стр. 124.

[btt-5] Перейти обратно: ^а ^б Дж. Бартольди III, К. А. Тови и М. А. Трик , «Схемы голосования, при которых может быть трудно определить, кто победил на выборах», Social Choice and Welfare , Vol. 6, № 2 (1989), стр. 157–165.

[6] К. Дворк, Р. Кумар, М. Наор, Д. Сивакумар. Методы агрегирования рангов для Интернета, WWW10, 2001 г.

[7] Бидль, Тереза ; Бранденбург, Франц Дж.; Дэн, Сяоте (12 сентября 2005 г.). Хили, Патрик; Николов, Никола С. (ред.). Пересечения и перестановки . Конспекты лекций по информатике. Шпрингер Берлин Гейдельберг. стр. 1–12. дои : 10.1007/11618058_1 . ISBN 9783540314257 . S2CID 11189107 .

[8] Бахмайер, Георг; Брандт, Феликс; Гейст, Кристиан; Харренштейн, Пол; Кардель, Кейван; Петерс, Доминик; Сидиг, Ханс Георг (01 ноября 2019 г.). «К-мажоритарные орграфы и сложность голосования при постоянном числе избирателей» . Журнал компьютерных и системных наук . 105 : 130–157. arXiv : 1704.06304 . дои : 10.1016/j.jcss.2019.04.005 . ISSN 0022-0000 . S2CID 2357131 .

[computingKemeny-9] Перейти обратно: ^а ^б Винсент Конитцер, Эндрю Давенпорт и Джаянт Каланьянам, « Улучшенные границы для расчета рейтингов Кемени » (2006).

[ks10-10] Перейти обратно: ^а ^б Карпински М. и Шуди В. «Быстрые алгоритмы для турнира по набору дуг обратной связи, турнира по агрегированию рангов Кемени и турнира по взаимосвязи» , в: Чеонг О., Чва К.-Ю. и Парк К. (ред. ): ISAAC 2010, Часть I, LNCS 6506, стр. 3–14.

[11] Лоулер, Э. (1964), «Комментарий к минимальным наборам дуг обратной связи», IEEE Transactions on Circuit Theory , 11 (2): 296–297, doi : 10.1109/tct.1964.1082291

[12] Бодлендер, Ганс Л .; Фомин Федор Владимирович; Костер, Арье MCA; Крач, Дитер; Тиликос, Димитриос М. (2012), «Заметка о точных алгоритмах для задач упорядочения вершин на графах», Theory of Computing Systems , 50 (3): 420–432, doi : 10.1007/s00224-011-9312-0 , hdl : 1956/4556 , МР 2885638 , S2CID 253742611

[13] «Как ранжировать с небольшим количеством ошибок» . http://cs.brown.edu/~claire/stoc07.pdf

[14] Может, Бурак; Сторкен, Тон (01 марта 2013 г.). «Обновить правила монотонного предпочтения» (PDF) . Математические социальные науки . 65 (2): 136–149. doi : 10.1016/j.mathsocsci.2012.10.004 . ISSN 0165-4896 .

[15] HP Young, «Теория голосования Кондорсе», American Political Science Review 82 , вып. 2 (1988), стр. 1231–1244.

[16] HP Young, «Оптимальное ранжирование и выбор из парных сравнений», в « Объединении информации и принятии групповых решений» под редакцией Б. Грофмана и Г. Оуэна (1986), JAI Press, стр. 113–122.

[17] HP Young, «Оптимальные правила голосования», Journal of Economic Perspectives 9 , № 1 (1995), стр. 51–64.

[18] HP Young, «Групповой выбор и индивидуальные суждения», Глава 9 « Перспективы общественного выбора: справочник» , под редакцией Денниса Мюллера (1997), Cambridge UP., стр. 181–200.

[19] Ричард Фобс, «Набор инструментов творческого решения проблем», ( ISBN 0-9632-2210-4 ), 1993, стр. 223–225.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ Тн 1 ]

[ Тн 2 ]

[ Тн 3 ]

[ Тн 4 ]

[ Тн 5 ]

[ Тн 6 ]

[ Тн 7 ]

[ Тн 8 ]