Методы решения матричных игр (на примере игры «Зачет»)

Итак, при  <   максиминная и минимаксная стратегии не являются оптимальными.

Рассмотрим теперь второй случай. Равенство (7) означает, что величина, которую гарантирует себе игрок  I, совпадает с величиной, больше которой игрок IIне позволит ему получить. Поэтому игрокам необходимо выбрать максиминную и минимаксную стратегии соответственно.

Пример 2

 

 

 

 

 

= ; 2-я строка – максиминная стратегия; 2-й столбец – минимаксная стратегия. В этом случае любое отклонение каждого из игроков от этих стратегий (игрока I–от максиминной, игрока II – от минимаксной) не может оказаться выгодным.

Определение 3. В случае = максиминная и минимаксная стратегии называются оптимальными стратегиями игроков, а общее значение   и (в дальнейшем мы будем обозначать через v) - значением или ценой игры.

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

Определение 3. В случае = максиминная и минимаксная стратегии называются оптимальными стратегиями игроков, а общее значение   и (в дальнейшем мы будем обозначать через v) - значением или ценой игры.

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

Определение 4. Точка (a, b) называется седловой точкой функции Н, если

H() ≤ H(a, b) ≤ H(a, ), А, B.

Это неравенство выражает следующее свойство функции  Н в точке (a, b): при любом изменении значения переменной, а значение функции Н может уменьшиться, а при изменении значения переменной b – увеличиться. Термин  “седловая точка” вводится по аналогии с термином “поверхность седла”, которая искривляется вверх в одном направлении и вниз – в другом.

Теорема 1. Для того чтобы  в матричной игре (2) существовали седловые точки, необходимо и достаточно, чтобы

 ≤ H(, ) = .       (8)

Доказательство. Необходимость. Пусть существуют седловые точки и (, ) – одна из них. Это означает, что

H(i, ) ≤ H(, ) ≤ H(, j), А, B.                (9)

Из равенства (9) получим 

(Г) = ≤ ≤ H(, ) ≤ H(, j) ≤ = (Г).                                                                                   (10)

В силу неравенства (6) все  неравенства (10) являются равенствами. Следовательно,

= ,

Что и доказывает необходимость.

Достаточность. Пусть теперь справедливо равенство (8).

При его выполнении двойное  неравенство (6) превращается в

(Г) = = H( , ) = = (Г).

Подставляя в неравенства (4) и (5) вместо (Г) и (Г) значенияH( , ), получим двойное неравенство (9), то есть – седловая точка.

Замечание 1. Из доказательства теоремы 1 видно, что  - соответственно максиминная и минимаксная стратегии игроков I и II и наоборот.

Замечание 2. При доказательстве теоремы 1 было установлено, что в качестве седловой  точки могут быть взяты любые i и j, на которых достигаются внешние экстремумы в минимаксах

, .

Поэтому если (– седловые точки функции , то, по-видемому, точки также будут седловыми для этой функции. И это действительно так.

Теорема 2. Пусть – седловые точки матричной игры (2). Тогда: а) являются седловыми точками;

b) H() = H() = H() = H().(11)

Доказательство. Точка () является седловой. Следовательно,

,

И в частности при i =

H() ≥ H().                                        (12)

Так как точка () является седловой,

H() ≤ H(), B,

В том числе при j =

H() ≤ H().                                        (13)

Объединяя неравенства (12) и (13), получим:

H() ≤ H() ≤ H().

Аналогично можно получить, что

H() ≤ H() ≤ H(),

И это доказывает равенство (11).

Далее, для любого i∈A

H() ≤ H() = H().

А для любого  j∈B

H() ≥ H() = H().

Следовательно,

H() ≤ H() ≤ H(), А, B

И () – седловая точка.

Аналогично доказывается, что и точка () является седловой.

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

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

Рисунок 1

Пример 3

 

 

 

 

 

Седловой точкой является пара , v = (Г)= (Г) = 2. Заметим, что хотя в ситуациях (1, 1) и (3, 4) выигрыш также равен 2, они не являются седловыми точками (этот выигрыш не является минимальным в строке и максимальным в столбце).

 

 

 

 

 

Пример 4

 

 

 

 

Седловыми точками являются пары  , , , ; Н() = H() = Н() = Н() = v = 2.

Пример 5

 

 

 

 

 

(Г) = 2,  (Г)=1. Так как(Г)≠(Г),рассматриваемая игра не имеет седловых точек.

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

 

1.3. Смешанные стратегии

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

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

Пусть задана матричная игра (2). В дальнейшем мы будем называть стратегии ∈ А, ∈B чистыми, чтобы отличать их от смешанных стратегий, определение которых будет дано ниже.

Определение 5. Смешанной  стратегией игрока называется произвольное распределение вероятностей на множестве его чистых стратегий.

Смешанная стратегия игрока I в игре Г есть вектор

X = (),

Где (i = 1, 2, … , m) – вероятность выбора им i-й чистой стратегии, 0 ≤ ≤ 1, а поскольку одна из m чистых стратегий будет обязательно выбрана, представляет собой вероятность полной группы событий и, следовательно,

 

Аналогично смешанная  стратегия игрока II есть вектор

Y = (),

Где (j = 1, 2, … , n) – вероятность выбора им j-й чистой стратегии,  

0 ≤   ≤ 1 и = 1.

Чистые стратегии являются частным случаем смешанной стратегии, задаваемой единичным вектором.

Множества смешанных стратегий  игроков I и II будем обозначать соответственно через и :

= { X = () ∈ |  0 ≤ ≤ 1, i = , };

= { Y = () ∈ | 0 ≤ ≤ 1, j = , }.

1.4. Смешанное расширение игры

Пусть в игре (2) с матрицей выигрышей

H = {, i= , j = }

Игроки I и II независимо друг от друга выбирают свои смешанные стратегии

X = () и Y = ().

Определение 6. Пара (X, Y) смешанных стратегий игроков в матричной игре (2) называется ситуацией в смешанных стратегиях в этой игре.

Так как игроки I и II выбирают свои смешанные стратегии X и Y независимо (это возможно в силу отсутствия какого-либо обмена информацией между игроками). В условиях ситуации (X, Y) каждая ситуация (i, j) (в чистых стратегиях) оказывается случайным событием, которое реализуется с вероятностью *. Следовательно, в условиях применения стратегий X и Y выигрыш игрока I есть двумерная дискретная случайная величина, заданная следующей таблицей:

Таблица 1.

Значения выигрышей игрока		…			…		…		…
Вероятности появления выигрышей	*	…	*	*	…	*	…	*	…	*

 

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

H(X, Y) = E(X, Y) = .                   (14)

Игрок II получит –E(X, Y).

Задав множества смешанных  стратегий ,  и функцию выигрыша       E(X, Y), мы определили новую игру

= <,  , E(X, Y) > ,                                   (15)

которая называется смешанным расширением игры (2).

Определение 7. Смешанным  расширением матричной игры Г = <А, В, Н> называется антагонистическая  игра Г = <, , E(X, Y) >, в которой множествами стратегий игроков являются их смешанные стратегии в исходной игре, а функция выигрыша игрока I определяется выражением (14).

В матричной форме выражение (14) можно записать так:

H(X, Y) = (, …, )  = ,

Где Т – знак транспонирования.

Вспоминая определение седловой точки (2), видим, что ситуация (, ) в смешанном расширении матричной игры являются седловой точкой, если при любых X∈ и Y∈ выполняется двойное неравенство

 ≤   ≤ .   (16)

Определение 8. Стратегии  , называются оптимальными смешанными стратегиями играков I, II в игре  (2), если для любых X∈ и Y∈ справедливо двойное неравенство (16).

Аналогично тому, как это  было сделано для игры (2), можно  ввести понятие нижнего и верхнего значения игры (15):

;

v˜ = .

Величина 

V = = =

Называется значением (ценой) игры Н.

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

Теорема 3. Для того чтобы  игра Н имела решение в смешанных  стратегиях, необходимо и достаточно, чтобы

= .(17)

Равенство (17) представляет собой принцип максимина (минимакса) в смешанных стратегиях.

Теорема 4. Если (, ) и (, ) – седловые точки игры в смешанных стратегиях, то:

А) (, ) и (,) также являются седловыми точками;

Б) Н(, ) = Н(, ) = Н(, ) = Н(,).

Доказательства теорем (3), (4) аналогичны доказательствам теорем (1) и (2).

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

Теорема 5. Какова бы была матрица  Н,

= .

Мы не будем останавливаться  на доказательстве этой теоремы. Впервые  она была доказана Джономфон Нейманом. Приводимое им доказательство основано на теореме Брауэра о неподвижной точке и в силу этого является неконструктивным (не дает способа нахождения решения игры).

Замечание 3. В литературе по теории игр можно встретить  различные названия этой теоремы  – теорема о минимаксах, терема Неймана, основная теорема (матричных игр).

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

2. Методы решения матричных игр

Согласно теореме 5 любая  матричная игра имеет значение v, а игроки в ней – оптимальные стратегии , (смешанные).

Тройку (, , v) будем называть решением матричной игры.

Сравнительно просто решаются игры, в которых один из игроков  имеет всего 2 чистые стратегии: игры 2×2, 2×n и m×2. При этом, как правило, игры 2×2 решается аналитическим методом, а 2 × n и m × 2 – графическим. При m, n> 2 матричные игры сводятся к задачам линейного программирования и решаются симплексным методом. Однако следует заметить, что уже в игре   3 × 3 применение этого метода приводит к довольно громоздким вычислениям.

2.1  Доминирование

Любая матричная игра может  быть решена путем решения системы  линейных неравенств

 ≤ v, i = 1, 2, …, m;

 ≤ v, j = 1, 2, …, n;

          , i = 1, 2, …, m;

             ≥ 0, j = 1, 2, …, n;