§2. Решение матричной игры

Пусть имеется матричная игра с платёжной матрицей A=(a_ij)_mn. Тогда игра называется mn-игрой. Если игра является игрой без седловой точки (то есть когда нижняя цена игры  и верхняя цена игры  не совпадают: <), то при многократном повторении игры игроки свои стратегии могут применить так, чтобы в среднем каждый игрок получил определённый средний фиксированный выигрыш. А именно, каждый игрок применяет свои стратегии случайным образом с определёнными вероятностями.

Пусть игрок А применяет свои стратегии A₁, A₂, …, A_m соответственно с вероятностями p₁, p₂, …, p_m, а игрок B применяет свои стратегии B₁, B₂, …, B_n соответственно с вероятностями q₁, q₂, …, q_n. Тогда математическое ожидание M(A, B)= двумерной случайной величины (A, B)  средний выигрыш игрока A. Обозначим его через V(A, P, Q). Попутно заметим, что p₁+p₂+…+p_m=q₁+q₂+…+q_n=1.

Стратегии P⁰=( , , …, ) и Q⁰=( , , …, ) называются оптимальными стратегиями игроков А и А соответственно, если выполнено следующее соотношение: V(A, P, Q⁰)V(A, P⁰, Q⁰)V(A, P⁰, Q). Величина =V(A, P⁰, Q⁰) называется ценой игры. Набор (P⁰, Q⁰, ) называется решением игры. Решить игру  это значит найти её решение.

2.1. Геометрический метод решения матричной игры.

1) Решение 2m-игры. Пусть  платёжная матрица 2n-игры. Тогда игру можно решить геометрически. Достигается это следующим образом:

I этап (шаги 1  3). Определяются вероятности (p₁, p₂)=(p, 1p) применения первым игроком соответственно первой и второй своих стратегий:

1. На плоскости pOw проводятся прямые w=(a_1ka_2k)p+a_2k, k=1, 2, …, n. Получаем некоторое семейство прямых.

2. Проводится нижняя огибающая этих прямых.

3. Определяется верхняя точка (p⁰, w⁰) нижней огибающей. Её абсцисса p⁰ и есть вероятность применения первым игроком своей первой стратегии: p₁=p⁰, а ордината  цена игры: =w⁰. Тогда p₂=1p⁰.

II этап (шаги 4, 5). Определяются вероятности q₁, q₂, …, q_n применения своих стратегий вторым игроком:

4. Пусть (p⁰, w⁰) (верхняя точка нижней огибающей)  точка пересечения i-й и j-й прямых, соответственно w=(a_1ia_2i)p+a_2i и w=(a_1ja_2j)p+a_2j. Тогда q_k=0 для всех k={1, 2, … n}\{i, j}, и можно положить q_i=q, q_j=1q.

5. Вероятности q_i=q и q_j=1q определяются из системы уравнений (точнее, только вероятность q_i, а по ней определяется q_j)

6. Выписываем ответ ((p⁰, 1p⁰), (0, …, 0, q_i, 0, …, 0, q_j, 0, …, 0), w⁰).

2) Решение m2-игры проводится по схеме, аналогичной схеме 2m-игры с некоторыми своими особенностями. Они  следующие:

1. Пусть  платёжная матрица m2-игры. Тогда события «разворачиваются» на плоскости qOw вокруг прямых w=(a_k1a_k2)q+a_k2, k=1, 2, …, m.

2. Проводится верхняя огибающая этих прямых и определяется нижняя точка (q⁰, w⁰) этой огибающей. Её абсцисса q⁰  вероятность применения вторым игроком своей первой стратегии: q₁=q⁰, q₂=1q⁰  вероятность применения второй стратегии, =w⁰  цена игры.

3. Если прямые w=(a_i1a_i2)q+a _{i 2} и w=(a_j1a_j2)q+a_j2 пересекаются в точке (q⁰, w⁰) то q_k=0 для всех k={1, 2, …, m}\{i, j}, и полагаем p_i=q, p_j=1p.

4. По системе

определяем p_i и p_j.

Не забываем сформулировать ответ ((0, …, 0, p_i, 0, …, 0, p_j, 0, …, 0), (q⁰, 1q⁰), w⁰).

Пример 1. Решить 42-игру с матрицей .

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

I этап. Определяем вероятности применения первым игроком соответственно первой и второй своих стратегий:

1. Проводим прямые

1. w=(42)p+2  w=2p+2

2. w=(23)p+3  w=p+3

3. w=(6(2))p2  w=8p2

Нижняя огибающая  это угол :

Верхняя точка этой огибающей  это точка B. Это  точка пересечения прямых (2) и (3). Находим её координаты:

 p+3=8p2  9p=5  p= ,

то есть p₁= , p₂=1p= , =w= +3= .

II этап. Определяем вероятности применения своих стратегий вторым игроком:

2. B  верхняя точка нижней огибающей  точка пересечения второй и третьей прямых. Поэтому q₁=0.

3. Вероятности q₂=q и q₃=1q определяем из системы уравнений

Имеем следующие равносильности:

 2q+6(1q)=3q2(1q)  9q=8  q= , q₃=1q= .

Ответ: (В исходной задаче у второго игрока четыре стратегии. Поэтому в ответе учитываем все!)

Пример 2. Найти решение 24-игры:

.

Решение. Так же, как и предыдущем примере, первому игроку выгоднее применение первой стратегии по сравнению со второй. Поэтому вторую строку исключаем из матрицы:

1. Стром прямые

1. w=(42)q+2  w=2q+2

2. w=(23)q+3  w=q+3

3. w=(6(2))q2  w=8q2

2. Верхняя огибающая этих прямых  это ломаная (ABCD):

3. Нижняя точка этой огибающей  это точка B. Это  точка пересечения прямых (1) и (2). Находим её координаты:

 2q+2=q+3  3q=1  q= ,

то есть q₁= , q₂=1q= , =w= .

4. B  нижняя точка верхней огибающей  точка пересечения первой и второй прямых. Поэтому p₃=0.

5. Вероятности p₁=p и p₂=1p определяем из системы уравнений

Имеем следующие равносильности:

 4p+2(1p)=2q+3(1p)  3q=1  p= , p₃=1p= .

Ответ: (Снова ответ формулируем с учётом того, что в исходной задаче у первого игрока четыре стратегии.)