Введение

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

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

Алгоритм вычисления ранжирования Кемени Янга во времени полиномиала по количеству кандидатов не известен, и вряд ли существует, поскольку проблема NP жесткая или 7 избирателей (нечетная). Сообщалось, что методы расчета, основанные на программировании целых чисел, иногда позволяли рассчитывать полный рейтинг голосов на целых 40 кандидатов за секунды. Однако некоторые выборы 40 кандидатов 5 избирателей Kemeny, сгенерированные случайным образом, не были решены на компьютере Pentium 3 ГГц в полезный срок в 2006 году. Существует многочленная схема приближения времени для вычисления рейтинга Кемени Янга, а также существует параметризированный субекспоненциальный алгоритм времени с временем выполнения O*(2O ) для вычисления такого рейтинга.