Метод Кемени-Янга — это избирательная система , в которой используются ранжированные бюллетени и подсчет попарных сравнений для определения наиболее популярных вариантов на выборах. Это метод Кондорсе, потому что, если есть победитель Кондорсе, он всегда будет считаться самым популярным выбором.
Этот метод присваивает балл каждой возможной последовательности, где каждая последовательность учитывает, какой выбор может быть наиболее популярным, какой выбор может быть вторым по популярности, какой выбор может быть третьим по популярности и так далее, вплоть до того, какой вариант может быть наименее популярным. популярный. Последовательность, набравшая наибольшее количество очков, является выигрышной, а первый выбор в выигрышной последовательности является самым популярным выбором. (Как объясняется ниже, ничья может возникнуть на любом уровне рейтинга.)
Метод Кемени-Янга также известен как правило Кемени , рейтинг популярности VoteFair , метод максимального правдоподобия и медианное отношение .
Метод Кемени-Янга использует избирательные бюллетени , в которых избиратели ранжируют выбор в соответствии со своими предпочтениями. Избирателю разрешено ранжировать более одного варианта на одном и том же уровне предпочтений. [ нужна цитата ] Варианты без рейтинга обычно интерпретируются как наименее предпочтительные.
Расчеты Кемени-Янга обычно выполняются в два этапа. Первым шагом является создание матрицы или таблицы, которая подсчитывает попарные предпочтения избирателей. Второй шаг — протестировать все возможные рейтинги , подсчитать балл для каждого такого рейтинга и сравнить результаты. Каждый рейтинговый балл равен сумме попарных оценок, применимых к этому рейтингу.
Рейтинг, набравший наибольшее количество баллов, считается общим рейтингом. (Если более одного рейтинга имеют один и тот же наибольший балл, все эти возможные рейтинги равны, и обычно общий рейтинг включает одну или несколько связей.)
Другой способ просмотреть порядок состоит в том, что он минимизирует сумму тау-расстояний Кендалла ( расстояние пузырьковой сортировки ) до списков избирателей.
Чтобы продемонстрировать, как индивидуальный порядок предпочтений преобразуется в итоговую таблицу, стоит рассмотреть следующий пример. Предположим, что один избиратель имеет выбор среди четырех кандидатов (т. е. Эллиота, Мередита, Роланда и Селдена) и имеет следующий порядок предпочтений:
Эти предпочтения могут быть выражены в сводной таблице. Таблица подсчета голосов, в которой все попарные подсчеты расположены в трех столбцах, полезна для подсчета (подсчета) предпочтений в бюллетенях и расчета рейтинговых баллов. В центральном столбце отслеживаются случаи, когда избиратель указывает более одного варианта выбора на одном и том же уровне предпочтений. Вышеупомянутый порядок предпочтений можно выразить в виде следующей таблицы:
Теперь предположим, что несколько избирателей проголосовали за этих четырех кандидатов. После подсчета всех бюллетеней можно использовать одну и ту же таблицу подсчета голосов для суммирования всех предпочтений всех избирателей. Вот пример случая, в котором 100 избирателей:
Сумма подсчетов в каждой строке должна равняться общему количеству голосов.
После заполнения итоговой таблицы поочередно исследуется каждый возможный рейтинг вариантов, и его рейтинговый балл рассчитывается путем сложения соответствующего числа из каждой строки итоговой таблицы. Например, возможный рейтинг:
удовлетворяет предпочтениям Эллиот > Роланд, Эллиот > Мередит, Эллиот > Селден, Роланд > Мередит, Роланд > Селден и Мередит > Селден. Соответствующие баллы, взятые из таблицы, равны
давая общий рейтинговый балл 30 + 60 + 60 + 70 + 60 + 40 = 320.
После подсчета баллов для каждого возможного рейтинга можно определить рейтинг, имеющий наибольшую оценку, и он становится общим рейтингом. В этом случае общий рейтинг выглядит следующим образом:
с рейтингом 370.
Если есть циклы или ничьи, более одного возможного рейтинга может иметь один и тот же наибольший балл. Циклы разрешаются путем создания единого общего рейтинга, в котором некоторые варианты выбора связаны между собой. [ нужны разъяснения ]
После расчета общего рейтинга результаты парных сравнений можно сгруппировать в сводную матрицу, как показано ниже, в которой варианты располагаются в выигрышном порядке от самого популярного (сверху и слева) до наименее популярного (снизу и справа). Этот матричный макет не включает парные подсчеты с равными предпочтениями, которые появляются в итоговой таблице: [1]
В этой сводной матрице наибольший рейтинговый балл равен сумме значений в верхней правой треугольной половине матрицы (показаны здесь жирным шрифтом на зеленом фоне). Никакой другой возможный рейтинг не может иметь сводную матрицу, которая дает более высокую сумму чисел в верхней правой треугольной половине. (Если бы это было так, это был бы общий рейтинг.)
В этой сводной матрице сумма чисел в нижней левой треугольной половине матрицы (показанной здесь на красном фоне) является минимальной. В академических статьях Джона Кемени и Пейтона Янга [2] [3] говорится о нахождении этой минимальной суммы, которая называется оценкой Кемени и которая основана на том, сколько избирателей выступают против (а не поддерживают) каждый парный порядок:
Предположим, что в Теннесси проводятся выборы по вопросу о местонахождении своей столицы . Население сосредоточено вокруг четырех крупных городов. Все избиратели хотят, чтобы столица была как можно ближе к ним. Возможные варианты:
Предпочтения избирателей каждого региона таковы:
Эта матрица суммирует соответствующие счетчики парных сравнений :
Метод Кемени-Янга упорядочивает подсчеты парных сравнений в следующей таблице:
The ranking score for the possible ranking of Memphis first, Nashville second, Chattanooga third, and Knoxville fourth equals (the unit-less number) 345, which is the sum of the following annotated numbers.
This table lists all the ranking scores:
The largest ranking score is 393, and this score is associated with the following possible ranking, so this ranking is also the overall ranking:
If a single winner is needed, the first choice, Nashville, is chosen. (In this example Nashville is the Condorcet winner.)
The summary matrix below arranges the pairwise counts in order from most popular (top and left) to least popular (bottom and right):
In this arrangement the largest ranking score (393) equals the sum of the counts in bold, which are in the upper-right, triangular half of the matrix (with a green background).
In all cases that do not result in an exact tie, the Kemeny–Young method identifies a most-popular choice, second-most popular choice, and so on.
A tie can occur at any preference level. Except in some cases where circular ambiguities are involved, the Kemeny–Young method only produces a tie at a preference level when the number of voters with one preference exactly matches the number of voters with the opposite preference.
All Condorcet methods, including the Kemeny–Young method, satisfy these criteria:
The Kemeny–Young method also satisfies these criteria:
In common with all Condorcet methods, the Kemeny–Young method fails these criteria (which means the described criteria do not apply to the Kemeny–Young method):
The Kemeny–Young method also fails these criteria (which means the described criteria do not apply to the Kemeny–Young method):
An algorithm for computing a Kemeny-Young ranking in time polynomial in the number of candidates is not known, and unlikely to exist since the problem is NP-hard[5] even if there are just 4 voters (even)[6][7] or 7 voters (odd).[8]
It has been reported[9] that calculation methods based on integer programming sometimes allowed the computation of full rankings for votes on as many as 40 candidates in seconds. However, certain 40-candidate 5-voter Kemeny elections generated at random were not solvable on a 3 GHz Pentium computer in a useful time bound in 2006.[9]
The Kemeny–Young method can be formulated as an instance of a more abstract problem, of finding weighted feedback arc sets in tournament graphs.[10] As such, many methods for the computation of feedback arc sets can be applied to this problem, including a variant of the Held–Karp algorithm that can compute the Kemeny–Young ranking of candidates in time , significantly faster for many candidates than the factorial time of testing all rankings.[11][12] There exists a polynomial-time approximation scheme for computing a Kemeny-Young ranking,[13] and there also exists a parameterized subexponential-time algorithm with running time O*(2O(√OPT)) for computing such a ranking.[10]
The Kemeny–Young method was developed by John Kemeny in 1959.[2]
In 1978, Peyton Young and Arthur Levenglick axiomatically characterized the method, showing that it is the unique neutral method satisfying consistency and the so-called quasi-Condorcet criterion.[3] It can also be characterized using consistency and a monotonicity property.[14] In other papers,[15][16][17][18]Young adopted an epistemic approach to preference aggregation: he supposed that there was an objectively 'correct', but unknown preference order over the alternatives, and voters receive noisy signals of this true preference order (cf. Condorcet's jury theorem.) Using a simple probabilistic model for these noisy signals, Young showed that the Kemeny–Young method was the maximum likelihood estimator of the true preference order. Young further argues that Condorcet himself was aware of the Kemeny-Young rule and its maximum-likelihood interpretation, but was unable to clearly express his ideas.
In the papers by John Kemeny and Peyton Young, the Kemeny scores use counts of how many voters oppose, rather than support, each pairwise preference,[2][3] but the smallest such score identifies the same overall ranking.
Since 1991 the method has been promoted under the name "VoteFair popularity ranking" by Richard Fobes.[19]
The following table compares the Kemeny-Young method with other single-winner election methods:
