В 1944 году была опубликована работа фон Неймана и Моргенштерна «Теория игр и экономическое поведение», в которой излагался алгоритм поиска оптимальных решений в играх с нулевой суммой для двух лиц. Именно это событие считается отправной точкой теории игр. Основным предметом исследований новой теории стали кооперативные игры и анализ оптимальных стратегий в случаях, когда оппоненты могут прийти к соглашению относительно выбранных стратегий.
В 50-е годы XX века в теории игр произошел заметный прорыв. Появились первые исследования дилеммы заключенного, Джон Нэш определил понятие оптимальной стратегии для игр со множеством игроков, когда оптимальную стратегию нельзя определить заранее (подобная ситуация известна как равновесие Нэша). Этот алгоритм применим для некооперативных игр, но может быть расширен и для кооперативных. В это же время теория игр впервые начала применяться в других областях помимо экономики, например, в философии и политологии. Позднее, уже в 1970-е годы, теория игр начала применяться в биологии в основном благодаря работам Джона Мейнарда Смита, который ввел понятие эволюционно стабильной стратегии.
Фотография Оскара Моргенштерна, который вместе с Джоном фон Нейманом является создателем теории игр.
Математика сотрудничества: игры с ненулевой суммой
Чтобы показать разницу между играми с нулевой и с ненулевой суммой, рассмотрим ситуацию, связанную с распространением рекламы. Две компании, А и Б, хотят прорекламировать свою продукцию. В обе компании поступает предложение от телеканала: рекламу можно показать днем (когда ее увидят 40% телезрителей) или вечером (тогда ее увидят 60% зрителей), причем можно выбрать только один из предложенных вариантов. Известно, что дневная и вечерняя аудитории не пересекаются. Если обе компании закажут рекламу на одно и то же время, то их продукцию купят 30% зрителей, включивших телевизор в это время, и никто из тех, кто смотрел телевизор в другое время. Если же компании закажут рекламу на разное время, то охватят 50% аудитории, которая в тот момент находилась у экранов. Какое решение оптимально для каждой компании? Будет лучше проконсультироваться с другой компанией или скрыть свои намерения?
Эту игру можно выразить в виде платежной матрицы, значения которой будут соответствовать доле аудитории. Однако в этом случае в каждую ячейку таблицы нельзя поместить какое-то одно значение, так как выигрыш одной компании не равен проигрышу другой и каждая компания будет иметь свою выгоду. По этой причине элементами матрицы будут пары значений. Первое число в каждой паре — выгода компании А, второе — выгода компании Б в зависимости от стратегий, выбранных обеими компаниями.
Если А и Б запустят рекламу днем, то каждой компании достанется 12% аудитории (30% от 40%). Если рекламные ролики выйдут в разное время, то результаты будут симметричны: если А запустит рекламу днем, а Б — вечером, то А получит 20% (половину от 40%), компания Б — 30% (половину от 60%). Если обе компании в этом случае сменят стратегии на прямо противоположные, противоположными окажутся и результаты.
Для анализа этой игры аналогично тому, как мы это делали ранее, нужно рассматривать две матрицы (с выигрышами каждого игрока), учитывая, что каждый игрок стремится максимально увеличить свой выигрыш в соответствии с платежной матрицей.
С учетом того, что матрицы симметричны и что стратегии А указаны в строках, а стратегии Б — в столбцах, анализ обеих матриц проводится аналогичным образом. Можно выполнить те же действия, что и для игр с нулевой суммой: седловая точка отсутствует (максиминное значение равно 18, минимаксное — 12), поэтому нужно найти смешанную стратегию, чтобы определить цену игры для игрока А. Эта стратегия такова: нужно использовать стратегию 1 (выпускать рекламу днем) с вероятностью 3/5 и стратегию 2 (выпускать рекламу ночью) с вероятностью 2/5. Таким образом мы получим цену 19,2 (средний выигрыш за партию). Аналогично для игрока Б (с учетом симметрии): в каждых пяти партиях он должен произвольным образом два раза выбрать стратегию 1 и три раза — стратегию 2, при этом его средний выигрыш будет тем же. Пока что нет никаких отличий от прошлых примеров, и читатель может посчитать, что мы определили оптимальную стратегию для каждого игрока и что игра решена.
Однако более подробный анализ игры показывает, что в этом случае каждый из двух игроков ожидает выиграть больше, и при этом выигрыш другого игрока останется прежним. Поэтому предыдущее решение не является оптимальным, и цена игры, найденная для оптимальных смешанных стратегий, используемых в играх с нулевой суммой, не всегда является наибольшей.
Это происходит потому, что оптимальные стратегии в играх с нулевой суммой основаны на ограничении или уменьшении выигрыша соперника. Если игра имеет нулевую сумму, то уменьшение выигрыша одного игрока равносильно увеличению выигрыша другого, но в нашем случае это не так. Допустим, что компания Б не будет использовать смешанную стратегию и всегда будет применять стратегию 2 (выпуск рекламы вечером), в то время как компания Б будет придерживаться смешанной стратегии. В этом случае компания А в среднем получит 30 • 2/5 + 18 • 3/5 = 22,8, а компания Б — по-прежнему 19,2. Заметим, что выигрыш Б не изменился, а выигрыш А возрос. В играх с нулевой суммой это невозможно. Очевидно, компания Б может действовать подобным образом и всегда использовать чистую стратегию 2, ожидая, что А будет придерживаться смешанной стратегии. В этом случае результат Б возрастет, результат А останется на прежнем уровне.
Но что произойдет, если обе компании используют чистую стратегию 2? Обе получат лишь по 18% аудитории, выигрыш обоих игроков уменьшится одинаково. Кажется, что мы зашли в тупик: каждая компания может выиграть больше, не повредив конкуренту, но если оба игрока захотят получить больше, то, напротив, выиграют меньше среднего ожидаемого значения.
Однако возможен и другой вариант. Допустим, что оба игрока заключили соглашение, чтобы не попасть одновременно в клетки с наименьшим выигрышем, то есть не размещать рекламу в одно и то же время. В этом случае каждая компания получит больше, при этом выигрыши компаний могут стать равными: если компания А будет чередовать стратегии 1 и 2, а компания Б — чередовать стратегии 2 и 1, то средний выигрыш для обеих компаний будет равен 25% за партию. Компания А будет попеременно получать 20 и 30 процентов, компания Б — 30 и 20. Это решение кажется оптимальным и, более того, является равновесным.
Разумная мысль: равновесие Нэша
Фон Нейман и Моргенштерн, изучив игры с нулевой суммой для двух лиц, перешли к анализу игр с большим числом игроков, учитывая возможные альянсы (группы из двух игроков и более, которые действуют согласованно), то есть отошли от чисто конкурентных игр. В 50-е годы XX века именно Джон Нэш расширил теорию игр, включив в нее некооперативные игры для n игроков, где альянсы были запрещены. Нэш уделял особое внимание играм с ненулевой суммой для двух и более игроков и пришел к мысли о равновесии, которое теперь известно как равновесие Нэша.
Алгоритм Нэша (или по меньшей мере его суть) кажется простым. Допустим, что разные игроки проанализировали игру и каждый выбрал определенную стратегию. Зная результат игры, зададим каждому игроку вопрос: считает ли он результат удовлетворительным? Иначе говоря, предпочел бы он действовать иначе? Если ответ положителен, то есть все участники считают, что грамотно выбрали стратегию, то, согласно Нэшу, в игре достигнуто равновесие.
Рассмотрим применение этой идеи в конкретном случае. В следующей матрице приведены результаты игры с ненулевой суммой:
Оба игрока выбрали стратегию 2. Узнав результат, они остались довольны выбором и сочли, что сделали все возможное. Первый игрок (его стратегии указаны в строках) считает, что его выигрыш, 5, был максимально возможным. Второй игрок, узнав, что первый выбрал стратегию 2, также посчитал свой выбор оптимальным: он выиграл 2, а мог не выиграть ничего.
Эту ситуацию можно оспорить, сказав, что первый игрок сделал «правильный» выбор, потому что выбранная им стратегия (2) является доминантной, а второй игрок может решить, что стоило выбирать первую стратегию, так как в этом случае он мог выиграть 100. Однако в конкурентной игре, где каждый игрок хочет увеличить свой выигрыш, подобная ситуация невозможна, если игрок 1 будет действовать рационально.
Следовательно, из четырех возможных результатов единственным, который не вызовет неприятия игроков, является (5, 2). Этот результат и является точкой равновесия Нэша. В партии с любым другим исходом один из игроков мог бы усомниться в правильности выбора. В этом случае в терминологии Нэша решение было бы нестабильным.
Примененный нами алгоритм интересен и дает рациональное решение. В этом контексте Нэш доказал, что любая конечная игра для двух лиц имеет минимум одну точку равновесия, и расширил таким образом теорему фон Неймана о минимаксе. В играх с нулевой суммой точка равновесия совпадает с точкой, найденной по теореме о минимаксе. Однако результат Нэша интересен тем, что позволяет найти точки равновесия в играх с ненулевой суммой, как мы увидели из прошлого примера. При этом найденное решение будет обоснованным.
Однако так происходит не всегда, и порой точка равновесия выглядит непривычно и имеет необычные свойства.
Возможно, труды Нэша, особенно его первые работы, являются важнейшими после работ фон Неймана за всю короткую историю теории игр. Уже в детстве Нэш продемонстрировал выдающийся интеллект и в то же время обнаружил трудности в общении с другими людьми. Он начал изучать химию, но вскоре переключился на математику, где отличался особым талантом. В 1948 году он получил стипендию Принстонского университета, где в то время работали Эйнштейн и фон Нейман, для написания докторской диссертации по теории игр под руководством Альберта Такера. В 1950 году он представил свою диссертацию — краткую и оригинальную работу о некооперативных играх. Его труд быстро нашел широкое признание среди специалистов по теории игр. Нэш при