Теорема Эрроу и парадокс Кондорсе

[kaipa]

Теорема Эрроу -- это весьма показательный формальный математический результат, показывающий, что не существует справедливой системы голосования. Справедливость задается несколькими разумными предпосылками:
1) универсальность, то есть при любом голосовании есть механизм определения результата
2) отсутствие диктатора, то есть голосующего, предпочтения которого доминируют
3) независимость от "посторонних" альтернатив, другими словами, если в списке A,B,C,D поменялись предпочтения между C и D, то это не изменяет предпочтения между A и B
4) самое парадоксальное, что сюда же входит и оптимальность по Парето, то есть если A>B для всех голосующих, то это верно и для финального результата.

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

В несколько более частной форме тот же парадоксальный результат известен как парадокс Кондорсе: правило простого большинства не обеспечивает транзитивность предпочтений. На википедии подробно написано, как регламент голосования, то есть "правила игры", влияют на результат.

Самый простой пример:
Пусть у нас имеются три человека, голосующих по трем вопросам. Первый из них голосует «да» по первому вопросу, «да» по второму и «нет» по третьему («да»/«да»/«нет»), второй — «да»/«нет»/«да», третий — «нет»/«да»/«да». Суммарный итог голосования подсчитывается как соотношение сумм голосов «да» и «нет» по каждому из вопросов. В рассмотренном случае суммарный итог голосования будет «да»/«да»/«да». Этот итог не отражает мнения ни одного из голосовавших и, естественно, не удовлетворяет никого.

Comments

[ushastyi.livejournal.com]

Еще как! Это называется (математическия) теория принятия решений. Надо бы написать об этом поподробнее, так как этим я занимался на старших курсах и аспирантуре, а тема малоизвестная за пределами специалистов.

[ushastyi.livejournal.com]

Никак не связана. Чистая прикладная математика.

[ushastyi.livejournal.com]

Немного подумав, все же связь есть. Одна из проблем принятия решений, это максимизировать функцию полезности. Существует много интерактивных процедур, задача которых тем или иным образом выявить, аппроксимировать функцию полезности человека. Эти процедуры могут делаться и компьютером, что можно трактовать как процесс обучения. Выучив функцию полезности, компьютер может предложить человеку те решения проблемы, которые максимизируют его функцию (более точно, лежат на Парето оболочке множества достижимости).

чОрная стрела :)

[falcao.livejournal.com]

А я доказательство этой теоремы рассказываю студентам в курсе дискретной математики.

И в ЖЖ тоже писал об этом:

http://falcao.livejournal.com/4769.html
http://falcao.livejournal.com/5101.html

Re: чОрная стрела :)

[ushastyi.livejournal.com]

Ой, спасибо. Я в общем достаточно случайно на это наткнулся вчера, хотя и занимался системами поддержки принятия решений и многокритериальной оптимизацией, где подобного рода материал мог бы быть. Может быть, пропустил :)