Как избежать тюрьмы?

Дилемма заключенного и теория игр

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

Обдумав эту ситуацию, прокурор приходит в камеру к Алу и предлагает ему следующую сделку:

1. Если вы дадите показания против своего подельника, а он против вас — нет, тогда, используя ваши показания, мы сможем осудить его за мошенничество. Ему дадут 10 лет тюрьмы, а вы выйдете на свободу;

2. Если вы откажетесь от сотрудничества, а ваш подельник даст показания против вас, все будет с точностью до наоборот. Вам дадут 10 лет тюрьмы, а он выйдет на свободу;

3. Если ни один из вас не сдаст другого, тогда нам ничего не остается, как предъявить менее серьезное обвинение в уклонении от уплаты налогов. Каждый из вас получит по 2 года тюрьмы;

4. Если вы оба дадите показания друг на друга, каждый из вас получит по 8 лет тюрьмы;

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

Оставшись один в своей камере, Ал раздумывает над возможными вариантами: «Для нас обоих лучшим вариантом будет третий. Там самый маленький срок среди всех предложенных. Так что, может, лучше сидеть и помалкивать и надеяться, что Берни будет вести себя так же. Хотя, минуточку... если он заговорит, мне грозит 10 лет. Если хорошо подумать, что бы ни выбрал Берни, мне-то выгоднее всего его сдать». Остановившись на этом, Ал решил сотрудничать с полицией. Берни же в своей камере рассуждает точно таким же образом и приходит к такому же выводу. Они сдают друг друга, и, таким образом, возникает ситуация номер 4.

Эта задача известна под названием дилеммы заключенного. Причина, по которой она интересна математикам, — в ее парадоксальном оттенке. Глядя с некоторого расстояния на все варианты, описанные выше, и рассматривая заключенных как пару, мы ви­дим, что третий вариант и правда самый лучший. Однако оптимальной тактикой для каждого из них по отдельности будет сдать другого, что приводит нас к четвертому варианту, который для них обоих самый плохой.

Больше, чем просто игра

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

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

Игры разума и равновесие

Одна из наиболее известных фигур в теории игр — Джон Нэш. Его докторская диссертация в Принстоне в 1950 году стала ключевой работой в этой науке.



Дилемма заключенного

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

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

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

Как сдержать обещание?

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



Дилемма заключенного с жестким договором

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

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

Договоры, конечно, не всегда полезны. В дилемме заключенного полиция несомненно захотела бы избежать описанного выше сценария. (Чтобы избежать таких случаев, в криминальных кругах часто заведен неизменный порядок — не сотрудничать с властями.

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

Компьютерные игры меняют мир

Теория игр уходит корнями в изучение древних настольных игр, таких как шахматы в Индии, го в Китае, мельница в Риме и манкала в Африке. Это необычное ответвление математики продолжает вызывать огромный интерес. Особенно это актуально со времен появления компьютеров. Одним из отцов современной компьютерной науки был Клод Шеннон (см. Как разговаривать с компьютером). В 1950 году он написал статью «Программирование компьютера для игры в шахматы». В ней он утверждал, что, хотя проблема «не имеет практической значимости», она заслуживает внимания, так как «шахматы в общем считаются игрой, требующей „мышления"; обучение компьютера игре в шахматы заставит нас либо признать возможность мышления у машины, либо ограничить наше понимание мышления».

Это были пророческие слова. Со времен работы Шеннона теория игр стала тесно связанной с погоней за искусственным интеллектом, а настольные игры, подобные шахматам, оказались отличными опытными образцами для его изучения. Поэтому, когда историки будущего будут смотреть назад на развивающиеся взаимоотношения между людьми и машинами, переломной датой, которую они отметят, возможно, станет 11 мая 1997 года. В этот день компьютер Deep Blue одержал победу над Гарри Каспаровым, чемпионом по шахматам среди людей. Он сразил его со счетом 2-1 в шести играх, три из которых окончились вничью.

Сильная сторона Deep Blue отчасти была в его исключительной вычислительной мощи: компьютер мог анализировать 200 миллионов игровых позиций в секунду. Конечно, кажется, что это много, но ведь шахматы — это очень сложная игра. Шеннон оценил приблизительное количество различных возможных шахматных позиций в 10^43, то есть 1 с 43 нулями. Deep Blue потребовалось бы несравнимо больше времени, чем время существования Вселенной, чтобы рассмотреть лишь мизерную их часть. Поэтому Deep Blue нужно было не перебирать все позиции подряд, а применять стратегии, чтобы число рассматриваемых вариантов было обозримым.

Шашки — игра попроще, чем шахматы, но, даже имея число позиций на доске, равное 5 х 10^20, она все равно слишком сложна, чтобы непосредственно просчитать все возможные ходы. Однако в 2007 году команда под руководством программиста Джонатана Шеффера объявила о том, что им удалось завершить необычный анализ этой игры. При помощи сети из десятков компьютеров, работающих одновременно с 1989 года, и новейших технологий в области искусственного интеллекта Шефферу и его коллегам удалось выявить, что «секрет шашек раскрыт». Они нашли идеальную стратегию игры — такую, что никогда не сможет быть побита ни величайшим из игроков среди людей, ни любой машиной, которую можно себе вообразить.

Отрывок из книги Элвса Ричарда "Как разгадать код да Винчи и еще 34 удивительных способа применения математики"