Аксиоматическое обоснование правила передачи голосов Ф.Т. Алескеров А.В. Карпов Работа поддержана Научным фондом НИУ ВШЭ (грант 10-04- 0030) и Лабораторией. - презентация

1 Аксиоматическое обоснование правила передачи голосов Ф.Т. Алескеров А.В. Карпов Работа поддержана Научным фондом НИУ ВШЭ (грант ) и Лабораторией Анализа и Выбора Решений НИУ ВШЭ.

2 Правило передачи голосов (STV) STV используется в Австралии Индии Ирландии Исландии(с 2010) Новой Зеландии США (в Кембридже и Миннеаполисе (с 2009)) Шотландии (с 2007) и Северной Ирландии

3 Как работает STV С точки зрения процесса голосования методы STV практически не различаются. Избиратели голосуют за любое количество кандидатов, ранжируя их. Различия проявляются только в процессе подсчета и понятны только специалистам.

4 Подсчет голосов (1) 1.Определяется квота 2.Бюллетени раскладываются по первым предпочтениям 3.Кандидат, набравший квоту, объявляется победителем.

5 Ирландия 2011

6 Подсчет голосов (2) 4. Излишек бюллетеней у победившего кандидата передается остальным кандидатам согласно последующим предпочтениям. 5. Если ни один из кандидатов на текущем этапе не набирает квоту, то 5а. Если количество оставшихся кандидатов равно количеству оставшихся мест, то все кандидаты объявляются победителями, иначе 5б. Кандидат с наименьшим количеством голосов исключается и его голоса переходят последующим кандидатам. Процедура продолжается, пока все места не будут заполнены.

7 Различные методы Основное различие методов, реализующих STV, - в способе определении бюллетеней передающихся другим кандидатам. Отбор может быть случайным или нет, учитывать только голоса последней передачи (метод Грегори) или все голоса (включающий метод Грегори), зависеть от этапа, кандидата и т.д.

8 Проблемы STV. Парадокс неявки Количество голосов голос 1.15adcb 2.15bcad 3.10bcad 4.20cadb 5.25dbac 6.15adcb q=[100/(2+1)]+1=34 голоса, если все избиратели участвуют и q=[90/(2+1)]+1=31 без группы 3

9 Подсчет голосов (1) Первый этап Второй этап Третий этап a30+20=50-16=34 b25 c20-20=00 d25 +16=41

10 Подсчет голосов (2) Первый этап Второй этап Третий этап a30 +4=34 b15-15=00 c20+15=35-4=31 d25 Вместо {a,d} группа избирателей, не участвовавшая в голосовании, получила {a,c}.

11 Аксиоматика Woodall (1987) 1. Увеличение поддержки кандидата, который и без этого был избран, должно также привести к его избранию. 2a Последующие предпочтения не должны оказывать отрицательное влияние. 2b Последующие предпочтения не могут быть учтены, пока не учтены предшествующие. 3 Если никто не указал вторых предпочтений, то кандидат с наибольшим количеством голосов по первым предпочтениям должен быть избран. 4 Если сумма бюллетеней с кандидатом x на первом месте и кандидатом y на втором месте и бюллетеней, где y - первый, а x - второй, составляет больше половины голосов, то хотя бы один из этих кандидатов должен быть избран.

12 Эффект бабочки ABBCDEFG BCFGGCAF CGAFFBD GFDACA FEEE Профиль предпочтений 1 (на основе Miller, 2007)

13 Передача голосов при профиле предпочтений 1 ABCDEFG 1144[125] [144] = = = = = = 251 [145] = = = = = 251

14 Профиль предпочтений 2 (на основе Miller, 2007) A B BBCDEFG B A CFGGCAF C C GAFFBD G G FDACA F F EEE

15 Передача голосов при профиле предпочтений 2 ABCDEFG [126] = = = =[144] = = = [148] = = = =293 --

16 Теорема о невозможности Аксиомы 1-4 несовместны. Кроме немонотонности и парадокса неявки STV демонстрирует нарушение критерия Кондорсе и условия согласованности. Задача: выделить свойства, разделяющие процедуры внутри класса STV, и найти в некотором смысле наилучшую процедуру.

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

18 Формальное описание процедуры (1) Если существует выигрывающая коалиция то кандидат, поддержанный этой коалицией, объявляется избранным. Тогда Если, то переход к началу нового этапа;

19 Формальное описание процедуры (2) Кандидат с наименьшей мощностью объявляется проигравшим и максимальной коалиции переход к началу следующего этапа.

20 Пример сокращения профиля Голоса Первые предпоч a a a b c Вторые предпоч c b c c b Третьи предпоч b c b a a Голоса Первые предпоч c b c Вторые предпоч b c b После победы кандидата а.

21 Аксиомы 1. Независимость от предыстории 2. Независимость от последующих предпочтений 3. Анонимность Независимость от имен избирателей 4. Нейтральность Независимость от имен альтернатив

22 Нарушение Аксиомы 2 Голоса за кандидата a Осталь- ные голоса a a a a … c c c c d d d d… Голоса за кандидата a Осталь- ные голоса a a a a … d c c c с d d d…

23 Доказательство независимости аксиом (1) 1.Случайным образом раздаются номера избирателям 1 раз на нулевом этапе. Лексикографическим способом перенумеровываются коалиции. Выбираем коалицию с наименьшим номером. Выполняются аксиомы 2 - 4, но нарушается 1. 2.На каждом этапе пересчитывается квота и случайно упорядочиваются альтернативы. Коалиция образуется из тех избирателей, у которых следующая по предпочтениям альтернатива наиболее близка к избранной. При неразличимости коалиций по данному критерию, выбираем среди этих коалиций равновероятно. Выполняются аксиомы 1, 3, 4, но нарушается 2.

24 Доказательство независимости аксиом (2) 3. По существующим именам избирателей лексикографически упорядочим коалиции. На каждом этапе пересчитываем квоту и выбираем коалицию с наименьшим номером. Выполняются аксиомы 1, 2, 4, но нарушается 3.

25 Результаты (1) Пересчет квоты по формуле является необходимым условием Аксиомы 1 (независимость от предыстории) Теорема 1. Для квоты, посчитанной на последнем этапе процедуры, выполняется Лемма 1. Квота, пересчитанная на каждом этапе процедуры, не может увеличиться ни на каком этапе.

26 Результаты (2) Теорема 2. Единственным методом, удовлетворяющим аксиомам 1-4 одновременно, будет случайный равновероятный на каждом этапе метод выбора выигрывающей коалиции с пересчетом квоты на каждом шаге по формуле.

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

28 Благодарю за внимание