Решение матричной игры: графическим методом, методом линейного программирования
Решение матричной игры
Цена игры, седловая точка
Примеры решений Метод Брауна Системы массового обслуживания Матрица рисков Седловая точка Платежная матрица Цена игры Смешанные стратегии Матричная игра онлайн Чистые стратегии

Пример решения биматричной игры

Математической моделью конфликтов с двумя участниками являются биматричные игры. Такая игра 2х2 задается биматрицей (aij,bij) . В кооперативном варианте такой игры игроки могут согласованно выбирать элемент биматрицы. Если они выбрали элемент (a,b), то Первый игрок получает a , а Второй получает b . Цели игроков одинаковы - выиграть как можно больше в расчете на партию в среднем. Пусть (x,y), (a,b) - две точки из CE. Говорят, что (x,y) доминирует (a,b) если x≥a, y≥b и хотя бы одно из этих неравенств строгое. Недоминируемые точки называются оптимальными по Парето, а их множество - множеством оптимальности по Парето. Еще более узкое множество называется переговорным. Оно определяется так: пусть Vk - максимальный выигрыш, который k-й игрок может обеспечить себе при любой стратегии другого игрока, тогда переговорное множество определяется как множество тех точек множества Парето, у которых k-я координата не меньше Vk. Для нахождения Vk надо решить две задачи ЛП:

V1→max, a11*x+a21*(1-x) ≥V1,a11*x+a12*(1-x)≥V1, 0≤x≤1;

V2→max, a11*y+a12*(1-y) ≥V2,a21*y+a22*(1-y)≥V2, 0≤y≤1.

Дано:
Биматрица

22
87

66
91

Нанесем на плоскость элементы биматрицы и начертим выпуклую оболочку. Биматричная игра
Графическое решение биматричной игры

Где красным и зеленым цветом обозначено множество оптимальности по Парето, а зеленым – та его часть, которая является переговорным множеством. V1=8, V2=4.

Цена игры первого игрока V1 находится легко, так как в матрице аij есть седловая точка а[2,1]=8. Основная теорема матричных игр утверждает, что для любой матричной игры max{min{M[P,Q]:Q}:P}=min{max{M[P,Q]:P}:Q}, т.е. во множестве смешанных стратегий есть седловая точка, дающая оптимальное решение игры. Поэтому V1= а[2,1]=8, а оптимальная стратегия 1-го игрока Р*=(0,1), так как ему выгодно выбирать все время 2-ю строку.

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

V2→max
y/V2=x1
x1 + x2 →min

2*y+6*(1-y)≥ V2, (1-y)/V2=x22*x1+6*x2≥1

7*y+1*(1-y) ≥V2, 7*x1 +1*x2≥1

0≤y≤1.   x1, x2 ≥0

Решая ее находим V2=4.

Итак, цена игры 2-го игрока V2=4

Перейти к онлайн решению своей задачи

Пример. Найдите решения биматричной игры. Решение находим с помощью калькулятора.
В каждом столбце матрицы A найдем максимальный элемент. Эти элементы подчеркнуты в матрице A. Их положение соответствует приемлемым ситуациям 1-го игрока, когда второй игрок выбрал стратегию j соответственно.
Затем в каждой строке матрицы B выберем наибольший элемент. Эти элементы подчеркнуты в матрице B. Их положение будет определять приемлемые ситуации 2-го игрока, когда первый игрок выбрал стратегию i соответственно.
Платежная матрица игрока А:

-102
1-1
Платежная матрица игрока B:
5-2
-11

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

Итак, чтобы в биматричной игре:
А=(aij), В = (bij) пара (p,q);
определяемая равновесную ситуацию, необходимо и достаточно одновременное выполнение следующих неравенств:
(p–1)(Cq-α) ≥ 0, p(Cq-α) ≥ 0; 0 ≥ p ≥ 1
(q-1)(Dp-β) ≥ 0, q(Dp-β) ≥ 0; 0 ≥ q ≥ 1
где
C = a11 - a12 - a21 + a22
α = a22- a12
D = b11-b12-b21+b22
β = b22-b21
Проводя необходимые вычисления:
C = -10 - 2 - 1 -1 = -14
α = -1 - 2 = -3
D = 5 - (-2) - (-1) + 1 = 9
β = 1 - (-1) = 2
и рассуждения
(p–1)(-14q+3) ≥ 0
p(-14q+3) ≥ 0
(q-1)(9p-2) ≥ 0
q(9p-2) ≥ 0
получаем, что:
1) p=1,q ≥ 3/14
p=0, q ≤ 3/14
0 ≤ p ≤ 1, q=3/14
2) q=1,p ≥ 2/9
q=0, p ≤ 2/9
0 ≤ q ≤ 1, p=2/9

Цена игры
Ha(2/9;3/14) = -4/7
Hb(2/9;3/14) = 1/3

Ответ:
P* = (2/9;7/9); Q* = (3/14;11/14).
Выигрыш игроков в равновесной ситуации:
f(P*,Q*) = (-4/7;1/3).

Перейти к онлайн решению своей задачи

Требуются авторы студенческих работ!
  • регулярный поток заказов;
  • стабильный доход
Подробнее
Учебно-методический
  • курсы переподготовки и повышения квалификации;
  • вебинары;
  • сертификаты на публикацию методического пособия
Подробнее
Яндекс 360 для бизнеса
  • Бесконечный почтовый ящик;
  • Объем облачного хранилища от 100 Гб;
  • Загрузка больших файлов — от 1 ГБ
  • Поддержка файлов MS Office
  • Трансляции и их планирование в календаре
Подробнее
Курсовые на заказ