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

912 253
Нейдер 97 488
Другие 40 579

Выдвинут республиканской партией: Буш
Выдвинут демократической партией: Гор
Пошел сам – Нейдер (вообще – демократ)

912 253
Нейдер 97 488
Другие 40 579

Республиканцы: Буш значительно лучше Гора и Нейдера.
Демократы Гора: Гор лучше Нейдера, оба – значительно лучше Буша.
Демократы Нейдера: Нейдер лучше Гора, оба – значительно лучше Буша

Демократы Нейдера:
Нейдер не выиграет
Если проголосуют правдиво (за Нейдера) – выиграет Буш
Если проголосуют за Гора – выиграет Гор.
Выигрыш Гора для демократов Нейдера значительно лучше выигрыша Буша.

ВЫВОД: Демократам Нейдера нужно было врать!

идут кандидаты у каждого избирателя*
Что должен выдать ЦИК:
кандидата – победителя

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

победил Б
P.S> Все остальные голосовали одинаково в обоих случаях
Для данного избирателя Б лучше, чем A!
Выгодно солгать = манирулируемость!

Неманипулируемые правила:
Правило диктатора
Один избиратель назначается диктатором. Кого он поставит на первое место – всегда победит.
Все бюллетени, кроме диктаторского – в мусорку.
Правило навязанного выбора
Все бюллетени – в мусорку.
Победит тот, за кого договаривались☺

чтобы не было избирателя-диктатора☺
Навязанный выбор ☹
Нужно, чтобы у каждого кандидата был шанс хоть когда-нибудь победить☺

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

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

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

подъемом кандидата A. До подъема побеждал кандидат A. Вопрос: кто теперь победит?
Монотонность: A останется победителем.

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

P.S> Условие монотонности гораздо слабее условия строгой монотонности.

побеждал A. Он сохранил или усилил позицию при переходе от u к v. Тогда в v он обязан победить.

Из неманипулируемости следует строгая монотонность.



P.S> Взрывать мозг доказательством этих утверждений не буду. Оно несложное. Честно-честно☺ Кто захочет – расскажу после лекции. Кто хочет – может попытаться сам☺

диктатора
Без кандидатов, не имеющих шанса победить.

Теорема Гибборда-Саттертруэйта.
«Честных» и «демократических» выборов не существует!

B не может победить!

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

монотонные
Без кандидатов, не имеющих шанса победить.

Теорема Гибборда-Саттертруэйта.
Должен быть диктатор

Демократия = диктатура ☺

считают, что А лучше 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 также (см выше)

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)

Уменьшили коалицию!
Будем уменьшать пока не останется найдем коалицию с одним избирателем.

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)

Диктатор является решающей коалицией для любых двух кандидатов

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