Платежная матрица

Рассмотрим конечную игру, в которой игрок («мы») имеет стратегий, а игрок В («противник») — стратегий. Такая игра называется игрой Будем обозначать наши стратегии стратегии противника — Предположим, что каждая сторона выбрала определенную стратегию: мы выбрали противник — Если игра состоит только из личных ходов, то выбор стратегий однозначно определяет исход игры — наш выигрыш (положительный или отрицательный); обозначим его

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

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

Такая таблица называется платежной матрицей или просто матрицей игры.

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

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

Рассмотрим несколько элементарных примеров игр и построим для них платежные матрицы.

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

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

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

прятаться в убежище I,

прятаться в убежище II.

У противника (В) тоже две стратегии:

— искать в убежище I,

— искать в убежище II.

Перед нами игра Ее матрица имеет вид:

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

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

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

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

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

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

Пример 2. Игра «три пальца».

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

Решение. У каждого игрока по три стратегии: показывать один, два или три пальца. Матрица игры 3x3 имеет вид:

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

Однако попробуем стать на точку зрения второго игрока (В). Его положение тоже не из блестящих. Если он выберет мы ответим ему и он отдаст нам 4 руб; если — мы ответим и снова получим 4 руб; также и на у нас есть ответ приводящий к еще худшему результату: В проиграет 6 руб.

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

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

Решение. Матрица игры 3x3 имеет вид: где выигрыш — вероятность поражения самолета (мы стремимся его максимизировать, а противник — минимизировать).

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

Станем сперва на точку зрения игрока А и переберем одну за другой все его стратегии. На противник ответит нам и мы выиграем 0,5; на и мы выиграем 0,7; на — снова и мы выиграем 0,5. Очевидно, некоторое преимущество над другими имеет стратегия А 2 — при ней мы выиграем больше, а именно 0,7.

Станем теперь на точку зрения противника; не забудем, что он хочет отдать поменьше! Пусть он выбирает — мы отвечаем ему и он отдает 0,9; на мы отвечаем ему и он отдает 0,7; на и он отдает 0,8. Естественно, он предпочтет чтобы отдать только 0,7.

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

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