Гимли.

Немного теории игр. Часть 2. Дилемма узника.

Начало здесь.

Желающие могут поиграть с знакомыми, партий 30, не выдавая своей стратегии и не меняя ее по ходу дела (просто пишите на листке одновременно - П (предательство) или Л (лояльность). Распространенные стратегии и соображения будут примерно такие (обратите внимание, как легко можно предсказать, как поведут себя большинство людей… "дилемма узника" - очень простой строительный кубик, часть более сложных игр).
1. Не выдавать никогда (в надежде на то, что партнер по игре поймет преимущество общего блага)
2. Выдавать всегда (приносит максимально возможный выигрыш, если повезет)
3. Не выдавать до первой (второй, третьей измены), потом выдавать всегда.
4. Выдавать до двух (трех, четырех) проявлений лояльности подряд, после чего никогда не выдавать.
5. Выдавать каждую 3 (4, 5) партию.
6. Выдавать каждую 3 и 4 партию, и, если противник два раза подряд отреагировал лояльно, эксплуатировать это до тех пор, пока он не ответит предательством.
... и так далее, во всевозможных вариациях, до появления следующего уровня анализа:

99. Чем сложнее становится стратегия, тем труднее ее понять, и оценить возможный выигрыш, тогда как случайный выбор, интуитивно говоря, должен выигрывать в половине случаев. Если интуиция подсказывает другое, можно делать случайный выбор с неравной вероятностью лояльности и предательства… можно, как это сделал я, рассматривать случайную игру как метод оскорбления партнера и использовать ее в ответ на повторяющееся предательство.
100. Ясно, что если партнер может выбрать такую безответственную линию поведения как бросание монетки, ожидать от него понимания общего блага не стоит. Имеет смысл продумать алгоритм, который по первым ответам попытается определить хотя бы самые экстремальные стратегии (полная лояльность, случайный выбор, периодически повторяющийся выбор) и реагировать на их присутствие наилучшим образом.
101. Имеет смысл также учесть опасность провоцирования предательского поведения в партнере. Можно оценить по его действиям, или хотя бы прикинуть заранее, какое поведение точно не будет прощено. Не забывайте, что единственный способ что-то выяснить о поведении партнера - посмотреть его реакцию на ваши действия, провоцирующие его на предательство.
Довольно неприятная ситуация - чтобы выяснить, можно ли доверять другому, нужно показать ему, что нельзя доверять вам. Логические цепочки в стиле "я знаю, что он знает, что я знаю, что он знает" можно наращивать до бесконечности...

300. Можно еще раз повысить уровень сложности, и, рассчитывая на длинную игру, написать экспертную систему, которая определяет не только простые алгоритмы, но алгоритмы типа (100) и реагирует на них соответственно, не забывая при этом гасить вспышки агрессивности противника проявлениями лояльности.

В 1980 году 15 профессоров социологии, политологии, психологии и математики подали программу на Фортране, реализующую алгоритм, который, по их мнению, обеспечивал лучший шанс выигрыша. Наилучшим исходом для игрока, очевидно, является полная лояльность его партера, и его постоянное предательство. Исход такой игры примем за максимум… интуитивно понятно, что хороший алгоритм должен достигать хотя бы четверти от максимума.
По результатам соревнования выяснился ряд не совсем очевидных фактов:
1. В очень короткой партии случайный выбор лучше любого другого алгоритма.
2. В короткой партии случайный выбор лучше любого алгоритма первого уровня сложности (номер 100 и выше), в длинной партии алгоритмы второго и третьего уровня сложности хуже любого алгоритма 0 уровня. (Парадокс, однако - более гибкое поведение, учитывающее больше фактов, приводит к худшему результату). Алгоритмы, написанные математиками, не вышли выше 6 места из 15.
3. Наилучший алгоритм, "TIT for TAT", состоящий из 4 строк (лояльность на первом ходу, повторение предыдущего хода противника на следующем) победил во всех длинных играх, и в коротких вышел на первое место наравне с "TIT for 2 TATs" (лояльность на первом ходу, одно предательство за два предательства подряд, лояльность во всех других случаях).
4. Наилучший результат наилучшего алгоритма не оправдал интуитивных ожиданий - выражаясь нашими неточными терминами, ожидаемая четверть от максимума оказалась одной шестнадцатой.

Давайте теперь немного о выводах…

28 Октября 2001 (06:08:11)

Продолжение здесь.

Обсудить эту лекцию вы можете здесь:

http://www.elhe.ru/cgi-bin/dekanat/YaBB.pl?board