Геометрический метод решения задач теории игр

Антагонистические игры.

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

Найти нижнюю и верхнюю цены игры для матрицы

Ai	Bj	αi α=max αi
B1	B2	B3
A1	0.4	0.6	0.8	0.4
A2	1.1	0.7	0.9	0.7
A3	0.7	0.3	0.5	0.3
βJ β = min βJ	1.1	0.7	0.9

Для этой матрицы видно, что α = β = 0,7 = (А₂, В₂).

Общее значение нижней и верхней цены игры α = β = ν называется чистой ценой игры. Седловой точке соответствует пара минимаксных стратегий (А₂В₂), эти стратегии называются оптимальными, а их совокупность - решением игры ( γ = 0,7).

Если седловой точки нет, то можно применить графический способ для задач (2 × n, m × 2) или (если m>2 и n >2)составить математическую модель задачи линейного программирования и решить ее симплекс-методом.

Здесь m – число стратегий игрока А, n – число стратегийигрока В.

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

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

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

Рассмотрим платежную матрицу

5	4	3	2	3
5	6	6
2	3	3	2	4

Упростим матрицу, вычеркивая заведомо невыгодные стратегии игроков, начиная с игрока А, а затем игрока В.

Путем упрощения, ее можно свести к матрице (2 * 2)

ВJ АJ	В1	В2
A1
A2

р₁ - вероятность применения игроком А стратегии A₁;

р₂ - вероятность применения игроком А стратегии A₂.

Так как р₁+ р₂=1, то р₂=1- р₁. Тогда получим:

Чистые стратегии игрока В	Ожидаемые выигрыши игрока А
В1	4 р1+3 р2= (4-3)р1+3=р1+3
В2	2 р1+5 р2=(2-5)р1+5=-3р1+5

На оси Ох разместим точки р₁=0 и р₁=1, через которые проведем прямые, перпендикулярны оси Ох. Подставляя р₁=0 и р₁=1 в выражение р₁+3, найдем значения, которые отложим на соответствующих перпендикулярных прямых. Соединив эти точки, получим прямую.

Аналогично рассмотрим выражение -3р₁+5.

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

р₁+3 и -3р₁+5: р₁= р₂=0,5. S_A = (0,5; 0; 0,5; 0), при этом цена игры равна 3,5.

Для второго игрока оптимальная стратегия ищется аналогично.

Если же игра не сводится путем упрощения к 2 x n или m x 2, то составляется математическая модель и задача решается симплекс-методом.

8.3 Игры с «природой».

Для того чтобы можно сделать вывод о том какую именно стратегию выбирать игроку, необходимо использовать наиболее применяемые критерии Вальда, Гурвица, Сэвиджа, Лапласа, Байеса.

1. Критерий Вальда. Рекомендуется применять максиминную стратегию. Она достигается из условия max min α_ij и совпадает с нижней ценой игры.

j i

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

Рассмотрим задачу.

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

Если булочка не продана днем, то она м.б. реализована за 15 центов к концу дня. Свежие булочки продаются по 49 центов за штуку. Затраты магазина на одну булочку 25 центов.

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

Составим платежную матрицу. Сначала вычислим прибыль (49-25=24) и убыток (15-25=-10).

	100*24	100*24	100*24	100*24	100*24
	100*24-50*10	150*24	150*24	150*24	150*24
	100*24-100*10	150*24-50*10	200*24	200*24	200*24
	100*24-150*10	150*24-100*10	200*24-50*10	250*24	250*24
	100*24-200*10	150*24-150*10	200*24-100*10	250*24-50*10	300*24

Платежная матрица примет вид

Вычислим критерий Вальда - максиминный. Он отражает принцип гарантированного результата:

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

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

Н = max min α_ij

j i

Подсчитать min по строкам и выбрать ту стратегию, при которой минимум строки максимален.

А1
А2
А3
А4
А5

Критерий Вальда рекомендует выбирать стратегию А_1.

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

H = Max {γmin a_ij + (1- γ)max a_ij}

j i i

где γ - степень оптимизма - изменяется в диапазоне [0, 1].

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

Рассмотрим платежную матрицу.

Параметр Гурвица возьмем равным 0,6.

	min	max	γmin aij + (1- γ)max aij
А1			2400*0.6+0.4*2400=2400
А2			1900*0.6+3600*0.4=2580
А3			1400*0.6+4800*0.4=2760
А4			900*0.6+6000*0.4=2940
А5			400*0.6+7200*0.4=3120

Критерий Гурвица рекомендует стратегию А₅.

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

Элементы матрицы рисков находится по формуле (r_ij):

r_ij = maxa_ij - a_ij

где maxa_ij - максимальный элемент в столбце исходной матрицы.

Оптимальная стратегия находится из выражения

H = Min {max(max a_ij - a_ij)}

Составим матрицу риска, (max a_ij - a_ij).

Выберем максимальный элемент в столбце и вычитаем из него остальные элементы столбца, получим max(max a_ij - a_ij).

						Мax
А1
А2
А3
А4
А5

Из максимальных значений последнего столбца выбираем минимальную величину, получим Min {max(max a_ij - a_ij)}.

Критерий Сэвиджа рекомендует стратегию А₄.

4. Критерий Лапласа. Этот критерий основывается на принципе недостаточного обоснования. Поскольку вероятности состояния не известны, необходимая информация для вывода, что эти вероятности различны, отсутствует. Поэтому можно предположить, что они равны. Выбор стратегии осуществляется по формуле

H = Max {1/n·∑ a_ij}

где 1/n вероятность реализации одного из состояний р = 1/n.

А1	(2400+2400+2400+2400+2400)/5=2400
А2	(1900+3600+3600+3600+3600)/5=3260
А3	(1400+3100+4800+4800+4800)/5=3780
А4	(900+2600+4300+6000+6000)/5=3960
А5	(400+2100+3800+5500+7200)/5=3800

Критерий Лапласа рекомендует нам стратегию А₄.

Таким образом, рассмотрев одну платежную матрицу, мы получили, что критерии Лапласа и Сэвиджа рекомендует стратегию А₄. То есть необходимый заказ булочек составит 250 единиц ежедневно.

5. Критерий Байеса. Принятие решения в условиях риска.

Если в рассмотренных выше критериях, необходимая информация о вероятностях какого-либо состояния отсутствовала, то критерий Байеса действует в условиях не полной информации, т.е. в условиях риска (имеется информация о вероятностях применения стратегий второй стороной). Эти вероятности называются априорными вероятностями.

Выбор стратегии осуществляется по формуле

H = Max {∑p_i a_ij}

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

0,2	0,25	0,3	0,15	0,1

Подставив значение a_ij и p_i в формулу, получим:

А1	2400*0,2+2400*0,25+2400*0,3+2400*0,15+2400*0,1=2400
А2	1900*0,2+3600*0,25+3600*0,3+3600*0,15+3600*0,1=3260
А3	1400*0,2+3100*0,25+4800*0,3+4800*0,15+4800*0,1=3695
А4	900*0,2+2600*0,25+4300*0,3+6000*0,15+6000*0,1=3620
А5	400*0,2+2100*0,25+3800*0,3+5500*0,15+7200*0,1=3290

Критерий Байеса рекомендует стратегию А₃

В условиях полной неопределенности теория игр не дает однозначных принципов выбора того или иного критерия.

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

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

ПРИМЕР №1

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

а₁₁ а₁₂ а₁₃ а₁₄ 5 10 18 25

а₂₁ а₂₂ а₂₃ а₂₄ 8 7 8 23

А = а₃₁ а₃₂ а₃₃ а₃₄ ; А = 21 18 12 21

а₄₁ а₄₂ а₄₃ а₄₄ 20 22 19 15

Дата добавления: 2014-01-04