Решение игр 2xn и mx2

Как уже отмечалось в теореме об активных стратегиях, любая конечная игра mxn имеет решение, в котором число активных стратегий каждого игрока не превосходит, где . Следовательно, у игры 2xn или mx2 всегда имеется решение содержащее не более двух активных стратегий у каждого из игроков . Если эти активные стратегии игроков будут найдены, то игры 2xn и mx2 превращаются в игры 2x2, методы решения которых рассмотрены выше.

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

Использование данной теоремы позволяет в частности, упрощать решение матричных игр 2 x n и m x 2.

Практически решение игры 2xn осуществляется следующим образом:

1) строится графическое изображение игры для игрока А;

2) выделяется нижняя граница выигрыша и находится наибольшая ордината нижней границы (максимин), которая равна цене игры v;

3) определяется пара стратегий игрока В, пересекающихся в точке оптимума. Эти стратегии и являются активными стратегиями игрока В.

Таким образом, игра 2xn сведена к игре 2x2, которую более точно можно решить алгебраическим методом.

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

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

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

Bj   Ai	B1	B2	B3
A1
A2

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

Рис. 2.10

Точка N (максимин) является точкой оптимума. В этой точке пересекаются линии, соответствующие активным стратегиям В₁ и В₂ игрока В. Таким образом, исключая стратегию В₃, получаем матричную игру 2x2 с платежной матрицей вида

Bj   Ai	B1	B2
A1
A2

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

; ;

; ;

.

Ответ: ; ; .

Пример. Найти решение игры, платежная матрица которой имеет вид

Bj   Ai	B1	B2
A1
A2
A3	-1
A4		-3
A5		-2
A6	1,5

Платежная матрица не имеет седловой точки. Для сведения данной игры к игре 2x2 строим ее графическое изображение для игрока В (рис. 2.11).

Точка М (минимакс) является точкой оптимума. В этой точке пересекаются отрезки, соответствующие активным стратегиям А₂, А₆ и А₃ игрока А. Таким образом, исключая стратегии А₁, А₄ и А₅ и выбирая из трех активных стратегий две (например, А₂ и А₃ или А₂ и А₆), приходим к матричной игре 2x2. Выбор стратегий А₃ и А₆ исключен, так как в этом случае точка М перестанет быть точкой минимакса.

Рис.2.11

Пусть выбираются стратегии А₂ и А₃. Тогда игра 2x2 приобретает вид

Bj   Ai	B1	B2
A2
A3	-1

Оптимальные смешанные стратегии данной игры, а, следовательно, и исходной игры определяются следующими вероятностями:

; ;

; ;

.

Ответ: ; ; .

Другой вариант игры 2x2 получается, если использовать стратегии А₂ и А₆. В этом случае платежная матрица имеет вид

Bj   Ai	B1	B2
A2
A6	1,5

Тогда

; ;

; ;

.

Ответ: ; ; .

Естественно, что цена игры для обоих вариантов одинакова.

В заключение наметим общую схему решения матричных игр 2xn и mx2:

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

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

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

4. Решается матричная игра 2x2.

Дата добавления: 2014-01-07