Парадокс Кондорсе - Condorcet paradox

Эта статья посвящена результатам, которые могут возникнуть в результате коллективного выбора из трех или более альтернатив. По поводу утверждения о том, что голосование отдельного лица, вероятно, не повлияет на результат, см. Парадокс голосования.

В Парадокс Кондорсе (также известный как парадокс голосования или парадокс голосования) в теория социального выбора ситуация, отмеченная Маркиз де Кондорсе в конце 18 века,^[1][2][3] в котором коллективные предпочтения могут быть цикличными, даже если предпочтения отдельных избирателей не цикличны. Это парадоксальный, потому что это означает, что желания большинства могут противоречить друг другу: большинство предпочитает, например, кандидата A, а не B, B, а не C, и все же C, а не A. Когда это происходит, это происходит потому, что каждое из конфликтующих большинства составляет разных групп лиц.

Таким образом, ожидание, что транзитивность со стороны предпочтений всех индивидов должны приводить к транзитивности социальных предпочтений - это пример ошибка композиции.

Парадокс был независимо открыт Льюис Кэрролл и Эдвард Дж. Нэнсон, но его значение не было признано до тех пор, пока Дункан Блэк в 1940-е гг.^[4]

Пример

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

Предположим, у нас есть три кандидата, A, B и C, и что есть три избирателя со следующими предпочтениями (кандидаты перечислены слева направо для каждого избирателя в порядке убывания предпочтений):

Избиратель	Первое предпочтение	Второе предпочтение	Третье предпочтение
Избиратель 1	А	B	C
Избиратель 2	B	C	А
Избиратель 3	C	А	B

Если C выбран победителем, можно утверждать, что вместо этого B должен победить, поскольку два избирателя (1 и 2) предпочитают B, а не C, и только один избиратель (3) предпочитает C вместо B. предпочтительнее B, и C предпочтительнее A, с разницей в два к одному в каждом случае. Таким образом, предпочтения общества демонстрируют цикличность: A предпочтительнее B, который предпочтительнее C, который предпочтительнее A. Парадоксальная особенность отношений между предпочтениями избирателей, описанная выше, заключается в том, что, хотя большинство избирателей согласны с тем, что A предпочтительнее B, От B до C и от C до A, все три коэффициента ранговой корреляции между предпочтениями любых двух избирателей отрицательны (а именно, –,5), как рассчитано с помощью Формула коэффициента ранговой корреляции Спирмена разработано Чарльз Спирман много позже.^[5]

Кардинальные рейтинги

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

Обратите внимание, что в графическом примере избиратели и кандидаты не симметричны, но система ранжированного голосования «выравнивает» их предпочтения в симметричный цикл.^[6] Кардинальные системы голосования предоставляют больше информации, чем рейтинги, позволяя найти победителя.^[7][8] Например, под оценка голосования бюллетени могут быть:^[9]

	А	B	C
1	6	3	0
2	0	6	1
3	5	0	6
Общий:	11	9	7

Кандидат A набирает наибольшее количество очков и становится победителем, поскольку A является ближайшим ко всем избирателям. Тем не менее, у большинства избирателей есть стимул поставить А 0 и С 10, что позволяет С победить А, что они предпочитают, и в этот момент у большинства будет стимул дать С 0 и В 10, чтобы побудить B и т. д. (Однако в этом конкретном примере стимул слаб, так как те, кто предпочитает C вместо A, получают только C на 1 балл выше A; вполне возможно, что при ранжированном методе Кондорсе они просто одинаково оценили бы A и C из-за того, насколько слабы их предпочтения, и в этом случае цикл Кондорсе изначально не сформировался бы, и A был бы победителем Кондорсе). Таким образом, хотя этот цикл не происходит ни в одном заданном наборе голосов, он может проявляться в повторных выборах со стратегическими избирателями с кардинальными рейтингами.

Необходимое условие парадокса

Предположим, что Икс - доля избирателей, которые предпочитают А, а не В, и у - доля избирателей, предпочитающих B, а не C.^[10] что фракция z голосов, предпочитающих A, а не C, всегда не менее (х + у - 1). Поскольку парадокс (большинство предпочитает C над A) требует z <1/2, необходимое условие парадокса состоит в том, что

${displaystyle x+y-1leq z<{frac {1}{2}}quad { ext{and hence}}quad x+y<{frac {3}{2}}.}$

Вероятность парадокса

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

Модель беспристрастной культуры

Мы можем рассчитать вероятность увидеть парадокс для особого случая, когда предпочтения избирателей равномерно распределены между кандидатами (это "беспристрастная культура "заведомо нереалистичная модель,^{[11][12][13]:40} так что на практике парадокс Кондорсе может быть более или менее вероятным, чем этот расчет.^[14]:320[15])

За ${displaystyle n}$ избиратели, предоставляющие список предпочтений из трех кандидатов A, B, C, пишем ${displaystyle X_{n}}$ (соотв. ${displaystyle Y_{n}}$, ${displaystyle Z_{n}}$) случайная величина, равная количеству избирателей, которые поставили A перед B (соответственно B перед C, C перед A). Искомая вероятность равна ${displaystyle p_{n}=2P(X_{n}>n/2,Y_{n}>n/2,Z_{n}>n/2)}$ (мы удваиваем, потому что есть еще симметричный случай A> C> B> A). Мы показываем, что для нечетных ${displaystyle n}$, ${displaystyle p_{n}=3q_{n}-1/2}$ куда ${displaystyle q_{n}=P(X_{n}>n/2,Y_{n}>n/2)}$ что заставляет знать только совместное распределение ${displaystyle X_{n}}$ и ${displaystyle Y_{n}}$.

Если мы положим ${displaystyle p_{n,i,j}=P(X_{n}=i,Y_{n}=j)}$, мы показываем соотношение, которое позволяет вычислить это распределение повторением: ${displaystyle p_{n+1,i,j}={1 over 6}p_{n,i,j}+{1 over 3}p_{n,i-1,j}+{1 over 3}p_{n,i,j-1}+{1 over 6}p_{n,i-1,j-1}}$.

Тогда получаются следующие результаты:

${displaystyle n}$	3	101	201	301	401	501	601
${displaystyle p_{n}}$	5.556%	8.690%	8.732%	8.746%	8.753%	8.757%	8.760%

Последовательность, кажется, стремится к конечному пределу.

С использованием Центральная предельная теорема, мы показываем, что ${displaystyle q_{n}}$ как правило ${displaystyle q={1 over 4}P(|T|>{{sqrt {2}} over 4})}$ куда ${displaystyle T}$ переменная, следующая за Распределение Коши, который дает ${displaystyle q={dfrac {1}{2pi }}int _{{sqrt {2}}/4}^{+infty }{frac {dt}{1+t^{2}}}={dfrac {arctan 2{sqrt {2}}}{2pi }}={dfrac {arccos {frac {1}{3}}}{2pi }}}$ (постоянный цитируется в OEIS ).

Таким образом, асимптотическая вероятность столкнуться с парадоксом Кондорсе равна ${displaystyle {{3arccos {1 over 3}} over {2pi }}-{1 over 2}={arcsin {{sqrt {6}} over 9} over pi }}$ что дает значение 8,77%.

Рассчитаны некоторые результаты для случая более трех объектов.^[16]

Модели групповой согласованности

При моделировании с более реалистичными предпочтениями избирателей парадоксы Кондорсе на выборах с небольшим количеством кандидатов и большим количеством избирателей становятся очень редкими.^[13]:78

Эмпирические исследования

Было сделано много попыток найти эмпирические примеры парадокса.^[17]

Обобщение 37 отдельных исследований, охватывающих в общей сложности 265 реальных выборов, больших и малых, выявило 25 случаев парадокса Кондорсе с общей вероятностью 9,4%.^[14]:325 (и это может быть высокой оценкой, поскольку о случаях парадокса сообщается больше, чем о случаях без него).^[13]:47. С другой стороны, эмпирическая идентификация парадокса Кондорсе предполагает обширные данные о предпочтениях лиц, принимающих решения, по сравнению со всеми альтернативами - что очень редко доступно.

Хотя примеры парадокса, кажется, иногда возникают в небольших учреждениях (например, в парламентах), очень мало примеров было обнаружено в более крупных группах (например, электорате), хотя некоторые из них были идентифицированы.^[18]

Подразумеваемое

Когда Метод Кондорсе используется для определения выборов, парадокс голосования циклических социальных предпочтений подразумевает, что выборы не имеют Кондорсе победитель: нет кандидата, который мог бы победить на выборах один на один против другого кандидата. По-прежнему будет существовать наименьшая группа кандидатов, так что каждый кандидат в группе может победить на выборах один на один против другого кандидата, однако, это известно как Набор Смита. Несколько вариантов метода Кондорсе отличаются тем, как они разрешить такую ​​двусмысленность когда они возникают, чтобы определить победителя.^[19] Методы Кондорсе, которые всегда выбирают кого-то из набора Смита, когда нет победителя Кондорсе, известны как Смит-эффективный. Обратите внимание, что использование только рейтингов не дает справедливого и детерминированного решения тривиального примера, приведенного ранее, потому что каждый кандидат находится в строго симметричной ситуации.

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

Вопреки широко распространенному мнению, продвигаемому среди других Элизабет Бадинтер и Роберт Бадинтер (в их биографии Кондорсе) этот парадокс ставит под сомнение только согласованность определенных систем голосования, а не саму демократию.

Двухэтапный процесс голосования

Одним из важных следствий возможного существования парадокса голосования в практической ситуации является то, что в двухэтапном процессе голосования окончательный победитель может зависеть от того, как эти два этапа организованы. Например, предположим, что победитель A против B в открытая первичная Затем в борьбе за лидерство одной партии на всеобщих выборах будет участвовать лидер второй партии, C. В предыдущем примере A победит B при выдвижении первой партии, а затем проиграет C на всеобщих выборах. Но если бы B был во второй партии, а не в первой, B победил бы C при выдвижении этой партии, а затем проиграл бы A на всеобщих выборах. Таким образом, структура двух этапов имеет значение, будет ли A или C окончательным победителем.

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

Структуру парадокса Кондорсе можно воспроизвести в механических устройствах, демонстрирующих непроницаемость таких отношений, как «вращаться быстрее, чем», «поднимать и не подниматься», «быть сильнее, чем» в некоторых геометрических конструкциях.^[20]

Смотрите также

• Теорема о невозможности Эрроу
  • Кеннет Эрроу, Раздел с примером распределительной трудности непереходности + правило большинства
• Дискурсивная дилемма
• Теорема Гиббарда – Саттертуэйта
• Независимость от нерелевантных альтернатив
• Мгновенное голосование
• Число Накамура
• Квадратичное голосование
• Камень ножницы Бумага
• Парадокс Симпсона
• Набор Смита

Рекомендации

1. Маркиз де Кондорсе. "Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix" (PNG) (На французском). Получено 2008-03-10.
2. Кондорсе, Жан-Антуан-Николя де Карита; Соммерлад, Фиона; Маклин, Иэн (01.01.1989). Политическая теория Кондорсе. Оксфорд: Оксфордский университет, факультет социальных исследований. С. 69–80, 152–166. OCLC  20408445. Ясно, что если бы чей-то голос был противоречивым (имел циклические предпочтения), его нужно было бы не учитывать, и поэтому мы должны установить форму голосования, которая сделает такие абсурды невозможными.
3. Герляйн, Уильям В. (2002). «Парадокс Кондорсе и вероятность его возникновения: разные взгляды на сбалансированные предпочтения *». Теория и решение. 52 (2): 171–199. Дои:10.1023 / А: 1015551010381. ISSN  0040-5833. Здесь Кондорсе отмечает, что у нас есть «противоречивая система», которая представляет то, что стало известно как парадокс Кондорсе.
4. Райкер, Уильям Харрисон. (1982). Либерализм против популизма: противостояние теории демократии и теории социального выбора. Waveland Pr. п. 2. ISBN  0881333670. OCLC  316034736.
5. Поддяков А., Валсинер Дж. (2013). «Циклы интранзитивности и их трансформации: как функционируют динамически адаптирующиеся системы». В Л. Рудольф (ред.), Качественная математика для социальных наук: математические модели для исследования динамики культуры (стр. 343–391). Абингдон, Нью-Йорк: Рутледж.
6. Procaccia, Ariel D .; Розеншайн, Джеффри С. (11 сентября 2006 г.). Клуш, Матиас; Ровацос, Майкл; Пэйн, Терри Р. (ред.). Искажение кардинальных предпочтений при голосовании (PDF). Конспект лекций по информатике. Springer Berlin Heidelberg. С. 317–331. CiteSeerX  10.1.1.113.2486. Дои:10.1007/11839354_23. ISBN  9783540385691. Кардинальные (основанные на полезности) предпочтения агентов встроены в пространство порядковых предпочтений. Это часто вызывает искажение в предпочтениях и, следовательно, в социальном благополучии результата
7. Паундстон, Уильям (2008). Игра на голосование: почему выборы несправедливы (и что мы можем с этим сделать). Хилл и Ван. п. 158. ISBN  978-0809048922. OCLC  276908223. Это основная проблема двусторонних сравнений. Степени предпочтений не учитываются. ... Циклы возникают в результате придания равного значения неравным предпочтениям. ... Парадокс затемняет тот факт, что избиратели действительно предпочитают один вариант.
8. Кок, Ян; Шентруп, Клей; Смит, Уоррен. «Циклы Кондорсе». RangeVoting.org. Получено 2017-02-09. ... любой метод, основанный только на рейтинге голосов, с треском проваливается. Голосование по диапазону, которое позволяет избирателям выразить сила предпочтений, вероятно, удастся выбрать лучший капитал A.
9. В этом примере доступны баллы от 0 до 6, и каждый избиратель нормализует свои максимальные / минимальные баллы к этому диапазону, выбирая средний балл, пропорциональный расстоянию.
10. Серебро, Чарльз. «Парадокс голосования», Математический вестник 76, ноябрь 1992 г., стр. 387–388.
11. Цетлин, Илья; Регенветтер, Мишель; Грофман, Бернард (2003-12-01). «Беспристрастная культура максимизирует вероятность циклов большинства». Социальный выбор и благосостояние. 21 (3): 387–398. Дои:10.1007 / s00355-003-0269-z. ISSN  0176-1714. широко признано, что беспристрастная культура нереальна ... беспристрастная культура - худший сценарий
12. Тайдман, Т; Плассманн, Флоренц (июнь 2008 г.). «Источник результатов выборов: эмпирический анализ статистических моделей поведения избирателей». Теоретики голосования в целом признают, что считают эту модель нереалистичной.
13. Герляйн, Уильям V .; Лепелли, Доминик (2011). Парадоксы голосования и групповая согласованность: конденсационная эффективность правил голосования. Берлин: Springer. Дои:10.1007/978-3-642-03107-6. ISBN  9783642031076. OCLC  695387286. большинство результатов выборов не соответствуют ни одному из DC, IC, IAC или MC ... эмпирические исследования ... показывают, что некоторые из наиболее распространенных парадоксов относительно маловероятно наблюдаются на реальных выборах. ... легко сделать вывод, что парадокс Кондорсе очень редко должен наблюдаться на любых реальных выборах небольшого числа кандидатов с большим электоратом, если предпочтения избирателей отражают разумную степень групповой взаимной согласованности
14. Ван Димен, Адриан (2014). «Об эмпирической значимости парадокса Кондорсе». Общественный выбор. 158 (3–4): 311–330. Дои:10.1007 / s11127-013-0133-3. ISSN  0048-5829. небольшие отклонения от предположения о беспристрастности культуры могут привести к большим изменениям в вероятности парадокса. Это может привести к огромному снижению или, наоборот, огромному росту.
15. Мэй, Роберт М. (1971). «Несколько математических замечаний о парадоксе голосования». Поведенческая наука. 16 (2): 143–151. Дои:10.1002 / bs.3830160204. ISSN  0005-7940.
16. Герляйн, Уильям В. (1997). «Парадокс Кондорсе и эффективность правил голосования по Кондорсе». Mathematica Japonica. 45: 173–199.
17. Куррилд-Клитгаард, Питер (2014). «Эмпирический социальный выбор: введение». Общественный выбор. 158 (3–4): 297–310. Дои:10.1007 / s11127-014-0164-4. ISSN  0048-5829.
18. Куррилд-Клитгаард, Питер (2014). «Эмпирический пример парадокса Кондорсе голосования в большом электорате». Общественный выбор. 107: 135–145. Дои:10.1023 / А: 1010304729545. ISSN  0048-5829.
19. Липпман, Дэвид (2014). «Теория голосования». Математика в обществе. ISBN  978-1479276530. OCLC  913874268. Существует множество методов Кондорсе, которые различаются в первую очередь тем, как они работают со связями, которые очень распространены, когда победителя Кондорсе не существует.
20. Поддяков, Александр (2018). «Непереходные машины». arXiv:1809.03869 [math.HO ].

дальнейшее чтение

• Гарман, М. Б .; Камиен, М. И. (1968). «Парадокс голосования: вероятностные расчеты». Поведенческая наука. 13 (4): 306–316. Дои:10.1002 / bs.3830130405. PMID  5663897.
• Niemi, R.G .; Вайсберг, Х. (1968). «Математическое решение вероятности парадокса голосования». Поведенческая наука. 13 (4): 317–323. Дои:10.1002 / bs.3830130406. PMID  5663898.
• Niemi, R.G .; Райт, Дж. Р. (1987). «Циклы голосования и структура индивидуальных предпочтений». Социальный выбор и благосостояние. 4 (3): 173–183. Дои:10.1007 / BF00433943. JSTOR  41105865.