Теорема Гибборда-Саттертруэйта презентация

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

Риторический вопрос: Что такое демократия?

О демократии

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

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

ЦИК

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

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

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

«Нечестные» и «недемократические» выборы Манипулируемые  Нужно, чтобы выборы не были манипулируемыми Диктатура  Нужно, чтобы не было избирателя-диктатора Навязанный выбор  Нужно, чтобы у каждого кандидата был шанс хоть когда-нибудь победить

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

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

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

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

Монотонность

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

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

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

Единогласие

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

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

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

Доказательство шаг за шагом. Шаг 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 также (см выше)

Доказательство шаг за шагом. Шаг 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) Уменьшили коалицию! Будем уменьшать пока не останется найдем коалицию с одним избирателем.

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

Доказательство шаг за шагом. Шаг 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) Диктатор является решающей коалицией для любых двух кандидатов

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

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

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