Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
417ПИ-Кривошеев / teoremaArrowKollectVibor.ppt
Скачиваний:
26
Добавлен:
27.03.2016
Размер:
1.53 Mб
Скачать

Кривошеев О.И.

МЭСИ, каф. Прикладной математики

Голосование

Индивидуальные

 

 

 

 

 

 

 

 

МНЕНИЯ:

A

 

 

 

B

 

 

 

C

1-й избиратель

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2-й избиратель

кандидат

 

 

 

кандидат

 

 

 

кандидат

 

 

 

 

 

 

 

 

 

 

 

 

C

 

 

 

A

 

 

 

B

3-й избиратель

Лучший

 

 

 

Второй

 

 

 

Худший

 

 

 

 

 

 

 

 

 

 

 

 

 

B

 

 

 

C

 

 

 

A

Проводим вторые тур со всеми сочетаниями ВЫШЕДШИХ в НИХ кандидатов:

A и B

B и С

A и С

Парное голосование: 1

1

1

1

1

1

1

1

1

Групповой выбор:

A B B C C A

Голосование

1-й избиратель

A

 

 

 

B

 

 

 

C

 

 

 

 

 

 

 

 

2-й избиратель

кандидат

 

 

 

кандидат

 

 

 

кандидат

 

 

 

 

 

 

 

 

 

 

 

 

C

 

 

 

A

 

 

 

B

 

Лучший

 

 

 

Второй

 

 

 

Худший

3-й избиратель

B

 

 

 

C

 

 

 

A

 

 

 

 

 

 

Парное голосование:

Групповой выбор:

A и B

B и С

A и С

1

1

1

1

1

1

1

1

1

A B C A

Явного победителя нет!

Разрежем цикл в произвольном месте:

A B

C

Z

Y D

A B C B C D E

Y Z A B

C

Z A B

Парадокс маркиза де Кондорсе

Парадокс маркиза де Кондорсе

против С

 

Считаем

z

6 балловПобедитель

баллы по

y

5

баллов

 

конкурента

правилу

x 5 баллов

 

Борда

 

 

 

t

4

балла

 

 

 

 

Доля

 

 

 

 

 

 

избирателей

 

 

x 4

1

 

 

1

y 4

 

 

 

x

реа льн о

 

y

избирателитопят

 

 

 

 

 

 

 

z

Победителем будет z

 

 

3

y

 

 

x

z 3

своего кандидата

 

Дела ютв ид

 

 

 

 

 

Дел юат вид

 

z

 

 

z

t 2

 

 

t 2

продвинуть

 

 

 

 

 

 

 

 

y

t

 

 

t

 

 

Чтобы

 

1

 

 

 

 

 

 

 

x 1

Допустим у нас по 50% владельцев двух профилей, предпочтительные кандидаты набирают равное число голосов все агенты могут поставить конкурента x и y на последнее место, а агента z на второе -> в результате z должен победить но он хуже как x так и y для всех избирателей. Дальше может быть всё что угодно.

Правило Борда манипулируемо!!!

и победителем может стать третий кандидат z, худший х и у

z 6 баллов

Победитель

y 5

баллов

Правило Борда манипулируемо!!!

x 5 баллов

Допустим у нас по 50% владельцев

t 4 балла

Доля

 

двух профилей,

избирателей

1

1

 

x 4

x

 

y

y 4

 

 

50%

 

50%

 

 

 

Д3

 

реа льн о

 

 

 

z

y

 

x

z 3

 

Победителем будет z

 

 

 

 

 

 

 

Дел юавти

 

ела ютвди

 

 

 

 

 

 

 

t 2

z

 

z

t 2

 

 

 

 

 

 

д

 

 

 

 

 

 

 

y

t

 

t

 

 

 

1

 

 

 

 

 

x 1

предпочтительные кандидаты набирают равное число голосов

все агенты могут поставить конкурента x и y на последнее место, а

агента z на второе -> в результате z должен победить, но он хуже

как x так и y для всех избирателей.

Дальше может быть всё что угодно...

Теорема Эрроу

Пусть есть 3 кандидата и 3 избирателя. Фиксируем предпочтения 1-го выборщика: a >b >c.

Парадокс возникает iff оставшиеся предпочтения таковы: для 3 (2) – b >c > a,

для 2 (3) – c >a >b

т.е. вероятность того, что победителя по Кондорсе не существует pп 118 П 3,3

В общем случае

вероятность того, что победителя по Кондорсе не существует при р кандидатах и n выборщиках П (р, n) возрастает по р,

и по числу выборщиков от n до n+2 – проверено для малых значений, но не доказано.

Если п достаточно велико при фиксированном р

получена оценка

 

 

p 3

 

p 0,2

 

0,63

П p p 9,53

2

 

 

 

 

 

справедливая при р <= 50 с точностью до полпроцента

1.

Всеобщность

 

A B

 

A, B

 

A ~ B

 

 

 

 

 

 

 

A B

2.

Сравнение

 

 

 

 

3.Независимость3го

4.Транзитивность

A B

и

 

A C

 

B C

 

 

 

 

 

5.Единство на 1 000 000 000 (!! мнение 999 999 999 из 1млрд не достаточно).