Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Национальный исследовательский ядерный университет (МИФИ)

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

Е.А. Елтаренко. Теория игр. Конспект лекций

.pdf

Скачиваний:

Добавлен:

05.06.2015

Размер:

928.35 Кб

Скачать

☆

1 / 31 2 3 > Следующая >>>

Contents
2. Теория игр............................................................................................	2
2.1. Основные понятия теории игр....................................................	2
2.2. Матричные игры с седловой точкой ..........................................	3
2.3. Матричные игры без седловой точки ........................................	4
2.3.1. Решение матричных игр 2 2 ...................................................	6
2.3.2. Решение матричных игр 2 m графоаналитическим
методом...............................................................................................	9
2.3.3. Решение матричных игр n 2 графоаналитиским
методом..................................................................................	10
2.3.4. Решение матричных игр n m ................................................	11
2.4. Биматричные игры.....................................................................	15
2.4.1. Принципы решения биматричных игр ..................................	15
2.4.2. Решение биматричных игр 2 2 .............................................	16
2.4.3. Решение биматричных игр n m ............................................	21
2.5. Коалиционные игры ..................................................................	22

2. ТЕОРИЯ ИГР

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

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

Имеются и другие постановки задач в теории игр [6].

2.1. Основные понятия теории игр

Пусть A, B, D – участники игры.

Каждый участник имеет в своем распоряжении множество чистых

стратегий (возможных ходов в этой игре):
A:{S1a , S2a ,...Sna } или {Sia} (i 1, 2,..., n) ;
B :{S jb} ( j 1, 2,..., m) ;
D :{Skd} (k 1, 2,..., l) .
Исход –	сочетание	Sia , S jb , Skd	(когда	A	выбирает одну чистую
стратегию, B	– другую, а D – третью).

Каждый из исходов характеризуется полезностью (выигрышем) для

каждого участника:
aijk – полезность исхода для участника			A ;
bijk	– для участника	B ;
cijk	– для участника	D .

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

–справедливость;

–устойчивость (устраивает всех участников).

Классификация игр

Если для всех участников существует конечное число чистых стратегий Sia (i 1, 2,..., n) , S jb ( j 1, 2,..., m) , где n и m конечны, то такие игры являются конечными.

Игры с двумя участниками

Если

b	a	,
ij	ij

то эти игры

называются антагонистическими (выигрыш одного влечет проигрыш

другого). В этом случае достаточно задать только одну матрицу

a	ij

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

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

2.2. Матричные игры с седловой точкой

Пусть задана для участника

называют платежной матрицей.

Рассмотрим решение матричных примере:

матрица выигрышей

aij

, которую

игр данного класса на следующем

				S	1b	S	2b	S	3b	S	4b	S	5b	min a		ij
					1b		2b		3b		4b		5b	j		ij
														j
	S	1a		16		22		7		14		8			22
		1a
	S	2a		11		10			8		9	21				8
		2a
	S	3a			6	9			6	13		13			13
		3a
	S	4a			2	16		5		3			4		5
		4a
max a			ij	16		16			8	14		21
i			ij
i

Определение 1 (доминирующая

Sia

Ska

выполняется условие

стратегия). Если для

a	a	( j 1, 2,..., m)
ij	kj

двух стратегий , и существует

хотя бы одна стратегия Ssb такая, что ais aks , тогда

S	ia

является

доминирующей стратегией по отношению к Ska , а чистая стратегия Ska –

доминируемой стратегией.

Если для	пары стратегий			S jb	и	Slb	aij ail	(i 1, 2,..., n)	,	и
существует	Ssa	такая, что	asj	asl ,		тогда	S j –	доминирующая		по

отношению к Sl , а Sl – доминируемая стратегия.

Доминируемые стратегии можно исключить из матрицы aij , так как

оптимального решения среди них не будет.

Выбираем оптимальную стратегию S2*a для участника А по принципу:

Величина

определяет

этому принципу гарантирует,

		.
max min aij		.
i	j

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

Для участника
принципу: min max
j	i

aij

оптимальная стратегия– верхняя цена игры.

	S	*
	S	2 a
		2 a

определяется по

Игры, у которых Отметим, что всегда

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

. Действительно, пусть aik

и asj

							aik . . .	aij
							.	.
							aij : .	.
							.	.
							ask . . .	asj
a	ik	a	ij	, так как	a	ik	– минимальное в строке i ;
	ik		ij			ik
максимальное в столбце j , откуда следует, что								aik

aij


a	sj

asj

, так как

a	sj

–

Может быть несколько седловых точек, тогда цена игры во всех этих точках одинакова: , где – цена игры.

Пусть существуют две седловые точки

определения седловых точек следует:

aik aij ; aij asj ; aik ask ; ask asj .

a	ik	, a	sj

Из условий

Все эти нестрогие неравенства 4 числа равны: aik aij ask asj

выполняются только в случае, когда все

2.3. Матричные игры без седловой точки

В данном классе игр нижняя цена игры строго меньше верхней Введем понятие смешанной стратегии. Смешанная стратегия

комбинация чистых стратегий с вероятностями выбора Pia :

		{P			n
S	a	{P	, P	,..., P };	P 1.
	a	1a	2a	na	ia
					i 1

–

Оптимальная смешанная стратегия: Sa* {Pia* } .

Для любой матрицы

a	ij

можно определить оптимальную смешанную

	*	*	*	*	},
стратегию:	Sa	{Pia	}, Sb	{Pjb	},	такую, что

определяемый в соответствии с выражением:

выигрыш участника

n m
aA aij Pia* Pjb* ,
i 1 j 1
будет в интервале , (для участника B	это проигрыш aB ).

Теорема о минимаксе. В матричной игре без седловой точки ( ) существует точка равновесия такая, что выигрыш участника A находится

в интервале

aA , и оптимальные решения для участников

находятся из условий:

для

a	A

*	} из условия
– {Pia	} из условия
– {P*	} из условия
jb
B	– цена игры.


max min
	j

min max

n aij i 1

m aij j 1

Pia

Pjb


,


	,

Доказательство теоремы будет рассмотрено далее.

Определение 2 (активные стратегии). Активные стратегии для

участника

A – это те стратегии из множества чистых

Sia (i 1, 2,..., n) ,

	*	0 .
для которых	Pia	0 .
Утверждение 1. Если участник			A	придерживается оптимальной

смешанной стратегии, то его выигрыш не зависит от стратегии участника

B в пределах активных стратегий участника B .
Доказательство. Пусть	участник	A	придерживается оптимальной
смешанной стратегии, а B – произвольной смешанной. Тогда выигрыш
участника равен:
m	n	m		n
A aij Pia* Pjb Pjb				aij	Pia* .
j 1 i 1		j 1	i 1

	m
Пусть j	aij Pia* – выигрыш участника
	j 1

, если участник

придерживается чистой стратегии S jb , и одновременно j – проигрыш для участника B , тогда

	m
A		j	P
A		j	jb
	j 1

(2.1)

Поскольку чистая стратегия

S jb

не является оптимальной стратегией

для участника B , то j , j 1, 2,..., m , где	– цена игры.
Запишем (2.1) с учетом этого неравенства:

	m			m		m
A		j	P		P	P
A		j	jb		jb	jb
	j 1			j 1		j 1

С учетом, что

Pjb 1, j 1

получаем нестрогое неравенство

	a

. Но

так как	участник			B осуществляет выбор
		*
стратегий,	а	Pia	–	оптимальная стратегия для

на	множестве активных
A,	то a не может быть

больше . Следовательно a

2.3.1. Решение матричных игр 2 2

Каждый из участников имеет по две чистые стратегии. Матрица выигрышей для A имеет вид:

	a		a
aij		11		12	.
	a		a
		21		22

Элементы матрицы таковы, что , т.е. седловой точки нет.

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

{P	*	,

1a

P	*	},{P	*	,

2a		1b

P	*

2b

}

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

a P

Учитывая, что P2a

P1a :

(1 P

Откуда получим

a22

a11

1 P*

a22

P	*	a		P	*	a

1a			12	2a				22
P	*	a		(1 P			*		)

1a			12			1a
a21				,
a12
			a21
	a11		a12						.
a11			a12 a21

a	22

(2.2)

(2.3)

Для определения

также составим уравнение:

;

P1b

P2b

1 P1b

Цена игры (выигрыш для участника A ) будет равна:

a P

j 1

i 1

;

(2.4)

(2.5)

Для того чтобы решения (2.2), (2.3), (2.4), (2.5) были положительными числами (вероятностями), необходимо, чтобы для элементов матрицы

aij выполнялись следующие неравенства:

a		22	a		21	0

	a		a			0
		22
				12
	a		a			0
				21
	11
a			a			0
	11		12

или

a		22	a		21	0

	a		a			0
		22
				12
	a		a			0
				21
	11
a			a			0
	11		12

	Пример задачи. Правила игры. Каждый из участников имеет две
чистые стратегии:
	S1 – выбрать число 1,
	S2 – выбрать число 2.
	Если сумма у двух участников окажется четным числом, то выигрыш
A	составит эту сумму. Если же сумма окажется нечетной, то выигрывает
участник B .
	Данные правила отражены в следующей платежной матрице:
		S1	S2
	S1	2	3	.
	S2	3	4

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

	P	*					a	22	a		21
	P

	1a			a		a			a				a				4
				a	22	a			a				a			21	4
					22			11	12							21
	P	*		5		.
		*
	2a			12
				12
Для участника		B	решением будет:
							P1b							4 3

												2			3		3
									4			2			3		3
							P			5			.
							P						.
								2b	12
									12
Цена игры равна:							4 2 3 3										1	.
Цена игры равна:																		.
									12							12
Поскольку	0		,	выигрывает участник

вывод, что правила игры несправедливы. Отметим, что при выборе участником

4 3	7	;
2 3 3	12

127 ;

В; из этого можно сделать

В оптимальной смешанной

стратегии его выигрыш

112

не будет зависеть от действий

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

Графическая интерпретация решения игры 2 2. Построим

зависимость выигрыша участника A от		Pia (рис. 2.1),
γ		где	1	P a	(1 P	)a	–
				1a 11	1a	21
γ1	а11	выигрыш участника А, если
а22		участник придерживается чистой

стратегии

S1b

				γ2			2	P		P
а21							2	1a a12 (1		1a )a22 – если
а21
				а12		участник придерживается чистой
				а12		стратегии S2b .
0		Р*1а		1	Р1а	стратегии S2b .
0		Р*1а		1	Р1а			Приравняв	1 и 2, получим
								Приравняв	1 и 2, получим
Рис. 2.1. Графическая интерпретация						оптимальное				значение	*
решения игры за участника А						оптимальное				значение	P1a ,
решения игры за участника А
						которое				соответствует

max min		, т.е.	A	максимизировал свой выигрыш.
	j
j

Теперь рассмотрим решение игры с позиции участника

Построим

зависимость его проигрыша от

P1b

(рис. 2.2),

где

–

1ba11

a12

а11

γ2

а22

проигрыш участника В, если участник

придерживается чистой стратегии

S1a ,

– если

γ1

1ba21

a22

участник придерживается чистой

а21

а12

стратегии

S2a .

Оптимальное значение

Р*1b

1 Р1b

получается из условия

min max i ,

Рис. 2.2. Графическая интерпретация

т.е. он минимизирует проигрыш.

решения игры за участника В

2.3.2. Решение матричных игр

2 m графоаналитическим

методом

Если участник	A	имеет 2 чистые	стратегии, а
стратегий, то матрица выигрышей для A			имеет вид:

–

чистых

					a		a
		a		:	11		12
		a	ij	:	a		a
			ij
						21		22
						21		22
	γ
a23	γ3	γ1			а11
a23					а11
а22
		γ2				а12
						а12
а12					а13
					а13
0	Р*1а				1		Р1а

Рис. 2.3. Графическая интерпретация решения игры 2xm

	a
		1m		.
	a			.
	a	2m
		2m
	Построим зависимость
выигрыша участника								A	от P1a
при чистых стратегиях
участника B
S jb ( j			1, 2,..., m)			:
			j	a	P			1	P		.
			j	1 j	1a a2 j				1a		.
	Оптимальное P1a						находим из
									2
условия					max min aij					Pia
						j			i 1
						j

(рис. 2.3). Найденному

P	*

1a

соответствуют две чистые стратегии участника

B , которые будут для него активными. Таким образом, игру 2 m сводим к игре 2 2 .

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

Пример. Дана платежная матрица, смешанные стратегии:

a		:	2	1
a	ij	:	4	2
	ij

6 3

	1
4	2
0	1
1	P1a

необходимо найти оптимальные

6	3,2	.
3	1

Строим зависимость					j	от
Строим зависимость					j	от
P1a	: выбираем стратегии				S2b
и S	3b	по
принципу
			2
max min			aij	Pia .
		j	i 1
		j
Переходим к матрице 2 2						-
aij		1	6	и
aij		2	3	и
		2	3

рассчитываем оптимальные

P1*a и P2*a :

P	*	3 2	5	;
	*
1a		3 1 2 6	12
		3 1 2 6	12

P	*

2a

		7
		12
		12

. Решением игры для участника В

является:

3 6

;

0; P

2.3.3. Решение матричных игр n 2 графоаналитиским методом

Участник A имеет n чистых стратегий, а					B
платежная матрица имеет вид:
		a11	a12
		a21	a22	.
				.

		an1	an 2
Построим зависимость проигрыша участника
стратегиях A Sia (i 1, 2,..., n) :				1 P		.
	i	a P	a	1 P		.
	i	i1 1b	i2	1b

– 2 чистые стратегии,

B	от P1b при чистых

1 / 31 2 3 > Следующая >>>

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
04.06.2015927.74 Кб78Домашнее задание2.doc
#
04.06.201514.84 Кб10Домашнее задание_1.docx
#
21.08.201999.84 Кб2Доп к практическим заданиям по сетевой экономик...doc
#
08.11.2019136.99 Кб0ДФП.docx
#
04.06.2015175.62 Кб47Дыхательная гимнастика Стрельниковой.doc
#
05.06.2015928.35 Кб54Е.А. Елтаренко. Теория игр. Конспект лекций.pdf
#
11.11.2019307.2 Кб28Е.И. Бабаджан "Методические рекомендации к испо...doc
#
04.06.201569.63 Кб26Жесткость воды.doc
#
20.11.2018476.16 Кб1Журналы лабораторных работ.doc
#
16.09.2019102.91 Кб2Задание на ДП.doc
#
04.06.201522.87 Кб34Задание.docx