Настала пора её реанимировать, ибо сейчас в канун бесконечных выборов она очень актуальна.
Пусть у нас есть "честные демократические выборы", в которых участвуют несколько (>2) кандидатов (пускай a,b,c,d,e и так далее)
Каждый из M избирателей определяется со своими предчтениями. Он расставляет кандидатов в порядке убывания для себя.
Обозначим функцию предпочтения i-го избирателя как f_i. Т.е. если f_i(a)>f_i(b), до для этого избирателя кандидат a лучше, чем b.
Далее все избиратели сообщают свои предпочтения (т.е. список всех кандидатов в порядке убывания) в ЦИК, и последний единственным
образом формирует функцию общественного предпочтения F (т.е. так же однозначно расставляет кандидатов в порядке убывания).
Вот так формулируется процедура выборов. Сфорулируем 3 условия, при которых выборы можно считать честными и демократическими:
1) Принцип единогласия. Если абсолютно все избиратели считают, что Иванов лучше Сидорова, то ЦИКу придется с ними согласиться.
Формально, если при всех i: f_i(a)>f_i(b), то F(a)>F(b).
2) Принцип независимости от посторонних альтернатив. Общественное мнение относительно того, лучше Иванов Сидорова или хуже, никак не должно зависеть от кандидата Петрова.
Формально. Пусть прошли 2 голосования, функция предпочтения на первом f_i, на втором - f*_i. Тогда если для всех i { f_i(a) - f_i(b) } { f*_i(a) - f*_i(b) }>0 (т.е. для каждого избирателя взаимное расположение этих двух кандидатов относительно друг друга одинаково), то взаимное общественное расположение этих кандидатов так же должно быть одинаковым. { F(a)-F(b) } { F*(a)-F*(b) } > 0. Если Иванов стоял выше Сидорова так он и должен остаться стоять выше Сидорова, хотя между ними мог вклиниться Петров.
3) Отсутствие диктатора. Не должно существовать диктатора, который бы сам назначал итоги выборов.
Формально. Не существует такой избиратель, что общественное предпочтение, которое выдал ЦИК всегда совпадает с предпочтениями этого кандидата, не зависимо от предпочтений других избирателей. Т.е. не существует такого i, что порядок кандидатов по убыванию, заданный функцией предпочтения f_i совпадает с общественным порядком, заданным функцией F не зависимо от фуннкций f_j при j не равном i.
Надо доказать, что "честных и демократических" выборов существовать не может.
Это называют теоремой Эрроу. Эта теорема в своё время произвела на меня неизгладимое впечатление и сейчас настало как раз самое время опубликовать её здесь.
Хотя я понимаю, что за это Эрроу вроде бы Нобелевку получил, и она произвела фурор в 70х годах, но решение этой задачи также очень красивое и перекликается по идеям с задачей про лампочки. Так что предлагаю заработать на Нобелевку
