Теория коллективного выбора Филатов А.Ю. Институт систем энергетики им.Л.А.Мелентьева, Иркутский государственный университет

Постановка проблемы кооперативного принятия решений Примеры: Финансирование общественных благ Трагедия общины (истощение ресурсов из-за чрезмерного использования) Дилемма заключенного (доминирующие стратегии ведут к худшему исходу) Асимметричность информации (отрицательный отбор; моральный риск) Многие общественно значимые решения не могут приниматься на основе рыночных механизмов, поскольку кооперативные возможности не будут эффективно использованы при децентрализованных действиях агентов. Индивидуальные предпочтения коллективный выбор (принимают все!) Предположение: пренебрегаем мнением меньшинства; из двух альтернатив побеждает та, за которую проголосовало более 50% человек! Практика: альтернатив более двух! Правило большинства – единственный метод, удовлетворяющий требованиям 1.Анонимность (равноправие избирателей). 2.Нейтральность (равноправие кандидатов). 3.Монотонность (усиление поддержки не подвергает сомнению избрание).

Системы голосования Системы голосования: Мажоритарная (Россия, президентские выборы – два тура) Пропорциональная (Россия, парламентские выборы, с 2003 года) Смешанная (Россия, парламентские выборы, до 2003 года) Голосование выборщиков (США, президентские выборы) Парадоксы «голосования выборщиков»: Победитель может набрать меньше голосов избирателей, чем соперник (2000, Буш

Правило Кондорсе vs Борда Правило относительного большинства: 3576 A AB C A – победитель в голосовании (8 голосов) B CD B A – наихудший кандидат (13 голосов из 21) CBC D C >A (13 из 21), C > B (11 из 21), C > D (14 из 21) победитель C D DA A B > C: 1 место (7:6), 1–2 м (16:11), 1–3 м (21:21) победитель B Правило Борда (учет рангов кандидатов): Кандидаты от худшего к лучшему получают ранги … Победитель по Борда – кандидат с максимальной суммой очков. Правило Кондорсе: Победитель по Кондорсе – кандидат, побеждающий любого из соперников при парном сравнении. Обобщение правила Борда: произвольные шкалы Правило относительного большинства – 0 0 … 0 1. Правило антибольшинства – 0 1 … 1 1.

Парадокс Кондорсе Победитель по Кондорсе может отсутствовать: К > П > Ч > K К ЧП П КЧ ЧПК Вероятности отсутствия победителя по Кондорсе: p – число кандидатов, n – число избирателей p / n357911предел 30,0560,0690,0750,0780,0800,088 40,1110,1390,1500,1560,1600,176 50,1600,2000,2150,2300,251 60,2020,2550,2580,2840,2940,315 70,2390,2990,3050,3420,3430,369 предел Вариация Копленда (из Кондорсе): максимизация разницы побед и поражений (выиграть у максимального числа кандидатов). Вариация Симпсона (из Кондорсе): максимизация наименьшего числа избира- телей, голосующих за данного кандидата при парном сравнении с другими (ни- кому сильно не проиграть).

Борда Кондорсе Пример для строго монотонного правила подсчета очков : 3211 s 2 A BB C A > B (4 из 7), A > C (4 из 7) A – победитель по Кондорсе s 1 B CA A очки B = = очки A s 0 C AC B Существуют профили предпочтений избирателей, при которых победитель по Кондорсе не может быть избран ни при каком методе подсчета очков! Пример для произвольного правила подсчета очков : 6443 s 2 A BB C A > B (9 из 17), A > C (10 из 17) A – победитель по Кондорсе s 1 B CA A очки B = = очки A s 0 C AC B

Профиль Страффина 1413A CE EB DA AC BD BDEBDEACC1413A CE EB DA AC BD BDEBDEACC Победитель по Кондорсе отсутствует, у всех есть поражения в парных играх. Вариация Копленда: победитель A (+3–1) B=C=D (+2 –2), E (+1–3). Вариация Симпсона: победители B=C=D=E (4), A (1). ABCDE A 5551 B 4545 C 4455 D 4545 E 8444 Правило Борда – классическое и случай произвольных шкал. Победителем может стать любой из кандидатов. 4A=1*4+4*0+1*3+3*3=16 3B=1*3+4*2+1*1+3*2=18 2С=1*2+4*4+1*0+3*0=18 1D=1*1+4*3+1*2+3*1=18 0E=1*0+4*1+1*4+3*4=20 4A=19,6 3,9B=18,9 2С=18 1D=21,6 0E=20 4A=19,6 3B=18 2С=21,6 1D=18 0,9E=20,9 4A=16 3B=24,3 2,9С=18,9 1D=18,9 0E=20 9A=41 8B=23 2С=38 1D=38 0E=40

Аксиоматический подход 1.Однозначность – правило всегда дает сделать однозначный выбор. Не вы- полняется для анонимных и нейтральных правил, если n имеет делитель p. 2.Анонимность (равноправие избирателей) – имена избирателей не имеют значения: если два избирателя поменяются голосами, то результат выборов не изменится. Не выполняется, если при равенстве победителем становится выбранный определенным избирателем. 3.Нейтральность (равноправие альтернатив) – имена кандидатов не имеют значения: если поменять местами кандидатов A н B в предпочтении каждого избирателя, то исход голосования изменится соответственно. Не выполняет- ся, если при равенстве победителем становится определенный кандидат. 4.Состоятельность по Кондорсе – правило всегда выбирает победителя по Кондорсе, если он существует. Не выполняется для любых методов подсчета очков, в т.ч. для правила относительного большинства, правила Борда и т.д. 5.Парето-эффективность (единогласие) – если кандидат A для всех избира- телей лучше B, то B не может быть избранным. Не выполняется для правила антибольшинства.

Последовательные сравнения по правилу большинства 1. Не выполняется нейтральность. Повестка определяет контроль над выборами. B D A C A D B C Побед. A Побед. B Побед. C Побед. D A B D C A B C D AA DDB A>B, A>C, BB BCC B>C, В>D, CC AA D C>D, D>A. DDCBA 2. Не выполняется Парето-эффективность. BA C AD BAD, A>C (при равенстве голосов) BBBBпри этом D>A для всех избирателей

Аксиоматический подход 6.Монотонность – увеличившаяся поддержка кандидата не может уменьшить шанса быть избранным. Не выполняется для относительного большинства с выбыванием (голосования в 2 тура). профиль 1:профиль 2: Профиль 1: выходят A и B, A > B (11:6) AC BB ACBAПрофиль 2: A улучшает свое положение, BA CA BACB выходят A и C, C > A (9:8). CB AC CBAC Не выполняется для правила альтернативных голосов (последовательного ис- ключения неудачников) для любого способа подсчета очков Шаг 1: исключается C, s 2 AB BC CA s 1 BA CB ACШаг 2: A > B (15:12). s 0 =0 CC AA BB 91683В выделенных столбцах A становится лучше B s 2 AB BCAШаг 1: исключается B, s 1 BA CAC s 0 =0 CC ABBШаг 2: C > A (14:13).

Аксиоматический подход 7.Пополнение – если 2 независимые группы избирателей выбирают кандида- та A, то, объединившись, они выберут его же. Не выполняется для любого правила, состоятельного по Кондорсе. Состоятельный по Кондорсе метод выбирает A в группе 1, при этом B>A Гр.1: Гр. 2: Гр.1: победитель A. A C (4:2), BB (4:3), A>C (7:0), B>С (7:0). BC ABAГр.1+2: победитель B. A C (11:2), B>С (9:4). AB CC C 8.Участие – собственный бюллетень не может уменьшит полезность избира- теля. Не выполняется для любого правила, состоятельного по Кондорсе, при 4 и более кандидатах AA DBCПравило Симпсона до участия: победитель A. DD BCAS(A)=6(B,C), S(B)=4(D), S(C)=3(B), S(D)=5(A). CB CA BПравило Симпсона после участия: победитель B. BCADDS(A)=6(C), S(B)=8(D), S(C)=7(D), S(D)=5(A).

Аксиоматический подход 9.Неманипулируемость (независимость от посторонних альтернатив) – нельзя увеличить свою полезность, ведя стратегическое голосование. При наличии 3 и более кандидатов справедливо только для правила диктатора (теор. Гиббарда-Сэттертуэйта). 322Избиратели с профилем C > B > A видят, что C не побеждает ни AB Cпри каких обстоятельствах и стратегически голосуют B > C > A. BA BВ результате от положения C меняется победитель голосования. CC A Разрешение проблемы: 1.Вероятностные правила голосования. Пример: «Правило случайного диктатора» – вероятностная версия относительного большинства. Доминирующая стратегия – указать наи- лучшего для себя кандидата. Не выполняется «Парето-эффективность». 2.Ограничение области предпочтений Пример: «однопиковые предпочтения» – предпочтения, для которых при линейном упорядочении кандидатов полезность сначала возрастает до некоторого пика, а затем уменьшается.

Случай однопиковых предпочтений Коллективный выбор температуры в комнате (открыть / закрыть окно) Из двух альтернатив побеждает под- держанная медианным избирателем! C Экономическая свобода –1,59 КПРФ –0,87 СР 0,30 ЕР 1,14 СПС 0,69 ЛДПР 24>26 (4:1), 22>24 (3:2), 21>22 (3:2) Упорядочение не обязательно должно быть изначально. Можно придумать порядок, при котором предпочтения однопиковые! Ц ЛС ЦСКА, Локомотив, Спартак

ЛЛ СЦСЦУ Локомотива при игре с ЦСКА и Спартаком СЦ ЛЛЦСдвойная поддержка трибун! ЦС ЦС ЛЛ 2000 – Локомотив во внутригрупповом выше Спартака, хотя в чемпионате Спартак по-прежнему (как и в 90-е) победитель с большим отрывом , 2008 – одинаковые результаты в чемпионате и в турнире 3 команд (!!!) – Локомотив лучший в группе, хотя худший в чемпионате 2007 – Локомотив существенно хуже остальных в чемпионате, но второй в группе с большим опережением Спартака и рядом с 1 местом ЦСКА. Сопоставление результатов в турнире троих и в чемпионате: Неограниченная область предпочтений приводит к стратегическому поведению и плохим для всех исходам для любых правил голосования!

Выполнение аксиом для различных правил голосования ОБАМШ2КВСПДЖ Простота +––––++––+++ Однозначность –+++++ Анонимность –+ Нейтральность ––––––+–––++ Состоятельность по Кондорсе ––––––++++–– Парето-эффективность ++–+–++++–+– Монотонность +++++–+++++– Пополнение +++++–––––+– Участие +++++–––––+– Неманипулируемость ––––––+–––++ О – относительное большинство Б – правило Борда A – правило антибольшинства М – Борда со строго монотонной шкалой Ш – Борда с произвольной шкалой 2 – относительное большинство, 2 тура К – правило Кондорсе В – вариация Копленда С – вариация Симпсона П – повестка дня Д – правило диктатора Ж – жребий

Теорема Эрроу N={1,2,…,n} – избиратели, A={a,b,c,…} – кандидаты. P(A) – множество линейных порядков на A R(A) – множество нестрогих порядков на A Более сложная задача – не просто найти победителя, но составить порядок P(A) n R(A) Если |A|=2, есть единственное анонимное, нейтральное и монотонное правило – правило большинства. Оно также является неманипулируемым. Теорема Эрроу о невозможности демократии: если |A|>2, существует единст- венное Парето-эффективное неманипулируемое правило – правило диктатора. 4ЛЦ СС=Л=Ц=9ЛЦС Д=9 3СЛЦ Д=3ДДД М=6 2ЦС Л М=0МММЛ=Ц=С=5 1ДДДСЛЦ 0МММЦСЛ Пример стратегического поведения, приводящего к плохому для всех исходу, для правила Борда:

Метод Шульце (1997) (метод разъезженного пути) Избиратели указывают в бюллетене предпочтения относительно кандидатур. 1 – наиболее желаемый кандидат, 2 – второй по предпочтительности и т.д. Разрешается ставить одинаковые числа нескольким кандидатурам. Разрешается вообще не заполнять поле для части кандидатур (в таком случае считается, что они одинаково хуже всех, для которых указано число). Обработка результатов голосования: d(A,B) – число избирателей, строго предпочитающих кандидата A кандидату B. Путь силы p от A до B – последовательность кандидатов C(1),…,C(n) со св-ми: 1. C(1)=A, C(n)=B. 2. d(C(i),C(i+1)) > d(C(i+1),C(i)), i=1,…,n. 3. p=min d(C(i),C(i+1)). Сила сильнейшего пути p(A,B) – максимальное значение силы пути от A до B. Если пути от кандидата A к кандидату B не существует, p(A,B)=0. Победитель – кандидат A, такой что p(A,B) p(B,A) для каждого кандидата B.

Метод Шульце (1997). Пример 45 избирателей, 5 кандидатов: AAB CC CDE CDE AA BCB BED BE AEA ECAEBDBD DBCDDEAC d(*,A)d(*,B)d(*,C)d(*,D)d(*,E) d(A,*)d(A,*) d(B,*)d(B,*) d(C,*)d(C,*) d(D,*)d(D,*) d(E,*)d(E,*) к Aк Bк Cк Dк E от A A-30-D-28-C-29-BA-30-D-28-CA-30-DA-30-D-28-C-24-E от B B-25-AB-33-D-28-CB-33-DB-33-D-28-C-24-E от C C-29-B-25-AC-29-BC-29-B-33-DC-24-E от D D-28-C-29-B-25-AD-28-C-29-BD-28-CD-28-C-24-E от E E-31-D-28-C-29-B-25-AE-31-D-28-C-29-BE-31-D-28-CE-31-D E > A (25:24), E > B (28:24), E > C (28:24), E > D (31:24) A > B (28:25), A > C (28:25), A > D (30:25) C > B (29:28), C > D (29:28) B > D (33:28) E > A > C > B > D

Метод Шульце. Еще примеры Кондорсе: AB BC C BC AA B CA CB A d(*,A)d(*,B)d(*,C) d(A,*)d(A,*) d(B,*)d(B,*) d(C,*)d(C,*) 3518 к Aк Bк C от A A-33-BA-33-B-42-C от B B-42-C-35-AB-42-C от C C-35-AC-35-A-33-B B > A (35:33), B > C (42:33), C > A (35:33) B > C > A Янг, 100 избирателей: ABCD A B C D к Aк Bк Cк D от A A-76-BA-76-B-68-D-70-CA-76-B-68-D от B B-68-D-66-AB-68-D-70-CB-68-D от C C-64-B-68-D-66-AC-64-BC-64-B-68-D от D D-66-AD-66-A-76-BD-70-C A > B (76:66), A > C (68:64), A > D (68:66), B > C (68:64), B > D (68:66), D > C (70:64). A > B > D > C. Общая поддержка этого порядка =322. D > C > A > B. Общая поддержка этого порядка =370 > 322.

Спасибо за внимание!