Принцип максимина в антагонистических играх. Седловая точка

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

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

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

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

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

Как видно, принцип максимина - это принцип крайне осторожного игрока, но именно он является основным принципом теории матричных игр.

Для пояснения принципа максимина рассмотрим пример 1 матричной игры G (4х5) с платежной матрицей, приведенной на рис. 2.2.

Пример 1.

 

Bj   Ai	B1	B2	B3	B4	B5	ai
A1	5	6	7	4	5	4
A2	3	10	6	5	6	3
A3	12	5	3	9	8	3
A4	6	7	5	6	10	5	максимин aij
bj	12	10	7	9	10
			минимакс aij

Рис. 2.2

Какой стратегией игроку А воспользоваться? Есть соблазнительный выигрыш 12, при применении стратегии А ₃. Но при этом противник может выбрать стратегию В ₃, и игрок А получит выигрыш, равный всего трем.

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

Эта величина - наш гарантированный выигрыш. Он называется нижней ценой игры (или «максимином» - максимальный из минимальных выигрышей). Будем обозначать его a. В нашем примере a = a_ij =5.

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

Припишем к платежной матрице (рис.2.2) нижнюю строку и в ней запишем наихудшее для игрока В возможные результаты (максимумы столбцов b _j.

Очевидно, осторожный противник должен выбрать стратегию, при которой величина b _j минимальна. Эта величина называется верхней ценой игры (или “минимаксом” - минимальный из максимальных проигрышей). Будем обозначать ее b. В нашем примере b = a_ij = 7.

Итак, исходя из принципа осторожности, игрок А должен выбрать стратегию А ₄, а его противник - В ₃. Такие стратегии называются максиминными или минимаксными стратегиями (вытекающие из принципа максимина).

До тех пор, пока обе стороны в нашем примере будут придерживаться своих максиминных стратегий, выигрыш игрока А и проигрыш игрока В будет равен а ₄₃=5.

Легко показать, что нижняя цена игры никогда не превосходит верхней цены игры.

Лемма 1. Пусть задана матрица выигрышей

А = êêa_ijêêи определены b=  и a= .

Тогда .

Доказательство. По определению максимума и минимума для любых фиксированных значений i и j имеем

                      (2.1)

Поскольку левая часть неравенства (2.1) не зависит от i, то можем записать

                           (2.2)

Так как правая часть неравенства (2.1) не зависит от j, то

                             (2.3)

Объединяя неравенства (2.2) и (2.3), получаем неравенство (2.1), что и требовалось доказать. Итак, всегда b ³ a.

Случай b = a, соответствует наличию у платежной матрицы так называемой седловой точки.

Определение. Точка (i *, j *) называется седловой точкой платежной матрицы || a _ij||, если для всех остальных i и j этой матрицы выполняется условие

a_i*j ³a_i*j*³ a_ij*,

т.е. а_ij является одновременно минимумом своей строки и максимумом своего столбца.

Приведем без доказательства следующую теорему.

 

Теорема 1. Для того чтобы

               

необходимо и достаточно, чтобы матрица || a _ij|| имела седловую точку. Кроме того, если (i ^*, j ^*) - седловая точка матрицы || a _ij||, то

         (2.4)

Говорят, что матричная игра имеет седловую точку, если соответствующая ей матрица выигрышей (платежная матрица) имеет седловую точку.

 

Пример 2. Найти решение игры G (3х3), платежная матрица которой имеет следующий вид:

 

Bj   Ai	B1	B2	B3	a i
A1	0	-1	-2	-2
A2	3	2	-1	-1
A3	6	3	0	0
bj	6	3	0

 

Определим  и и запишем их в таблицу.

Нижняя цена игры

Верхняя цена игры

Так как a=b=0, то платежная матрица и матричная игра имеют седловую точку. Оптимальными стратегиями для игрока А является стратегия А₃, а для игрока В - В₃.

Легко заметить, что отклонение игрока А от оптимальной стратегии приводит к уменьшению его выигрыша, а одностороннее отклонение игрока В - к увеличению его проигрыша.

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

 

Пример 3. Найти решение игры G (3х4), платежная матрица которой имеет вид:

Bj   Ai	B1	B2	B3	B4	a i
A1	7	6	9	6	6
A2	8	4	3	4	3
A3	7	6	8	6	6
b j	8	6	9	6

 

Определим a _i и b_j и запишем их в таблицу.

Находим нижнюю и верхнюю цену игры:

; . Видно, что игра имеет четыре седловые точки с соответствующими парами оптимальных стратегий: А₁В₂; А₁В₄; А₃В₂ и А₃В₄. Цена игры равна 6.

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

ТЕСТЫ

(В – Верно, Н – Неверно)

 

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

2. Название “матричная игра” произошло из-за того, что такая игра описывает платежной функцией в виде матрицы.

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

4. Оптимальной стратегией игрока в матричной игре называется такая, которая обеспечивает ему максимальный средний выигрыш.

5. Принципом максимина руководствуются очень азартные и рискованные люди (оптимисты).

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

7. Стратегии, выбираемые из принципа максимина, называются максиминными.

8. Нижняя цена матричной игры всегда равна верхней цене.

9. Случай, когда нижняя цена матричной игры равна верхней цене, соответствует наличию у платежной матрицы седловой точки.

10. Платежная матрица игры не может иметь несколько седловых точек.

11. Если платежная матрица игры содержит седловую точку, то ее решение сразу находится по принципу максимина.

 

(Ответы: 1-В; 2-В; 3-В; 4-В; 5-Н; 6-В; 7-В; 8-Н; 9-В; 10-Н; 11-В.)

 

ЗАДАЧИ

1. Составьте платежную матрицу игры Морра, если в ней участвуют два игрока, а максимально возможное количество «выбрасываемых» пальцев равно i (i =2,3,4,5,6,7,8,9,10). Выигрыш равен сумме пальцев выброшенных игроками. При четной сумме выигрывает первый игрок, при нечетной – второй.

2. Составьте платежную матрицу игры борьба за рынки, если фирма А имеет в своем распоряжение а условных денежных единиц, а противник - в. а=3,4,5,6,7,8,9,10; а соответствующие в=2,3,4,5,6,7,8,9.

3. Найдите седловую точку и максиминные стратегии игроков для следующих матричных игр:

 

3.1.	3	7	5		3.2.	3	6	1	8
	3	8	4			3	4	4	9
	1	8	3			6	8	5	9
	2	1	9			7	2	3	5
3.3.	4	7	4	8	3	3.4.	5	9	7
	7	6	5	6	9		5	10	6
	9	9	6	8	8		3	10	5
	5	7	3	4	3		4	3	11
	4	8	2	3	7
3.5.	6	12	2	16	3.6.	7	13	3	17
	6	8	8	18		7	9	9	19
	12	16	10	18		15	17	11	19
	14	4	6	10		15	5	7	11
3.7.	3	5	9		3.8.	3	5	6	4
	4	7	8			4	8	4	3
	2	1	5			6	8	5	5
						2	7	4	2

 

3.9.		4		6			3.10.			1		3	8	4	2
		5		2						8		5	5	9	11
		8		7						8		3	6	7	2
		3		1
3.11	3		6		2			3	5
	5		7		3			2	4