Упрощение игры

Простейшим является случай существования седловой точки игры. Поиск оптимального решения сводится здесь к перебору элементов матрицы а_ij с целью выявить a_pq==. Другими словами, исследование свойств игры автоматически приводит к отысканию оптимальных чистых стратегий s_pa, s_qb, если обнаруживается равенство =. Для теории этот случай не представляет большого интереса, хотя он встречается на практике.

Пусть установлено, что некоторая игра mn не имеет седловой точки и, следовательно, ее решение нужно искать в смешанных стратегиях, анализируя те или иные распределения вероятностей

{p_1a, …, p_ma}=S_A, {p_1b, …, p_nb}=S_B.

Можно ожидать, что процесс отыскания оптимальных стратегий S^*_A, S^*_B окажется довольно трудоемким, особенно при больших m и n, поэтому целесообразно для начала рассмотреть вопрос об упрощении игр как средстве, с помощью которого ускоряется подготовка решений.

Паретовские правила отношений в антагонистических играх можно трактовать следующим образом. Если матрица а_ij обладает свойствами a_kj  a_rj (1k, rm; kr; j=1, n) и a_kj>a_rj хотя бы для одного номера j, то ее k-я строка доминирует над r-й строкой, в случае равенства строки эквивалентны. Аналогично, при a_ila_ih (1l, hn; lh; i= ) и a_ih<a_il хотя бы для одного номера l столбец i доминирует над столбцом h, в случае равенства столбцы эквивалентны. Очевидно, сторона А всегда должна предпочесть стратегию s_ka стратегии s_ra, а сторона В s_ib стратегии s_hb (предполагается, что речь идет о выигрышах А и о проигрышах В). Следовательно, цена игры должна остаться неизменной при сохранении в матрице а_ij только доминирующих строк и столбцов, что позволяет уменьшить m и n, т. е. упростить исследования.

Таким образом, приступая к исследованию любой игры mn, необходимо сначала проверить, имеет ли матрица а_ijседловые точки и связанные с ними решения в чистых стратегиях. Если этого нет, то нужно попытаться выявить доминирующие стратегии (строки и столбцы), а также стратегии, приводящие к одинаковым (дублированным) результатам

В итоге определяется игра m’n’ (2m’m; 2n’n) без седловых точек, представляющая собой аналог исходной игры mn.

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

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

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

Графоаналитический метод решения применим к играм вида 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. Ожидаемые выигрыши.

Чистые стратегии игрока В	Ожидаемые выигрыши игрока А
1 2 … 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	2	3	4
1	2	2	3	-1
2	4	3	2	6

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

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

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

Чистые стратегии игрока В	Уравнения прямых для выигрышей игрока A	Ожидаемые выигрыши игрока А
1 2 3 4	1  2p1+4p2 2  2p1+3p2 3  3p1+2p2 1  -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. Ожидаемые проигрыши

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

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

–q₂+3=q₂+2

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

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

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

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

B A	q1	q2
p1	2	4
p2	2	3
p3	3	2
p4	-2	6

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

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

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

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

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

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

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

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