stringtranslate.com

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

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

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

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

Описание

Метод Кемени–Янга использует преференциальные бюллетени , в которых избиратели ранжируют варианты в соответствии с их порядком предпочтения. Избирателю разрешено ранжировать более одного варианта на одном и том же уровне предпочтения. [ необходима цитата ] Неранжированные варианты обычно интерпретируются как наименее предпочтительные.

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

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

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

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

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

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


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

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

  1. Эллиот
  2. Роланд
  3. Мередит
  4. Селден

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

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

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

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

  1. Роланд
  2. Эллиот
  3. Селден
  4. Мередит

с рейтинговым баллом 370.

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

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

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

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

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

Пример

  • в
  • т
  • е

Теннесси и его четыре крупных города: Мемфис на крайнем западе; Нэшвилл в центре; Чаттануга на востоке; и Ноксвилл на крайнем северо-востоке

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

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


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


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


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

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


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


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


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

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


В этой схеме наибольший рейтинговый балл (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] Таким образом, к этой задаче можно применить множество методов вычисления наборов дуг обратной связи, включая вариант алгоритма Хелда–Карпа , который может вычислять рейтинг Кемени–Янга кандидатов за время , значительно быстрее для многих кандидатов, чем факториальное время тестирования всех рейтингов. [11] [12] Существует полиномиальная схема аппроксимации для вычисления рейтинга Кемени–Янга, [13] а также существует параметризованный субэкспоненциальный алгоритм со временем выполнения O * (2 O( √ OPT ) ) для вычисления такого рейтинга. [10]

История

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

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

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

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

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

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



Примечания

  1. ^ Цифры в этом примере взяты из Примера выборов, использованного в Википедии. Архивировано 30 марта 2017 г. на Wayback Machine .
  2. ^ abc Джон Кемени, «Математика без чисел», Daedalus 88 (1959), стр. 577–591.
  3. ^ abc HP Young и A. Levenglick, «Последовательное расширение принципа выборов Кондорсе», SIAM Journal on Applied Mathematics 35 , № 2 (1978), стр. 285–300.
  4. ^ Джузеппе Мунда, «Социальная многокритериальная оценка для устойчивой экономики», стр. 124.
  5. ^ ab J. Bartholdi III, CA Tovey и MA Trick , «Схемы голосования, в которых может быть трудно сказать, кто победил на выборах», Social Choice and Welfare , том 6, № 2 (1989), стр. 157–165.
  6. ^ C. Dwork, R. Kumar, M. Naor, D. Sivakumar. Методы ранговой агрегации для Интернета, WWW10, 2001
  7. ^ Biedl, Therese ; Brandenburg, Franz J.; Deng, Xiaotie (2005-09-12). Healy, Patrick; Nikolov, Nikola S. (ред.). Crossings and Permutations . Lecture Notes in Computer Science. Springer Berlin Heidelberg. стр. 1–12. doi :10.1007/11618058_1. ISBN 9783540314257. S2CID  11189107.
  8. ^ Бахмайер, Георг; Брандт, Феликс; Гейст, Кристиан; Харренштейн, Пол; Кардель, Кейван; Петерс, Доминик; Зеедиг, Ханс Георг (01.11.2019). «k-большинство орграфов и сложность голосования с постоянным числом избирателей». Журнал компьютерных и системных наук . 105 : 130–157. arXiv : 1704.06304 . doi : 10.1016/j.jcss.2019.04.005. ISSN  0022-0000. S2CID  2357131.
  9. ^ ab Винсент Конитцер, Эндрю Дэвенпорт и Джайант Калагнанам, «Улучшенные границы для вычисления рейтингов Кемени» (2006).
  10. ^ ab Карпински, М. и Шуди, В., «Более быстрые алгоритмы для турнира по набору дуг обратной связи, агрегации рангов Кемени и турнира по промежуточности», в: Чонг, О., Чва, К.-Й. и Парк, К. (редакторы): 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. ^ Bodlaender, Hans L .; Fomin, Fedor V.; Koster, Arie MCA; Kratsch, Dieter; Thilikos, Dimitrios M. (2012), "Заметка о точных алгоритмах для задач упорядочения вершин на графах", Теория вычислительных систем , 50 (3): 420–432, doi :10.1007/s00224-011-9312-0, hdl : 1956/4556 , MR  2885638, S2CID  253742611
  13. ^ «Как ранжировать с минимальным количеством ошибок». http://cs.brown.edu/~claire/stoc07.pdf
  14. ^ Can, Burak; Storcken, Ton (2013-03-01). "Обновить правила монотонного предпочтения" (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, «Оптимальное ранжирование и выбор из парных сравнений», в книге « Объединение информации и принятие групповых решений» под редакцией B. Grofman и G. Owen (1986), JAI Press, стр. 113–122.
  17. ^ HP Young, «Оптимальные правила голосования», Журнал экономических перспектив 9 , № 1 (1995), стр. 51–64.
  18. ^ HP Young, «Групповой выбор и индивидуальные суждения», Глава 9 « Перспектив общественного выбора: справочник» , под редакцией Денниса Мюллера (1997) Cambridge UP., стр. 181–200.
  19. ↑ Ричард Фобс, «Инструментарий творческого решателя проблем», ( ISBN 0-9632-2210-4 ), 1993, стр. 223–225. 

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