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

Рисунок 4

Абсциссу точки М (точки  пересечения прямых (2) и (3)) найдем, решая уравнение

 

Следовательно, и   v = = 17/7.

Применяя формулы (22) для  игры

,

Найдем оптимальную стратегию  игрока II:

 

Таким образом,

 

Пример 10

Решить игру Н = .

Решение. Построим прямые

(1): Н = 1*х + 1*(1 – х) = 1;

(2): Н = 2*х + 0*(1 – х) = 2х;

(3): Н = 0*х + 2*(1 – х) = -2х  + 2.

Построим нижнюю огибающую  прямых (1) – (3)  (Рисунок5). Она имеет “пиковую” точку М, которая лежит строго между 0 и 1.

Рисунок 5

Решения уравнение

 

Найдем    и, следовательно,  

Применяя формулы (22) для  игры

 

Найдем оптимальную стратегию  игрока II:

   и

Так как через точку  М  проходит горизонтальная прямая (1), 

 

Таким образом,

, = 1), v = 1 .

 

2. Пусть теперь в матричной игре две чистые стратегии имеет игрок II, а игрок I – их произвольное число m. Это означает, что матрица выигрышей такой игры имеет следующий вид:

                                              (32)

Анализ игры подобного  вида сходен с приведенным выше анализом  2 × n – игр. Произвольная смешанная стратегия игрока II имеет вид Y = (y, 1 – y) , а их множество описать сегментом [0, 1]. Из теоремы 8 следует, что целью игрока II является минимизация величины

H(y) = .                             (33)

Графически зависимость  выигрыша

H(i, Y) =

От  y изображаются прямой линией. Каждой чистой стратегии игрока I соответствует своя прямая (Рисунок6).

Рисунок 6

Графиком функции (33) будет  верхняя огибающая всех прямых, соответствующих  стратегиям игрока I (на Рисунок7 она выделена жирной линией). Минимуму функции h(y) соответствует нижняя точка М огибающей, то есть

.

Так как 

,

По основной теореме (теорема 5)

v =

и, следовательно, абсцисса точки М является оптимальной  смешанной стратегией игрока II, а ее ордината – значением игры.

Пример 11

Решить игру 

Решение. Построим прямые

(1): H = 4*y + 3*(1 – y) = y + 3;

(2): H = 2*y + 4*(1 – y) = -2y + 4;

(3): H = 0*y + 5*(1 – y) = -5y + 5;

(4): H = -1*y + 6*(1 – y) = -7y + 6.

Построим верхнюю огибающую  прямых (1) – (4)  (Рисунок7). Ее нижняя точка М лежит строго между 0 и  1.

Рисунок 7

Далее,

 

 

Применяя формулы (22) для  игры

 

Найдем оптимальную стратегию  игрока I:

 

Таким образом,

 

 

Замечание 4. Графический  способможно применить и к решению игр      3 × n   и m × 3. Однако получающиеся при этом построения оказываются весьма громоздкими и требуют привлечения методов начертательной геометрии. При  m> 3 (n> 3)  графическое решение игры практически невозможно.

 

2.4. Сведение матричной игры к задаче линейного программирования

Решение матричной игры можно  свести к решению стандартной  задачи линейного программирования (ЛП).

Рассмотрим игру с  m × n – матрицей  выигрышей Н.

Теорема 9. Тройку () является решением игры Г = <> тогда и только тогда, когда ()  является решение игры

= < + a> , где а – любое вещественное число,  k> 0.

Доказательство. Утверждение  теоремы следует из того, что неравенства

Н(X, ) Н() ≤ Н(,  X∈, Y∈,

и

kН(X, ) + аkН() + a ≤ kН( + a,  X∈, Y∈,

эквивалентны.

В силу теоремы 9 всегда можно  добиться того, чтобы было v> 0 (в противном случае следует прибавить ко всем элементам матрицы выигрышей достаточно большую константу, что, по теореме 9, не меняет множества оптимальных стратегий игроков). Поэтому, не нарушая общности, будем считать, что все элементы матрицы Н положительны.

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

Пусть Х = () – произвольная стратегия игрока I в игре Н. положим v(X) = . из положительности элементов Н следует, что v(X) > 0. Мы имеем

v(X) ≤ , j = 1, 2, …, n;                                (34)

v(X)  ≤ v(H) = v  и равенство v(X) = v(H)  являются необходимым и достаточным условием оптимальности стратегии Х. следовательно, оптимальность стратегии Х равносильна тому, что

v(X) = .                               (35)

Так как  v(X) > 0 , обе части неравенства (34) разделим на  v(X)  и введем новую переменную  . в результате получим

.                                 (36)

То, что  Х – стратегия, означает

,                                   (37)

Где .

Из соотношений (35) и (37) следует, что стратегия Х будет оптимальной тогда и только тогда, когда

.

В результате задачу определения  оптимальной стратегии игрока I мы можем сформировать так:

T =

При условиях

 

………………………………………..

 

………………………………………...

 

 

Рассуждая аналогично, задачу нахождения оптимальной стратегии  игрока II можно записать в следующем виде:

L =

При условиях

 

………………………………………..

 

………………………………………...

 

 

 

Решив эти задачи, найдем    и v из соотношений

v= 1/ = 1/ .

Пример 12

Решить игру  Н =

Решение. Чтобы гарантировать  v> 0, прибавим ко всем элементам матрицы  Н константу  +1. Тогда получим матрицу

 

Пара двойственных задач  ЛП будет в данном случае выглядеть  следующим образом.

Минимизировать

Т =

при условии

 

 

 

 

 

 

Максимизировать

L =

при условиях

 

 

 

 

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

Таблица 2.

Номер интера-ции	Базисные перемен-ные
0		1 1 1	6             4         1         1        0        0 11        6      13        11        0       1      0 11       1  6        21        0        0       1							1/7 1/6 1
	L	0	-1       -1       -1        -1        0     0       0
I		1/7 1/7 6/7	6/7      1       4/7      1/7      1/7        0       0 41/7    0    67/7 -6/7      1      0 71/7038/7146/7-1/7 0      1							1 1/71 3/73
	L	1/7	-1/7     0     -3/7     -6/7      1/7     0      0
II		10/71 1/71	1        0                           0 41/71    0   67/71    1     -6/71     7/71    0
		40/71	0                0                    1
	L	11/71	25/71    0    27/71     0      5/71   6/71    0

 

После второй итерации симплексного метода получим оптимальное решение

= 0,   = 10/71,   = 0,  = 1/71и .

 Отсюда   и

= 71/11 * 10/71 = 10/11,   = 71/11 * 0 = 0,  = 71/11 * 1/71 = 1/11.

Таким образом, оптимальная  стратегия игрока II есть

=  (0, 10/11, 0, 1/11),  v = - 1 = 71/11 – 1 = 60/11.

Из индексной строки против переменных   ,  ,    получаем оптимальное решение первой задачи

= 5/71,   = 6/71,   = 0,  откуда  = 71/11 * 5/71 = 5/11, 

= 71/11 * 6/71 = 6/11,   = 71/11 * 0 = 0   и  

Итак,

( ((5/11, 6/11, 0), (0, 10/11, 0, 1/11), 60/11).

 

 

 

II. Практическая часть

1. Семейный спор

Два партнера договариваются о совместной реализации одного из двух действий,(1) или (2).

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

 

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

Решение.

Выигрыши игроков А и В в этой биматричной игре задаются так:

 

 

Проведя необходимые вычисления

 

 

 

Из неравенств

 

 

получаем, что

 

 

 

Геометрически результат описывается так (Рисунок8).

 

Рисунок 8

Данная игра имеет три  точки равновесия. Две из них отвечают

чистым стратегиям игроков,

 

 

а одна – смешанным,

 

 

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

Ситуации  (1,1) и (0,0) соответствуют  одновременному выбору игроками своих  первых или, соответственно, вторых стратегий, то есть определенной договоренности о совместных действиях. Однако в  данном случае есть еще одна ситуация равновесия состоящая в выборе игроками вполне определенных смешанных стратегий. В ней оба игрока получают одинаковые выигрыши, правда, меньшие тех, которые  дают две другие равновесные ситуации. Какой же из этих трех ситуаций равновесия следует отдать предпочтение? Какую выбрать игрокам? Если бы игроки договорились играть оба, скажем, первую чистую стратегию, причем игрокА за получение большего выигрыша, чем игрок В заплатил бы ему 1/2, то выигрыш каждым полутора единиц можно было бы считать и выгодным, и справедливым. Однако в рамках теории бескоалиционных игр такого рода дележи не рассматриваются. Ясно, что для выбора каждым из игроков своей линии поведения (напомним, что подобная ситуация может повторяться и повторяется многократно) необходимы либо расширение возможностей, имеющихся у игроков, либо иные, измененные критерии.  

2. Студент – преподаватель (игра «Зачет»)

Обратимся к одному из примеров биматричных игр – студент-преподаватель. Впечатления у каждого из них относительно результатов общения в матричном виде выглядит следующим образом:

 

Проводя необходимые вычисления:

 

 

и рассуждения:

 

Получаем, что

 

 

(Рисунок 9).

Рисунок 9

Число точек пересечения  зигзагов (равновесных ситуаций) равно  трем. Две из них отвечают чистым стратегиям игроков:

 

 

 

 

одна – смешанной:

 

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

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

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

 

 

 

Заключение

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