метод Доджсона

Метод Доджсона — избирательная система , основанная на предложении математика Чарльза Доджсона, более известного как Льюис Кэрролл . Метод ищет победителя, которого предпочитает большинство ; если такой победитель не найден, метод продолжается поиском кандидата, который может быть преобразован в победителя Кондорсе с наименьшим возможным количеством изменений бюллетеня , где редактирование бюллетеня переключает двух соседних кандидатов в бюллетене избирателя. ^{[ 1 ]}

Описание

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

Вычисление

Короче говоря, мы должны найти профиль голосования с минимальным тау-расстоянием Кендалла от входных данных, чтобы в нем был победитель Кондорсе; затем победитель Кондорсе объявляется победителем. Вычисление победителя или даже показателя Доджсона кандидата (количества замен, необходимых для того, чтобы сделать этого кандидата победителем) является NP-сложной задачей. ^{[ 2 ]} путем снижения с Exact Cover на 3 комплекта (X3C). ^{[ 3 ]}

Учитывая целое число k и выборы, NP-полно определить, может ли кандидат стать победителем Кондорсе с менее чем k обменами.

Ссылки

^ Рэтлифф, Томас К. (1 января 2001 г.). «Сравнение метода Доджсона и правила Кемени» . Социальный выбор и благосостояние . 18 (1): 79–89. дои : 10.1007/s003550000060 . ISSN 1432-217X .
^ Бартольди Дж.; Тови, Калифорния; Трик, Массачусетс (апрель 1989 г.). «Схемы голосования, при которых может быть сложно определить, кто победил на выборах». Социальный выбор и благосостояние . 6 (2): 157–165. дои : 10.1007/BF00303169 . S2CID 154114517 . Статья лишь напрямую доказывает NP-трудность, но ясно, что проблема решения находится в NP, поскольку, имея кандидата и список k свопов, вы можете определить, является ли этот кандидат победителем Кондорсе за полиномиальное время.
^ Гэри, Майкл Р.; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимость . WH Freeman Co., Сан-Франциско. ISBN 9780716710455 .

Эта выборах статья о незавершена . Вы можете помочь Википедии, расширив ее .

[1] Рэтлифф, Томас К. (1 января 2001 г.). «Сравнение метода Доджсона и правила Кемени» . Социальный выбор и благосостояние . 18 (1): 79–89. дои : 10.1007/s003550000060 . ISSN 1432-217X .

[btt-2] Бартольди Дж.; Тови, Калифорния; Трик, Массачусетс (апрель 1989 г.). «Схемы голосования, при которых может быть сложно определить, кто победил на выборах». Социальный выбор и благосостояние . 6 (2): 157–165. дои : 10.1007/BF00303169 . S2CID 154114517 . Статья лишь напрямую доказывает NP-трудность, но ясно, что проблема решения находится в NP, поскольку, имея кандидата и список k свопов, вы можете определить, является ли этот кандидат победителем Кондорсе за полиномиальное время.

[gj1979-3] Гэри, Майкл Р.; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимость . WH Freeman Co., Сан-Франциско. ISBN 9780716710455 .

[ 1 ]

[ 2 ]

[ 3 ]