Теория_игр_методичка

21

Рис. 2. Графическая интерпретация матричной игры 2х2 для игрока В.

Найдя координаты точки М (х, у), как точки пересечения прямых А1А1 и А2А2,

компоненты оптимальной смешанной стратегии игрока В и цену игры: Y*(q1, q2), можно найти по следующим формулам:

q1 = 1 – x, q2 = x, = y.

Решениетиповогопримера

Матричную игру 2х2 решить в смешанных стратегиях:

1)аналитически (для игрока А); геометрически (для игрока В)

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

10		7
Игра задана платежной матрицей: P		.
	8
		11

Решение:

1. Найдем аналитически оптимальную стратегию игрока А и соответствующую цену

игры Х*(р1, р2), .

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

для стратегии В1: 10 p1 8 p2 ; для стратегии В2: 7 p1 11p2 .

С учетом того, что сумма компонентов смешанной стратегии равна 1, получаем систему уравнений:

10 p1 8p2 ,7 p1 11p2 ,p1 p2 1.

Вычтем из первого уравнения второе: 3p1 3p2 0 или p1 p2 .Значит:

												22
					p		1		,
						1		2
								1
p1 p2 ,
					p2			2	,
									1		1
p1 p2 1,										11		9.
					7
			,						2		2
7 p1 11p2
	1	;	1	, = 9.
Итак: X *	2
			2

Найдем геометрически оптимальную смешанную стратегию игрока В: Y*(q1, q2). Стратегию А1 изобразим точками с ординатами 10 и 7 на прямых В1 и В2

соответственно. Стратегию А2 – точками с ординатами 8 и 11 (см. рис. 1).

Каждой точке на отрезке [0; 1] соответствует смешанная стратегия игрока В. Среди них оптимальной будет та, которая определяется самой низкой точкой ломаной А1МА2, т.е. точкой М. Для нахождения компонентов оптимальной стратегии игрока В надо найти координаты точки М, причем если М (х, у), то

q1 = 1 – х, q2 = х, = y. Для этого найдем уравнения прямых А1А1 и А2А2, воспользовавшись уравнением прямой, проходящей через две точки:

	x x1				y y1			.
	x	2	x		y	2	y
Так как А1(0; 10) и А1(1; 7), то			1				1

	x 0		y 10	, x	y 10	, 3x y 10 , 3x y 10 0 .
	1 0		7 10		3

Т.е. уравнение прямой А1А1 имеет вид: 3x y 10 0 .

Рис. 3. Геометрическая интерпретация матричной игры для игрока В

Так как А2(0; 8) и А2(1; 11), то
	x 0		y 8	,	x	y 8	, 3x y 8 , 3x y 8 0.
	1 0		11 8
					3

Т.е. уравнение прямой А2А2 имеет вид: 3x y 8 0.

Найдем координаты точки М, решив систему уравнений прямых А1А1 и А2А2:

23

						3x y 10 0,								2y 18,					x 1,
																					3
																	0,
						3x y 8 0,							3x y 8
																			y 9.
	1	; 9												1	;	1	Y *		2	;	1
Итак, M	3			, значит				= 9, Y * 1						3		или			3		.
																3					3
Ответ: X			1	;	1			2	;	1		= 9.
	*		2		2	,	Y *	3		3	,

2. Проведем моделирование результатов решения с помощью таблицы равномерно распределенных случайных чисел (см. приложение). Для 30 партий хватит 60 чисел, на основе которых будут выбираться стратегии игроками. Используемые случайные числа сгенерированы в MS Excel функцией =СЛЧИС(). В приложении достаточно много чисел, но использовать для моделирования можно любые 60, выбранные произвольно с любого места таблицы. Мы возьмем числа из первого блока (для игрока А используется 1, 3 и 5 столбики).

Будем выбирать стратегии игроков, используя геометрическое определение вероятности. Так как все случайные числа из отрезка [0; 1], то чтобы стратегия А1 появлялась примерно в половине случаев, будем ее выбирать если случайное число меньше 0,5; в остальных случаях выбирается стратегия А2. Аналогично для игрока В.

Стратегию В1 будем выбирать, если соответствующее случайное число меньше 23 0,67 , в противном случае выбираем стратегию В1.

24

Заполним расчетную таблицу:

		Стратеги
Номер	Случайно	я игрока	Случайно
парти	е число	А	е число
и	игрока А	(А1: <	игрока В
		0,5)
1.	0,029	А1	0,125
2.	0,611	А2	0,490
3.	0,766	А2	0,958
4.	0,738	А2	0,564
5.	0,944	А2	0,257
6.	0,416	А1	0,886
7.	0,513	А1	0,226
8.	0,717	А2	0,467
9.	0,994	А2	0,822
10.	0,412	А1	0,244
11.	0,259	А1	0,176
12.	0,610	А2	0,658
13.	0,207	А1	0,451
14.	0,071	А1	0,994
15.	0,391	А1	0,724
16.	0,835	А2	0,469
17.	0,062	А1	0,392
18.	0,181	А1	0,457
19.	0,891	А2	0,336
20.	0,375	А1	0,094
21.	0,009	А1	0,522
22.	0,255	А1	0,806
23.	0,273	А1	0,562
24.	0,111	А1	0,805
25.	0,888	А2	0,037
26.	0,392	А1	0,341
27.	0,843	А2	0,808
28.	0,086	А1	0,585
29.	0,426	А1	0,370
30.	0,562	А2	0,688

	Стратеги		Накоплен	Средний
	я игрока	Выигры	ный	выигры
	В			ш А
		ш А	выигрыш
	(В1: <			(цена
			А
	0,667)			игры)
	В1	10	10	10,000
	В1	8	18	9,000
	В2	11	29	9,667
	В1	8	37	9,250
	В1	8	45	9,000
	В2	7	52	8,667
	В1	10	62	8,857
	В1	8	70	8,750
	В2	11	81	9,000
	В1	10	91	9,100
	В1	10	101	9,182
	В1	8	109	9,083
	В1	10	119	9,154
	В2	7	126	9,000
	В2	7	133	8,867
	В1	11	144	9,000
	В1	10	154	9,059
	В1	10	164	9,111
	В1	8	172	9,053
	В1	10	182	9,100
	В1	10	192	9,143
	В2	7	199	9,045
	В1	10	209	9,087
	В2	7	216	9,000
	В1	8	224	8,960
	В1	10	234	9,000
	В2	11	245	9,074
	В1	10	255	9,107
	В1	10	265	9,138
	В2	11	276	9,200

Таким образом, в результате моделирования в 30 партиях цена игры (средний выигрыш) равен 9,2. Этот результат согласуется с теоретической ценой игры 9.

Частоты использования игроками своих чистых стратегий соответственно равны: Х(18/30;12/30), Y(21/30; 9/30) или

Х(0,6; 0,4), Y(0,7; 0,3)

Сравнивая с теоретическими оптимальными стратегиями Х*(0,5; 0,5) и

Y*(0,67; 0,33) можно сделать вывод, что результаты моделирования достаточно близко им соответствуют даже для небольшого количества партий.

25

Заданиена самостоятельнуюработу

Матричную игру 2х2 решить в смешанных стратегиях:

1)аналитически (для игрока А); геометрически (для игрока В)

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

Вариант 1						Вариант 2						Вариант 3						Вариант 4						Вариант 5
		5	13					1	5					7	2					3	11					13	5
		8	4					6	4					5	14					18	7					7	8
Вариант 6						Вариант 7						Вариант 8						Вариант 9						Вариант 10
		6	10					6	14					2	6					8	3					4	12
		18	5					9	5					7	5						15					19	8
Вариант 11						Вариант 12						Вариант 13						Вариант 14						Вариант 15
		14	6					7	11					7	15					3	7					9	4
		8	9					19	6					10	6					8	6					7	16
Вариант 16						Вариант 17						Вариант 18						Вариант 19						Вариант 20
		5	13					15	7					8	12					8	16					4	8
		20	9					9	10					20	7					11	7					9	7
Вариант 21						Вариант 22						Вариант 23						Вариант 24						Вариант 25
		10	5					6	14					16	8					9	13					9	17
		8	17					21	10					10	11					21	8					12	8
Вариант 26						Вариант 27						Вариант 28						Вариант 29						Вариант 30
		5	9					11	6					7	15					17	9					10	14
		10	8					9	18					22	11					11	12					22	9

26

Приложение

Равномерно распределенные случайные числа

	0,02988		0,12558		0,25974		0,17641		0,00937		0,52264		0,08086		0,84858		0,99427		0,49452
	0,61109		0,49042		0,61076		0,65834		0,25579		0,80641		0,07675		0,84419		0,18268		0,29702
	0,76606		0,95854		0,20704		0,45154		0,27367		0,56261		0,30037		0,96485		0,47252		0,55084
	0,73868		0,56421		0,07183		0,99420		0,11184		0,80524		0,42897		0,45031		0,05350		0,67078
	0,94483		0,25710		0,39190		0,72491		0,88888		0,03791		0,50773		0,63034		0,94091		0,80165
	0,41647		0,88664		0,83519		0,46930		0,39285		0,34159		0,77252		0,65987		0,48750		0,79735
	0,51314		0,22625		0,06211		0,39299		0,84336		0,80859		0,52694		0,73306		0,36874		0,93390
	0,71749		0,46727		0,18182		0,45791		0,08667		0,58570		0,75495		0,68645		0,90270		0,87484
	0,99401		0,82235		0,89122		0,33631		0,42694		0,37053		0,70413		0,59805		0,40425		0,96181
	0,41244		0,24426		0,37553		0,09464		0,56208		0,68889		0,59503		0,92378		0,03108		0,33182
	0,06428		0,40308		0,61733		0,25701		0,55144		0,42344		0,36034		0,67524		0,19628		0,39112
	0,76893		0,80957		0,56225		0,62275		0,04293		0,47489		0,13456		0,77198		0,12468		0,75491
	0,13208		0,75581		0,31683		0,24176		0,67439		0,64703		0,15862		0,25507		0,03202		0,21096
	0,73643		0,55302		0,47629		0,93283		0,68451		0,42510		0,54809		0,05326		0,19976		0,97378
	0,62204		0,94838		0,15169		0,70663		0,83586		0,13781		0,63465		0,21988		0,93957		0,31520
	0,07839		0,11666		0,35227		0,13427		0,61833		0,16719		0,12016		0,64336		0,77480		0,86041
	0,83250		0,42249		0,51044		0,25119		0,94154		0,99712		0,83641		0,20537		0,63808		0,39483
	0,85673		0,85089		0,28419		0,59462		0,47904		0,31065		0,02794		0,54871		0,31417		0,55898
	0,75347		0,92514		0,04964		0,75030		0,93800		0,97254		0,41409		0,31032		0,23870		0,29442
	0,62758		0,61130		0,12625		0,72826		0,48506		0,99660		0,44510		0,21017		0,17870		0,02981
	0,79640		0,51130		0,07301		0,51032		0,66215		0,47242		0,30286		0,80875		0,06193		0,58888
	0,88354		0,78258		0,64343		0,54479		0,08452		0,57100		0,20346		0,83214		0,38734		0,44309
	0,44882		0,45845		0,17718		0,05551		0,38909		0,85212		0,56127		0,14715		0,09910		0,19302
	0,14129		0,02946		0,35912		0,62844		0,64329		0,19039		0,33253		0,24154		0,19577		0,74391
	0,04527		0,37561		0,61878		0,02553		0,14727		0,59539		0,82544		0,05170		0,94714		0,30052
	0,35683		0,23365		0,57521		0,11776		0,36137		0,09732		0,06056		0,80001		0,31284		0,57280
	0,62673		0,25879		0,21243		0,38995		0,11879		0,36586		0,02472		0,71774		0,49823		0,17584
	0,28306		0,95646		0,51488		0,19821		0,05984		0,19862		0,80922		0,71920		0,14294		0,20082
	0,98928		0,41612		0,57121		0,01453		0,58725		0,89637		0,05521		0,67878		0,39561		0,74919
	0,44108		0,43385		0,86583		0,11482		0,19384		0,92890		0,52784		0,01360		0,91198		0,98159
	0,28697		0,19942		0,41087		0,35288		0,98234		0,66017		0,91334		0,89508		0,56661		0,29694
	0,45216		0,45960		0,52410		0,57526		0,50903		0,74213		0,61221		0,60080		0,82132		0,68069
	0,27331		0,08052		0,44792		0,84242		0,26637		0,32982		0,46604		0,65241		0,84421		0,15063
	0,34311		0,63930		0,43829		0,48463		0,02902		0,09894		0,13703		0,08368		0,11494		0,25139
	0,04077		0,75021		0,15293		0,33430		0,08619		0,89567		0,59706		0,38817		0,17403		0,35937
	0,01042		0,46584		0,85385		0,65072		0,21152		0,59361		0,78327		0,72696		0,47454		0,40506
	0,00667		0,08945		0,55206		0,68136		0,62554		0,65966		0,34458		0,36694		0,08815		0,34070
	0,31149		0,53934		0,82927		0,35491		0,31710		0,24980		0,71555		0,90912		0,89007		0,19737
	0,77603		0,36895		0,38569		0,32902		0,67927		0,54222		0,42100		0,82640		0,44906		0,93955
	0,60127		0,21631		0,51221		0,56408		0,74953		0,26179		0,43488		0,44669		0,25248		0,85931
	0,79172		0,60996		0,46486		0,48824		0,22891		0,42349		0,40216		0,20702		0,12331		0,36567
	0,55588		0,20937		0,01108		0,37251		0,99880		0,44969		0,02010		0,11352		0,15533		0,18635
	0,19998		0,59670		0,05333		0,76846		0,10413		0,78771		0,52544		0,92986		0,23817		0,96863
	0,38874		0,68853		0,90859		0,85754		0,76407		0,26378		0,74911		0,30056		0,43540		0,24335
	0,87837		0,17863		0,36411		0,01456		0,19101		0,46579		0,80272		0,91756		0,08297		0,74312
	0,16727		0,62836		0,33135		0,51248		0,19511		0,79050		0,57783		0,05399		0,65791		0,96858
	0,24944		0,10878		0,84673		0,79399		0,26243		0,65681		0,48544		0,01817		0,68618		0,28303
	0,82386		0,83907		0,05172		0,30709		0,44124		0,41150		0,10495		0,22372		0,72297		0,66630
	0,08585		0,53025		0,12744		0,01054		0,96998		0,03388		0,29976		0,72498		0,03166		0,01429
	0,08350		0,87209		0,72819		0,72269		0,87351		0,38623		0,87481		0,86403		0,72317		0,79337

27

Бланк для моделирования результатов решения игры 2х2

ФИО______________________________ Вариант ___________

	Номер	Случайное	Стратегия	Случайное	Стратегия
		число	игрока А	число	игрока В
	партии
		игрока А		игрока В
	1.	0,029		0,125
	2.	0,611		0,490
	3.	0,766		0,958
	4.	0,738		0,564
	5.	0,944		0,257
	6.	0,416		0,886
	7.	0,513		0,226
	8.	0,717		0,467
	9.	0,994		0,822
	10.	0,412		0,244
	11.	0,259		0,176
	12.	0,610		0,658
	13.	0,207		0,451
	14.	0,071		0,994
	15.	0,391		0,724
	16.	0,835		0,469
	17.	0,062		0,392
	18.	0,181		0,457
	19.	0,891		0,336
	20.	0,375		0,094
	21.	0,009		0,522
	22.	0,255		0,806
	23.	0,273		0,562
	24.	0,111		0,805
	25.	0,888		0,037
	26.	0,392		0,341
	27.	0,843		0,808
	28.	0,086		0,585
	29.	0,426		0,370
	30.	0,562		0,688

		Накоплен-	Средний
	Выигрыш		выигрыш
		ный выиг-
	А		А (цена
		рыш А
			игры)

28

6. Методы решения матричных игр mxn в смешанных стратегиях

Краткая теоретическая справка

Матричная игра в общем виде решается как задача линейного программирования симплекс-методом. Обязательным условием применения симплексного метода является наличие условия неотрицательности переменных, поэтому один из способов сведения матричной игры к задаче линейного программирования подразумевает 0 (цена игры – положительная). Это условие соблюдается, если все элементы платежной матрицы положительны. Добиться этого можно с помощью следующей теоремы.

Теорема. Пусть дана матричная игра с матрицей P aij и ценой					игры . Тогда
оптимальные	смешанные	стратегии	игроков матричной	игры	с матрицей
P b aij c ,	где b 0	совпадает	с оптимальными	смешанными	стратегиями

соответствующих игроков в матричной игре , а цена игры равна: b c .

На практике можно пользоваться следующим алгоритмом, который рассмотрим на примере игры 3х3, которая задана платежной матрицей:

a11	a12	a13
	a22	a23
P a21			.
	a32	a33
a31

Найти оптимальные стратегии игроков и цену игры: Х *( p1 , p2 , p3 ), Y *(q1 ,q2 ,q3 ), . 1) Преобразуем платежную матрицу: увеличим все ее элементы на число :

min aij

1 – модуль минимального элемента матрицы, увеличенный на единицу;

i, j

a11

a12

a13

b11

b12

b13

a22

a23

b22

b23

P a21

b21

a

31

a

32

a

33

b

b

b

31

32

33

Если все элементы платежной матрицы положительны, то можно считать 0 и

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

2) Записать задачу линейного программирования для игрока А:

Найти значения переменных

x1 , x2 ,

x3 ,

при

которых

функция zA x1 x2

x3

достигает минимального значения и удовлетворяющих условиям:

b11 x1 b21 x2 b31 x3 1,

b12 x1 b22 x2 b32 x3 1,

b13 x1 b23 x2 b33 x3 1,

x

0, x

2

0, x

3

0.

1

3) Решить записанную задачу симплексным методом и перейти от ее решения к

решению матричной игры для игрока А:

x3

p

x1

,

p

2

x2

,

p

3

,

1

.

1

zA

zA

zA

zA

4) Записать задачу линейного программирования для игрока В:

Найти значения переменных y1 , y2 , y3 , при которых функция zB y1 y2 y3 достигает максимального значения и удовлетворяющих условиям:

29

b11 y1 b12 y2 b13 y3 1,b21 y1 b22 y2 b23 y3 1,b31 y1 b32 y2 b33 y3 1,

y1 0, y2 0, y3 0.

3) Решить записанную задачу симплекс-методом и перейти от ее решения к решению матричной игры для игрока А:

q	y1	, q	2		y2	, q	3		y3	.
1	zB				zB				zB

Цена игры является общей для обоих игроков (выполнение этого условия является элементом проверки правильности решения).

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

Решение типового примера

Две отрасли могут осуществлять капитальные вложения в 3 объекта. Стратегии отраслей: i-я стратегия состоит в финансировании i-го объекта (i = 1, 2, 3). Учитывая особенности вкладов и местные условия, прибыли первой отрасли выражаются следующей матрицей:

1		1	6
	5	2
А			3
	2	4	5

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

1. Решим матричную игру симплекс-методом, записав ее как задачу линейного программирования.

Рассмотрим игрока А. Будем искать оптимальную смешанную стратегию игрока А: Х *( p1, p2 , p3 ) , где p i – частота (вероятность) использования игроком А своей i-стратегии

(i 1,2,3).Обозначим цену игры (средний выигрыш) – .

Чтобы свести матричную игру для игрока А к задаче линейного программирования преобразуем платежную матрицу так, чтобы все ее элементы были больше нуля – прибавим ко всем элементам матрицы число 4. Получаем преобразованную платежную матрицу:

3		5	10
	9	6	1
B
	2	8	9

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

игрока А составит: 3p1 9 p2 2 p3 , получаем неравенство 3p1 9 p2 2 p3 .

Аналогично, записав неравенства для стратегий В2 и В3, получаем систему линейных ограничений:

30

3p1 9 p2 2 p35p1 6 p2 8p310 p1 p2 9 p3

Из условия p1 p2 p3 1, разделив обе части уравнения на 0 (цена игры больше нуля, т.к. все элементы преобразованной матрицы больше нуля), получаем

целевую функцию Z

p1

p2

p3

1

. Цель игрока А – получить максимальный

1 min . Если обозначить

pi

средний выигрыш, т.е. max , а значит

x (i=1, 2, 3), то

i

целевая функция Z x

x

x

min .

2

3

1

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

0 :

i

3x1 9x2 2x3 1

6х2

8х3 1

5х1

х2

9х3 1

10х1

Таким образом, для нахождения оптимальной стратегии игрока А необходимо

решить задачу линейного программирования:

найти значения переменных x , x

2

,

x

, удовлетворяющих системе ограничений

1

3

3x1 9x2 2x3 1

6

х2

8х3 1

5х1

х1

х2

9х3 1

: 10

и условию x 0, x

2

0, x

0 , при котором функция Z x

x

2

x

3

принимает

1

3

1

минимальное значение.

Далее применяем симплекс-метод, рассмотренный выше.

2. Решим матричную игру в MS Excel, используя инструмент «Поиск решения».

1. Оформим расчетную таблицу, как показано на рисунке 4:

–ячейки В2, В3, В4 играют роль переменных x1, x2 , x3 ;

–в ячейке В8 вычисляется значение целевой функции;

–в ячейках В12, В13, В14 вычисляются левые части ограничений.

2. В меню СЕРВИС выбираем команду ПОИСК РЕШЕНИЯ (если нет такого пункта меню, то сначала необходимо в меню СЕРВИС выбрать команду НАДСТРОЙКИ, в появившемся диалоговом окне установить флажок на пункте ПОИСК РЕШЕНИЯ и нажать кнопку ОК; теперь в меню СЕРВИС будет команда ПОИСК РЕШЕНИЯ).