Лекция №17

Рассмотрим парную конечную игру с нулевой суммой с игрокам А и В, которые имеют конечное число стратегий соответственно А₁, А₂,... А_m и В₁, В₂,... В_n. Такая игра называется игрой m x n. Исход каждой партии завершается выигрышем одного из игроков.

Обозначим a_ij - выигрыш игрока А, если он использует стратегию А_i, а игрок В стратегию В_j. Тогда выигрыш игрока В очевидно равен b_ij=- a_ij, так как игра с нулевой суммой. Поэтому в дальнейшем будем рассматривать лишь выигрыш одного из игроков. Если игра содержит кроме личных и случайные ходы, то выигрыш a_ij есть величина случайная, зависящая от исходов всех случайных ходов. В этом случае оценкой ожидаемого выигрыша является математическое ожидание случайного выигрыша. В дальнейшем будем обозначать a_ij как сам выигрыш (в игре без случайных ходов), так и его мат. ожидание (в игре со случайными ходами).

Предположим, что известны a_ij для любой пары (А_i В_j). Эти значения записываются в таблицу, называемую ПЛАТЕЖНОЙ МАТРИЦЕЙ.

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

Пример 1. Игра «поиск».

Имеется два игрока А и В, игрок А прячется, а В его ищет. В распоряжении игрока А имеется два убежища (I и II), любое из которых он может выбрать по своему усмотрению. Условия игры таковы: если В найдет А в том убежище, где А спрятался, то А платит ему штраф 1 руб.; если В не найдет А (т. е. будет искать в другом убежище), то он сам должен заплатить А такой же штраф. Требуется построить платежную матрицу.

Решение. Игра состоит всего из двух ходов, оба - личные. У нас (А) две стратегии:

А₁ — прятаться в убежище I, А₂ — прятаться в убежище II. У противника (В) тоже две стратегии:

В₁ — искать в убежище I, В₂,— искать в убежище II. Модель этой задачи представляется игрой 2х2. Ее матрица имеет, вид табл. 7.1.

Таблица 1

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

Предположим сначала, что данная игра выполняется только один раз (играется единственная «партия»). Тогда, очевидно, нет смысла говорить о преимуществах тех или других стратегий - каждый из игроков может с равным основанием принять любую из них. Однако при многократном повторении игры положение меняется.

Действительно, допустим, что мы (игрок А) выбрали какую-то стратегию (скажем, А ₁ ) и придерживаемся ее. Тогда, уже по результатам первых нескольких партий, противник догадается о нашей стратегии, начнет всегда искать в убежище I и выигрывать. То же будет, если мы выберем стратегию А ₂. Нам явно невыгодно придерживаться одной какой-то стратегии; чтобы не оказаться в проигрыше, мы должны чередовать их. Однако, если мы будем чередовать убежища I и II в какой-то определенной последовательности (скажем, через одну партию), противник тоже догадается об этом и ответит наихудшим для нас образом. Очевидно, надежным способом, гарантирующим нас от верного проигрыша, будет такая организация выбора в каждой партии, когда мы сами его наперед не знаем. Например, можно бросить монету, и, если выпадет герб, выбрать убежище I, а если решка - убежище II.

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

Таким образом, мы подошли к одному из существенных понятий теории игр - к понятию смешанной стратегии, то есть такой, в которой отдельные «чистые» стратегии чередуются случайным образом с какими-то вероятностями. В данном примере из соображений симметрии ясно, что стратегии А ₁ и А ₂ должны применяться с одинаковыми вероятностями; в более сложных примерах решение может быть далеко не тривиальным.

Пример 2. Игра «вооружение и самолет».

В нашем распоряжении имеются три вида вооружения: А ₁, А ₂ ., А ₃; у противника - три вида самолетов: В ₁, В ₂, В₃. Наша задача - поразить самолет; задача противника - сохранить его непораженным. Наш личный ход - выбор типа вооружения; личный ход противника - выбор самолета для боевых действий. В данной игре имеется еще и случайный ход - применение вооружения. Вооружением А ₁ самолеты В ₁, В ₂, В ₃ поражаются соответственно с вероятностями 0,5, 0,6, 0,8; вооружением А ₂. - с вероятностями 0,9, 0,7, 0,8; вооружением А ₃, - с вероятностями 0,7, 0,5, 0,6. Построить матрицу игры и проанализировать ситуацию.

Решение. Матрица игры 3х3 имеет следующий вид.

Таблица 2

где выигрыш - вероятность поражения самолета (мы стремимся его максимизировать, а противник - минимизировать). Станем сначала на точку зрения игрока А и переберем одну за другой все его стратегии. На А ₁ противник ответит нам В ₁, и мы выиграем 0,5; на А₃ – В ₂, и мы выиграем 0,7; на А ₃ - снова В ₂, и мы выиграем1ё 0,5. Очевидно, некоторое преимущество над другими имеет стратегия А ₂ - при ней мы выиграем больше, а именно 0,7.

Станем теперь на точку зрения противника. Пусть он выбирает В ₁ - мы отвечаем ему А ₂ ., и он отдает 0,9; на В ₂ мы отвечаем ему А ₂ ., и он отдает 0,7; на В ₃ – А ₃, и он отдает 0,8. Естественно, он предпочтет В ₂, чтобы отдать только 0,7.

Мы видим, что в данном примере стратегии А ₂. и В₂ с выигрышем 0,7 являются наивыгоднейшими сразу для обеих сторон; игроку А выгоднее всего выбирать стратегию А ₂, игроку В - стратегию В ₂, и максимальный выигрыш А совпадает с минимальным проигрышем В. Достигнуто как бы положение равновесия: если А выберет стратегию А ₂ ., то В не может найти лучшего выхода, чем В ₂, и наоборот: если В выберет стратегию В ₂, то А не может найти лучшего выхода, чем А ₂.

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

Лекция №17.