Теорема Гибборда-Саттертруэйта

1. Теорема Гибборда-Саттертруэйта

Теорема ГиббордаСаттертруэйта

2. Риторический вопрос:

Что такое демократия?

3. О демократии

4. Америка, Флорида, 2000г.

Выборы президента Америки, Флорида, 2000г.
Буш
Гор
Нейдер
Другие
2 912 790
2 912 253
97 488
40 579
Выдвинут республиканской партией: Буш
Выдвинут демократической партией: Гор
Пошел сам – Нейдер (вообще – демократ)

5. Америка, Флорида, 2000г.

Выборы президента Америки, Флорида, 2000г.
Буш
Гор
Нейдер
Другие
2 912 790
2 912 253
97 488
40 579
Республиканцы: Буш значительно лучше Гора и Нейдера.
Демократы Гора: Гор лучше Нейдера, оба – значительно лучше Буша.
Демократы Нейдера: Нейдер лучше Гора, оба – значительно лучше Буша
Демократы Нейдера:
Нейдер не выиграет
Если проголосуют правдиво (за Нейдера) – выиграет Буш
Если проголосуют за Гора – выиграет Гор.
Выигрыш Гора для демократов Нейдера значительно лучше выигрыша Буша.
ВЫВОД: Демократам Нейдера нужно было врать!

6. ЦИК

7. Функции ЦИК

ЦИК должен выдать результат выборов
Что может знать ЦИК:
в каком порядке идут кандидаты у каждого избирателя*
Что должен выдать ЦИК:
кандидата – победителя
* Предположим, что ЦИК знает всё!
По-хорошему, ЦИК не должен знать, у кого именно какие
предпочтения (бюллетени не подписаны)
пусть знает, только лишь бы не пользовался этим
Обычно избиратели не сообщают все свои предпочтения, а дают голос
за одного кандидата
все равно пусть ЦИК всё знает. Не захочет – не воспользуется

8. Манипулируемость

9. Манипулируемость

Избиратель проголосовал «сердцем» (правильно) – победил A
Избиратель проголосовал «умом» (солгал) – победил Б
P.S> Все остальные голосовали одинаково в обоих случаях
Для данного избирателя Б лучше, чем A!
Выгодно солгать = манирулируемость!
Неманипулируемые правила:
Правило диктатора
Один избиратель назначается диктатором.
Кого он поставит на первое место – всегда победит.
Все бюллетени, кроме диктаторского – в мусорку.
Правило навязанного выбора
Все бюллетени – в мусорку.
Победит тот, за кого договаривались

10. «Нечестные» и «недемократические» выборы

1.
Манипулируемые
Нужно, чтобы выборы не были манипулируемыми
2. Диктатура
Нужно, чтобы не было избирателя-диктатора
3. Навязанный выбор
Нужно, чтобы у каждого кандидата был шанс хоть
когда-нибудь победить

11. «Честные» и «демократические» выборы

1. Неманипулируемые.
2. Без диктатора
3. Без кандидатов, не имеющих права победить
Теорема Гибборда-Саттертруэйта.
«Честных» и «демократических» выборов не
существует!
ВАЖНО: в условии теоремы обязано
быть хотя бы 3 кандидата!
P.S> Мы в формулировке даже не пользовались тем, что ЦИК не имеет права смотреть, кто именно
как голосовал, для теоремы хватит только условия отсутствия диктатора.

12. Определения, обозначения

13. Доказательство: шаг за шагом. Шаг 1.1: обозначения.

Кандидаты, избиратели, голосования
A,B,C,… – кандидаты;
i,j,k,… – избиратели;
u, v – голосования
На каждое голосование ЦИК обязан выдать победителя!

14. Доказательство: шаг за шагом. Шаг 1.2: определения.

Кандидат A сохраняет или усиливает свою позицию
при переходе от голосования u к голосованию v:
Если в первом голосовании (u) кто-то считает, что A
лучше чем какой-то другой кандидат B, то во втором
голосовании (v) он обязан считать так же!
Голосование v получено из голосования u подъемом
кандидата A.
Если вычернуть A, это будут одинаковые голосования
A сохраняет или усиливает свою позицию при переходе
от голосования u к голосованию v.

15. Монотонность

16. Доказательство: шаг за шагом. Шаг 2.1: монотонность.

Голосование v получено из голосования u подъемом
кандидата A. До подъема побеждал кандидат A. Вопрос:
кто теперь победит?
Монотонность: A останется победителем.
Голосование v получено из голосования u подъемом
кандидата A. А теперь кто победит?
Строгая монотонность: либо тот же, кто и был, либо A.
(Никто третий сюда влезть не может )
P.S> Условие монотонности гораздо слабее условия
строгой монотонности.

17. Доказательство: шаг за шагом. Шаг 2.2: строгая монотонность.

Строгая монотонность эквивалентна следующему:
В u побеждал A. Он сохранил или усилил позицию при
переходе от u к v. Тогда в v он обязан победить.
Из неманипулируемости следует строгая монотонность.
P.S> Взрывать мозг доказательством этих утверждений не буду.
Оно несложное. Честно-честно
Кто захочет – расскажу после лекции. Кто хочет – может попытаться сам

18. Доказательство: шаг за шагом. Шаг 2.3: переформулировка.

«Честные» и «демократические» выборы:
Неманипулируемые Строго монотонные
Без диктатора
Без кандидатов, не имеющих шанса победить.
Теорема Гибборда-Саттертруэйта.
«Честных» и «демократических» выборов не
существует!

19. Единогласие

20. Доказательство: шаг за шагом. Шаг 3.1: единогласие.

Все считают, что A лучше B.
Тогда B не может победить!
Доказательство:
Пусть в этом голосовании (u) B победил.
v – голосование в котором побеждает A.
Такое существует – условие теоремы!!!
v’ – голосование, полученное из v, в котором A переходит на 1 место, B – на второе,
остальные остаются на своих местах.
Вопрос: кто победит в v’
B сохранил или усилил свою позицию при переходе от u к v’, он побеждал в u => он и останется
победителем.
A сохранил или усилил свою позицию при переходе от v к v’, он побеждал в u => он и останется
победителем.
Противоречие!
Внимание: было использовано условие, что каждый хоть когда-либо обязан
победить.

21. Доказательство: шаг за шагом. Шаг 3.2: переформулировка #2.

«Честные» и «демократические» выборы:
Неманипулируемые Строго монотонные
Без кандидатов, не имеющих шанса победить.
Теорема Гибборда-Саттертруэйта.
Должен быть диктатор
Демократия = диктатура

22. Давайте поможем Даше найти диктатора!

23. Доказательство шаг за шагом. Шаг 4.1: Создание коалиции

S(A,B) – множество избирателей, которые считают, что А лучше B (а
остальные считают наоборот)
Если при этом хоть когда-нибудь А победит, S(A,B) называется решающей
коалицией A против B. (u)
Утверждения, эквивалентные определению:
S(A,B) решающая коалиция => B – не победитель. (v)
Доказательство от противного.
Поднимем A,B на 1,2 места с сохранением порядка между собой (v’).
A сохранило или усилило свою позицию при переходе от u к v’, А был победителем =>
А победитель в v’
B сохранило или усилило свою позицию при переходе от v к v’, B был победителем =>
B победитель в v’
Противоречие.
S(A,B) решающая коалиция, A,B занимают первые два места => А
победитель
Все остальные проиграют (единогласие), и B также (см выше)

24. Доказательство шаг за шагом. Шаг 4.2: Уменьшение коалиции

T=S(A,B). Разделим людей на подгруппы T1 и T2. Голосование:
A>B>C для T1
C>A>B для T2
B>C>A для остальных избрателей
P.S> A,B,C всегда на первых трех местах.
Кто победит?
A,B или C (все остальные их хуже, единогласие)
Не B (ибо условия коалиции A против B удовлетворены)
Если A, то T1 = S(A,C)
Если C, то T2 = S(C,B)
Уменьшили коалицию!
Будем уменьшать пока не останется найдем коалицию с одним избирателем.

25. Он остался один!

26. Доказательство шаг за шагом. Шаг 4.2: Диктатор всех коалиций

i = S(A,B) => i = S (A,D). Голосование:
A>B>D – диктатор
B>D>A – остальные избиратели
P.S> A,B,D всегда на первых трех местах
Кто победит?
A, B или D (остальные ещё хуже, единогласие)
Не D (все считают, что B его лучше)
Не B (i = S(A,B))
Только А может победить.
i=S(A,D)
P.S> замену первого кандидата (i = S(A,D) => i = S (С,D)) – аналогично.
i=S(C,D)
Диктатор является решающей коалицией для любых двух кандидатов

27. Доказательство шаг за шагом. Шаг 4.2, заключительный: Диктатор гасит всех.

Диктатор является решающей коалицией для любых двух кандидатов
Знаем: Если диктатор голосует как надо, все остальные против его голоса,
диктатор победит.
Нужно: Если диктатор голосует как надо, всем остальным без разницы,
диктатор победит.
Голосование:
A – первый для для диктатора.
A – худший для остальных.
Для любого кандидата B:
i=S(A,B) => B не может победить!
Победит А.
Как и задумывал диктатор!
Dictator wins!

28. Что такое демократия

Демократия это
манипулируемость
или
диктатура
или
невозможность для кого-то когда-либо победить
Что выбираешь ты?

29.

Заключительный слайд им. С. Шнурова
Выборы, выборы, кандидаты молодцы!