16. Геометрический метод нахождения цены игры 2×2 и оптимальных стратегий игрока b.

Для игрока В оптимальная смешанная стратегия находится аналогично, но точка М определяется не самой высокой точкой нижней ломанной, а самой низкой точкой высокой ломанной – полужирная ломанная на рис. 3.2.

Рис. 3.2. Графическая интерпретация игры для игрока В

Найдя координаты точки , как точки пересечения прямых и , компоненты оптимальной смешанной стратегии игрока В и цену игры, ν, можно найти по следующим формулам:

16. Геометрический метод нахождения цены игры 2 n и оптимальных стратегий игрока а

Пусть имеется игра с матрицей

///// матрица ////

Алгоритм «А»

1.Берем горизонтальный отрезок [0,1].

( )

2.Через концы отрезка [0,1] проводим к нему два перпендикуляра: левый и правый.

3.На левом перпендикуляре, лежащем на вертикальной числовой оси, от точки 0 его пересечения с отрезком [0,1] откладываем все элементы первой строки матрицы А.

4.На правом перпендикуляре от точки 1 его пересечения с отрезком [0,1] откладываем все эл-ты второй строки матрицы А.

5.Каждую пару точек, изображающих элементы стоящие в м столбце матрицы А, соединяем отрезком Таким образом, будут построены n отрезков, представляющих собой графики n линейных функций

6.Если все отрезки - неубывающие (имеют неотрицательный наклон): то стратегия доминирует стратегию Если все отрезки - возрастающие (имеют положительный наклон): то стратегия строго доминирует стратегию

7. Если все отрезки - невозрастающие (имеют неположительный наклон): то стратегия доминирует стратегию

Если все отрезки - убывающие (имеют отрицательный наклон): то стратегия строго доминирует стратегию

8.Если отрезок лежит не ниже отрезка то стратегия доминирует стратегию Если отрезок лежит выше отрезка то стратегия строго доминирует стратегию

9.Находим нижнюю огибающую

семейства отрезков

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

10.Находим наивысшие точки нижней огибающей.

11.Абсцисса этой точки (удовлетворяющая равенству

) является вероятностью выбора игроком А чистой стратегии в оптимальной смешанной стратегии .

12.Ордината наивысшей точки нижней огибающей равна цене игры .

13.Верхний из двух концов нижн. огибающей (лежащих на перпендикулярах) есть нижняя цена игры в чист. стратегиях .

14.Нижний из верхних концов отрезков есть верхняя цена игры в чистых стратегиях

15.Элемент матрицы А, изображающая точка которого является нижней на перпендикуляре, где она лежит, и верхним концом отрезка, на котором она лежит, будет седловой точкой игры.

В этом случае чистая стратегия игрока В, номер которой совпадает со вторым индексом седловой точки, является оптимальной.

20. Геометрический метод нахождения цены игры m×2 и оптимальных стратегий игрока b.

(!!! Помним про обозначения вероятностей чистых стратегий через p,q)

Решение игр размера 2xn или nx2 допускает наглядную геометрическую интерпретацию. Такие игры можно решать графически.

1)Дадим геометрическую интерпретацию игры

На плоскости XY по оси абсцисс отложим единичный отрезок A₁A₂ (рисунок 5.1). Каждой точке отрезка поставим в соответствие некоторую смешанную стратегию U = (u₁, u₂). Причем расстояние от некоторой промежуточной точки U до правого конца этого отрезка – это вероятность u₁ выбора стратегии A₁, расстояние до левого конца - вероятность u₂ выбора стратегии A₂. Точка А₁ соответствует чистой стратегии А₁, точка А₂ – чистой стратегии А₂.

В точках А₁ и А₂ восстановим перпендикуляры и будем откладывать на них выигрыши игроков. На первом перпендикуляре (совпадающем с осью OY) покажем выигрыш игрока А при использовании стратегии А₁, на втором – при использовании стратегии A₂. Если игрок А применяет стратегию A₁, то его выигрыш при стратегии B₁ игрока B равен 2, а при стратегии B₂ он равен 5. Числам 2 и 5 на оси OY соответствуют точки B₁ и B₂. Аналогично на втором перпендикуляре найдем точки B^'₁ и B^'₂ (выигрыши 6 и 4).

Соединяя между собой точки B₁ и B^'₁, B₂ и B^'₂, получим две прямые, расстояние от которых до оси OX определяет средний выигрыш при любом сочетании соответствующих стратегий.

Например, расстояние от любой точки отрезка B₁B^'₁ до оси OX определяет средний выигрыш игрока A при любом сочетании стратегий A₁ и A₂ (с вероятностями u₁ и u₂) и стратегии B₁ игрока B.

6. Рисунок 5.1 – Геометрическая интерпретация игры примера 5.3 (нахождение оптимальной стратегии игрока А)

Ординаты точек, принадлежащих ломаной B₁MB^'₂ определяют минимальный выигрыш игрока A при использовании им любых смешанных стратегий. Эта минимальная величина является наибольшей в точке М, следовательно, этой точке соответствует оптимальная стратегия U^* = ( ,  ), а ее ордината равна цене игры v.

Координаты точки M найдем, как координаты точки пересечения прямых B₁B^'₁ и B₂B^'₂.

Для этого необходимо знать уравнения прямых. Составить такие уравнения можно, используя формулу для уравнения прямой, проходящей через две точки:

Составим уравнения прямых для нашей задачи.

Прямая B₁B^'₁:

=     или   y = 4x + 2.

Прямая B₂B^'₂:

=     или   y = -x + 5.

Получим систему:

y = 4x + 2, y = -x + 5.

Решим ее:

4x + 2 = -x + 5, 5x = 3, x = 3/5, y = -3/5 + 5 = 22/5.

Таким образом, U^* = (2/5, 3/5), v = 22/5.

Аналогично решается задача по нахождению оптимальной стратегии игрока B. Разница состоит в том, что находится точка, сводящая к минимуму средний проигрыш, поэтому на рисунке 5.2 рассматривается ломаная A₂MA^'₁.

Рисунок 5.2 – Геометрическая интерпретация игры примера 5.3 (нахождение оптимальной стратегии игрока B)

Найдем координаты точки М.

Прямая A₁A^'₁:

=   ,  откуда  y = 3x + 2.

Прямая A₂A^'₂:

=   ,  откуда  y = -2x + 6,

3x + 2 = -2x + 6, 5x = 4, x = 4/5.

Таким образом,   = 1/5,   = 4/5.