by prophet


0. Азартная игра "Войны Роз"

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

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

Сумма ставок на Ланкастеров - 3 шиллинга, победа
Сумма ставок на Йорков - 2 шиллинга, поражение

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

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

1. Искусственный Макиавелли

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

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

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

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

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

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

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

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

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

3. Принято единогласно?

Для наглядности предположим, что наше государство очень невелико - всего три избирателя (назовём их Алиса, Боб и Кэрол). Поскольку вариантов голосования для каждого гражданина только два, общее количество исходов - 2^3 = 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
            ---------------+---------------+---------------+---------------+-----+-----+-----

Анализ с позиций классической теории игр легко обнаруживает две точки равновесия Нэша3 - единогласные голосования за любую из партий с нулевой выплатой всем участникам.

Этот результат вполне интуитивен - чтобы не платить штраф, каждому избирателю выгодно голосовать вместе с большинством, что в свою очередь приводит к тому, что штрафов не платит никто, а значит и делить нечего.

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

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
            -----------+-----------+-----------+-----------+-----+-----+-----

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

7. Отвечает Александр Друзь

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

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

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

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

Дорогие сограждане

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

Ваша Кэрол

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

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



1http://ai.ato.ms/MITECS/Entry/whiten.html
2http://en.wikipedia.org/wiki/Tactical_voting
3http://faculty.lebow.drexel.edu/McCainR/top/eco/game/nash.html
4http://www.eprisner.de/MAT109/Mixedb.html
5http://www.cs.cornell.edu/courses/cs513/2007fa/TL04.asymmetric.html