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

Сентябрь 14, 2022

Главная
Математика
Теорема Гибборда-Саттертруэйта

Содержание

2. Риторический вопрос: Что такое демократия?
3. О демократии
4. Америка, Флорида, 2000г. Выборы президента Америки, Флорида, 2000г. Буш 2 912 790 Гор 2 912 253
5. Америка, Флорида, 2000г. Выборы президента Америки, Флорида, 2000г. Буш 2 912 790 Гор 2 912 253
6. ЦИК
7. Функции ЦИК ЦИК должен выдать результат выборов Что может знать ЦИК: в каком порядке идут кандидаты
8. Манипулируемость
9. Манипулируемость Избиратель проголосовал «сердцем» (правильно) – победил A Избиратель проголосовал «умом» (солгал) – победил Б P.S>
10. «Нечестные» и «недемократические» выборы Манипулируемые ☹ Нужно, чтобы выборы не были манипулируемыми☺ Диктатура ☹ Нужно, чтобы
11. «Честные» и «демократические» выборы Неманипулируемые. Без диктатора Без кандидатов, не имеющих права победить Теорема Гибборда-Саттертруэйта. «Честных»
12. Определения, обозначения
13. Доказательство: шаг за шагом. Шаг 1.1: обозначения. Кандидаты, избиратели, голосования A,B,C,… – кандидаты; i,j,k,… – избиратели;
14. Доказательство: шаг за шагом. Шаг 1.2: определения. Кандидат A сохраняет или усиливает свою позицию при переходе
15. Монотонность
16. Доказательство: шаг за шагом. Шаг 2.1: монотонность. Голосование v получено из голосования u подъемом кандидата A.
17. Доказательство: шаг за шагом. Шаг 2.2: строгая монотонность. Строгая монотонность эквивалентна следующему: В u побеждал A.
18. Доказательство: шаг за шагом. Шаг 2.3: переформулировка. «Честные» и «демократические» выборы: Неманипулируемые Строго монотонные Без диктатора
19. Единогласие
20. Доказательство: шаг за шагом. Шаг 3.1: единогласие. Все считают, что A лучше B. Тогда B не
21. Доказательство: шаг за шагом. Шаг 3.2: переформулировка #2. «Честные» и «демократические» выборы: Неманипулируемые Строго монотонные Без
22. Давайте поможем Даше найти диктатора!
23. Доказательство шаг за шагом. Шаг 4.1: Создание коалиции S(A,B) – множество избирателей, которые считают, что А
24. Доказательство шаг за шагом. Шаг 4.2: Уменьшение коалиции T=S(A,B). Разделим людей на подгруппы T1 и T2.
25. Он остался один!
26. Доказательство шаг за шагом. Шаг 4.2: Диктатор всех коалиций i = S(A,B) => i = S
27. Доказательство шаг за шагом. Шаг 4.2, заключительный: Диктатор гасит всех. Диктатор является решающей коалицией для любых
28. Что такое демократия Демократия это манипулируемость или диктатура или невозможность для кого-то когда-либо победить Что выбираешь
30. Скачать презентацию

Слайд 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

«Нечестные» и «недемократические» выборы
Манипулируемые ☹
Нужно, чтобы выборы не были манипулируемыми☺
Диктатура ☹
Нужно,

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

Слайд 11

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

и «демократических» выборов не существует!
ВАЖНО: в условии теоремы обязано быть хотя бы 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

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

Содержание

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

О демократии

Америка, Флорида, 2000г.Выборы президента Америки, Флорида, 2000г.Буш 2 912 790Гор 2

Америка, Флорида, 2000г.Выборы президента Америки, Флорида, 2000г.Буш 2 912 790Гор 2

ЦИК

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

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

МанипулируемостьИзбиратель проголосовал «сердцем» (правильно) – победил AИзбиратель проголосовал «умом» (солгал) –

«Нечестные» и «недемократические» выборыМанипулируемые ☹Нужно, чтобы выборы не были манипулируемыми☺Диктатура ☹Нужно,

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

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

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

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

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

Доказательство: шаг за шагом. Шаг 2.1: монотонность.Голосование v получено из голосования u

Доказательство: шаг за шагом. Шаг 2.2: строгая монотонность.Строгая монотонность эквивалентна следующему:В u

Доказательство: шаг за шагом. Шаг 2.3: переформулировка.«Честные» и «демократические» выборы:Неманипулируемые Строго монотонныеБез

Единогласие

Доказательство: шаг за шагом. Шаг 3.1: единогласие.Все считают, что A лучше B.Тогда

Доказательство: шаг за шагом. Шаг 3.2: переформулировка #2.«Честные» и «демократические» выборы:Неманипулируемые Строго

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

Доказательство шаг за шагом. Шаг 4.1: Создание коалицииS(A,B) – множество избирателей, которые

Доказательство шаг за шагом. Шаг 4.2: Уменьшение коалицииT=S(A,B). Разделим людей на подгруппы

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

Доказательство шаг за шагом. Шаг 4.2: Диктатор всех коалицийi = S(A,B) =>

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

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

Похожие презентации

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

Америка, Флорида, 2000г.
Выборы президента Америки, Флорида, 2000г.
Буш 2 912 790
Гор 2

Америка, Флорида, 2000г.
Выборы президента Америки, Флорида, 2000г.
Буш 2 912 790
Гор 2

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

Манипулируемость
Избиратель проголосовал «сердцем» (правильно) – победил A
Избиратель проголосовал «умом» (солгал) –

«Нечестные» и «недемократические» выборы
Манипулируемые ☹
Нужно, чтобы выборы не были манипулируемыми☺
Диктатура ☹
Нужно,

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

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

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

Доказательство: шаг за шагом. Шаг 2.1: монотонность.
Голосование v получено из голосования u

Доказательство: шаг за шагом. Шаг 2.2: строгая монотонность.
Строгая монотонность эквивалентна следующему:
В u

Доказательство: шаг за шагом. Шаг 2.3: переформулировка.
«Честные» и «демократические» выборы:
Неманипулируемые Строго монотонные
Без

Доказательство: шаг за шагом. Шаг 3.1: единогласие.
Все считают, что A лучше B.
Тогда

Доказательство: шаг за шагом. Шаг 3.2: переформулировка #2.
«Честные» и «демократические» выборы:
Неманипулируемые Строго

Доказательство шаг за шагом. Шаг 4.1: Создание коалиции
S(A,B) – множество избирателей, которые

Доказательство шаг за шагом. Шаг 4.2: Уменьшение коалиции
T=S(A,B). Разделим людей на подгруппы

Доказательство шаг за шагом. Шаг 4.2: Диктатор всех коалиций
i = S(A,B) =>

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

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