Теория игр: как математика выбирает правильную стратегию и находит выход из лабиринта противоречивых интересов

Играли ли вы сегодня во что-нибудь? Не спешите говорить «нет». Вы договорились о чем-то с другом, коллегой, членом семьи? Значит, вы играли. Выполняли свои служебные или бытовые обязанности? Это тоже игра. Делали покупки? Строили планы? Да-да, вы поняли. Жизнь вообще сплошная игра, по крайней мере, с точки зрения теории игр.

Что наша жизнь?

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

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

Теория игр — сложная наука, плотно сросшаяся с другими разделами высшей математики. Но ее важнейшие идеи можно объяснить без формул и на самых простых примерах (что совсем не значит, что до этих идей было легко додуматься!).

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

Что ж, приведем несколько примеров. В середине XX века специалисты по теории игр занимались вопросами ядерного сдерживания и гонки вооружений. В 1990-е «теоретико-игровики» из компании Market Design заработали миллионы долларов на аукционах по продаже радиочастот.

Дадим слово одному из богатейших людей и известнейших инвесторов в мире Уоррену Баффету: «Представьте себе, что некий эксцентричный миллиардер (только не я!) делает такое предложение: если законопроект будет отклонен, этот эксцентричный миллиардер любым допустимым способом пожертвует миллиард долларов в пользу политической партии, которая отдаст больше всего голосов за принятие законопроекта. Благодаря такому дьявольскому применению теории игр законопроект спокойно пройдет через Конгресс, на что наш эксцентричный миллиардер не потратит ни цента — а это говорит о том, что он не так уж эксцентричен».

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

Стратегия без стратега

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

Вы можете возразить, что играете в шахматы без продуманной и заранее выбранной стратегии. Просто делаете ход, который в данный момент считаете правильным. А уж о семейных спорах и деловых отношениях и вовсе не думаете в подобных терминах. Но, с точки зрения теории игр, то, что делает игрок, — и есть его стратегия.

Так, с точки зрения лингвиста, все, что мы говорим — речь, даже если это отнюдь не торжественная речь политика перед народом. Так что коль скоро мы всю жизнь играем в игры, то и ежечасно пользуемся стратегиями. Даже если не подозреваем об этом, как господин Журден не подозревал, что говорит прозой.

В простейшей формулировке задача теории игр — найти лучшую стратегию.

Дети и монеты

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

Возможные стратегии Ани непросто даже подсчитать в уме, не то что проанализировать каждую из них. У девочки три варианта первого хода. Затем ходит Боря, и на каждое из трех его возможных решений у Ани три варианта ответа, и так далее.

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

Первое правило теории игр — считать с конца, с победного хода.Если ваш последний ход принес победу, то каким был предпоследний? Ане нужно, чтобы на ее последнем ходу на столе лежало от одной до трех монет. Девочка заберет их и победит.

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

Игры, в которые играют люди

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

Как обстоит дело в шахматах, неизвестно. Эта игра очень сложна и до сих пор не просчитана полностью. Шутка ли: по приблизительным оценкам, различных шахматных партий около 10¹²⁰ (1 с 120 нулями). Это больше числа атомов в известной Вселенной!

Более того, игрокам не обязательно быть соперниками. Антагонистические игры, где выигрыш одного означает проигрыш другого — лишь одна из многочисленных разновидностей игр. Допустим, вы покупаете на рынке огурцы. У вас есть две стратегии: купить или нет, и у продавца две: продать или не продать. Если цена устраивает обе стороны, то покупка выгодна всем! Вы получаете вожделенные огурцы, а продавец — деньги.

В поисках равновесия

Идеальной — как говорят математики, доминирующей — стратегии выгодно придерживаться при любой стратегии партнера. Если доминирующая стратегия есть, то задача теории — ее отыскать. А если ее нет? Тогда в игру вступает более тонкое понятие — равновесие Нэша.

Игроки находятся в равновесии Нэша, если их стратегии являются оптимальным ответом друг на друга. Может быть, Боря и не выигрывает, но его стратегия — лучшее, что можно предпринять в ответ на усилия Ани. И наоборот, стратегия Ани — лучший ответ на действия Бори.

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

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

Бег к пропасти

Равновесие Нэша еще не означает, что выигрыш каждой из сторон одинаков. Это показывает классический пример — игра в труса.

Два водителя, Дураков и Тяпкин, едут навстречу друг другу (не пытайтесь воспроизвести эту метафору буквально!). У каждого водителя две стратегии: ехать прямо или свернуть. Тот, кто свернет первым, — «трус», или проигравший. Ему полагается пинок по мягкому месту. Но если никто не свернет, оба погибнут.

Проговорим еще раз: игроки находятся в равновесии Нэша, если их стратегии являются оптимальным ответом друг на друга. Если Дураков выбрал стратегию «ехать», то для Тяпкина лучший ответ «свернуть»: пинок всяко лучше смерти. Ну а поскольку Тяпкин сворачивает, то для Дуракова оптимальное решение — продолжать ехать прямо: он не только останется жив, но еще и выиграет.

Это равновесие Нэша, хотя Дуракову оно более выгодно, чем Тяпкину. Разумеется, есть и зеркально симметричное равновесие, когда Дураков сворачивает, а его бесшабашный друг едет прямо.

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

Игра кажется надуманной? Однако философ Бертран Рассел использовал ее как метафору гонки ядерных вооружений. Каждая сторона хочет заставить другую уступить. Выигрыш велик: победитель будет диктовать свои условия побежденному. Но что если никто так и не свернет? Не упустят ли «водители» момент, когда сворачивать будет поздно?

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

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

Свидание на «Смоленской»

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

Рассмотрим такую игру. Валентина и Геннадий случайно познакомились в Большом театре. Они договорились встретиться завтра в метро на станции «Смоленская». Увы, сутолока театрального буфета сыграла с парой злую шутку: ни один не вспомнил, что в московском метро две станции с таким названием. Как назло, легкомысленные театралы забыли обменяться телефонами.

Что теперь делать Геннадию? Можно выбрать одну из станций и надеяться, что Валентина придет именно туда. Если надежда оправдается, будет романтическое свидание. Присвоим этому исходу 5 баллов. Но если девушка выберет другую станцию или останется дома, Геннадий впустую простоит в метро. Это не лучший способ провести вечер, так что присвоим ему 0. С другой стороны, можно остаться дома и смотреть сериалы. Это будет вечер на троечку, зато гарантированную. Само собой, перед Валентиной открываются такие же альтернативы.

В этой игре целых три равновесия Нэша. Если Геннадий придет на станцию «Смоленская» Филевской линии, для Валентины оптимальная стратегия прийти туда же (равновесие 5, 5). Если Арбатско-Покровской, то и ей следует поступить так же (снова равновесие 5, 5). Если же кавалер предпочтет общество телевизора, то и даме не стоит утруждаться (равновесие 3, 3, менее выгодное, чем 5, 5).

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

Специальный раздел теории игр посвящен тому, как угадывать намерения игрока, если нет возможности спросить о них напрямую. В двух словах идея в том, чтобы опираться на общее знание. Если Валентина говорила, что ездит на работу по Филевской линии, туда и стоит отправиться Геннадию.

В экспериментах люди довольно часто находили друг друга в Нью-Йорке, не договариваясь ни о месте, ни о времени встречи — просто зная, что они будут друг друга искать. Они выбирали самое очевидное время (для американца это полдень) и самую известную достопримечательность в городе: небоскреб Эмпайр-Стейт-билдинг или площадь Таймс-сквер.

Баланс групп

Теория игр так же необозрима, как жизнь, которую она моделирует. Мы не касались игр, где больше двух игроков, и обошли стороной временные союзы и обязывающие договоры, обещания и обман, баланс между индивидуальными и групповыми интересами и многое другое. Главное, что нужно знать: теория не сделает вас гениальным игроком, но поможет понять, в какую игру вы играете. Возможно, игра проста и решение очевидно. Если вы обнаружите себя за рулем автомобиля, летящего навстречу другому, — лучше сверните.

Око за око

Простейшая игра «Дилемма заключенного», о которой полстолетия спорят математики, философы и психологи, затрагивает глубокие вопросы справедливости и объясняет, как «добрые» стратегии побеждают «злые» — всегда и везде, вопрос лишь во времени.

Правила игры «Дилемма заключенного» предельно просты. Полиция арестовала двух подельников — Алана и Боба. Если оба заключенных молчат на допросах, то каждый получает полгода тюрьмы. Если оба дают показания, каждый получает по два года. Но если один дает показания, а другой молчит, то предатель освобождается, а молчальник получает 10 лет.

Все возможные варианты действий (как говорят математики, стратегии) можно перечислить в короткой таблице внизу. Из нее видно, что для Алана стратегия «говорить» выгоднее стратегии «молчать» при любом поведении товарища. Даже если Боб молчит, выгоднее «сдать» его и выйти на свободу, чем полгода провести за решеткой.

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

Большие уроки маленькой игры

Итак, для каждого игрока в отдельности рациональная стратегия — дать показания. Но если оба игрока ей последуют, они получат по два года. Тогда как если бы оба промолчали, то отсидели бы всего по полгода.

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

Но что если Боб решит хранить молчание? Что ж, он сильно рискует. Если Алан окажется эгоистом, это будет стоить Бобу десяти лет. Второй урок очевиден: безропотный альтруизм в окружении эгоистов принесет лишь неприятности.

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

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

Китайский фантаст Лю Цысинь обыграл этот парадокс в романе «Темный лес». Он выдумал мрачную Вселенную, в которой каждая цивилизация уничтожает все известные ей разумные виды на всех планетах. И не по злобе, а из осторожности и недоверия: лучше нанести превентивный удар, чем допустить, чтобы инопланетяне напали первыми. Вот и третий урок: чтобы сотрудничать, нужно вести диалог, понимать друг друга и быть способным на доверие.

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

Удивительно, как много важных жизненных уроков можно извлечь из простенькой таблички 2х2. Но встречается ли дилемма заключенного в реальной жизни? Да, и чаще, чем хотелось бы.

Безбилетные пассажиры

Проехать «зайцем» в электричке выгодно. Но если в поездах останутся только «зайцы», транспорт перестанет ходить. Другой пример: каждый хочет бесплатного образования для детей, но мало кто хочет платить налоги. Для каждого в отдельности выгодная стратегия — уклониться от налогов и учить детей за чужие деньги.

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

Экономист Гаррет Хардин придумал термин «трагедия общин», объясняя, почему английские общественные пастбища XV–XVI вв. превратились в бесплодные пустыри. Каждый стремился получить больше овечьей шерсти, перекладывая последствия своих действий на всех остальных людей или на будущие поколения.

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

Добро с кулаками

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

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

Ученые полагают, что тяга к справедливости развилась у человека за миллионы лет эволюции. Человек не выживет в одиночку. Чтобы добыть пищу и защититься от опасностей, нужно сотрудничать. Однако в любом общем деле возникает опасность со стороны «безбилетников», которые даром пользуются результатами чужого труда. Сообщества, умевшие защитить себя от эгоистов, лучше выживали и размножались.

Искусство побеждать

Политолог Роберт Аксельрод заставлял компьютерные программы играть друг с другом в дилемму заключенного много раундов подряд и выбирал победителя по сумме набранных очков. Каждая программа придерживалась собственной стратегии: были альтруисты, предатели, любители справедливости и так далее.

В итоге Аксельрод сформулировал четыре свойства успешной стратегии.

• Во-первых, доброжелательность. Успешные программы никогда не предавали первыми.

• Во-вторых, готовность наказать за предательство.

• В-третьих, умение прощать: наказав предателя, успешный игрок снова был готов сотрудничать с ним (ссориться навсегда — не лучшая стратегия).

• Наконец, прозрачность: успеха добивались только алгоритмы, реакцию которых на сотрудничество или предательство было легко предсказать.

Лучше всего показала себя древняя как мир стратегия «око за око». Программа начинает с сотрудничества, а дальше копирует действия соперника. На сотрудничество она отвечает сотрудничеством, а на предательство — предательством.

Мудрость против справедливости

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

Удивительно, но эту опасность понимают даже обезьяны. В одном эксперименте хохлатые тамарины помогали друг другу добраться до еды до тех пор, пока одна из обезьян дважды подряд не совершила предательство. Можно назвать это стратегией «око за два ока».

Если оба игрока играют в «око за око», то на предательство Алана, настоящее или мнимое, ответом будет предательство Боба, влекущее за собой новое предательство Алана, и так без конца. Всегда отвечая ударом на удар, игроки никогда не закончат обмен ударами. История знает примеры кровной вражды, длившейся так долго, что никто уже не помнил, из-за чего она началась.

«Ибо никогда в этом мире ненависть не прекращается ненавистью, но отсутствием ненависти прекращается она», — сказано в одной буддийской притче.