Примеры решений Метод Брауна Системы массового обслуживания Матрица рисков Седловая точка Платежная матрица Цена игры Смешанные стратегии Матричная игра онлайн Чистые стратегии

Формализация игры. Матрица игры

Пусть у игрока A есть m возможных ходов (стратегий) A1, A2,... Am, а у игрока B n возможных ходов (стратегий) B1, B2, ... Bn. Если игрок A сделает ход Ai, а игрок B сделает ход Bj, то эти ходы Ai и Bj однозначно определяют исходы игры aij для игрока А и bij для игрока В. Полные наборы исходов игры записываются в виде платёжных матриц размером mⅹn, стратегии игрока А соответствуют строкам матриц, а стратегии игрока В соответствуют столбцам матриц.

В общем случае у каждого игрока своя платёжная матрица и игра называется биматричной. Две матрицы могут быть преобразованы в одну - биматрицу, каждый элемент которой состоит из двух чисел, выигрыша игрока А и проигрыша игрока В. Поскольку мы ограничились рассмотрением антагонистическими играми, при которых выигрыш одного из игроков точно равен проигрышу другого, то на матрицы А и В налагается условие А + В = 0 (или А = - В, aij = - bij ). В этом случае можно ограничиться только одной матрицей - матрицей А. Такие игры называются матричными.

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

Пример 1. Рассмотрим антагонистическую игру, в которой участвуют два игрока, каждый из которых имеет две стратегии. Выигрыши каждого из игроков определены следующими правилами: если оба из игроков выбирают стратегии с одинаковыми номерами, то первый выигрывает одну условную единицу. Если игроки выбирают разные стратегии, то выигрывает второй игрок условную единицу. В этом случае платёжная матрица имеет вид:
А =

Пример 2. Игроки A и B играют в следующую игру. Игрок A записывает одно из чисел 6, 7, 9, а игрок B записывает одно из чисел 4, 5. Если сумма чисел четная, то это выигрыш игрока А. Если сумма чисел нечётная, то это выигрыш игрока В (проигрыш игрока А). Найти платёжную матрицу игры А.
Имеем три стратегии первого игрока. А1 = 6, А2 = 7, А3 = 9, В1 = 4, В2 = 5. Матрица игры:
А =

Оптимальные стратегии

С платёжной матрицей A = (aij) связано несколько основных понятий теории игр (игровых моделей).

Определение 1. Нижней ценой игры V* называется величина, являющаяся максиминным значением платёжной матрицы:
V* = max min aij
(сначала находится минимум в каждой строке, а затем из полученных минимумов находят максимум). Нижняя цена игры - это гарантированный выигрыш первого игрока А при любой стратегии игрока В.

Определение 2. Верхней ценой игры V* называется величина, являющаяся минимаксным значением платёжной матрицы:
V* = min max aij
(сначала находится максимум в каждом столбце, а затем из полученных максимумов находят минимум). Верхняя цена игры - это гарантированный проигрыш второго игрока B при любой стратегии игрока A.
В силу того, что игра антагонистическая, всегда V* ≤ V*. Если V* = V* = V, то просто говорят о цене игры, такая игра называется вполне определённой, игрой с седловой точкой, поскольку значение элемента платёжной матрицы, равное V = V* = V* является минимальным в своей строке и максимальным в своём столбце. Соответствующие этой цене игры стратегии называются оптимальными, поскольку второй игрок не может понизить нижнюю цену игры, а первый игрок не может повысить верхнюю цены игры.

Пример 3. Платёжная матрица игры:
А = .

Определим, существует ли седловая точка. Для этого находим минимум в каждой строке матрицы. Минимальным числом в первой строке будет 3, во второй -- 4 и в третьей -- 2. Из полученных минимумов находим максимум:
V* = max(3,4,2) = 4
Находим максимум в каждом столбце. Это числа 6, 7, 4 соответственно. Из полученных максимумов находим минимум:
V* = min(6,7,4) = 4
Следовательно, исходя из данного выше определения цены игры, в данном случае цена игры V = V* = V* = 4, седловая точка существует, и это есть элемент платёжной матрицы a23 = 4. Ей соответствуют единственная оптимальная стратегии - A2 первого игрока и единственная оптимальная стратегия - B3 второго игрока.
В общем случае в игре может быть несколько седловых точек и, следовательно, несколько оптимальных стратегий (решений) игровой задачи.

Пример 4. Задана платёжная матрица игры, необходимо найти оптимальное решение игры.
А =
Определим, существует ли седловая точка. Для этого находим минимумы в каждой строке матрицы. Минимальным числом в первой строке будет 1, во второй это 2 и в третьей тоже 2. Из полученных минимумов находим максимум:
V* = max(1,2,2) = 2
Находим максимум в каждом столбце. Это числа 4, 2, 2 соответственно. Из полученных максимумов находим минимум:
V*=min(4,2,2) = 2
Следовательно, исходя из данного выше определения цены игры, в данном случае цена игры V = V* = V* = 2. Ей соответствуют стратегии A2 , А4 первого игрока, и стратегии В2, B3второго игрока (так как a22= а23 = а32 = а33 = 2). Из приведённого анализа следует, что в рассматриваемой платёжной матрице A существуют четыре седловых точек a22 , а23 , а32 , а33, поскольку каждый из этих элементов является минимальным элементом в своей строке и максимальным элементом в своём столбце.
Данная игра будет иметь четыре оптимальных решения, которыми являются следующие пары стратегий:

Данный пример иллюстрирует тот факт, что конечная антагонистическая игра может иметь множество оптимальных решений (множество пар оптимальных стратегий).

Пример 5. Задана платёжная матрица игры A, необходимо найти решение игры.
A =
В данной игре
V* = max (min aij)= 3aij

V* = min (max aij) = 4
Поскольку V* < V* - выполняется соотношение строгого неравенства, следовательно, седловая точка в игре отсутствует, ситуации равновесия не существует. Очевидно, что для данной игры рассмотренный выше подход к нахождению оптимального решения неприменим, а максиминная и минимаксная стратегия игроков не являются решением игры.

Приведённые выше примеры иллюстрируют тот факт, что антагонистические игры делятся на два класса:

  1. вполне определённые игры, т.е. те, в которых существует седловая точка, ситуация равновесия и решение игры в чистых стратегиях;
  2. не вполне определенные игры, т.е. те, в которых не существует седловой точки, ситуации равновесия и решения игры в чистых стратегиях. Для не вполне определённых игр принцип решения в той форме, для которой он изложен для вполне определённых игр, неприменим.