Теория_игр_УП_ЭК_ЭлРесурс

		21
SA =||p1 ,	p2 ,	...,	p m ||,
SB =||q 1 ,	q2 ,	...,	q n ||,

m

где pi – вероятность применения игроком А чистой стратегии Аі; pi 1;

i 1

n

qj – вероятность применения игроком В чистой стратегии Bj; qj 1.

j 1

В частном случае, когда все вероятности, кроме одной, равны нулю, а эта одна – единице, смешанная стратегия превращается в чистую.

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

равными pi и qj.

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

чистую стратегию выберет противник в данной партии.
Если игрок А применяет смешанную стратегию S A =||p1 ,	p 2 ,	... ,
pm ||, а игрок В смешанную стратегию SB =||q1 , q2 , ...,	q n ||,	то

средний выигрыш (математическое ожидание) игрока А определяется соотношением

m	n	a	p	q		.	(2.6)
i 1 j 1		ij	i		j

Естественно, что ожидаемый проигрыш игрока В равен такой же величине.

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

максимальный выигрыш .

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

2.4. Основные теоремы матричных игр

Если игрок А выбирает смешанную стратегию SA =||p1 , p 2 , ...,
pm ||, а игрок В смешанную стратегию SB =||q 1 ,	q 2 , ... ,	qn ||,то средний
выигрыш математическое ожидание выигрыша	игрока	А (проигрыша

игрока В) определится суммой

m	n	a	p	q		,
i 1 j 1		ij	i		j

которая может рассматриваться в качестве характеристики выбранных SА и

SB.

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

		m n	22
			(2.7)
maxmin aij pi qj vA.
i	j	i 1 j 1

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

стратегию SB, которая обеспечивает
		m n	(2.8)
minmax aij pi qj vB .
j	i	i 1 j 1

Весьма важным для теории и практики является вопрос о том, связаны ли между собой vА и vB. Ответ на него дает теорема о максимине.

Теорема о максимине. В конечной игре двух игроков (коалиций) с нулевой суммой (матричной игре) при имеет место равенство

A B .	(2.9)
Теорема о максимине указывает на существование равновесия для
случая v А = v B , при	и, следовательно, существования оптимальных

смешанных стратегий.

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

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

Обе эти теоремы эквивалентны. Из этих теорем следует, что любая матричная игра имеет цену v . Цена игры v – средний выигрыш, приходящийся на одну партию, – всегда удовлетворяет условию

,

(2.10)

т.е. лежит между нижней и верхней ценами игры.

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

Эта пара стратегий образует в игре положение равновесия: один игрок хочет обратить выигрыш в максимум, другой – в минимум, каждый “тянет” в свою сторону и, при оптимальном поведение обоих,

устанавливается равновесие и устойчивый выигрыш .

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

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

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

23

любых пропорциях), причем число активных стратегий каждого игрока, входящих в их оптимальные смешанные стратегии, не превосходит L, где

L = min(m, n).

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

ТЕСТЫ

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

1.В антагонистической игре пара стратегий (Ai, Bj) называется равновесной или устойчивой, если ни одному из игроков не выгодно отходить от своей стратегии.

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

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

4.Игра решается в чистых стратегиях, если нижняя цена платежной матрицы равна верхней.

5.Игры с полной информацией всегда имеют седловую точку.

6.Случайная величина, значениями которой являются чистые стратегии игрока, называется его смешанной стратегией.

7.Если игрок А применяет смешанную стратегию SA=||p1, p2, ..., pm||, а игрок В смешанную стратегию SB=||q1, q2, ..., qn||, то средний выигрыш

игрока А определяется соотношением m a	p .
i 1 ij	i

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

9.Оптимальные смешанные стратегии в отличие от оптимальных чистых стратегий не обладают свойством равновесия (устойчивости).

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

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

цену .

12. Теорема о максимине утверждает, что

	m n		m n
maxmin aij pi qj min max aij pi qj v.
i j	i 1 j 1	j i	i 1 j 1

13.При оптимальных смешанных стратегиях цена игры удовлетворяет условию .

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

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

24

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

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

	Bj	B1	B2
	Ai
	A1	a11	a12
	A2	a21	a22

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

В соответствии с основной теоремой игра имеет оптимальное решение в смешанных стратегиях: SA =||p 1 , p 2 || и S B =||q1 , q2 ||, где вероятности применения (относительные частоты применения) чистых стратегий удовлетворяют соотношениям

p1 p2	1;	(2.11)
q1 q2	1.	(2.12)

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

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

активную стратегию В1, то цена игры равна
a11 p1 a21 p2								,										(2.13)
а при использовании игроком В чистой активной стратегии В2,
выигрыш будет равен								.										(2.14)
a12 p1 a22 p2
Уравнения (2.11), (2.13) и (2.14) образуют систему трех линейных
алгебраических уравнений с тремя неизвестным: р1 , р2 и .
Решая ее, легко находим, что
p1					a22				a21								.	(2.15)
		a			a		22		a	21		a
	11													12
p2					a11 a12											.		(2.16)
			a		a				a		a
	11					22			21					12
				a11a22				a12a21							.			(2.17)
	a
				a				a		a
	11				22				21				12
Если игрок В использует свою оптимальную смешанную стартегию, а
игрок А – свою чистую активную стратегию А1, то цена игры равна
a11q1 a12q2							,											(2.18)

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

a21q1 a22q2 . (2.19)

25

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

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

q1					a22 a12												.		(2.20)
		a			a		22			a		21			a
				11											12
q2					a11 a21													.	(2.21)
			a		a			22		a			21		a
				11											12
				a11a22					a12a21							.			(2.22)
	a
				a		22			a		21			a
	11														12

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

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

a		a	0;		a		a	0;
	22	21				22	21
a11		a12	0;	или	a11		a12	0;
a		a	0;		a		a	0;
	22	12				22	12
a		a	0,		a		a	0.
	11	21				11	21

Тогда 0<p1<1; 0<p2<1; 0<q1<1; 0<q2<1.

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

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

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

		26
vA		vA
a22	B2	a11
		B1

N

vopt

a21		p2=1-p1	a12
0	p1opt	1	p1

Рис. 2.4.

Если при этом игрок В применяет чистую стратегию В1, то выигрыш игрока А равен а11, а при применении чистой стратегии В2 – а12. Так как значения р1 лежат в пределах [0,1], то соединяя крайние точки для

стратегий В1 и В2 (строя графики функций vА=(a11-a21)p1+a22 и vА=(a12- a22)p1+a22), получаем значения выигрышей игрока А для всех

промежуточных значений р1.

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

как оптимальную цену игры vopt, так и оптимальные вероятности p1opt и p2opt=1-p1opt, соответствующие оптимальной смешанной стратегии игрока

А, т.е. дает решения системы уравнений (2.11), (2.13), (2.14).

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

vВ=(a11-a12)q1+a12; (2.23) vВ=(a21-a22)q1+a22. (2.24)

vB	vB
a22	a11

M

vopt

a12	A1	A2		a21
0	q1opt		1	q1

Рис. 2.5.

27

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

q1opt;q2opt=1-q1opt и vopt.

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

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

vA	В2	vA
a22
		a12
	N	a11
a21	В1
0	1	p1
	Рис. 2.6.

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

стратегии В1. В данной игре р1 o p t =1;р2 o p t=0; vo p t =а1 1, т.е. игра имеет седловую точку N и решается в чистых стратегиях. Игрок А должен

применять стратегию А1, а игрок В – стратегию В1.

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

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

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

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

i

-2

1

28

vA

vA

a22

a21

	N
	В1
	В2		a11
0
		1 p1

a12

Рис. 2.7.

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

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

p1			a22 a21									3 1			2			1	;
		a	a		a	21	a	12				4 3 1 2			8			4
11				22
			a11		a12							4 2			3
p2															4 .
	a		a		a		a				4 3 1 2
11			22		21		12

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

						a22 a12												3 2				5
		q1																				8 ;
					a	a	a					a						4 3 1 2
				11		22					21	12
						a22 a12												4 1	3
		q2															8		8 .
					a	a	a					a
				11		22					21	12
	Таким					образом,												оптимальные смешанные стратегии игроков
S A		1 ;	3		; SB					5	; 1		, а цена игры в соответствии с формулой (2.22) равна:
			4							8
		4									8
					a11 a22 a12 a21												4 3 ( 2) 1					7 .
				a a a a
																		4 3 1 2 4
				11		22					21	12

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

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

													29
	vA															vA
4,0									B1							4,0
3,0															3,0
2,0					N											2,0
v=1.75
1,0			C												1,0
	0														1		p1
			0.1	0.2	0.3	0.4	0.5	0.6	0.7		0.8		0,9
															-1,0
				p1opt=0.25										B2
														D		-2,0

Рис. 2.8.

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

решение, что и алгебраический метод: SA				025.;075.				,	v 175. .

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

	vB														vB
4,0															4,0
3,0															3,0
2,0													М		2,0
														А2
1,0						C									1,0
	0					0.1	0.2					0.4	0.6	0.8	1	q1
-1,0															-1,0
-2,0						А1								D	-2,0
														Рис. 2.9.
			Оптимальное решение,											определяемое		точкой М, дает решение
SB					0625.;0375.						,	v 175. .

ЗАДАЧИ

Определите алгебраическим и геометрическим методами оптимальные решения следующих игр 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 A1 -10 -16 A2 -12 -14

10.B1 B2 A1 -3 -2 A2 0 -2

13.B1 B2 A1 6 -2 A2 -2 6

16.	B1	B2
A1	4	7
A2	5	4
19.	B1	B2
A1	6	9
A2	13	11
22.	B1	B2
A1	5	8
A2	7	6
25.	B1	B2
A1	0	-3
A2	-1	0

8.B1 B2 A1 7 9 A2 13 11

11.B1 B2 A1 0 2 A2 3 1

14.B1 B2 A1 4 -5 A2 -5 4

17. B1 B2 A1 4 -5 A2 -4 5

20. B1 B2 A1 1 -3 A2 -8 5

23. B1 B2 A1 6 9 A2 8 7

26. B1 B2 A1 12 3 A2 9 7

30
9.	B1	B2
A1	1	2
A2	4	3
12.	B1	B2
A1	-1	1
A2	2	0
15.	B1	B2
A1	5	6
A2	6	5
18.	B1	B2
A1	8	-1
A2	1	9
21.	B1	B2
A1	4	-2
A2	-3	5
24.	B1	B2
A1	2	5
A2	3	4
27.	B1	B2
A1	4	-5
A2	1	-1

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

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

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

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

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