Материалы по курсу (часть 2)

18. Решение игр 2хn

Пусть мы располагаем двумя стратегиями А1, А2, а противник – n стратегиями: В1, В2 …Вn. Матрица || aij || состоит из двух строк и n столбцов. Аналогично случаю двух стратегий дадим задаче геометрическую интерпретацию: n стратегий противника изобразятся n прямыми.

Строим нижнюю границу выигрыша (ломаную В1MN В2) и находим на ней точку N с максимальной ординатой.

Эта точка дает решение игры (стратегию):

ордината точки N равна цене игры, а абсцисса равна частоте р2 стратегии

А2.

В данном случае (см. рисунок) оптимальная стратегия противника получается применением смеси двух «полезных» стратегий: В1 и В4, пересекающихся в точке N.

Стратегия B3 является заведомо невыгодной, а стратегия B1 – невыгодной при оптимальной стратегии А. Если А будет придерживаться своей оптимальной стратегии, то выигрыш не изменится, какой бы из своих «полезных» стратегий ни пользовался В, однако, он изменится, если В перейдет к стратегиям B1 или B3.

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

Пользуясь геометрической интерпретацией, можно дать простой способ решения любой игры 2 n. Непосредственно по чертежу находим пару «полезных» стратегий противника Bj и Bk, пересекающиеся в точке N (если в точке N пересекается более двух стратегий, берем любые две из них). Мы знаем, что если игрок А придерживается своей оптимальной стратегии, то выигрыш не зависит от того, в какой пропорции применяет В свои «полезные» стратегии, следовательно,

1 1 + 2 2 = ;1 1 + 2 2 = .

Из этих уравнений и условия 2 = 1 − 1 , находим 1 и 2 и цену игры v (В методе цена игры обозначается, как ).

Зная стратегию игры, можно сразу определить оптимальную стратегию игрока В:

Для этого решается, например, уравнение:

1 + 1 = , где + = 1

Пример:

Матричная игра 2×n задана следующей матрицей:

Найти: решение игры графическим и аналитическим методом.

Решение:

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

= max min

= min max

Вычисляя, получим:

= max(2,3) = 3= min(7,5,8) = 5

Цена игры [3,5]

Так как < , то игра имеет седловой точки, и поэтому имеет решение в смешанных стратегиях.

Строим графическое изображение игры:

Находим точку оптимума – О. В этой точке пересекаются стратегии

В1 и В2 игрока В. Таким образом, исключая стратегию В3, получаем матричную

игру 2×2 с платежной матрицей вида:

19. Решение игр mx2

В игре mx2 мы имеем две m стратегий (A1, A2, …, Аm), а наш противник 2

стратегии (B1, B2). В игре mx2 всегда имеется решение, содержащее не более двух активных стратегий у каждого из игроков, если эти активные стратегии игроков будут найдены, то игры mx2 превращаются в игры 2x2 (описано в вопросе 18).

Правила решения игр mx2:

1)строится графическое изображение игры;

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

3)определяется пара стратегий, пересекающихся в точке оптимума M. Эти стратегии являются активными стратегиями игрока B. Если в точке оптимума пересекаются более двух стратегий, то в качестве активных стратегий может быть выбрана любая пара из них;

4)решается полученная игра 2x2.

Пример:

Дана матрица стратегий

Решение:

α= 0,5, β= 1,0. Седловой точки нет.

1. Cтроим графическое изображение игры относительно игрока В.

Если А применяет А1, то при использовании игроком В стратегии В1 выигрыш игрока А равен 0,4, а выигрыш А при стратегии В2 равен 1,0, поэтому на перпендикулярах строим такие отрезки. Видно, что стратегия А4 заведомо невыгодная по сравнению со стратегией А3 (выигрыш меньше).

2.Выделяем верхнюю границу выигрыша А3NА1′; точка с наименьшей ординатой – N.

3.В этой точке пересекаются отрезки А1А1′ и А3А3′, соответствующие активным стратегиям А1 и А3. Стратегия А2 не является активной, поэтому из

матрицы исключаем вторую и четвертую строки:

4. решаем игру:

13p3 = 6; p3 = 6/13; p1 = 7/13

q2 = 6/13.

Ответ: γ = 44/65; PA = (7/13; 0; 6/13; 0); QB = (7/13; 6/13). (γ – стоимость игры)

Примечание: Игроку А не выгодно отклоняться от спектра своих активных стратегий.

20. Решение игр mxn.

Для игр m × n геометрическая интерпретация неприменима. Здесь применяются чисто расчетные методы. Можно показать, что решение любой конечной игры m × n может быть сведено к задаче линейного программирования.

Рассмотрим игру m × n. У игрока A имеется m стратегий: A1, A2, ..., Am; у

игрока B есть n стратегий: B1, B2, ..., Bn. Такая игра задается матрицей игры m × n [aij]. Нужно найти две оптимальные смешанные стратегии S*A = (p1, p2, ..., pm)

и S*B = (q1, q2, ..., qn), где p1, p2, ..., pm и q1, q2, ..., qn – вероятности применения

соответствующих чистых стратегий A1, A2, ..., Am и B1, B2, ..., Bn и ∑=1 pi = 1,

∑=1 qj = 1.

Нахождение S*A. Положим, что цена игры γ положительна, γ ≥ 0. Это всегда можно сделать, добавив ко всем членам матрицы игры достаточно большое положительное число М. При этом решение игры не изменится, а

найденную величину γ нужно будет в конце также увеличить на М.

Если мы применяем S*A, а противник – чистую стратегию B j, то наш средний выигрыш будет равен

Так как мы применяем S*A, то наш средний выигрыш не может быть меньше цены игры γ, т. е. a j ≥ γ, j = 1, 2, ..., n, поэтому

(1)

Строки вышеприведенной системы пишутся по столбцам матрицы игры.

Разделим все вышеприведенные неравенства на положительную величину

γ и введем обозначения

Тогда система (1) превращается в следующую:

(2)

Так как p1 + p2 + ... + pm = 1, то

Мы хотим сделать наш гарантированный выигрыш максимально возможным. При этом величина 1/ γ принимает минимальное значение.

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

..., xm, которые удовлетворяли бы линейным ограничениям (2) и обращали бы в минимум линейную функцию

Решив эту задачу линейного программирования, мы можем найти оптимальную стратегию S*A игрока A.

Нахождение SB*. Оптимальная стратегия SB* находится аналогично.

Разница заключается в том, что игрок B стремится не максимизировать, а

минимизировать выигрыш, а значит максимизировать величину 1γ.

Следовательно, вместо условий (2) должны соблюдаться условия