WikiDer > Метод Кемени – Янга
Часть Политика серии |
Избирательные системы |
---|
Множественность / мажоритарность
|
|
Другие системы и родственная теория |
Политический портал |
В Метод Кемени – Янга является избирательная система который использует преференциальные бюллетени и попарное сравнение имеет значение для определения наиболее популярных выборов на выборах. Это Метод Кондорсе потому что, если есть победитель Кондорсе, он всегда будет считаться самым популярным выбором.
Этот метод присваивает оценку каждой возможной последовательности, где каждая последовательность учитывает, какой вариант может быть наиболее популярным, какой вариант может быть вторым по популярности, какой вариант может быть третьим по популярности, и так далее, вплоть до того, какой вариант может быть наименее популярным. популярный. Последовательность, которая имеет наибольшее количество очков, является выигрышной последовательностью, а первый вариант в выигрышной последовательности - самый популярный выбор. (Как объясняется ниже, ничьи могут возникнуть на любом ранговом уровне.)
Метод Кемени – Янга также известен как Правило Кемени, Рейтинг популярности 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 |
Сумма подсчетов в каждой строке должна равняться общему количеству голосов.
После того, как таблица подсчета была заполнена, каждое возможное ранжирование вариантов выбора исследуется по очереди, и ее рейтинг ранжирования вычисляется путем добавления соответствующего числа из каждой строки таблицы подсчета. Например, возможный рейтинг:
- Эллиот
- Роланд
- Мередит
- Selden
удовлетворяет предпочтениям Эллиот> Роланд, Эллиот> Мередит, Эллиот> Селден, Роланд> Мередит, Роланд> Селден и Мередит> Селден. Соответствующие баллы, взятые из таблицы, являются
- Эллиот> Роланд: 30
- Эллиот> Мередит: 60
- Эллиот> Селден: 60
- Роланд> Мередит: 70
- Роланд> Селден: 60
- Мередит> Селден: 40
что дает общий рейтинг 30 + 60 + 60 + 70 + 60 + 40 = 320.
Расчет общего рейтинга
После того, как будут подсчитаны баллы для каждого возможного ранжирования, можно определить рейтинг, имеющий наибольший балл, и он станет общим рейтингом. В этом случае общий рейтинг будет следующим:
- Роланд
- Эллиот
- Selden
- Мередит
с рейтинговой оценкой 370.
Если есть циклы или ничья, более чем один возможный рейтинг может иметь одинаковое наибольшее количество очков. Циклы решаются путем создания единого общего рейтинга, в котором некоторые из вариантов связаны.[требуется разъяснение]
Сводная матрица
После расчета общего рейтинга подсчеты попарных сравнений можно упорядочить в сводной матрице, как показано ниже, в которой варианты выбора отображаются в порядке выигрыша от наиболее популярных (вверху и слева) до наименее популярных (внизу и справа). Этот макет матрицы не включает парные подсчеты равного предпочтения, которые появляются в таблице подсчета:[1]
... над Роланд | ... над Эллиот | ... над Selden | ... над Мередит | |
Предпочитать Роланд ... | - | 70 | 60 | 70 |
Предпочитать Эллиот ... | 30 | - | 60 | 60 |
Предпочитать Selden ... | 40 | 40 | - | 50 |
Предпочитать Мередит ... | 30 | 40 | 40 | - |
В этой сводной матрице наивысший рейтинг равен сумме значений в правой верхней треугольной половине матрицы (выделенной здесь жирным шрифтом на зеленом фоне). Никакой другой возможный рейтинг не может иметь сводную матрицу, которая дает более высокую сумму чисел в правой верхней треугольной половине. (Если бы это было так, то это был бы общий рейтинг.)
В этой сводной матрице сумма чисел в левой нижней треугольной половине матрицы (показанной здесь на красном фоне) является минимальной. Научные статьи Джона Кемени и Пейтона Янга[2][3] относятся к поиску этой минимальной суммы, которая называется оценкой Кемени и которая основана на том, сколько избирателей против (а не поддерживают) каждый попарный порядок:
Метод | Первое место |
---|---|
Кемени – Янг | Роланд |
Кондорсе | Роланд |
Мгновенное голосование во втором туре | Эллиот или Селден (в зависимости от того, как будет решена ничья во втором туре) |
Множество | Selden |
Пример
Представьте себе, что Теннесси проходит выборы по месту нахождения капитал. Население Теннесси сосредоточено вокруг четырех крупных городов, расположенных по всему штату. В этом примере предположим, что весь электорат живет в этих четырех городах, и каждый хочет жить как можно ближе к столице.
Кандидатами в капитал являются:
- Мемфис, крупнейший город штата, с 42% голосовавших, но расположенный далеко от других городов
- Нашвилл, с 26% избирателей, недалеко от центра штата
- Knoxville, при 17% голосовавших
- Чаттануга, с 15% голосовавших
Предпочтения избирателей можно разделить так:
42% проголосовавших (недалеко от Мемфиса) | 26% проголосовавших (недалеко от Нэшвилла) | 15% проголосовавших (недалеко от Чаттануги) | 17% проголосовавших (недалеко от Ноксвилля) |
---|---|---|---|
|
|
|
|
Эта матрица суммирует соответствующие попарное сравнение подсчитывает:
... над Мемфис | ... над Нашвилл | ... над Чаттануга | ... над Knoxville | |
Предпочитать Мемфис ... | - | 42% | 42% | 42% |
Предпочитать Нашвилл ... | 58% | - | 68% | 68% |
Предпочитать Чаттануга ... | 58% | 32% | - | 83% |
Предпочитать Knoxville ... | 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% предпочитают Чаттанугу Ноксвиллу
В этой таблице перечислены все рейтинговые баллы:
Первый выбор | Второй выбор | В третьих выбор | Четвертый выбор | Рейтинг счет |
---|---|---|---|---|
Мемфис | Нашвилл | Чаттануга | Knoxville | 345 |
Мемфис | Нашвилл | Knoxville | Чаттануга | 279 |
Мемфис | Чаттануга | Нашвилл | Knoxville | 309 |
Мемфис | Чаттануга | Knoxville | Нашвилл | 273 |
Мемфис | Knoxville | Нашвилл | Чаттануга | 243 |
Мемфис | Knoxville | Чаттануга | Нашвилл | 207 |
Нашвилл | Мемфис | Чаттануга | Knoxville | 361 |
Нашвилл | Мемфис | Knoxville | Чаттануга | 295 |
Нашвилл | Чаттануга | Мемфис | Knoxville | 377 |
Нашвилл | Чаттануга | Knoxville | Мемфис | 393 |
Нашвилл | Knoxville | Мемфис | Чаттануга | 311 |
Нашвилл | Knoxville | Чаттануга | Мемфис | 327 |
Чаттануга | Мемфис | Нашвилл | Knoxville | 325 |
Чаттануга | Мемфис | Knoxville | Нашвилл | 289 |
Чаттануга | Нашвилл | Мемфис | Knoxville | 341 |
Чаттануга | Нашвилл | Knoxville | Мемфис | 357 |
Чаттануга | Knoxville | Мемфис | Нашвилл | 305 |
Чаттануга | Knoxville | Нашвилл | Мемфис | 321 |
Knoxville | Мемфис | Нашвилл | Чаттануга | 259 |
Knoxville | Мемфис | Чаттануга | Нашвилл | 223 |
Knoxville | Нашвилл | Мемфис | Чаттануга | 275 |
Knoxville | Нашвилл | Чаттануга | Мемфис | 291 |
Knoxville | Чаттануга | Мемфис | Нашвилл | 239 |
Knoxville | Чаттануга | Нашвилл | Мемфис | 255 |
Наибольшая оценка рейтинга составляет 393, и эта оценка связана со следующим возможным рейтингом, поэтому этот рейтинг также является общим рейтингом:
Предпочтение порядок | Выбор |
---|---|
Первый | Нашвилл |
Второй | Чаттануга |
В третьих | Knoxville |
Четвертый | Мемфис |
Если требуется единственный победитель, выбирается первый вариант - Нэшвилл. (В этом примере Нэшвилл - это Кондорсе победитель.)
Сводная матрица ниже упорядочивает попарные подсчеты в порядке от наиболее популярных (вверху и слева) до наименее популярных (внизу и справа):
... над Нашвилл ... | ... над Чаттануга ... | ... над Knoxville ... | ... над Мемфис ... | |
Предпочитать Нашвилл ... | - | 68% | 68% | 58% |
Предпочитать Чаттануга ... | 32% | - | 83% | 58% |
Предпочитать Knoxville ... | 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]
Сообщается[8] что методы расчета на основе целочисленное программирование иногда позволял подсчитывать полные рейтинги за голоса до 40 кандидатов за секунды. Тем не менее, некоторые выборы Кемени с 40 кандидатами и 5 голосами, сгенерированные случайным образом, не были решены на компьютере Pentium с тактовой частотой 3 ГГц в 2006 году.[8]
Обратите внимание, что сложность вычислений линейно зависит от количества избирателей, поэтому время, необходимое для обработки данного набора голосов, во многом зависит от количества голосов. кандидаты[9] а не количество голосов, ограничивая важность этого ограничения выборами, на которых избиратели могут эффективно рассматривать значительно больше, чем обычные семь пунктов оперативной памяти.
Существует схема полиномиальной аппроксимации для расчета рейтинга Кемени-Янга,[10] а также существует параметризованный алгоритм субэкспоненциального времени с временем работы O*(2O (√OPT)) для вычисления такого рейтинга.[11]
История
Метод Кемени – Янга был разработан Джон Кемени в 1959 г.[2]
В 1978 г. Пейтон Янг и Артур Левенглик показал[3] что этот метод был единственным нейтральным методом, удовлетворяющим подкрепление и разновидностью критерия Кондорсе. В других статьях[12][13][14][15]Янг усыновил эпистемический подход к агрегации предпочтений: он предположил, что существует объективно `` правильный '', но неизвестный порядок предпочтений по сравнению с альтернативами, и избиратели получают шумные сигналы этого истинного порядка предпочтений (см. Теорема присяжных Кондорсе.) Используя простую вероятностную модель для этих зашумленных сигналов, Янг показал, что метод Кемени – Янга был оценщик максимального правдоподобия истинного порядка предпочтений. Янг далее утверждает, что Кондорсе Сам был осведомлен о правиле Кемени-Янга и его максимально правдоподобной интерпретации, но не мог четко выразить свои идеи.
В статьях Джона Кемени и Пейтона Янга для оценки Кемени используется подсчет количества избирателей, которые выступают против, а не поддерживают каждое парное предпочтение.[2][3] но наименьшая такая оценка определяет тот же общий рейтинг.
С 1991 года Ричард Фобс продвигает этот метод под названием «Рейтинг популярности VoteFair».[16]
Сравнительная таблица
В следующей таблице сравнивается метод Кемени-Янга с другими льготный методы выборов с одним победителем:
Система | Монотонный | Кондорсе | Большинство | Кондорсе неудачник | Неудачник большинства | Взаимное большинство | Смит | ISDA | LIIA | Независимость клонов | Обратная симметрия | Участие, последовательность | Позже без вреда | Позже - без помощи | Полиномиальное время | Разрешимость |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Шульце | да | да | да | да | да | да | да | да | Нет | да | да | Нет | Нет | Нет | да | да |
Ранжированные пары | да | да | да | да | да | да | да | да | да | да | да | Нет | Нет | Нет | да | да |
Альтернатива приливного человека | Нет | да | да | да | да | да | да | да | Нет | да | Нет | Нет | Нет | Нет | да | да |
Кемени – Янг | да | да | да | да | да | да | да | да | да | Нет | да | Нет | Нет | Нет | Нет | да |
Copeland | да | да | да | да | да | да | да | да | Нет | Нет | да | Нет | Нет | Нет | да | Нет |
Nanson | Нет | да | да | да | да | да | да | Нет | Нет | Нет | да | Нет | Нет | Нет | да | да |
Чернить | да | да | да | да | да | Нет | Нет | Нет | Нет | Нет | да | Нет | Нет | Нет | да | да |
Мгновенное голосование | Нет | Нет | да | да | да | да | Нет | Нет | Нет | да | Нет | Нет | да | да | да | да |
Борда | да | Нет | Нет | да | да | Нет | Нет | Нет | Нет | Нет | да | да | Нет | да | да | да |
Болдуин | Нет | да | да | да | да | да | да | Нет | Нет | Нет | Нет | Нет | Нет | Нет | да | да |
Баклин | да | Нет | да | Нет | да | да | Нет | Нет | Нет | Нет | Нет | Нет | Нет | да | да | да |
Множество | да | Нет | да | Нет | Нет | Нет | Нет | Нет | Нет | Нет | Нет | да | да | да | да | да |
Условное голосование | Нет | Нет | да | да | да | Нет | Нет | Нет | Нет | Нет | Нет | Нет | да | да | да | да |
Кумбс[17] | Нет | Нет | да | да | да | да | Нет | Нет | Нет | Нет | Нет | Нет | Нет | Нет | да | да |
MiniMax | да | да | да | Нет | Нет | Нет | Нет | Нет | Нет | Нет | Нет | Нет | Нет | Нет | да | да |
Анти-множественность[17] | да | Нет | Нет | Нет | да | Нет | Нет | Нет | Нет | Нет | Нет | да | Нет | Нет | да | да |
Шри-ланкийское условное голосование | Нет | Нет | да | Нет | Нет | Нет | Нет | Нет | Нет | Нет | Нет | Нет | да | да | да | да |
Дополнительное голосование | Нет | Нет | да | Нет | Нет | Нет | Нет | Нет | Нет | Нет | Нет | Нет | да | да | да | да |
Доджсон[17] | Нет | да | да | Нет | Нет | Нет | Нет | Нет | Нет | Нет | Нет | Нет | Нет | Нет | Нет | да |
Примечания
- ^ Цифры в этом примере адаптированы из Примеры выборов, использованные в Википедии В архиве 2017-03-30 в Wayback Machine.
- ^ а б c Джон Кемени, «Математика без чисел», Дедал 88 (1959), стр. 577–591.
- ^ а б c Х. П. Янг и А. Левенглик "Последовательное расширение избирательного принципа Кондорсе", Журнал SIAM по прикладной математике 35, нет. 2 (1978), стр. 285–300.
- ^ Джузеппе Мунда, "Многокритериальная социальная оценка для устойчивой экономики", стр. 124.
- ^ а б Дж. Бартольди III, К. А. Тови и М. А. Трюк, «Схемы голосования, по которым сложно определить, кто победил на выборах», Социальный выбор и благосостояние, Vol. 6, № 2 (1989), стр. 157–165.
- ^ К. Дворк, Р. Кумар, М. Наор, Д. Сивакумар. Методы ранжирования в Интернете, WWW10, 2001 г.
- ^ Бидль, Тереза; Бранденбург, Франц Дж .; Дэн Сяотэ (12 сентября 2005 г.). Хили, Патрик; Николов, Никола С. (ред.). Пересечения и перестановки. Конспект лекций по информатике. Springer Berlin Heidelberg. С. 1–12. Дои:10.1007/11618058_1. ISBN 9783540314257.
- ^ а б Винсент Конитцер, Эндрю Давенпорт и Джаянт Калагнанам "Улучшены оценки для расчета рейтинга Кемени" (2006).
- ^ «Рейтинговая служба VoteFair».
- ^ «Как ранжировать с несколькими ошибками». http://cs.brown.edu/~claire/stoc07.pdf
- ^ Карпинский М. и Шуди В., «Более быстрые алгоритмы для турнира по набору дуг обратной связи, агрегирования рангов Кемени и турнира по промежуточным отношениям», in: Cheong, O., Chwa, K.-Y., and Park, K. (Eds.): ISAAC 2010, Part I, LNCS 6506, pp. 3-14.
- ^ Х. П. Янг, "Теория голосования Кондорсе", Обзор американской политической науки 82, нет. 2 (1988), стр. 1231–1244.
- ^ Х. П. Янг, «Оптимальное ранжирование и выбор из парных сравнений», в Объединение информации и групповое принятие решений под редакцией Б. Грофмана и Г. Оуэна (1986), JAI Press, стр. 113–122.
- ^ Х. П. Янг, "Оптимальные правила голосования", Журнал экономических перспектив 9, № 1 (1995), стр. 51–64.
- ^ Х. П. Янг, "Групповой выбор и индивидуальные суждения", глава 9 Перспективы общественного выбора: справочник, отредактированный Деннисом Мюллером (1997) Cambridge UP., pp.181–200.
- ^ Ричард Фобс, "Набор инструментов творческого лица для решения проблем", (ISBN 0-9632-2210-4), 1993, с. 223–225.
- ^ а б c Предполагается, что анти-множественность, Кумбс и Доджсон получают усеченные предпочтения, равномерно распределяя возможные рейтинги неуказанных альтернатив; например, бюллетень A> B = C засчитывается как A> B> C и A> C> B. Если предполагается, что эти методы не получают усеченные предпочтения, тогда позже без вреда и позже-без помощи не применимы.
внешняя ссылка
- VoteFair.org - Веб-сайт, на котором рассчитываются результаты Кемени – Янга. Для сравнения он также вычисляет победителя согласно множественности, подсчету Кондорсе, подсчету Борда и другим методам голосования.
- VoteFair_Ranking.cpp - Программа на C ++, доступная на GitHub под лицензией MIT, которая вычисляет результаты рейтинга VoteFair, включая вычисления Кондорсе-Кемени.
- Кондорсе Класс PHP библиотека поддержка нескольких методов Кондорсе, включая метод Кемени – Янга.
- Программа C ++ для агрегирования предпочтений Кемени-Янга - Программа командной строки для быстрого расчета результатов Кемени-Янга в виде исходного кода и скомпилированных двоичных файлов для Windows и Linux. Открытый исходный код, кроме случаев использования Числовые рецепты.
- Программа C для объединения предпочтений Кемени-Янга - Реализует алгоритм Давенпорта без зависимостей от других библиотек. Открытый исходный код, лицензия LGPL. Привязка Ruby к библиотеке также имеет открытый исходный код, лицензируется LPGL.
- Оптимальное ранговое агрегирование Кемени-Янга в Python - Учебник, использующий простую формулировку целочисленной программы и адаптируемый к другим языкам с привязкой к lpsolve.