Ранговые пары

Ранговые пары (RP) или метод Тайдмана - это избирательная система разработан в 1987 г. Николаем Тидеманом, который выбирает единственного победителя с помощью голосов, выражающих предпочтения. RP также можно использовать для создания отсортированного списка победителей.

Если есть кандидат, который предпочтительнее других кандидатов, при сравнении, в свою очередь, с каждым из остальных, RP гарантирует, что кандидат победит. Благодаря этому свойству RP по определению является методом Кондорсе.

• 1 Процедура
  • 1.1 Подсчет
  • 1.2 Сортировка
  • 1.3 Блокировка
  • 1.4 Победитель
• 2 Пример
  • 2.1 Ситуация
  • 2.2 Подсчет
  • 2.3 Сортировка
  • 2.4 Блокировка
  • 2.5 Пример разрешения неоднозначности
  • 2.6 Резюме
• 3 Критерии
  • 3.1 Независимость нерелевантных альтернатив
  • 3.2 Сравнительная таблица
• 4 Ссылки
• 5 Внешние ссылки

Процедура RP (Ранговая пара) выглядит следующим образом:

1. Подсчитайте количество голосов, сравнивая каждую пару кандидатов, и определить победителя каждой пары (при условии, что нет равного числа)
2. Сортировка (ранжирование) каждой пары по наибольшей силе победы от первой к наименьшей последней.
3. «Зафиксируйте» каждую пару, начиная с той, у которой больше всего выигравших голосов, и добавьте один по очереди к графику, пока они не создадут цикл (что создало бы двусмысленность). Заполненный график показывает победителя.

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

Подсчет

Чтобы подсчитать голоса, учитывайте предпочтения каждого избирателя. Например, если избиратель заявляет «A>B>C» (A лучше, чем B, а B лучше, чем C), в результате должен быть добавлен один для A в A по сравнению с B, один для A в A по сравнению с C., и один для B в B против C. Избиратели также могут выражать безразличие (например, A = B), и предполагается, что неустановленные кандидаты равны заявленным кандидатам.

После подсчета голосов можно определить большинство. Если «Vxy» - это количество голосов, которые ставят x выше y, то «x» выигрывает, если Vxy>Vyx, и «y» выигрывает, если Vyx>Vxy.

Сортировка

Пары победителей, называемые «большинством», затем сортируются от наибольшего большинства до наименьшего. Большинство для x над y предшествует большинству для z над w тогда и только тогда, когда выполняется одно из следующих условий:

1. Vxy>Vzw. Другими словами, первое место занимает большинство, имеющее большую поддержку его альтернативы.
2. Vxy = Vzw и Vwz>Vyx. Если большинство равны, то большинство с меньшим противником меньшинства занимает первое место.

Блокировка

Следующим шагом является проверка каждой пары по очереди, чтобы определить пары, которые «фиксируются».

1. Зафиксируйте первую отсортированную пару с наибольшим большинством.
2. Оцените следующую пару на предмет того, возникает ли цикл Кондорсе, когда эта пара добавляется к заблокированным парам.
3. Если цикл является обнаружена, оцениваемая пара пропускается.
4. Если цикл не обнаружен, оцениваемая пара блокируется с другими заблокированными парами.
5. Возвращайтесь к этапу № 2, пока не будут выполнены все пары.

Оценку цикла Кондорсе можно визуализировать, нарисовав стрелку от победителя пары к проигравшей паре на ориентированном графе. Используя отсортированный список выше, заблокируйте каждую пару по очереди, если только пара не создаст замкнутость на графике (например, где A больше B, B больше C, но C больше A).

Победитель

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

Ситуация

• v
• t

Представьте себе, что Теннесси проводит выборы на месте столицы. Население Теннесси сосредоточено вокруг четырех крупных городов, расположенных по всему штату. Для этого примера предположим, что весь электорат проживает в этих четырех городах и что каждый хочет жить как можно ближе к столице.

Кандидатами в столицу являются:

• Мемфис, крупнейший город штата, с 42% голосовавших, но расположенный далеко от других городов
• Нашвилл, с 26 % избирателей, недалеко от центра штата
• Ноксвилл, с 17% избирателей
• Чаттануга, с 15% избирателей

Предпочтения избирателей будут разделены примерно так:

Результаты будут сведены в следующую таблицу:

• [A] указывает на избирателей, которые предпочли кандидата, указанного в заголовке столбца, кандидату, указанному в заголовке строки
• [B] указывает избирателей, которые предпочли кандидата, указанного в заголовке строки, кандидату, указанному в заголовке столбца

Tally

Сначала перечислите каждую пару и определите победителя:

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

Сортировать

Затем голоса сортируются. Наибольшее большинство - «Чаттануга над Ноксвиллом»; 83% избирателей предпочитают Чаттанугу. Нэшвилл (68%) опережает Чаттанугу и Ноксвилл со счетом 68% против 32% (ничья, маловероятная в реальной жизни для такого количества избирателей). Поскольку Чаттануга>Ноксвилл, а они проигравшие, сначала будут добавлены Нэшвилл против Ноксвилля, а затем Нэшвилл против Чаттануги.

Таким образом, пары сверху будут отсортированы следующим образом:

Блокировка

Затем пары блокируются по порядку, пропуская любые пары, которые могли бы создать цикл:

• Заблокируйте Чаттанугу над Ноксвиллом.
• Заприте Нэшвилл над Ноксвиллом.
• Заприте Нэшвилл над Чаттанугой.
• Заприте Нэшвилл над Мемфисом.
• Заблокируйте Чаттанугу над Мемфис.
• Заблокируйте Ноксвилл над Мемфисом.

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

Каждая «блокировка» будет добавьте еще одну стрелку на график, показывающую взаимосвязь между кандидозами тес. Вот окончательный график (где стрелки указывают в сторону от победителя).

В этом примере Нэшвилл является победителем с показателем RP, за ним следуют Чаттануга, Ноксвилл и Мемфис, занимающие второе, третье и четвертое места соответственно.

Пример разрешения неоднозначности

Для простой ситуации с кандидатами A, B и C.

• A>B: 68%
• B>C: 72%
• C>A: 52%

В этой ситуации мы «фиксируем» большинство, начиная с самого большого.

• Блокировка B>C
• Блокировка A>B
• C>A игнорируется, так как она создает неопределенность или цикл.

Следовательно, A является победителем.

Резюме

В примере выборов победителем является Нэшвилл. Это было бы верно для любого метода Кондорсе.

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

Из формальных критериев голосования метод ранжированных пар соответствует критерию большинства, критерию монотонности, критерий Смита (который подразумевает критерий Кондорсе ), критерий проигравшего Кондорсе и критерий независимости клонов. Ранжированные пары не соответствуют критерию согласованности и критерию участия . Хотя ранжированные пары не полностью независимы от нерелевантных альтернатив, они все же удовлетворяют локальной независимости нерелевантных альтернатив.

Независимость нерелевантных альтернатив

Ранжированные пары не соответствуют независимости нерелевантных альтернатив. Однако этот метод придерживается менее строгого свойства, иногда называемого независимостью от альтернатив, в которых доминирует Смит (ISDA). В нем говорится, что если один кандидат (X) побеждает на выборах и добавляется новая альтернатива (Y), X победит на выборах, если Y не входит в набор Смита. ISDA подразумевает критерий Кондорсе.

Таблица сравнения

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

1. ^ На самом деле, есть разные способы измерения силы победы. Подход, использованный в этой статье, называется выигрыш голосов . Другой распространенный подход, который также использовал Tideman для определения метода ранжированных пар в 1987 году, - это вариант с использованием запаса победы. Предел победы, также называемый «силой поражения», - это разница в количестве голосов двух сравниваемых кандидатов.

• Тайдман, Т. (1987) Независимость клонов как критерий правил голосования. Social Choice and Welfare 4: 185–206.

• Описание методов ранжированного голосования Роб Легранд
• Пример реализации JS Асафа Хаддада
• Парный рейтинг Ruby Gem Бала Параранж
• Реализация ранжированных пар Tideman на основе маржи

1. ^ Предполагается, что антимножественность, Кумбс и Доджсон получают усеченные предпочтения, равномерно распределяя возможные рейтинги неуказанных альтернатив; например, бюллетень A>B = C считается как $1\; 2\; \{\backslash \; displaystyle\; \{\backslash \; tfrac\; \{1\}\; \{2\}\}\}$A>B>C и $1\; 2\; \{\backslash \; displaystyle\; \{\backslash \; tfrac\; \{1\}\; \{2\}\}\}$A>C>B. Если предполагается, что эти методы не принимают усеченные предпочтения, то later-no-damage и later-no-help неприменимы.