Многие игры и задачи, в которых используется подобная модель, нельзя решить в чистых стратегиях, так как в них отсутствует точка равновесия. Обычно для каждого игрока не существует доминантной чистой стратегии, то есть стратегии, которая каждый раз будет оптимальной. Напротив, игроки не могут раскрывать свою стратегию и всячески пытаются утаить ее от соперника, в том числе путем обмана. Например, именно так действуют игроки в покер, которые всячески стараются обмануть соперников и раскрывают свои карты только тогда, когда этого прямо требуют правила игры.
Определение оптимальной смешанной стратегии
Вспомним третью (последнюю) игру, о которой говорилось в первом разделе этой главы. Каждый из двух игроков может записать одно из двух чисел: игрок А может записать 1 или 8, игрок Б — 2 или 7. Если четность обоих чисел совпадает (они оба четные или оба нечетные), А выигрывает сумму, равную записанному им числу. Если же одно из чисел четное, а другое — нет, победа остается за игроком Б, который выигрывает сумму, равную записанному им числу. Матрица игры выглядит так:
Игра выглядит справедливой (игрок А может выиграть 1 или 8 евро, игрок Б — 2 или 7), седловой точки не существует: максиминное значение равно -2, минимаксное — 1. Поэтому ни для одного из игроков не существует чистой стратегии. Посмотрим, как в этом случае можно сформировать смешанную стратегию, которая будет оптимальной и позволит определить цену игры.
Смешанная стратегия — это некий «случайный» выбор одной чистой стратегии из набора. Чтобы сформировать смешанную стратегию, каждой чистой стратегии присваивается вероятность, означающая, с какой частотой игрок будет использовать эту чистую стратегию. Например, в нашем случае для игрока А есть две чистые стратегии (записать 1 или записать 8), для Б — две другие. Попробуем найти вероятности p(записать 1), p(записать 8) для игрока А и p(записать 7), p(записать 2) для игрока Б так, чтобы максимально повысить шансы каждого игрока на победу. Если мы определим вероятности и платежи для каждого случая, то сможем определить ожидаемый выигрыш.
Сначала нужно определить вероятности для чистых стратегий игрока А. Обозначим за р вероятность того, что этот игрок запишет 8. Тогда вероятность написания 1 будет равна 1 — р. Следовательно, если игрок Б запишет 7, ожидаемый выигрыш игрока А составит
V = 1 (1 - р) + (-7) р. Получим линейное уравнение V = 1 - 8р.
Если же, напротив, Б запишет 2, то ожидаемый выигрыш для игрока А составит
V = (-2)(1 - р) + 8р, что равносильно V = 10р — 2.
Игрок А хочет найти, для какого р ожидаемый выигрыш будет наибольшим вне зависимости от того, какую из двух стратегий выберет игрок Б. Решив систему из двух линейных уравнений, получим значения р и V для игрока А. В данной задаче р = 1/6, V = -1/3.
Аналогично можно найти смешанную стратегию для игрока Б. Обозначим за р вероятность того, что он запишет 2. Тогда вероятность того, что он напишет 7, будет равна (1 — р). Если А запишет 1, то ожидаемый выигрыш Б составит
V = 2р + ( -1) (1 - р), что равносильно V = Зр — 1.
Аналогично если А выберет другую стратегию и запишет 8, то ожидаемый выигрыш игрока Б составит
V = ( -8)р + 7 (1 - р), то есть V = 7 - 15р.
Игрок Б хочет найти, для какого р ожидаемый выигрыш будет наибольшим вне зависимости от того, какую из двух стратегий выберет игрок А. Решив систему из двух линейных уравнений, получим значения р и V для игрока Б. Результаты будут следующими: р = 4/9, V* = 1/3.
Метод, который мы только что применили, можно обобщить для матриц 2 × 2 и использовать для решения игр, которые не имеют седловой точки, в смешанных стратегиях. Проанализируем полученные результаты более подробно. Во-первых, заметим, что ожидаемые выигрыши совпадают (V = 1/3) и отличаются только знаком. Для А найденный выигрыш отрицательный, для Б — положительный. Это означает, что Б ожидает выиграть столько, сколько проиграет А. Цена игры (средний выигрыш игрока А) определяется с помощью уравнения (ad - bc)/(а + d - b - с), где a,b,c,d — элементы платежной матрицы (слева направо и сверху вниз). Так, в нашем случае цена игры равна (8 - 14)/18 = -6/18 = -1/3, что означает, что игрок А в среднем будет проигрывать 1 евро за каждые три партии, если оба игрока будут придерживаться оптимальных стратегий.
Теперь мы можем напрямую найти смешанные стратегии как для игрока А, так и для игрока Б. Соотношение, с которым игрок А должен применять смешанные стратегии, можно определить, если найти выигрыш и проигрыш для каждой строки матрицы. Так, его выигрыши равны 1 - (-2) = 3 (для первого ряда) и - 7 - 8 = -15 (для второго ряда). Следовательно, в рамках оптимальной стратегии игрок А должен действовать случайным образом, но соблюдать соотношение 15 к 3, или 5 к 1. Он должен записывать 1 в пять раз чаще (например, перед каждым ходом бросать обычный кубик, на пять граней которого нанесена цифра 1, а на одну грань — цифра 8). Заметим, что этот результат совпадает с тем, который мы получили, решив систему уравнений. Вероятность того, что игрок А запишет 8, должна равняться 1/6, следовательно, вероятность того, что он запишет 1, должна равняться 5/6.
Проведем аналогичные вычисления для игрока Б (по столбцам). Для первого столбца 1 — (—7) = 8, для второго столбца -2 -8 = -10. Следовательно, игрок Б должен придерживаться соотношения 10 к 8, либо, что аналогично, 5 к 4, в пользу числа 7. Это совпадает с решением системы уравнений, приведенной выше: мы вычислили, что вероятность написания 2 должна составлять 4/9, следовательно, вероятность написания 7 должна составлять 5/9.
Теперь мы можем сформулировать оптимальную смешанную стратегию для каждого игрока. А делает ходы произвольным образом, но должен записывать 1 с вероятностью 5/6 и записывать 8 с вероятностью 1/6. Аналогично игрок Б должен произвольным образом выбирать между 7 (с вероятностью 5/9) и 2 (с вероятностью 4/9).
Для всех конечных игр двух игроков с нулевой суммой существует значение V, равное среднему ожидаемому выигрышу игрока А у игрока Б, если оба будут действовать разумно, то есть совершать ходы с целью увеличения выигрыша.
Эта теорема считается основной в теории игр и используется множеством способов даже в этой главе. Фон Нейман, который ее сформулировал и доказал, полагал, что в ее основе лежат три основные предпосылки.
1. Существование стратегии для первого игрока, которая наилучшим образом соответствует его интересам и позволяет ему получить определенный выигрыш (среднюю цену игры). Второй игрок ничего не может сделать против этой стратегии.
2. Существование стратегии для второго игрока, которая наилучшим образом соответствует его интересам и позволяет ему не проиграть более определенного значения (больше средней цены игры). Первый игрок ничего не может сделать против этой стратегии.
3. Тот факт, что игра имеет нулевую сумму, то есть выигрыш одного игрока равен проигрышу другого, означает, что существует некая средняя цена игры. И первый, и второй игрок согласны с этой средней ценой (она будет выигрышем для одного игрока и проигрышем для другого), поскольку любая другая стратегия будет в меньшей степени соответствовать их интересам.
Наконец, несмотря на то что седловой точки не существует, можно показать, что если каждый игрок будет придерживаться оптимальной смешанной стратегии, то игрок Б в среднем будет выигрывать 1/3 евро за партию. Если Б выберет любую другую стратегию, а игрок А будет придерживаться прежней, то выигрыш Б уменьшится. Напротив, если игрок Б будет придерживаться оптимальной стратегии, а игрок А выберет другую, проигрыш А возрастет.
Применение смешанных стратегий
В прошлом разделе мы подробно рассмотрели пример игры, чтобы увидеть, как можно решить игру в смешанных стратегиях для обоих игроков в случае, если игра не имеет седловой точки, то есть максиминное и минимаксное значения не совпадают. Мы рассмотрели абстрактную игру, чтобы читатель не отвлекался и сосредоточил внимание на элементах платежной матрицы, а не задумывался о том, что они означают.
Рассмотрим другие примеры, чтобы увидеть возможные применения метода смешанных стратегий.
Рост компании
Некая компания занимается разработкой нового продукта и оценивает возможность его выхода на рынок в следующем году. Можно выпустить продукт ограниченной серией из-за опасений, что экономическая обстановка будет неудовлетворительной, либо выпустить продукт крупной серией в надежде на экономический рост. Ожидаемая прибыль (в тысячах евро) приведена в таблице:
Руководство компании считает, что экономическая обстановка определяется некоей смешанной стратегией. Какова оптимальная смешанная стратегия компании и ожидаемая прибыль?
Элементы матрицы позволяют увидеть, что не существует оптимальной чистой стратегии, так как седловая точка отсутствует (максиминное значение равно 300, минимаксное равно 500). Следовательно, нужно определить оптимальную смешанную стратегию.
Обозначим за р вероятность выпуска крупной серии, (1 — р) — малой серии, V — ожидаемый доход. При плохой экономической обстановке доход будет равняться
V = 500 (1 — р) + ЮОр, что равносильно V = 500 - 400р.
При хорошей экономической обстановке доход будет равняться
V = 300 (1 — р) + 900р, то есть V = 300 + 600р.
Решением этой системы уравнений является р = l/5, V = 420. Это означает, что если бы ситуация могла повториться несколько раз, то оптимальным вариантом было бы выпускать продукт крупной серией 1 раз из 5 случайным образом и 4 раза из 5 — малой серией, при этом средний ожидаемый доход составит 420 тысяч евро.
Средний доход можно было вычислить напрямую с помощью формулы V = (ad - bc) / (а + d - b - с), где a, b, с, d — элементы платежной матрицы (слева направо и сверху вниз). Для данной задачи получим (500 • 900 - 300 • 100)/(500 + 900 - 300 - 100) = 420000/1000 = 420, что очевидно совпадает с результатом, полученным выше из системы линейных уравнений.
С другой стороны, мы действовали так, как если бы экономическая обстановка определялась некоей смешанной стратегией. Аналогичные расчеты показывают, что вероятность хорошей экономической обстановки равна 2/5, следовательно, вероятность плохой экономической обстановки равна 3/5.
Серия пенальти
Пенальти в футболе можно рассматривать как антагонистическую игру между пенальтистом и вратарем, где интересы участников прямо противоположны. Допустим, что пенальтист может пробить вправо, влево или по центру (это три чистые стратегии), а вратарь может прыгнуть в правый или левый от себя угол или же остаться в центре ворот (это также три чистые стратегии). На основании статистики была сформирована следующая таблица:
Элементы матрицы означают вероятность гола (то есть выигрыш бьющего) в зависимости от стратегии, выбранной обоими игроками. Например, если пенальтист бьет вправо, а вратарь прыгает в правый от себя угол, вероятность гола равна 0,9. Если же удар придется по центру и вратарь останется стоять в центре, то вероятность гола будет равной всего 0,1. Какой стратегии должны придерживаться бьющий и вратарь?
Корпорация RAND (от англ. Research and Development — «Исследования и разработка») — американский исследовательский центр, созданный после Второй мировой войны с целью проведения стратегических исследований для военно-воздушных сил США. Многие проекты корпорации были засекречены и не доведены до логического завершения, но нет никаких сомнений, что в RAND работали одни из лучших ученых в области теории игр. В 1948 году Центр получил статус частной организации, работающей исключительно на военно-воздушные силы, которые полностью его финансировали. Именно в этой корпорации были проведены фундаментальные исследования, которые способствовали развитию теории игр.
Внутренняя организация Центра больше напоминала научно-исследовательский институт, чем военное учреждение. В 50-е и 60-е годы прошлого века помимо прикладных исследований, связанных с ядерным оружием и началом холодной войны, в корпорации также проводились фундаментальные исследования силами выдающихся математиков и экономистов. Среди них все тот же Джон фон Нейман, Джон Нэш, Меррил Флад, Кеннет Эрроу и многие другие ученые, расцвет деятельности которых пришелся на этот короткий промежуток времени, совпавший с началом бурного роста теории игр.
Новая штаб-квартира корпорации RAND в Санта-Монике, Калифорния.
Первоначальный анализ показывает, что не существует доминантной чистой стратегии и что задача не имеет решения в чистых стратегиях, так как максиминное значение равно 0,6, а минимаксное — 0,8. Иными словами, пенальтист ожидает забить 6 из 10 пенальти, а вратарь ожидает, что пропустит гол в 8 из 10 случаев. Оба хотят (и могут) улучшить свой результат (т. е. выигрыш): пенальтист хочет, чтобы вероятность забить была выше 0,6, а вратарь хочет, чтобы вероятность пропустить была ниже 0,8.
Рассчитаем оптимальную смешанную стратегию для бьющего и для вратаря, а также среднюю цену игры, которая будет означать среднюю вероятность того, что с пенальти будет забит гол. В этом случае средняя цена игры будет лежать в интервале от 0,6 до 0,8.
Чтобы определить оптимальную смешанную стратегию для бьющего, нужно рассчитать вероятности выбора каждой из трех чистых стратегий. Обозначим их p(правый угол), p(левый угол), p(центр). Так как p(правый угол) + p(левый угол) + p(центр) = 1, число переменных можно сократить до двух: p(правый угол), p(центр), 1 - p(правый угол) - p(центр). Ожидаемую цену игры обозначим за V.
Если вратарь прыгнет в правый от себя угол, то ожидаемый выигрыш пенальтиста составит
V = 0,9 p(правый угол) + 0,8 p(центр) + 0,5 (1 - p(правый угол) - p(центр)).
Если вратарь останется в центре, то
V = 0,9 p(правый угол) + 0,1 p(центр) + 0,8 (1 - p(правый угол) - p(центр)).
Если же вратарь прыгнет в левый от себя угол, то
V = 0,6 p(правый угол) + 0,7 p(центр) + 0,8 (1 - p(правый угол) - p(центр)).
Мы получили систему из трех линейных уравнений. Ее решением будет являться p(правый угол) = 0,37; p(центр) = 0,19; p(левый угол) = 1 - p(правый угол) - p(центр) = 0,44. Цена игры для бьющего равна V = 0,71.
Аналогично можно рассчитать вероятности для каждой из трех чистых стратегий вратаря, но эту задачу мы оставляем читателю.