WikiDer > Ранжированные пары

Эта статья поднимает множество проблем. Пожалуйста помоги Улучши это или обсудите эти вопросы на страница обсуждения. (Узнайте, как и когда удалить эти сообщения-шаблоны) Эта статья включает список литературы, связанное чтение или внешние ссылки, но его источники остаются неясными, потому что в нем отсутствует встроенные цитаты. Пожалуйста, помогите улучшить эта статья введение более точные цитаты. (Июнь 2011 г.) (Узнайте, как и когда удалить этот шаблон сообщения) эта статья в значительной степени или полностью полагается на один источник. Соответствующее обсуждение можно найти на страница обсуждения. Пожалуйста помоги улучшить эту статью путем введения цитаты к дополнительным источникам. Найдите источники: «Ранговые пары» – Новости · газеты · книги · ученый · JSTOR (Июнь 2011 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

Часть Политика серии
Избирательные системы
Множественность / мажоритарность Множество Мажоритарной Один голос без права передачи Ограниченное голосование Множественность в целом (голосование за блок) Общий билет Многократное голосование Два раунда Исчерпывающее голосование Рейтинговые / преференциальные системы Мгновенный сток (альтернативное голосование) Условное голосование Метод Кумбса Методы Кондорсе (Коупленда, Доджсона, Кемени – Янг, Минимакс, Нансона, ранжированные пары, Шульце, Альтернативный Смит) Позиционное голосование (Граф Борда, Науру / метод Даудалла, Евровидение) Баклин голосование Первичная избирательная система Оклахомы Преференциальное блокирующее голосование Кардинальные / ступенчатые системы Оценка голосования Утверждающее голосование (единая первичная) Комбинированное одобрительное голосование Голосование одобрения удовлетворения Решение большинства ЗВЕЗДНОЕ голосование
Пропорциональное отображение Партийный список (открытые списки, закрытые списки, местные списки) Самые высокие средние (Д'Ондт, Sainte-Laguë, Хантингтон-Хилл) Наибольший остаток (заяц, Падение, Imperiali, Hagenbach-Bischoff) Пропорциональные формы мгновенное голосование во втором туре Единый передаваемый голос (Грегори, Райт) Пропорциональные формы Методы Кондорсе CPO-STV Schulze STV Пропорциональные формы одобрительное голосование Пропорциональное одобрительное голосование Последовательное пропорциональное одобрительное голосование Бипропорциональное распределение Голосование справедливым большинством
Смешанные системы Смешанный пропорциональный Дополнительная система участников Параллельное голосование (смешанное мажоритарное голосование) Скорпион Бонус большинства Альтернативное голосование плюс Двухчленный пропорциональный Пропорциональный
Другие системы и родственная теория Кумулятивное голосование Биномиальное голосование Голосование по доверенности Делегированное голосование Случайный выбор (жеребьевка, случайное голосование) Сравнение избирательных систем Теория социального выбора Теорема Эрроу Теорема Гиббарда – Саттертуэйта Теория общественного выбора
Политический портал
v т е

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

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

Процедура

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

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

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

Tally

Чтобы подсчитать голоса, рассмотрите предпочтения каждого избирателя. Например, если избиратель заявляет «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. При равенстве большинства большинство с меньшей оппозицией меньшинства занимает первое место.^{[vs 1]}

Замок

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

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

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

Победитель

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

Пример

Ситуация

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

Кандидатами в капитал являются:

• Мемфис, крупнейший город штата, с 42% голосовавших, но расположенный далеко от других городов
• Нашвилл, с 26% избирателей, недалеко от центра штата
• Knoxville, при 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 подразумевает критерий Кондорсе.

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

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

использованная литература

• Тайдман, Т. (1987) Независимость клонов как критерий правил голосования. Социальный выбор и благополучие 4: 185–206.

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

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