?

Log in

9 апр, 2014 @ 01:32 4, 5
4. Пророческая монетка

В предыдущей главе Алиса, Боб и Кэрол голосовали, находясь строго в равных условиях, что привело к не слишком интересному результату. Попробуем же слегка нарушить симметрию, введя ещё одного персонажа - известного шамана Трента. Трент, не являясь гражданином Идеальной Охлократии сам голосовать не может, но будучи дружен с Алисой и Бобом решает помочь им облапошить Кэрол, которую на дух не переносит. План его странен, но прост в исполнении. Трент бросает симметричную монетку и пишет два одинаковых письма Алисе и Бобу. Если выпадает орёл, текст писем звучит так: "Моё гадание предсказало победу партии Путь Ленина в будущих выборах. Советую голосовать за них. Ваш Трент". Если же выпадает решка, то в тексте меняется только название партии.

Дальнейшие события зависят от суеверности граждан Идеальной Охлократии. Если Алиса и Боб люди рационально мыслящие и не верят в гадания, то в электоральной картине ничего не изменится. Но если они достаточно серьёзно отнесутся к пророчеству Трента, то мы можем снова составить таблицу возможных исходов голосования, вписав на этот раз в графы обозначающие за кого голосуют избиратели не названия партий, а их предсказанный статус - "лидер" или "лузер":
                  голосование                  |     выплата
-----------------------------------------------+-----------------
   Алиса   |    Боб    |   Кэрол   |большинство|Алиса| Боб |Кэрол
-----------+-----------+-----------+-----------+-----+-----+-----
   лидер   |   лидер   |   лидер   |   лидер   |  0  |  0  |  0
   лидер   |   лидер   |   лузер   |   лидер   | +1  | +1  | -2
   лидер   |   лузер   |   лидер   |   лидер   | +1  | -2  | +1
   лидер   |   лузер   |   лузер   |   лузер   | -2  | +1  | +1
   лузер   |   лидер   |   лидер   |   лидер   | -2  | +1  | +1
   лузер   |   лидер   |   лузер   |   лузер   | +1  | -2  | +1
   лузер   |   лузер   |   лидер   |   лузер   | +1  | +1  | -2
   лузер   |   лузер   |   лузер   |   лузер   |  0  |  0  |  0

Казалось бы, ничего не изменилось, ведь партии при подсчёте можно переназывать как угодно - для результатов голосования важно только, оказался ли кто-то в меньшинстве или же решение было единогласным. Однако, выбранная нами система обозначений обнажает незаметный ранее факт - Кэрол не получала письма, а значит не знает, какой из партий Трент нагадал победу. Поскольку наши обозначения определились броском симметричной монетки, любой алгоритм Кэрол пытающийся выяснить кто лидер, а кто лузер попадёт в цель только в половине случаев. Как бы она не старалась, сделать сознательный выбор Кэрол не может, что позволяет нам записать таблицу исходов в сокращённом виде - объединяя строчки, различающиеся только голосованием Кэрол, и вписывая в графы выплат матожидание объединяемых значений:
                  голосование                  | средняя выплата
-----------------------------------------------+-----------------
   Алиса   |    Боб    |   Кэрол   |большинство|Алиса| Боб |Кэрол
-----------+-----------+-----------+-----------+-----+-----+-----
   лидер   |   лидер   |    ???    |   лидер   | 0.5 | 0.5 | -1
   лидер   |   лузер   |    ???    |    ???    |-0.5 |-0.5 | +1
   лузер   |   лидер   |    ???    |    ???    |-0.5 |-0.5 | +1
   лузер   |   лузер   |    ???    |   лузер   | 0.5 | 0.5 | -1

При рассмотрении ситуации с точки зрения теории игр можно заметить, что вынужденная ограничиться единственной смешанной стратегией[1] Кэрол больше фактически не является игроком - ходы делают только Алиса и Боб. Что ещё интереснее, для Алисы и Боба голосование превратилось из антагонистической игры в игру с ненулевой суммой, где Кэрол выполняет роль банка, выплачивающего выигрыш или забирающего проигрыш. Самое же главное, изменились значения выплат в точках равновесия Нэша - теперь Алиса и Боб одновременно учитывая совет Трента в среднем остаются в плюсе.

5. Тайное знание

Как же так получилось, что предсказание Трента помогло Алисе и Бобу взять верх над Кэрол? Ситуация выглядит несколько парадоксально - мало того, что вопреки рационализму гадание на монетке даёт преимущество, вдобавок оно помогает, даже если все кто знает его результаты поступают наоборот. Одновременно голосуя за партию, которой монетка предсказала поражение, Алиса и Боб опровергают пророчество, но при этом оказываются в точке равновесия Нэша с такой же положительной выплатой как и при голосовании за предполагаемого победителя. Кажущемуся парадоксу, однако, находится вполне интуитивная интерпретация, если отказаться от понимания писем Трента как совета голосовать тем или иным образом.

Секрет фокуса в том, что Тренту не было необходимости делать собственно предсказание - в своих письмах он мог просто написать "Выпал орёл/решка. Ваш Трент". Бросок монеты создал новый бит информации, а благодаря письмам он стал известен Алисе и Бобу, но не Кэрол. Общее знание позволяет Алисе и Бобу использовать единую стратегию "если выпала решка, голосуем за X, если орёл - за Y", а то что это знание является тайной от Кэрол, не позволяет ей присоединиться к большинству, избегая штрафа.

Следующим разумным вопросом становится "а нужен ли вообще Трент?". На первый взгляд нет - поскольку смешанные стратегии в теории игр являются одним из фундаментальных понятий, разумно предположить что Алиса и Боб вполне умеют "бросать монетки" самостоятельно. Однако сила помощи Трента опирается на то, что Алиса и Боб используют знание об одном и том же случайном событии, так что если они хотят обходиться без внешней помощи, им придётся научиться обмениваться информацией самим. Это заставляет нас дополнить правила нашей Идеальной Охлократии описанием протокола общения её жителей, чем мы и займёмся в следующей главе.

* продолжение следует *

[1] http://www.eprisner.de/MAT109/Mixedb.html
About this Entry
Drak-head