Игровые модели. Графоаналитический метод решения

 

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

Графоаналитический метод решения применим к играм вида 2 n и m 2, в которых хотя бы один игрок имеет только две стратегии. Рассмотрим.следующую игру вида 2 х n (табл.7.4). Предполагается, что игра не имеет седловой точки.

Поскольку игрок А имеет только две стратегии, то p₂=1-p1 и ожидаемые выигрыши игрока А,соответствующие чистым стратегиям игрока В, представлены в таблице 7.5.

Таблица 7.4. Платежная матрица игры 2 x n

B A	q1	q2	…	qn
p1	a11	a12	…	a1n
p2	a21	a22	…	a2n

 

Таблица 7.5. Ожидаемые выигрыши.

Чистые стратегии игрока В	Ожидаемые выигрыши игрока А
… n	(a11 – a21) p1+a21 (a12 – a22) p1+a22 … (a1 n – a2 n) p1+a2 n

 

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

Рассмотрим решение на примере (табл.7.6).

 

Таблица 7.6. Платежная матрица вида 2x4

B A
				-1

Эта игра не имеет седловой точки. Ожидаемые выигрыши игрока А, соответствующие чистым стратегиям В, представлены в таблице 7.7.

На рис. 7.1 изображены четыре прямые, являющиеся графиками этих функций от p₁.

 

Таблица 7.7. Ожидаемые выигрыши.

Чистые стратегии игрока В	Уравнения прямых для выигрышей игрока A	Ожидаемые выигрыши игрока А
	n1 £ 2p1+4p2 n2 £ 2p1+3p2 n3 £ 3p1+2p2 n1 £ -p1+6p2	-2p1+4 -p1+3 p1+2 -7p1+6

 

Рис 7.1. Графическое решение игры по отношению к игроку A

 

Максимин достигается при p₁ = ½. В этой точке пересекаются любые две из прямых 2, 3 и 4. Следовательно, оптимальной стратегией игрока А является (p₁ = ½, p₂ = ½) и значение игры находится подстановкой p₁ в уравнение любой из прямых, проходящих через максиминную точку. Это дает ν^* = 5/2.

Интересно отметить, что при определении оптимальных страте­гий игрока В три прямые проходят через максиминную точку. Это означает, что оптимальная стратегия В представляет собой совокупность трех стратегий. Любые две прямые, имеющие противоположные наклоны, определяют одно возможное оптимальное решение. Таким образом, из трех комбинаций (2, 3), (2, 4) и (3, 4) комбинация (2, 4) должна быть исключена как неоптимальная.

Комбинация (2, 3) дает q₁=q₄=0. Следовательно, q₃ = 1- q₂. Ожидаемые проигрыши игрока В, соответствующие чистым стратегиям А, представлены в таблице 7.8.

 

Таблица 7.8. Ожидаемые проигрыши

Чистые стратегии игрока А	Ожидаемые проигрыши игрока В
	-q2+3 q2+2

 

Значение q₂ = ½ (соответствующее минимаксной точке) определяется из равенства

–q₂+3=q₂+2

Отметим, что подстановкой q₂ = ½ в выражение для ожидаемого проигрыша игрока В можно найти минимаксное значение, равное 5/2, совпадающее, как и должно быть, со значением игры n*.

Аналогично может быть рассмотрена и комбинация (3, 4), дающая другое оптимальное решение. Любое взвешенное среднее комбинаций (2, 3) и (3, 4) также будет давать оптимальное решение, в которое входят стратегии 2, 3 и 4.

Пример. Рассмотрим следующую игру вида 4x2 (табл. 7.9).

 

Таблица 7.9. Игра вида m x 2

B A	q1	q2
p1
p2
p3
p4	-2

 

Эта игра не имеет седловой точки. Пусть q₁и q₂(=1-q₁) - смешанные стратегии игрока В. Ожидаемые проигрыши игрока B приведены в таблице 7.10.

Четыре прямые из табл.7.10 изображены на рис. 7.2.

Таблица 7.10. Ожидаемые проигрыши

Чистые стратегии игрока А	Ожидаемые проигрыши игрока В
	-2q1+4 -q1+4 q1+2 -8q1+6

 

Минимаксная точка определяется как самая нижняя точка на огибающей сверху. У_\ определяет точка пересечения прямых 1 и 3, что дает q₁=2/3 и n*=8/3.

Прямые, пересекающиеся в минимаксной точке, соответствуют чистым стратегиям 1 и 3 игрока А. Это дает p₂ = p₄ = 0.Следовательно, p₁ = 1- p₃.

 

 

Рис. 7.2. Графическое решение игры по отношению к игроку B

 

Ожидаемые выигрыши игрока А, соответствующие чистым стратегиям игрока В, приведены ниже в таблице 7.11.

Значение p₁ = 1/3 определяется из уравнения -p₁+3=2p₁+2, p₃=2/3, n*=8/3.

 

 

Таблица 7.11. Ожидаемые выигрыши

Чистые стратегии игрока В	Ожидаемые выигрыши игрока А
	-p1+3 2p1+2

 

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

 

Практическая работа №8