Разработка вариантов решения задач теории игр

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

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

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

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

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

по дисциплине «Теория игр»

вариант 5

Преподаватель: Петрова С.Н.

Студент: Малютина Ю.Р.

Специальность: Экономика

Группа: ЭПБп-14Р

Екатеринбург 2017



1) Решить игру:

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

Исходные данные

1	-3	4
2	9	8
0	-7	6
1	4	2

Критерий Гурвица является критерием пессимизма - оптимизма. За оптимальную принимается та стратегия, для которой выполняется соотношение:

max(s_i)

где s_i = y min(a_ij) + (1-y)max(a_ij)

При y = 1 получим критерий Вальде, при y = 0 получим - оптимистический критерий (максимакс).

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

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

s₁ = 0.4*(-3)+(1-0.4)*4 = 1.2

s₂ = 0.4*2+(1-0.4)*9 = 6.2

s₃ = 0.4*(-7)+(1-0.4)*6 = 0.8

s₄ = 0.4*1+(1-0.4)*4 = 2.8



Ai	П1	П2	П3	min(aij)	max(aij)	y min(aij) + (1-y)max(aij)
A1	1	-3	4	-3	4	1.2
A2	2	9	8	2	9	6.2
A3	0	-7	6	-7	6	0.8
A4	1	4	2	1	4	2.8

Выбираем из (1.2; 6.2; 0.8; 2.8) максимальный элемент max=6.2

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

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

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

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

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

q₁ = q₂ =... = q_n = 1/n.

q_i = 1/3

Ai	П1	П2	П3	?(aij)
A1	0.333	-1	1.333	0.667
A2	0.667	3	2.667	6.333
A3	0	-2.333	2	-0.333
A4	0.333	1.333	0.667	2.333
pj	0.333	0.333	0.333

Выбираем из (0.67; 6.33; -0.33; 2.33) максимальный элемент max=6.33

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

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

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

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

a = min(max r_ij)

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

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

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

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

r₁₁ = 2 - 1 = 1; r₂₁ = 2 - 2 = 0; r₃₁ = 2 - 0 = 2; r₄₁ = 2 - 1 = 1;

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

r₁₂ = 9 - (-3) = 12; r₂₂ = 9 - 9 = 0; r₃₂ = 9 - (-7) = 16; r₄₂ = 9 - 4 = 5;

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

r₁₃ = 8 - 4 = 4; r₂₃ = 8 - 8 = 0; r₃₃ = 8 - 6 = 2; r₄₃ = 8 - 2 = 6;



Ai	П1	П2	П3
A1	1	12	4
A2	0	0	0
A3	2	16	2
A4	1	5	6

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

Ai	П1	П2	П3	max(aij)
A1	1	12	4	12
A2	0	0	0	0
A3	2	16	2	16
A4	1	5	6	6

Выбираем из (12; 0; 16; 6) минимальный элемент min=0

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

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

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

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

a = max(min a_ij)

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



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

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

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

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

1	4	8
9	6	5
7	8	3

Рассмотрим игру двух лиц, интересы которых противоположны. Такие игры называют антагонистическими играми двух лиц. В этом случае выигрыш одного игрока равен проигрышу второго, и можно описать только одного из игроков.

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

Если каждый из игроков выбрал свою стратегию, то эту пару стратегий называют ситуацией игры. Следует заметить, каждый игрок знает, какую стратегию выбрал его противник, т.е. имеет полную информацию о результате выбора противника.

Чистой стратегией игрока I является выбор одной из n строк матрицы выигрышей А, а чистой стратегией игрока II является выбор одного из столбцов этой же матрицы.

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

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

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

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

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

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

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

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

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

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

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

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

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

Аналогично, игрок II должен выбрать свои смешанные стратегии так, чтобы минимизировать математическое ожидание игрока I.

Пусть игра задана матрицей A размерности m x n. Каждое разыгрывание игры в чистых стратегиях будет далее называться партией. Метод Брауна-Робинсон -- это итеративная процедура построения последовательности пар смешанных стратегий игроков, сходящейся к решению матричной игры.

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

Пусть на первом этапе выбрана стратегия №1

Итерация №1. Минимальный элемент для нее равен 1 и находится под номером j=1. Следовательно, игрок II выбирает стратегию №1

Максимальный элемент равен 9 и находится под номером j=2. Следовательно, игрок I выбирает стратегию №2

Итерация №2. Минимальный элемент для нее равен 10 и находится под номером j=1. Следовательно, игрок II выбирает стратегию №1

Максимальный элемент равен 18 и находится под номером j=2. Следовательно, игрок I выбирает стратегию №2

Остальное решение сведем в таблицу.

k	i	B1	B2	B3	j	A1	A2	A3	Vmin	Vmax	Vср
1	1	1	4	8	1	1	9	7	1	9	5
2	2	10	10	13	1	2	18	14	5	9	7
3	2	19	16	18	2	6	24	22	16/3	8	20/3
4	2	28	22	23	2	10	30	30	11/2	15/2	13/2
5	2	37	28	28	2	14	36	38	28/5	38/5	33/5
6	3	44	36	31	3	22	41	41	31/6	41/6	6
7	2	53	42	36	3	30	46	44	36/7	46/7	41/7
8	2	62	48	41	3	38	51	47	41/8	51/8	23/4
9	2	71	54	46	3	46	56	50	46/9	56/9	17/3
10	2	80	60	51	3	54	61	53	51/10	61/10	28/5
11	2	89	66	56	3	62	66	56	56/11	6	61/11
12	2	98	72	61	3	70	71	59	61/12	71/12	11/2
13	2	107	78	66	3	78	76	62	66/13	6	72/13
14	1	108	82	74	3	86	81	65	37/7	43/7	40/7
15	1	109	86	82	3	94	86	68	82/15	94/15	88/15
16	1	110	90	90	2	98	92	76	45/8	49/8	47/8
17	1	111	94	98	2	102	98	84	94/17	6	98/17
18	1	112	98	106	2	106	104	92	49/9	53/9	17/3
19	1	113	102	114	2	110	110	100	102/19	110/19	106/19
20	1	114	106	122	2	114	116	108	53/10	29/5	111/20

здесь:

k - номер партии.

i - номер стратегии, выбираемой игроком A.

j - номер стратегии, выбираемой игроком В.

B_i - накопленный игроком А выигрыш за k партий, при условии, что в данной партии B выбирает стратегию B_i.

А_j - накопленный игроком В проигрыш за k партий, при условии, что в данной партии A выбирает стратегию А_j.

V_min - нижняя оценка игры = min (накопленный выигрыш)/k.

V^max - верхняя оценка игры = max (накопленный проигрыш)/k.

Доказано, что:

W=(V_min+V^max)/2, при k > ? и

p_i = N_i/k

q_j = N_j/k

N_i - сколько раз выбирается Аi стратегия.

N_j - сколько раз выбирается Bj стратегия.

N_A1 = 8

P(A₁) = 8/20 = ²/₅

N_A2 = 11

P(A₂) = 11/20 = ¹¹/₂₀

N_A3 = 1

P(A₃) = 1/20 = ¹/₂₀

N_B1 = 2

P(B₄) = 2/20 = ¹/₁₀

N_B2 = 8

P(B₄) = 8/20 = ²/₅

N_B3 = 10

P(B₄) = 10/20 = ¹/₂

Цена игры, W = ¹¹¹/₂₀

Стратегия игрока I: p = (²/₅, ¹¹/₂₀, ¹/₂₀)

Стратегия игрока II: q = (¹/₁₀, ²/₅, ¹/₂)

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

1	2	3	0
-8	4	6	1
3	7	4	6
3	6	1	0

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

Чистой стратегией игрока I является выбор одной из n строк матрицы выигрышей А, а чистой стратегией игрока II является выбор одного из столбцов этой же матрицы.

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

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



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

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

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

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

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

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

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

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

Стратегия A₃ доминирует над стратегией A₁ (все элементы строки 3 больше или равны значениям 1-ой строки), следовательно, исключаем 1-ую строку матрицы. Вероятность p₁ = 0.

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

-8	4	6	1
3	7	4	6

С позиции проигрышей игрока В стратегия B₁ доминирует над стратегией B₂ (все элементы столбца 1 меньше элементов столбца 2), следовательно, исключаем 2-й столбец матрицы. Вероятность q₂ = 0.

С позиции проигрышей игрока В стратегия B₁ доминирует над стратегией B₃ (все элементы столбца 1 меньше элементов столбца 3), следовательно, исключаем 3-й столбец матрицы. Вероятность q₃ = 0.

-8	1
3	6

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

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

0	9
11	14

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

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

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

11x₂ ? 1

9x₁+14x₂ ? 1

F(x) = x₁+x₂ > min

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

9y₂ ? 1

11y₁+14y₂ ? 1

Z(y) = y₁+y₂ > max

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

Определим максимальное значение целевой функции Z(Y) = y₁+y₂ при следующих условиях-ограничений.

9y₂?1

11y₁+14y₂?1

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

0y₁ + 9y₂ + 1y₃ + 0y₄ = 1

11y₁ + 14y₂ + 0y₃ + 1y₄ = 1

Решим систему уравнений относительно базисных переменных: y₃, y₄

Полагая, что свободные переменные равны 0, получим первый опорный план:

Y0 = (0,0,1,1)

Базис	B		y2	y3	y4
y3	1	0	9	1	0
y4	1	11	14	0	1
Z(Y0)	0	-1	-1	0	0

Переходим к основному алгоритму симплекс-метода.

Итерация №0.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

В качестве ведущего выберем столбец, соответствующий переменной y₂, так как это наибольший коэффициент по модулю.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i2

и из них выберем наименьшее:

min (1: 9, 1: 14 ) = ¹/₁₄

Следовательно, 2-ая строка является ведущей.

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

Базис	B	y1	y2	y3	y4	min
y3	1	0	9	1	0	1/9
y4	1	11	14	0	1	1/14
Z(Y1)	0	-1	-1	0	0

Формируем следующую часть симплексной таблицы. Вместо переменной y₄ в план 1 войдет переменная y₂.

Получаем новую симплекс-таблицу:

Базис	B	y1	y2	y3	y4
y3	5/14	-99/14	0	1	-9/14
y2	1/14	11/14	1	0	1/14
Z(Y1)	1/14	-3/14	0	0	1/14

Итерация №1.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

В качестве ведущего выберем столбец, соответствующий переменной y₁, так как это наибольший коэффициент по модулю.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i1

и из них выберем наименьшее:

min (-, ¹/₁₄: ¹¹/₁₄ ) = ¹/₁₁

Следовательно, 2-ая строка является ведущей.

Разрешающий элемент равен (¹¹/₁₄) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	y1	y2	y3	y4	min
y3	5/14	-99/14	0	1	-9/14	-
y2	1/14	11/14	1	0	1/14	1/11
Z(Y2)	1/14	-3/14	0	0	1/14

Формируем следующую часть симплексной таблицы. Вместо переменной y₂ в план 2 войдет переменная y₁.

Получаем новую симплекс-таблицу:

Базис	B	y1	y2	y3	y4
y3	1	0	9	1	0
y1	1/11	1	14/11	0	1/11
Z(Y2)	1/11	0	3/11	0	1/11

Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план

Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.

Окончательный вариант симплекс-таблицы:

Базис	B	y1	y2	y3	y4
y3	1	0	9	1	0
y1	1/11	1	14/11	0	1/11
Z(Y3)	1/11	0	3/11	0	1/11

Оптимальный план можно записать так:

y₁ = ¹/₁₁, y₂ = 0

Z(Y) = 1*¹/₁₁ + 1*0 = ¹/₁₁

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

x₁=0, x₂=¹/₁₁

Это же решение можно получить, применив теоремы двойственности.

Из теоремы двойственности следует, что X = C*A^-1.

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

A = (A3, A1) =	1 0 0 11

Определив обратную матрицу D = А^-1 через алгебраические дополнения, получим:

D = A-1 =	1 0 0 1/11

Как видно из последнего плана симплексной таблицы, обратная матрица A^-1 расположена в столбцах дополнительных переменных.

Тогда X = C*A^-1 =

(0, 1) x	1 0 0 1/11	= (0;1/11)

Оптимальный план двойственной задачи равен:



x₁ = 0, x₂ = ¹/₁₁

F(X) = 1*0+1*¹/₁₁ = ¹/₁₁

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

q_i = g*y_i; p_i = g*x_i.

Цена игры: g = 1: ¹/₁₁ = 11

p₁ = 11 * 0 = 0

p₂ = 11 * ¹/₁₁ = 1

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

P = (0; 1)

q₁ = 11 * ¹/₁₁ = 1

q₂ = 11 * 0 = 0

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

Q = (1; 0)

Поскольку ранее к элементам матрицы было прибавлено число (8), то вычтем это число из цены игры.

11 - 8 = 3

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

критерий оптимальность игра матрица

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



?a_ijq_j ? v

?a_ijp_i ? v

M(P₁;Q) = (-8*1) + (1*0) = -8 ? v

M(P₂;Q) = (3*1) + (6*0) = 3 = v

M(P;Q₁) = (-8*0) + (3*1) = 3 = v

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

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

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

P(0,0,1,0)

Q(1,0,0,0)

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

4	2
3	9
4	8

Рассмотрим игру двух лиц, интересы которых противоположны. Такие игры называют антагонистическими играми двух лиц. В этом случае выигрыш одного игрока равен проигрышу второго, и можно описать только одного из игроков.

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

Если каждый из игроков выбрал свою стратегию, то эту пару стратегий называют ситуацией игры. Следует заметить, каждый игрок знает, какую стратегию выбрал его противник, т.е. имеет полную информацию о результате выбора противника.

Чистой стратегией игрока I является выбор одной из n строк матрицы выигрышей А, а чистой стратегией игрока II является выбор одного из столбцов этой же матрицы.

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

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

Игроки	B1	B2	a = min(Ai)
A1	4	2	2
A2	3	9	3
A3	4	8	4
b = max(Bi)	4	9

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

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

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

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

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

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

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

Стратегия A₃ доминирует над стратегией A₁ (все элементы строки 3 больше или равны значениям 1-ой строки), следовательно, исключаем 1-ую строку матрицы. Вероятность p₁ = 0.

3	9
4	8

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

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

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

1. В декартовой системе координат по оси абсцисс откладывается отрезок, длина которого равна 1. Левый конец отрезка (точка х = 0) соответствует стратегии A₁, правый - стратегии A₂ (x = 1). Промежуточные точки х соответствуют вероятностям некоторых смешанных стратегий S₁ = (p₁,p₂).

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

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

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

p₁ = 0

p₂ = 1

Цена игры, y = 4

Теперь можно найти минимаксную стратегию игрока B, записав соответствующую систему уравнений

q₁ = 1.

q₂ = 0.

Ответ:

Цена игры: y = 4, векторы стратегии игроков:

Q(1, 0), P(0, 1)

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

?a_ijq_j ? v

?a_ijp_i ? v

M(P₁;Q) = (3*1) + (9*0) = 3 ? v

M(P₂;Q) = (4*1) + (8*0) = 4 = v

M(P;Q₁) = (3*0) + (4*1) = 4 = v

M(P;Q₂) = (9*0) + (8*1) = 8 ? v

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

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

P(0,0,1)

Q(1,0)

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

5	-3	4
2	5	9
9	0	6
1	3	2

Рассмотрим игру двух лиц, интересы которых противоположны. Такие игры называют антагонистическими играми двух лиц. В этом случае выигрыш одного игрока равен проигрышу второго, и можно описать только одного из игроков.

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

Если каждый из игроков выбрал свою стратегию, то эту пару стратегий называют ситуацией игры. Следует заметить, каждый игрок знает, какую стратегию выбрал его противник, т.е. имеет полную информацию о результате выбора противника.

Чистой стратегией игрока I является выбор одной из n строк матрицы выигрышей А, а чистой стратегией игрока II является выбор одного из столбцов этой же матрицы.

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

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

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

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

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

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

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

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

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

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

Стратегия A₃ доминирует над стратегией A₁ (все элементы строки 3 больше или равны значениям 1-ой строки), следовательно, исключаем 1-ую строку матрицы. Вероятность p₁ = 0.

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

2	5	9
9	0	6

С позиции проигрышей игрока В стратегия B₂ доминирует над стратегией B₃ (все элементы столбца 2 меньше элементов столбца 3), следовательно, исключаем 3-й столбец матрицы. Вероятность q₃ = 0.

2	5
9	0

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

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

Аналогично, игрок II должен выбрать свои смешанные стратегии так, чтобы минимизировать математическое ожидание игрока I.

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

Запишем систему уравнений.

Для игрока I

2p₁+9p₂ = y

5p₁ = y

p₁+p₂ = 1

Для игрока II

2q₁+5q₂ = y

9q₁ = y

q₁+q₂ = 1

Решая эти системы методом Гаусса (решение см. ниже), находим:

y = 3³/₄

p₁ = ³/₄ (вероятность применения 1-ой стратегии).

p₂ = ¹/₄ (вероятность применения 2-ой стратегии).

Оптимальная смешанная стратегия игрока I: P = (³/₄; ¹/₄)

q₁ = ⁵/₁₂ (вероятность применения 1-ой стратегии).

q₂ = ⁷/₁₂ (вероятность применения 2-ой стратегии).

Оптимальная смешанная стратегия игрока II: Q = (⁵/₁₂; ⁷/₁₂)

Цена игры:

y = 3³/₄

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

...