- •Кривошеев О.И.
- •Голосование
- •Голосование
- •Разрежем цикл в произвольном месте:
- •Парадокс маркиза де Кондорсе
- •Парадокс маркиза де Кондорсе
- •Считаем
- •z 6 баллов
- •Теорема Эрроу
- •1. Всеобщность
- •Теорема Эрроу
- •Теорема:
- •x Кандидат 1 (лучший)
- •Профиль общества состоит из вектора ВСЕХ профилей
- •V (x, y, P) i : Pi (x, y) true
- •Лемма о Нейтральности
- •Лемма
- •Лемма
- •Рассмотрим серию КОЛЛЕКТИВНЫХ профилей, где Кандидат а снизу или сверху – ЛУЧШИЙ или
- •Рассмотрим серию КОЛЛЕКТИВНЫХ профилей, где Кандидат а снизу или сверху – ЛУЧШИЙ или
- •Финал доказательства
- •Лемма
- •Одномерный вариант для всех избирателей
- •Не манипулируемые
- •Не манипулируемые
- •Обобщённые медианные механизмы
Кривошеев О.И.
МЭСИ, каф. Прикладной математики
Голосование
Индивидуальные |
|
|
|
|
|
|
|
|
|
МНЕНИЯ: |
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млрд не достаточно).