Метод Кемени – Янга - это избирательная система, в которой используются преференциальные бюллетени и подсчет парных сравнений для определения наиболее популярных вариантов выбора на выборах. Это метод Кондорсе, потому что, если есть победитель Кондорсе, он всегда будет считаться самым популярным выбором.
Этот метод присваивает оценку каждой возможной последовательности, где каждая последовательность учитывает, какой вариант может быть наиболее популярным, какой вариант может быть вторым по популярности, какой вариант может быть третьим по популярности и так далее, вплоть до того, какой вариант может быть наименее популярным популярный. Последовательность с наибольшим количеством очков - это выигрышная последовательность, а первый вариант в выигрышной последовательности - самый популярный выбор. (Как объясняется ниже, ничьи могут возникнуть на любом ранговом уровне.)
Метод Кемени-Янг также известен как правило Кемени , 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]
... над Роландом | ... над Эллиотом | ... над Селденом | ... над Мередит | |
Предпочитаю Роланда ... | - | 70 | 60 | 70 |
Предпочитаю Эллиота ... | 30 | - | 60 | 60 |
Предпочитаю Селдена ... | 40 | 40 | - | 50 |
Предпочитаю Мередит ... | 30 | 40 | 40 | - |
В этой итоговой матрице наибольший рейтинг равен сумме значений в правой верхней треугольной половине матрицы (выделенной здесь жирным шрифтом на зеленом фоне). Никакое другое возможное ранжирование не может иметь сводную матрицу, которая дает более высокую сумму чисел в правой верхней треугольной половине. (Если бы это было так, то это был бы общий рейтинг.)
В этой сводной матрице сумма чисел в нижней левой треугольной половине матрицы (показанной здесь на красном фоне) является минимальной. В научных статьях Джона Кемени и Пейтона Янга [2] [3] говорится о нахождении этой минимальной суммы, которая называется оценкой Кемени и которая основана на том, сколько избирателей возражают (а не поддерживают) каждый попарный порядок:
Методика | Занявший первое место |
---|---|
Кемени – Янг | Роланд |
Кондорсе | Роланд |
Мгновенное голосование во втором туре | Эллиот или Селден (в зависимости от того, как будет решена ничья во втором раунде) |
Множество | Selden |
Пример
Представьте, что в Теннесси проводятся выборы по месту нахождения своей столицы . Население Теннесси сосредоточено вокруг четырех крупных городов, которые разбросаны по всему штату. Для этого примера предположим, что весь электорат проживает в этих четырех городах и что каждый хочет жить как можно ближе к столице.
Кандидатами в капитал являются:
- Мемфис , крупнейший город штата, с 42% голосовавших, но расположенный далеко от других городов.
- Нашвилл , с 26% избирателей, недалеко от центра штата
- Ноксвилл , с 17% избирателей
- Чаттануга , с 15% избирателей
Предпочтения избирателей можно разделить так:
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]
Сообщалось [8], что методы расчета, основанные на целочисленном программировании, иногда позволяли вычислять полные рейтинги голосов за 40 кандидатов за секунды. Тем не менее, некоторые выборы Кемени с 40 кандидатами и 5 голосами, сгенерированные случайным образом, не были решены на компьютере Pentium с тактовой частотой 3 ГГц за полезный временной интервал в 2006 году. [8]
Обратите внимание, что сложность вычислений линейно зависит от количества избирателей, поэтому время, необходимое для обработки данного набора голосов, зависит от количества кандидатов [9], а не от количества голосов , ограничивая важность этого ограничения выборами, на которых Избиратели могут эффективно рассматривать значительно больше, чем обычные семь пунктов рабочей памяти .
Существует схема полиномиального приближения для вычисления ранжирования Кемени-Янга [10], а также существует параметризованный субэкспоненциальный алгоритм со временем выполнения O * (2 O ( √ OPT ) ) для вычисления такого ранжирования. [11]
История
Метод Кемени – Янга был разработан Джоном Кемени в 1959 г. [2]
В 1978 году Пейтон Янг и Артур Левенглик показали [3], что этот метод является единственным нейтральным методом, удовлетворяющим подкрепление и разновидностью критерия Кондорсе. В других статьях [12] [13] [14] [15] Янг использовал эпистемический подход к агрегации предпочтений: он предположил, что существует объективно «правильный», но неизвестный порядок предпочтений по сравнению с альтернативами, и избиратели получают шумные сигналы. этого истинного порядка предпочтения (см . теорему жюри Кондорсе ). Используя простую вероятностную модель для этих зашумленных сигналов, Янг показал, что метод Кемени – Янга является оценкой максимального правдоподобия истинного порядка предпочтения. Янг далее утверждает, что сам Кондорсе знал о правиле Кемени-Янга и его интерпретации с максимальной вероятностью, но не мог четко выразить свои идеи.
В статьях Джона Кемени и Пейтона Янга для оценки Кемени используется подсчет количества избирателей, выступающих против, а не поддерживающих каждое парное предпочтение [2] [3], но наименьшая такая оценка определяет тот же общий рейтинг.
С 1991 года метод продвигается Ричардом Фобсом под названием «Рейтинг популярности VoteFair». [16]
Сравнительная таблица
В следующей таблице сравнивается метод Кемени-Янга с другими методами преференциальных выборов с одним победителем:
Система | Монотонный | Кондорсе | Большинство | Кондорсе неудачник | Проигравший по большинству | Взаимное большинство | Смит | ISDA | LIIA | Независимость клонов | Обратная симметрия | Участие , последовательность | Позже - без вреда | Позже без помощи | Полиномиальное время | Разрешимость |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Шульце | да | да | да | да | да | да | да | да | Нет | да | да | Нет | Нет | Нет | да | да |
Ранжированные пары | да | да | да | да | да | да | да | да | да | да | да | Нет | Нет | Нет | да | да |
Разделенный цикл | да | да | да | да | да | да | да | да | Нет | да | да | Нет | Нет | Нет | да | Нет |
Альтернатива приливного человека | Нет | да | да | да | да | да | да | да | Нет | да | Нет | Нет | Нет | Нет | да | да |
Кемени – Янг | да | да | да | да | да | да | да | да | да | Нет | да | Нет | Нет | Нет | Нет | да |
Copeland | да | да | да | да | да | да | да | да | Нет | Нет | да | Нет | Нет | Нет | да | Нет |
Nanson | Нет | да | да | да | да | да | да | Нет | Нет | Нет | да | Нет | Нет | Нет | да | да |
Чернить | да | да | да | да | да | Нет | Нет | Нет | Нет | Нет | да | Нет | Нет | Нет | да | да |
Мгновенное голосование | Нет | Нет | да | да | да | да | Нет | Нет | Нет | да | Нет | Нет | да | да | да | да |
Смит / IRV | Нет | да | да | да | да | да | да | да | Нет | да | Нет | Нет | Нет | Нет | да | да |
Борда | да | Нет | Нет | да | да | Нет | Нет | Нет | Нет | Нет | да | да | Нет | да | да | да |
Геллер-ИРВ | Нет | Нет | да | да | да | да | Нет | Нет | Нет | Нет | Нет | Нет | Нет | Нет | да | да |
Болдуин | Нет | да | да | да | да | да | да | Нет | Нет | Нет | Нет | Нет | Нет | Нет | да | да |
Баклин | да | Нет | да | Нет | да | да | Нет | Нет | Нет | Нет | Нет | Нет | Нет | да | да | да |
Множество | да | Нет | да | Нет | Нет | Нет | Нет | Нет | Нет | Нет | Нет | да | да | да | да | да |
Условное голосование | Нет | Нет | да | да | да | Нет | Нет | Нет | Нет | Нет | Нет | Нет | да | да | да | да |
Кумбс [17] | Нет | Нет | да | да | да | да | Нет | Нет | Нет | Нет | Нет | Нет | Нет | Нет | да | да |
MiniMax | да | да | да | Нет | Нет | Нет | Нет | Нет | Нет | Нет | Нет | Нет | Нет | Нет | да | да |
Анти-плюрализм [17] | да | Нет | Нет | Нет | да | Нет | Нет | Нет | Нет | Нет | Нет | да | Нет | Нет | да | да |
Выборочное голосование в Шри-Ланке | Нет | Нет | да | Нет | Нет | Нет | Нет | Нет | Нет | Нет | Нет | Нет | да | да | да | да |
Дополнительное голосование | Нет | Нет | да | Нет | Нет | Нет | Нет | Нет | Нет | Нет | Нет | Нет | да | да | да | да |
Доджсон [17] | Нет | да | да | Нет | Нет | Нет | Нет | Нет | Нет | Нет | Нет | Нет | Нет | Нет | Нет | да |
Заметки
- ^ Цифры в этом примере взяты из Примеров выборов, использованных в Википедии, заархивированных 30 марта 2017 г. на Wayback Machine .
- ^ a b c Джон Кемени, «Математика без чисел», Дедал 88 (1959), стр. 577–591.
- ^ a b c Х. П. Янг и А. Левенглик, « Последовательное расширение принципа выборов Кондорсе », SIAM Journal on Applied Mathematics 35 , no. 2 (1978), стр. 285–300.
- ^ Джузеппе Мунда, "Социальная многокритериальная оценка для устойчивой экономики", стр. 124.
- ^ a b Дж. Бартольди III, К. А. Тови и М. А. Трик , «Схемы голосования, по которым бывает трудно сказать, кто победил на выборах», Social Choice and Welfare , Vol. 6, № 2 (1989), стр. 157–165.
- ^ К. Дворк, Р. Кумар, М. Наор, Д. Сивакумар. Методы ранжирования в Интернете, WWW10, 2001 г.
- ^ Бидль, Тереза ; Бранденбург, Франц Дж .; Дэн Сяотэ (12 сентября 2005 г.). Хили, Патрик; Николов, Никола С. (ред.). Пересечения и перестановки . Конспект лекций по информатике. Springer Berlin Heidelberg. С. 1–12. DOI : 10.1007 / 11618058_1 . ISBN 9783540314257.
- ^ a b Винсент Конитцер, Эндрю Дэвенпорт и Джаянт Калагнанам, « Улучшенные границы для вычисления рейтинга Кемени » (2006).
- ^ «Рейтинговая служба VoteFair» .
- ^ «Как ранжировать с несколькими ошибками». http://cs.brown.edu/~claire/stoc07.pdf
- ^ Карпинский, М. и Schudy, W., "быстрые алгоритмы для обратной связи Arc Set Tournament, Кемени Ранк агрегирование и промежуточность турнира" , в: Чонг, О., Chwa, K.-Y. и Парк, К. (ред .): ISAAC 2010, часть I, LNCS 6506, стр. 3-14.
- ↑ HP Young, «Теория голосования Кондорсе», American Polit 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 Янг, «Групповой выбор и индивидуальные суждения», Глава 9 Перспективы общественного выбора: справочник , отредактированный Деннисом Мюллером (1997) Cambridge UP., Стр.181–200.
- ^ Ричард Фобс, "Набор инструментов творческого решателя проблем", ( ISBN 0-9632-2210-4 ), 1993, стр. 223–225.
- ^ a b c Предполагается, что антимножественность, Кумбс и Доджсон получают усеченные предпочтения, равномерно распределяя возможные рейтинги не включенных в список альтернатив; например, бюллетень A> B = C засчитывается как A> B> C и A> C> B. Если предполагается, что эти методы не получают усеченных предпочтений, то later-no-damage и later-no-help неприменимы.
Внешние ссылки
- VoteFair.org - веб-сайт, на котором рассчитываются результаты Кемени – Янга. Для сравнения он также вычисляет победителя согласно множественности, Кондорсе, подсчету Борда и другим методам голосования.
- VoteFair_Ranking.cpp - программа на C ++, доступная на GitHub под лицензией MIT, которая вычисляет результаты рейтинга VoteFair, включая вычисления Кондорсе-Кемени.
- PHP- библиотека Condorcet Class, поддерживающая несколько методов Кондорсе, включая метод Кемени – Янга.
- Программа C ++ для агрегирования предпочтений Кемени-Янга - программа командной строки для быстрого вычисления результатов Кемени-Янга в виде исходного кода и скомпилированных двоичных файлов для Windows и Linux. Открытый исходный код, за исключением использования числовых рецептов .
- Программа C для агрегирования предпочтений Кемени-Янга - реализует алгоритм Давенпорта без каких-либо других библиотечных зависимостей. Открытый исходный код, лицензия LGPL. Привязка Ruby к библиотеке также имеет открытый исходный код и лицензию LPGL.
- Оптимальное агрегирование рангов Кемени-Янга в Python - Учебное пособие, использующее простую формулировку в виде целочисленной программы и адаптируемое к другим языкам с привязкой к lpsolve.