игра "войны Роз"

N игроков (не менее трёх) рассаживаются за круглым столом.
Каждый игрок приносит собственный набор карт, на лице которых обозначена масть (роза Ланкастеров или роза Йорков) и значение (денежная стоимость от нуля до заранее определённой максимальной ставки).
Каждый тур игрок может положить перед собой одну карту рубашкой вверх, делая таким образом тайную ставку.
По сигналу крупье игроки одновременно вскрываются, переворачивая сыгранные карты лицом вверх. Для каждой масти считается сумма сделанных на неё ставок. Масть собравшая большую сумму объявляется победителем тура.
Игроки, поставившие на проигравшую масть, выплачивают свою ставку в банк. Банк делится между победителями пропорционально сделанным ими ставкам.
По завершении тура каждый игрок забирает сыгранную карту назад в руку.

Пример: играют Эдмунд, Ричард, Генри, Томас и Джеймс
      ----------+----------------------------------
      Игрок     |    Ставка
      ----------+----------------------------------
      Эдмунд    |    6 пенсов      на Йорков
      Ричард    |    6 пенсов      на Йорков
      Генри     |    шиллинг       на Йорков
      Томас     |    шиллинг       на Ланкастеров
      Джеймс    |    2 шиллинга    на Ланкастеров
      ----------+---------------------------------- 
Сумма ставок на Ланкастеров - 3 шиллинга, победа
Сумма ставок на Йорков - 2 шиллинга, поражение

Эдмунд, Ричард и Генри выплачивают свои ставки в банк.
Томас получает треть банка - 8 пенсов
Джеймс получает две трети банка - 1 шиллинг 4 пенса

В промежутке между турами игроки могут гласно, в свободной форме обсуждать принятые решения, планировать дальнейшие действия, передавать друг другу деньги и беседовать о погоде. Правилами запрещаются непубличные контакты - шёпот, обмен записками, использование сигналов обговорённых до начала игры и т.д.

Идеальная охлократия

Теоремы Эрроу, Гиббарда-Саттертуэйта и Дуггана-Шварца не оставляют надежды на создание честной детерминированной избирательной системы не подверженной манипуляциям "тактического голосования". Говоря простым языком, на любых демократических выборах с более чем двумя альтернативами части избирателей на некотором этапе выгодно голосовать не в соответствии со своими истинными предпочтениями, а в соответствии с прогнозом конечных результатов голосования.

Для того чтобы удостовериться в этом, смоделируем избирательную систему таким образом, чтобы тактические соображения были единственным фактором голосования.

Представим себе суверенно-демократическое государство с двухпартийной системой. За места в парламенте идёт борьба между партиями "Путь Ленина" и "Лень Путина", избираемыми всенародным открытым голосованием по партийным спискам. Государство очень демократично, так что выборы нового состава парламента проходят часто - буквально каждый месяц. Однако, поскольку демократия всё-таки суверенная, то почти по всем вопросам обе партии голосуют одинаково и единогласно, оказывая всецелую поддержку курсу любимого народом президента. Единственный вопрос, в котором партии голосуют друг против друга, поднимается на следующий же день после каждых выборов - партия "Путь Ленина" настаивает на фиксированном налоговом сборе со всех избирателей партии "Лень Путина", чтобы поровну разделить собранные деньги между избирателями своей партии. В свою очередь, партия ""Лень Путина" настаивает на противоположной фискальной мере.

В описанной Идеальной Охлократии, единственным результатом голосования для рядового гражданина становится либо штраф в виде потери фиксированной суммы денег если избранная им партия оказалась в меньшинстве, или премия в виде равной доли при дележе собранных штрафов для голосовавших за победителя. Это заставляет избирателей стремиться как минимум самим не промахнуться с предугадыванием результата - все хотят избежать штрафа. Однако, делёж между победителями собранных с проигравших штрафов приводит к любопытному эффекту - наилучшим результатом голосования для гражданина становится не просто победа его партии, но победа с минимальным перевесом над противником. Ведь чем больше избирателей было у проигравшей партии, тем больше сумма собранных штрафов, а чем меньше избирателей у победившей партии, тем меньше ртов на которые приходится её делить.

Предположим, что наше государство очень невелико - всего три избирателя (назовём их Алиса, Боб и Кэрол). Поскольку вариантов голосования для каждого гражданина только два, общее количество исходов - 23 = 8 и мы можем составить сводную таблицу результатов для всех возможных случаев:

    ---------------------------------------------------------------+-----------------
                           голосование                             |     выплата
    ---------------+-----------------------------------------------+-----+-----+-----
       Алиса       |     Боб       |    Кэрол      | большинство   |Алиса| Боб |Кэрол
    ---------------+---------------+---------------+---------------+-----+-----+-----
     Лень Путина   | Лень Путина   | Лень Путина   | Лень Путина   |  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  |  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
            -----------+-----------+-----------+-----------+-----+-----+----- 
При рассмотрении ситуации с точки зрения теории игр можно заметить, что вынужденная ограничиться единственной смешанной стратегией, Кэрол больше фактически не является игроком - ходы делают только Алиса и Боб.

Что ещё интереснее, для Алисы и Боба голосование превратилось из антагонистической игры в игру с ненулевой суммой, где Кэрол выполняет роль крупье, выплачивающего выигрыш (или забирающего проигрыш).

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

Как же так получилось, что предсказание Трента помогло Алисе и Бобу взять верх над Кэрол?

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

Кажущемуся парадоксу, однако, находится вполне интуитивная интерпретация, если отказаться от понимания писем Трента как совета голосовать тем или иным образом.

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

Следующим разумным вопросом будет "А нужен ли вообще Трент?".

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

Это заставляет нас дополнить правила нашей Идеальной Охлократии описанием протокола общения её жителей.

Публичный заговор

Как мы помним, голосования в Идеальной Охлократии проводятся открытым образом, то есть после оглашения результатов все избиратели знают кто за какую партию голосовал. Неудивительно, что при таком уровне прозрачности демкратических институтов общаться граждане привыкли столь же публично - единственным способом коммуникации для них является раздел бесплатных объявлений в местной газете. Если один гражданин хочет сообщить что-то другому, его послание, подписанное и навсегда заархивированное, одновременно становится доступно и всем остальным гражданам тоже.

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

Тем не менее, каждый, кто хоть отдалённо знаком с современной криптографией, сразу же узнает в Кэрол Еву, а в происходящем - типичный паттерн использования ассиметричного шифрования. Это внезапное дежавю уводит нас в сторону от теоретико-игрового анализа Идеальной Охлократии, что требует небольшого философского отступления в качестве объяснения.

Дело в том, что классическая теория игр не занимается вопросами сложности вычислений, использующихся в оптимальных стратегиях. С точки зрения теории игр игра го, например, довольно скучна - последовательная игра с двумя игроками и полной информацией, решается минимаксом по дереву ходов. Проблема возникает только тогда, когда мы начинаем оценивать количество операций/объём памяти, необходимые для такого "решения" игры, и сравнивать числа с количеством материи во вселенной или сроком её жизни. Но мы не можем не принимать во внимание вопросы вычислительной сложности электоральных стратегий.

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

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

* * *

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

Представим себе спокойное течение жизни Идеальной Охлократии в период, когда никакой информационной ассиметрии ещё нет - Алиса, Боб и Кэрол на скучных ежемесячных выборах голосуют по единой стратегии (ну, скажем, всегда - за "Лень Путина"), обеспечивая тем самым "нулевое" равновесие Нэша. Эта идилия разрушается, когда Кэрол, обиженая унижениями предыдущих выборов, решает взять реванш и рассорить Алису и Боба. Для этого она публикует в газете объявление следующего содержания:

Дорогие сограждане
Я готова вступить в сговор с любым разгадавшим мою загадку. Я задумала последовательность натуральных чисел, начинающуюся с [3, 1, 4, 1, 5, 9, 2, 6] - с первым, кто опубликует следующие три числа, я готова впредь совместно голосовать за партию, определяющуюся чётностью очередного элемента последовательности, начиная с первого ещё не опубликованного. Чётные числа будут означать голосование за "Лень Путина", нечётные - за "Путь Ленина".
Ваша Кэрол

План Кэрол прост и коварен - своим объявлением она сделала Алису и Боба антагонистами в новой игре "кто первым разгадает загадку". Ведь если Боб, например, первым назовёт числа [5, 3, 5], то у него с Кэрол появится общая секретная стратегия, позволяющая поддерживать "прибыльное" равновесие Нэша.

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