Теория игр

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФГБОУ ВПО «Уральский государственный экономический университет»

Центр дистанционного образования

Контрольная работа

Теория игр

Исполнитель: студент

Направление Экономика

Профиль

Экономическая безопасность

группа ЭПБ - 11 Р

Урывков Алексей Вячеславович

Екатеринбург 2013г.

ЗАДАНИЯ

1) а) Решить игру с природой по критерию Гурвица, б=0,4;

б) Решить игру с природой по критерию Лапласа;

в) Решить игру с природой по критерию Сэвиджа;

г) Решить игру с природой по критерию Вальда.

2) Решить игру методом Брауна, выполнить 20 итераций.

3) Решить игру симплекс-методом.

4) Решить игру графически.

5) Найти верхнюю и нижнюю цену игры, проверить игру на наличие седловой точки.

№ задания	1	2	3	4	5
8

Задание 1

1) а) Решить игру с природой по критерию Гурвица, б=0,4;

б) Решить игру с природой по критерию Лапласа;

в) Решить игру с природой по критерию Сэвиджа;

г) Решить игру с природой по критерию Вальда.

Решение:

Критерий Гурвица.

Критерий Гурвица является критерием пессимизма - оптимизма.

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

max(si)

где si = y min(aij) + (1-y)max(aij)

При y = 1 получим критерий Вальде, при y = 0 получим - оптимистический критерий (максимакс). Критерий Гурвица учитывает возможность как наихудшего, так и наилучшего для человека поведения природы. Как выбирается y? Чем хуже последствия ошибочных решений, тем больше желание застраховаться от ошибок, тем y ближе к 1.

Рассчитываем si.

s1 = 0,4*(-1)+(1-0,4)*4 = 2

s2 = 0,4*3+(1-0,4)*9 = 6,6

s3 = 0,4*(-8)+(1-0,4)*6 = 0,4

s4 = 0,4*1+(1-0,4)*3 = 2,2

Ai	П1	П2	П3	min(aij)	max(aij)	y min(aij) + (1-y)max(aij)
A1	1	-1	4	-1	4	2
A2	3	9	9	3	9	6.6
A3	-8	-5	6	-8	6	0.4
A4	1	3	2	1	3	2.2

Выбираем из (2; 6,6; 0,4; 2,2) максимальный элемент max=6,6

Вывод: выбираем стратегию N=2.

Критерий Лапласа.

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

q1 = q2 = ... = qn = 1/n.

qi = 1/3

Ai	П1	П2	П3	?(aij)
A1	0.3333	-0.3333	1.33	1.33
A2	1	3	3	7
A3	-2.67	-1.67	2	-2.33
A4	0.3333	1	0.6667	2
pj	0.333	0.333	0.333	0

Выбираем из (1,33; 7; -2,33; 2) максимальный элемент max=7

Вывод: выбираем стратегию N=2.

Критерий Севиджа.

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

a = min(max rij)

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

Находим матрицу рисков.

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

Максимальный выигрыш в j-м столбце bj = max(aij) характеризует благоприятность состояния природы.

1. Рассчитываем 1-й столбец матрицы рисков.

r11 = 3 - 1 = 2; r21 = 3 - 3 = 0; r31 = 3 - (-8) = 11; r41 = 3 - 1 = 2;

2. Рассчитываем 2-й столбец матрицы рисков.

r12 = 9 - (-1) = 10; r22 = 9 - 9 = 0; r32 = 9 - (-5) = 14; r42 = 9 - 3 = 6;

3. Рассчитываем 3-й столбец матрицы рисков.

r13 = 9 - 4 = 5; r23 = 9 - 9 = 0; r33 = 9 - 6 = 3; r43 = 9 - 2 = 7;

Ai	П1	П2	П3
A1	2	10	5
A2	0	0	0
A3	11	14	3
A4	2	6	7

Результаты вычислений оформим в виде таблицы.

Ai	П1	П2	П3	max(aij)
A1	2	10	5	10
A2	0	0	0	0
A3	11	14	3	14
A4	2	6	7	7

Выбираем из (10; 0; 14; 7) минимальный элемент min=0

Вывод: выбираем стратегию N=2.

Критерий Вальда.

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

a = max(min aij)

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

Ai	П1	П2	П3	min(aij)
A1	1	-1	4	-1
A2	3	9	9	3
A3	-8	-5	6	-8
A4	1	3	2	1

Выбираем из (-1; 3; -8; 1) максимальный элемент max=3

Вывод: выбираем стратегию N=2.

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

Задание 2

игра решение лаплас риск

Решить игру методом Брауна, выполнить 20 итераций.

Решение

h	игрок А	игрок В	Приближенные значения цены
	стратегия	Накопл. выигр. В	стратегия	Накопл. выигр. А
		В1	В2	В3		А1	А2	А3	Vn1	Vn11	Vnср
1	А2	4	2	5	В2	-9	2	8	8	2	10/2
2	А3	4	10	8	В1	-8	6	8	8/2	4/2	12/4
3	А3	4	18	11	В1	-7	10	8	10/3	4/3	14/6
4	А2	8	20	16	В1	-6	14	8	14/4	8/4	22/8
5	А2	12	22	21	В1	-5	18	8	18/5	12/5	30/10
6	А2	16	24	26	В1	-4	22	8	22/6	16/6	38/12
7	А2	20	26	31	В1	-3	26	8	26/7	20/7	46/14
8	А2	24	28	36	В1	-2	30	8	30/8	24/8	54/16
9	А2	28	30	41	В1	-1	34	8	34/9	28/9	62/18
10	А2	32	32	46	В1	0	38	8	38/10	32/10	70/20
11	А2	36	34	51	В2	-9	40	16	40/11	34/11	74/22
12	А2	40	36	56	В2	-18	42	24	42/12	36/12	78/24
13	А2	44	38	61	В2	-27	44	32	44/13	38/13	82/26
14	А2	48	40	66	В2	-36	46	40	46/14	40/14	86/28
15	А2	52	42	71	В2	-45	48	48	48/15	42/15	90/30
16	А2	56	44	76	В2	-54	50	56	56/16	44/16	100/32
17	А3	56	52	79	В2	-63	52	64	64/17	52/17	116/34
18	А3	56	60	82	В1	-62	56	64	64/18	56/18	120/36
19	А3	56	68	85	В1	-61	60	64	64/19	56/19	120/38
20	А3	56	76	88	В1	-60	64	64	64/20	56/20	120/40

А1 = 0

А2 = 6

А3 = 14

В1 = 12

В2 =8

В3 =0

p=(0/20, 3/10, 7/10)

q=(3/5, 2/5, 0/20)

Р(В1)=0/20

Р(В2)=6/20=3/10

Р(В3)=14/20=7/10

Р(А1)=12/20=3/5

Р(А2)=8/20=2/5

Р(А3)=0/20

W=120/40 = 3

Задание 3

Решить игру симплекс-методом.

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

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

Игроки	B1	B2	B3	B4	a = min(Ai)
A1	1	2	3	0	0
A2	3	8	2	1	1
A3	5	4	4	6	4
A4	3	1	1	0	0
b = max(Bi)	5	8	4	6

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

a = max(ai) = 4, которая указывает на максимальную чистую стратегию A3.

Верхняя цена игры b = min(bj) = 4.

Седловая точка (3, 3) указывает решение на пару альтернатив (A3,B3). Цена игры равна 4.

2. Проверяем платежную матрицу на доминирующие строки и доминирующие столбцы.

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

Говорят, что i-я стратегия 1-го игрока доминирует его k-ю стратегию, если aij ? akj для всех j Э N и хотя бы для одного j aij > akj. В этом случае говорят также, что i-я стратегия (или строка) - доминирующая, k-я - доминируемая.

Говорят, что j-я стратегия 2-го игрока доминирует его l-ю стратегию, если для всех j Э M aij ? ail и хотя бы для одного i aij < ail. В этом случае j-ю стратегию (столбец) называют доминирующей, l-ю - доминируемой.

Стратегия A2 доминирует над стратегией A4 (все элементы строки 2 больше или равны значениям 4-ой строки), следовательно исключаем 4-ую строку матрицы. Вероятность p4 = 0.

1	2	3	0
3	8	2	1
5	4	4	6

В платежной матрице отсутствуют доминирующие столбцы.

Мы свели игру 4 x 4 к игре 3 x 4.

3. Находим решение игры в смешанных стратегиях.

Математические модели пары двойственных задач линейного программирования можно записать так:

найти минимум функции F(x) при ограничениях:

x1+3x2+5x3 ? 1

2x1+8x2+4x3 ? 1

3x1+2x2+4x3 ? 1

x2+6x3 ? 1

F(x) = x1+x2+x3 > min

найти максимум функции Ф(y) при ограничениях:

y1+2y2+3y3 ? 1

3y1+8y2+2y3+y4 ? 1

5y1+4y2+4y3+6y4 ? 1

Ф(y) = y1+y2+y3+y4 > max

Решаем эти системы симплексным методом.

Решение симплекс-методом доступно в расширенном режиме.

Цена игры будет равна g = 1/F(x), а вероятности применения стратегий игроков:

pi = g*xi; qi = g*yi.

Цена игры: g = 1 : 1/4 = 4

p1 = 4 * 0 = 0

p2 = 4 * 0 = 0

p3 = 4 * 1/4 = 1

Оптимальная смешанная стратегия игрока I:

P = (0; 0; 1)

q1 = 4 * 0 = 0

q2 = 4 * 1/12 = 1/3

q3 = 4 * 1/6 = 2/3

q4 = 4 * 0 = 0

Оптимальная смешанная стратегия игрока II:

Q = (0; 1/3; 2/3; 0)

Цена игры: v=4

4. Проверим правильность решения игры с помощью критерия оптимальности стратегии.

?aijqj ? v

?aijpi ? v

M(P1;Q) = (1*0) + (2*1/3) + (3*2/3) + (0*0) = 2.67 ? v

M(P2;Q) = (3*0) + (8*1/3) + (2*2/3) + (1*0) = 4 = v

M(P3;Q) = (5*0) + (4*1/3) + (4*2/3) + (6*0) = 4 = v

M(P;Q1) = (1*0) + (3*0) + (5*1) = 5 ? v

M(P;Q2) = (2*0) + (8*0) + (4*1) = 4 = v

M(P;Q3) = (3*0) + (2*0) + (4*1) = 4 = v

M(P;Q4) = (0*0) + (1*0) + (6*1) = 6 ? v

Все неравенства выполняются как равенства или строгие неравенства, следовательно, решение игры найдено верно.

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

P(0,0,1,0)

Q(0,1/3,2/3,0)

Задание 4

4) Решить игру графически.

Игроки	B1	B2	a = min(Ai)
A1	6	3	3
A2	2	6	2
A3	7	5	5
b = max(Bi)	7	6

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = 5, которая указывает на максимальную чистую стратегию A3.

Верхняя цена игры b = min(bj) = 6.

Что свидетельствует об отсутствии седловой точки, так как a ? b, тогда цена игры находится в пределах 5 <= y <= 6. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии)

Решим задачу геометрическим методом, который включает в себя следующие этапы:

1. В декартовой системе координат по оси абсцисс откладывается отрезок, длина которого равна 1. Левый конец отрезка (точка х = 0) соответствует стратегии B1, правый - стратегии B2 (x = 1). Промежуточные точки х соответствуют вероятностям некоторых смешанных стратегий S1 = (p1,p2).

2. На левой оси ординат откладываются выигрыши стратегии B1. На линии, параллельной оси ординат, из точки 1 откладываются выигрыши стратегии B2.

Решение игры (m x 2) проводим с позиции игрока B, придерживающегося максиминной стратегии. Доминирующихся и дублирующих стратегий ни у одного из игроков нет.

Максиминной оптимальной стратегии игрока B соответствует точка N, лежащая на пересечении прямых A2A2 и A3A3, для которых можно записать следующую систему уравнений:

y = 2 + (6 - 2)q2

y = 7 + (5 - 7)q2

Откуда

q1 = 1/6

q2 = 5/6

Цена игры, y = 51/3

Теперь можно найти минимаксную стратегию игрока A, записав соответствующую систему уравнений, исключив стратегию A1, которая дает явно больший проигрыш игроку A, и, следовательно, p1 = 0.

2p2+7p3 = y

6p2+5p3 = y

p2+p3 = 1

или

2p2+7p3 = 51/3

6p2+5p3 = 51/3

p2+p3 = 1

Решая эту систему методом обратной матрицы, находим:

p2 = 1/3

p3 = 2/3

Задание 5

Найти верхнюю и нижнюю цену игры, проверить игру на наличие седловой точки.

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

Если да, то выписываем решение игры в чистых стратегиях.

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

Игроки	B1	B2	B3	a = min(Ai)	max
A1	0	-3	4	-3
A2	8	5	7	5	5
A3	1	8	6	1
A4	1	3	2	1
b = max(Bi)	8	8	7
min			7

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = 5, которая указывает на максимальную чистую стратегию A2.

Верхняя цена игры b = min(bj) =7.

a = max(ai) ? b = min(bj); 5 ? 7 = > седловой точки нет.

Размещено на Allbest.ru