11. Теория игр
О чем думают остальные
Я оптимист в том смысле, что считаю, что люди благородны и честны, а некоторые из них еще и очень умны… Но у меня несколько более пессимистичный взгляд на людей в группах.
Стив Джобс
Инвестор продает акции; при этом продавец убежден, что их стоимость падает, а покупатель убежден, что растет; я думаю, что я знаю, о чем вы думаете, но не имею ни малейшего представления о том, что вы думаете по поводу того, о чем думаю я; экономический пузырь лопается; потенциальный любовник преподносит подарок, который не говорит ни «я хочу быть больше, чем другом», ни «я не хочу быть больше, чем другом»; за обеденным столом идет перебранка – кто должен заботиться о ком и почему; кто-то, желая помочь, нечаянно обижает; кто-то, пытаясь выглядеть крутым, вызывает усмешку; кто-то, пытаясь не поддаваться стадному инстинкту, к своему ужасу, сам становится лидером стада. «Я люблю тебя», – говорит один; «Я тоже люблю тебя», – отвечает второй; и каждому интересно, что именно имеет в виду другой.
А что же по поводу всего этого говорит информатика?
Школьников учат классифицировать сюжеты литературных произведений по принадлежности к одной из нескольких категорий: человек против природы, человек против себя, человек против человека, человек против общества. До сих пор в этой книге мы рассматривали главным образом случаи из первых двух категорий, то есть до настоящего времени информатика была нашим проводником среди проблем, порожденных фундаментальной структурой мира и нашими ограниченными возможностями обработки информации. Оптимальные пути решения проблем возникают из понимания необратимости и невозвратности времени, то есть при попытке найти выход из затруднительного положения в рамках ограниченного ресурса времени. Релаксация и рандомизация выступают такими же жизненно важными и необходимыми стратегиями для борьбы с неотвратимой сложностью задач, как планирование поездок или вакцинаций.
В этой главе мы сместим фокус и рассмотрим две оставшиеся категории – человек против человека и человек против общества: по сути дела, это связанные и вытекающие друг из друга проблемы. Самым лучшим навигатором на этом поле станет для нас направление математики, известное как теория игр, то есть та область, которая в ее классическом воплощении оказала огромное влияние на XX столетие. На протяжении пары последних десятилетий перекрестное опыление между теорией игр и информатикой породило алгоритмическую теорию игр, которая уже начала оказывать влияние на XXI век.
Рекурсия
Сейчас умный человек положил бы яд уже в собственный бокал, потому что он знает, что только полный глупец станет тянуться к тому бокалу, что стоит перед ним. Но ведь я не так глупа, чтобы выбирать вино, стоящее перед вами. Но вы также знаете (и явно на это рассчитываете), что я не так глупа, чтобы выбрать вино, стоящее передо мной.
Фильм «Принцесса-невеста»
Самый, пожалуй, влиятельный экономист XX века Джон Мейнард Кейнс однажды сказал, что «успешное инвестирование опережает предчувствие других». Чтобы продать пакет акций, скажем, за $60, покупатель должен верить, что потом он сможет продать его за $70 тому, кто считает, что он может продать его уже за $80 тому, кто уверен, что он может продать этот пакет уже за $90 тому, кто в свою очередь убежден, что он может продать его за $100 еще кому-то. Другими словами, стоимость акций – это не то, что люди думают по поводу стоимости, но то, что люди думают, что думают другие по поводу того, сколько это стоит. На самом деле даже не стоит так далеко углубляться. Как заметил Кейнс, делая важное различие между красотой и популярностью:
Профессиональные инвестиции можно сравнить с теми соревнованиями на страницах газет, когда участники должны выбрать шесть самых хорошеньких лиц из сотни фотографий, а приз присуждается тому участнику, чей выбор наиболее близко соответствует усредненным предпочтениям конкурентов в целом. Таким образом, чтобы победить, каждый участник должен выбирать не те лица, которые лично он считает симпатичными, но те, которые, наиболее вероятно, понравятся другим конкурентам, каждый из которых смотрит на проблему выбора с той же самой точки зрения. Это не тот случай, когда выбираются те, которые, на чей-то взгляд, на самом деле являются самыми симпатичными, и даже не те, которые, по общему среднему мнению, искренне считаются симпатичными. Мы достигли третьего уровня, когда наши размышления направлены на то, чтобы предвидеть, что общее усредненное мнение может думать по поводу того, каким может быть это среднее мнение. На мой взгляд, есть и такие, кто практикует четвертый, пятый и даже более высокие уровни.
Информатика иллюстрирует фундаментальные ограничения такого рода рассуждений с помощью так называемой задачи об остановке. Как в 1936 году доказал Алан Тьюринг, никакая компьютерная программа никогда не сможет с уверенностью сказать вам, сможет ли другая программа в конечном итоге закончить свои вычисления – если только специально не моделировать работу этой программы, чтобы, таким образом, попытаться потенциально дойти до самого конца. (Соответственно, у программистов никогда не было автоматизированных инструментов, которые могли бы сказать им, будет ли их программное обеспечение блокироваться.) Это один из основополагающих результатов для всех разделов информатики, на котором базируются многие последующие доказательства
[34]. Проще говоря, в любое время система – будь то машина или разум – моделирует работу чего-либо с той степенью сложности, которая ей соответствует, максимально полно используя свои ресурсы. Ученые-компьютерщики используют специальный термин «рекурсия» для обозначения этого потенциально бесконечного путешествия в зеркальную комнату, где разум моделирует разум, который моделирует разум.
«В покере вы никогда не играете себе на руку, – говорит Джеймс Бонд в фильме "Казино Рояль", – вы играете против человека, сидящего напротив вас». На самом деле то, что вы разыгрываете, является примером теоретически бесконечной рекурсии. Существует ваша собственная комбинация карт и комбинация, которую, как вы считаете, имеет ваш противник; затем рассматривается комбинация, которую, по вашему мнению, представляет у вас ваш оппонент, и комбинация, которую, как вы считаете, представляет себе ваш оппонент, размышляя о той комбинации, что он имеет… и т. д. «Я даже не знаю, реальный ли это термин теории игр, – говорит топовый игрок в покер Дэн Смит, – но игроки в покер называют это "выравнивание". Первый уровень – я знаю. Второй уровень – вы знаете, что я знаю. Третий уровень – я знаю, что вы знаете, что я знаю. Порой складываются ситуации, когда вы просто заходите туда, где вы начинаете думать: «Хм, это действительно неподходящий момент, чтобы блефовать; но, если он знает, что это неподходящий момент, чтобы блефовать, то он не будет поднимать ставки, и тогда это как раз самый подходящий момент, чтобы блефовать. Такое случается»».
