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

Пусть у игрока 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, поскольку каждый из этих элементов является минимальным элементом в своей строке и максимальным элементом в своём столбце.
Данная игра будет иметь четыре оптимальных решения, которыми являются следующие пары стратегий:

  • 2-я стратегия первого игрока и 2-я стратегия второго игрока, которым соответствует элемент а22;
  • 2-я стратегия первого игрока и 3-я стратегия второго игрока, которым соответствует элемент а23;
  • 3-я стратегия первого игрока и 2-я стратегия второго игрока, которым соответствует элемент а32;
  • 3-я стратегия первого игрока и 3-я стратегия второго игрока, которым соответствует элемент а33.

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

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

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

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

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