Решение матричной игры (2х2)

Пусть матричная игра G (2x2) имеет платежную матрицу

 

Bj   Ai	B1	B2
A1	a11	a12
A2	a21	a22

 

Предположим, что игра не имеет седловой точки, т.е. a¹b. При наличии седловой точки решение очевидно.

В соответствии с основной теоремой игра имеет оптимальное решение в смешанных стратегиях: S_A=||p₁, p₂|| и S_B=||q₁, q₂||, где вероятности применения (относительные частоты применения) чистых стратегий удовлетворяют соотношениям

;                    (2.11)

.                    (2.12)

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

,               (2.13)

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

.               (2.14)

Уравнения (2.11), (2.13) и (2.14) образуют систему трех линейных алгебраических уравнений с тремя неизвестным:

р₁, р₂ и n.

Решая ее, легко находим, что

.                        (2.15)

.                         (2.16)

.                           (2.17)

 

Если игрок В использует свою оптимальную смешанную стартегию, а игрок А - свою чистую активную стратегию А₁, то цена игры n равна

,                (2.18)

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

.                 (2.19)

Уравнения (2.12), (2.18) и (2.19) образует систему трех линейных алгебраических уравнений с тремя неизвестными: q₁; q₂ и n.

Решая ее, легко находим, что

.                        (2.20)

.                        (2.21)

.                         (2.22)

Естественно, что в обоих случаях цена игры (выражения (2.17) и (2.22)) получилась одна и та же.

Чтобы соотношения (2.15), (2.16), (2.17), (2.20), (2.21), (2.22) имели смысл, необходимо потребовать, чтобы

или

Тогда  0<p₁<1; 0<p₂<1; 0<q₁<1; 0<q₂<1.

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

Решения системы уравнений (2.15), (2.16), (2.17) и (2.20), (2.21), (2.22), полученные алгебраическим методом, удобно получать и графическим методом (рис. 2.4). Для нахождения вероятностей р ₁, р ₂ и цены игры v в прямоугольной системе координат по оси абсцисс откладывается вероятность р ₁Î[0,1], а по оси ординат - соответствующие этой вероятности - выигрыши игрока А.

При р₁=0, игрок А применяет чистую стратегию А ₂. Если при этом игрок В применяет чистую стратегию В ₁, то выигрыш игрока А равен а₂₁ (уравнение (2.13)), а если игрок В применяет чистую стратегию В ₂, то выигрыш игрока А равен а₂₂ (уравнение (2.14)). При р₁=1, игрок А применяет чистую стратегию А ₁.

Рис. 2.4

Если при этом игрок В применяет чистую стратегию В ₁, то выигрыш игрока А равен а₁₁, а при применении чистой стратегии В₂ - а₁₂. Так как значения р₁ лежат в пределах [0,1], то соединяя крайние точки для стратегий В₁ и В₂ (строя графики функций v_А =(a₁₁-a₂₁)p₁+a₂₂ и v_А =(a₁₂-a₂₂)p₁+a₂₂), получаем значения выигрышей игрока А для всех промежуточных значений р ₁.

В соответствии с принципом максимина, игрок А должен выбрать такую смешанную стратегию, при которой его минимальный выигрыш максимален. Точка N пересечения отрезков прямых (рис. 2.4) и определяет как оптимальную цену игры v _opt, так и оптимальные вероятности p _1opt и p _2opt=1- p _1opt, соответствующие оптимальной смешанной стратегии игрока А, т.е. дает решения системы уравнений (2.11), (2.13), (2.14).

Для графического решения системы уравнений (2.12), (2.18), (2.19) отложим по оси абсцисс вероятность q₁Î[0,1], а по оси ординат соответствующие этой вероятности выигрыши игрока В:

v_В =(a₁₁-a₁₂)q₁+a₁₂;                                   (2.23)

v_В =(a₂₁-a₂₂)q₁+a₂₂.                                   (2.24)

Рис. 2.5

Решением являются координат точки М пересечения прямых, описываемых уравнений (2.23) и (2.24):

q_1opt;q_2opt=1-q_1opt   и   v _opt.

Это же следует и из принципа максимина, в соответствии с которым игрок В должен выбрать такую смешанную стратегию, при которой его максимальный проигрыш будет минимальным.

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

Рис. 2.6

Стратегия В ₂ игрока В является для него явно невыгодной, так как, применяя ее, он в любой случае проигрывает больше, чем при применении стратегии В ₁. В данной игре р _1opt =1;р _2opt = 0; v _opt =а₁₁, т.е. игра имеет седловую точку N и решается в чистых стратегиях. Игрок А должен применять стратегию А ₁, а игрок В - стратегию В₁.

На рис. 2.7 показан случай, в котором решением игры для игрока А является чистая стратегия А ₂, а для игрока В - стратегия В ₁.

Игра имеет седловую точку N.

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

 

Bj   Ai	B1	B2	a i
A1	4	-2	-2
A2	1	3	1
b j	4	3

 

Рис. 2.7

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

Для игрока А, в соответствии с формулами (2.15) и (2.16), оптимальные вероятности применения стратегий А₁ и А₂ равны:

;

.

 

Для игрока В, в соответствии с формулами (2.20) и (2.21), оптимальные вероятности применения стратегий В₁ и В₂ равны:

;

.

 

Таким образом, оптимальные смешанные стратегии игроков ; , а цена игры в соответствии с формулой (2.22) равна:

.

Так как n >0, то игра выгодна для игрока А.

Графическое изображение игры для игрока А показана на рис. 2.8.

 

Рис. 2.8

Нижняя граница выигрыша игрока А определяется ломаной CND. Оптимальное решение, определяется точкой N, естественно, дает тоже решение, что и алгебраический метод: .

Геометрическое изображение игры для игрока В показано на рис.2.9.

 

Рис. 2.9

Оптимальное решение, определяемое точкой М, дает решение .

 

ЗАДАЧИ

 

Определите алгебраическим и геометрическим методами оптимальные решения следующих игр 2х2:

 

1.		B1	B2		2.		B1	B2		3.		B1	B2
	A1	5	2			A1	-3	-6			A1	6	9
	A2	-1	0			A2	-4	-5			A2	7	8
4.		B1	B2		5.		B1	B2		6.		B1	B2
	A1	0	7			A1	8	6			A1	0	-1
	A2	10	4			A2	4	7			A2	-3	0
7.		B1	B2		8.		B1	B2		9.		B1	B2
	A1	-10	-16			A1	7	9			A1	1	2
	A2	-12	-14			A2	13	11			A2	4	3
10.		B1	B2		11.		B1	B2		12.		B1	B2
	A1	-3	-2			A1	0	2			A1	-1	1
	A2	0	-2			A2	3	1			A2	2	0
13.		B1	B2		14.		B1	B2		15.		B1	B2
	A1	6	-2			A1	4	-5			A1	5	6
	A2	-2	6			A2	-5	4			A2	6	5
16.		B1	B2		17.		B1	B2		18.		B1	B2
	A1	4	7			A1	4	-5			A1	8	-1
	A2	5	4			A2	-4	5			A2	1	9
19.		B1	B2		20.		B1	B2		21.		B1	B2
	A1	6	9			A1	1	-3			A1	4	-2
	A2	13	11			A2	-8	5			A2	-3	5
22.		B1	B2		23.		B1	B2		24.		B1	B2
	A1	5	8			A1	6	9			A1	2	5
	A2	7	6			A2	8	7			A2	3	4
25.		B1	B2		26.		B1	B2		27.		B1	B2
	A1	0	-3			A1	12	3			A1	4	-5
	A2	-1	0			A2	9	7			A2	1	-1

 

Упрощение матричных игр

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

Определение 1. Если в платежной матрице игры все элементы строки (столбца) равны соответствующим элементам другой строки (столбца), то соответствующее этим строкам (столбцам) стратегии называются дублирующими.

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

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

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

Пример. Упростить матричную игру, платежная матрица которой имеет вид:

Bj   Ai	B1	B2	B3	B4	B5
A1	5	9	3	4	5
A2	4	7	7	9	10
A3	4	6	3	3	9
A4	4	8	3	4	5
A5	4	7	7	9	10

 

Из платежной матрицы видно, что стратегия А₂ дублирует стратегию А₅, потому любую из них можно отбросить (отбросим стратегию А₅). Сравнивая почленно стратегии А₁ и А₄, видим, что каждый элемент строки А₄ не больше соответствующего элемента строки А₁. Поэтому применение игроком А доминирующей над А₄ стратегии А₁ всегда обеспечивает выигрыш, не меньший того, который был бы получен при применении стратегии А₄. Следовательно, стратегию А₄ можно отбросить. Таким образом, имеем упрощенную матричную игру с платежной матрицей вида:

 

Bj   Ai	B1	B2	B3	B4	B5
A1	5	9	3	4	5
A2	4	7	7	9	10
A3	4	6	3	3	9

 

Из этой матрицы видно, что в ней некоторые стратегии игрока В доминируют над другими: В₃ над В₂, В₄ и В₅. Отбрасывая доминируемые стратегии В₂, В₄ и В₅, получаем игру 3x2, имеющей платежную матрицу вида:

 

Bj   Ai	B1	B3
A1	5	3
A2	4	7
A3	4	3

 

В этой матрице стратегия А₃ доминируется как стратегией А₁, так и стратегией А₂. Отбрасывая стратегию А₃, окончательно получаем игру 2x2 с платежной матрицей

 

Bj   Ai	B1	B3
A1	5	3
A2	4	7

 

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

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

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

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

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

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

1) если матрица игры наряду с положительными имеет и отрицательные элементы, то ко всем ее элементам прибавляют такое число, чтобы исключить отрицательные числа в матрице;

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

Пример. Решить матричную игру 2х2 с платежной матрицей вида:

 

Bj   Ai	B1	B2
A1	0.5	-0.2
A2	0.1	0.3

 

Умножая все элементы платежной матрицы на 10, а затем прибавляя к ним число 2, получаем игру с платежной матрицей

 

Bj   Ai	B1	B2
A1	7	0
A2	3	5

 

Решая эту игру алгебраическим методом, получаем

;     ;

;       ;

.

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

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

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

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

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

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

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

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

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

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

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

 

Bj   Ai	B1	B2	B3
A1	2	5	8
A2	7	4	3

 

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

Рис. 2.10

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

 

Bj   Ai	B1	B2
A1	2	5
A2	7	4

 

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

;     ;

;       ;

.

Ответ: ; ; .

 

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

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

 

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

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

Рис.2.11

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

 

Bj   Ai	B1	B2
A2	4	2
A3	-1	4

 

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

;     ;

;       ;

.

Ответ: ; ; .

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

 

Bj   Ai	B1	B2
A2	4	2
A6	1,5	3

 

Тогда

;     ;

;    ;

.

Ответ: ; ; .

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

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

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

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

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

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

 

ТЕСТЫ

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

1. Если в игре 2xn нет оптимального решения в чистых стратегиях, то оптимальное решение в смешанных стратегиях содержит две активные стратегии у каждого из игроков.

2. В игре mx2 число активных стратегий в оптимальной стратегии каждого из игроков может быть равно или единице, или двум.

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

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

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

6. Умножение всех элементов платежной матрицы на одно и тоже положительное число не изменяет оптимальных стратегий игроков.

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

8. Любая матричная игра 2xn или mx2 может быть сведена к игре 2х2.

 

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

 

ЗАДАЧИ

Решить следующие матричные игры: