Биматричная игра

Математической моделью конфликтов с двумя участниками являются биматричные игры. Такая игра 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.

Дано:

Биматрица

2

2

8

7

6

6

9

1

Нанесем на плоскость элементы биматрицы и начертим выпуклую оболочку.

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

Где красным и зеленым цветом обозначено множество оптимальности по Парето, а зеленым – та его часть, которая является переговорным множеством. 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=x2                 2*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

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

Пример. Найдите решения биматричной игры.
Решение:xml

загрузка...