| 6, 7 |
[Apr. 15th, 2014|06:27 pm] |
6. Публичный заговор
Как мы помним из главы 2, голосования в Идеальной Охлократии проводятся открытым образом, то есть после оглашения результатов все избиратели знают кто за какую партию голосовал. Неудивительно, что при таком уровне прозрачности демкратических институтов общаться граждане привыкли столь же публично - единственным способом коммуникации для них является раздел бесплатных объявлений в местной газете. Если один гражданин хочет сообщить что-то другому, его послание, подписанное и навсегда заархивированное, одновременно становится доступно и всем остальным гражданам тоже.
Что же в такой ситуации должны делать Алиса и Боб, если они хотят обыграть Кэрол без помощи Трента? Да, они могут кидать монетки самостоятельно, но любая коммуникация с целью обменяться результатами бросков не останется в тайне от Кэрол, что на первый взгляд не позволяет им выработать общую секретную стратегию. Тем не менее, каждый, кто хоть отдалённо знаком с современной криптографией, сразу же узнает в Кэрол Еву, а в происходящем - типичный паттерн использования асимметричного шифрования[1]. Это внезапное дежавю уводит нас в сторону от теоретико-игрового анализа Идеальной Охлократии, что требует небольшого философского отступления в качестве объяснения.
Дело в том, что классическая теория игр не занимается вопросами сложности вычислений, использующихся в оптимальных стратегиях. С точки зрения теории игр го, например, довольно скучна - последовательная игра с двумя игроками и полной информацией, решается минимаксом по дереву ходов. Проблема возникает только тогда, когда мы начинаем оценивать количество операций/объём памяти, необходимые для такого "решения" игры, и сравнивать числа с количеством материи во вселенной или сроком её жизни. Вспоминая о том, что целью Идеальной Охлократии является моделирование эволюции разума пригодное для практических применений, мы не можем не принимать во внимание вопросы вычислительной сложности электоральных стратегий.
Возвращаясь к нашему случаю, если Алиса и Боб для синхронизации своих действий будут использовать криптографические схемы, основанные на односторонних функциях, то Кэрол в попытках предугадать их ходы столкнётся с необходимостью производить вычисления субэкспоненциальной сложности (факторизация, дискретное логарифмирование и т.д.). На практике это означает, что при равном доступе к ограниченным вычислительным ресурсам Алиса и Боб могут сделать задачу Кэрол по расшифровке их переписки неразрешимой, тем самым достигая того же эффекта что и в случае помощи Трента.
7. Отвечает Александр Друзь
В прошлой главе было показано, что избирательная система Идеальной Охлократии поощряет не только примитивный конформизм, как виделось поначалу. Несмотря на доступность исключительно публичных каналов общения, граждане вполне могут создавать ситуации информационной асимметрии, склоняя тем самым равновесие Нэша в свою пользу. То что Алисе и Бобу при этом пригодился столь мощный инструмент как асимметричное шифрование иллюстрирует потенциал модели - в фундаменте современной криптографии лежат нетривиальные достижения теории чисел, а поощрение понимания и применения теории чисел определённо можно считать поощрением сложного поведения.
Тем не менее, у этой иллюстрации есть проблема - асимметричная криптография неупрощаемо сложна, и трудно представить, как опирающаяся на неё стратегия может быть создана в результате эволюционного процесса. Для демонстрации плавной кривой обучения необходимо другое - примеры создания сложных стратегий путём малых локальных изменений изначально простых стратегий таким образом, чтобы каждый шаг положительно отражался на доходе сделавшего его гражданина. Для предыдущих глав было вполне достаточно рассматривать выборы в Идеальной Охлократии как одиночное событие, но для иллюстрации постепенной эволюции необходимо взглянуть на них как на итеративный процесс, в котором граждане голосуют с учётом опыта предыдущих выборов и всей предшествовавшей переписки.
Представим себе спокойное течение жизни Идеальной Охлократии в период, когда никакой информационной ассиметрии ещё нет - Алиса, Боб и Кэрол на скучных ежемесячных выборах голосуют по единой стратегии (ну скажем всегда за Лень Путина), обеспечивая тем самым "нулевое" равновесие Нэша из главы 3. Эта идилия разрушается, когда Кэрол, обиженая унижениями предыдущих глав нашего исследования, решает взять реванш и рассорить Алису и Боба. Для этого она публикует в газете объявление следующего содержания:
Дорогие сограждане
Я готова вступить в сговор с любым разгадавшим мою загадку. Я задумала последовательность натуральных чисел, начинающуюся с [3, 1, 4, 1, 5, 9, 2, 6] - с первым, кто опубликует следующие три числа, я готова впредь совместно голосовать за партию, определяющуюся чётностью очередного элемента последовательности, начиная с первого ещё не опубликованного. Чётные числа будут означать голосование за Лень Путина, нечётные - за Путь Ленина.
Ваша Кэрол
План Кэрол прост и коварен - своим объявлением она сделала Алису и Боба антагонистами в новой игре "кто первым разгадает загадку". Ведь если Боб, например, первым назовёт числа [5, 3, 5], то у него с Кэрол появится общая секретная стратегия, позволяющая поддерживать "прибыльное" равновесие Нэша из главы 4. Конечно рано или поздно Алиса догадается, что речь идёт всего лишь о цифрах десятичной записи числа пи, и сможет присоединиться к синхронному голосованию. Однако, это лишь вернёт ситуацию к новому информационному равновесию с нулевыми выплатами, но не вернёт денег, проигранных Алисой за время её раздумий в пользу Кэрол и Боба.
* продолжение следует *
[1] http://www.cs.cornell.edu/courses/cs513/2007fa/TL04.asymmetric.html |
|
|
