Решение игры без седловой точки

Игра двух лиц с нулевой суммой

a_ij - выигрыш игрока А при выборе игроками А и В стратегий А_i и В_j соответственно.

Игрок А выбирает стратегию i. Его гарантированный выигрыш составит , где минимум берется по всем стратегиям игрока В.

V₁ =

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

V₂ =

Для матричной игры справедливо неравенство V₁ V₂.

Если V₁=V₂, то элемент платежной матрицы называется седловой точкой.

Пример. Определить нижнюю и верхнюю цену игры, заданной платежной матрицей

Решение игры без седловой точки

Пусть смешанные стратегии игроков А и В заданы векторами

S_A=(p₁,p₂,….p_m) и S_B=(q₁,q_2,…….q_n), где p_i – вероятность (частота) применения игроком А чистой стратегии А_i, q_j – вероятность (частота) применения игроком В чистой стратегии B_j. Т.к. речь идет о вероятностях, то справедливо равенство

.

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

Рассмотрим игру без седловой точки

Р= .

Оптимальное решение существует и определяется парой смешанных стратегий S_A =(p₁, p₂) и S_B = (q_1, q₂).

S_A = , S_B =

a₁₁p₁+a₂₁p₂ = V

a₁₂p₁ +a₂₂p₂ =V

р₁+р₂=1

р₁ =

р₂ =

V = .

Аналогично, при отыскании смешанной стратегии второго игрока,

a₁₁q₁+a₁₂q₂ = V

a₂₁q₁ +a₂₂q₂ = V

q₁+q₂ =1

Тогда оптимальная стратегия второго игрока определяется по формулам:

q₁=

q₂=

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

Игра (2 x n).

Ожидаемый выигрыш первого игрока при применении вторым игроком 1-ой стратегии составит

a₁₁p₁+a₂₁p₂=a₁₁p₁+a₂₁(1-p₁)=(a₁₁-a₂₁)p₁+a₂₁.

Аналогично находятся ожидаемые выигрыши первого игрока при применении вторым игроком 2, 3, n-ой стратегий.

Пусть дана платежная матрица Р=

Примеры. 1. Дана платежная матрица

р₁=1/2 р₂=1/2 S_A=(1/2, 1/2). Цена игры V = 7/2.

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

q₁=3/4 q₂=1/4 S_B=(3/4, 1/4). Цена игры V = 7/2.

2. Найдем решение игры вида (2хn), заданной платежной матрицей

3. Найдем решение игры (mx2), заданной платежной матрицей

Р =

При решении любой игры рекомендуется:

1). Исключить заведомо невыгодные стратегии по сравнению с другими.

2). Определить верхнюю и нижнюю цены игры и проверить есть ли седловая точка. Если седловая точка есть, то соответствующие ей стратегии будут оптимальными и цена совпадает с нижней (верхней) игрой.

3). Если седловая точка отсутствует, то решение ищут в смешанных стратегиях.

Решение игр с помощью линейного программирования

Пусть дана платежная матрица

a₁₁p₁ + a₂₁p₂ +…a_m1p_m V,

………………………

a_1np₁ + a_2np₂ +…a_mnp_m V,

p₁ + p₂ + …p_m=1

Разделим все ограничения на V

a_{11 +} a_{21 +…} 1,

…………..

a_1n + a_2n + .. 1

Обозначим =x_i, тогда

a₁₁x₁ + a₂₁x₂ +…a_m1x_m 1,

………………………

a_1nx₁ + a_2nx₂ +…a_mnx_m 1,

Т.к. =x_i, и p₁ + p₂ + …p_m=1, то x₁ +x₂ +…x_m = , где V необходимо максимизировать, следовательно - минимизировать.

Для игрока В задача линейного программирования примет вид

a₁₁y₁ + a₁₂y₂ +…a_1ny_n 1,

………………………

a_m1y₁ + a_m2y₂ +…a_mny_n 1,

Целевая функция Z(y) = y₁ + y₂ …y_n стремится к максимуму.

Задача. Предприятие выпускает продукцию трех видов А₁, А₂, А₃, получая прибыль, зависящую от спроса, который может быть в 4-х состояниях В₁, В₂, В₃, В₄. Дана матрица прибыли, которую получает предприятие при выпуске i- ой продукции с j –м состоянием спроса

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

Решение.

Р=

V₁ V₂, оптимальное решение ищем в смешанных стратегиях.

S_A=(p₁, p₂, р₃) S_B=(q₁,q_2,q₃)

x_i = , y_j = , тогда

Решая систему, получим

Y_опт.=(0,04; 0,15; 0), z(y) = 0,19.

X_опт.=(0,05; 0; 0,14), x₁+x₂+x₃=0,19

Цена игры V= 5,4.

Игры с природой

1. Критерий Вальде.Рекомендуется применять максиминную стратегию:

max min a_ij

2. Критерий максимума.Он выбирается из условия

maxmaxa_ij

3.Критерий Гурвица.Критерий рекомендует стратегию, определяемую по формуле

max(α min a_ij + (1- α)max a_ij), где α – степень оптимизма, которая изменяется в диапазоне (0, 1).

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

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

r_ij = max a_ij – a_ij, где max a_ij – максимальный элемент в столбце исходной матрицы.

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

min(max(max a_ij – a_ij)).