Глава 3. Решение игр в смешанных стратегиях

Минимумы строк

Максимумы столбцов

⇐ ПредыдущаяСтр 4 из 7Следующая ⇒

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

В игре, матрица которой имеет размерность , стратегии первого игрока задаются наборами вероятностей ( частот ) , с которыми игрок применяет свои чистые стратегии. Аналогично для второго игрока наборы вероятностей определяют n-мерные векторы . При этом суммы вероятностей для каждого игрока равны 1.

Основная теорема теории игр Дж. Фон Неймана. Каждая конечная игра имеет по крайней мере одно оптимальное решение в смешанных стратегиях.

3.1. Геометрическое решение игр 2´ 2, 2´ n, m´ 2

3.1.1. Геометрическое решение игры 2´ 2

Решение игры в смешанных стратегиях допускает графическую интерпретацию, и, следовательно, решение задачи можно показать графически.

Пусть имеем игру 2´ 2 с платежной матрицей , в которой первая строка.соответствует чистой стратегии игрока А, а вторая – его чистой стратегии .

Графический метод решения игры включает следующие этапы:

Этап 1. В декартовой системе координат pOH по оси абсцисс откладывается отрезок, длина которого равна 1. Левый конец отрезка (точка р=0) соответствует стратегии , правый – стратегии (р=1). Промежуточные точки оси абсцисс соответствуют вероятностям некоторых смешанных стратегий .

Этап 2. На левой оси – оси ординат, откладываются выигрыши стратегии .

Этап 3. На линии, параллельной оси ординат, из точки 1 откладываются выигрыши стратегии (рис. 1).

Рис. 1. Графический метод решения игры (2 2)

Этап 4. Соединяем точки прямой , точки прямой .

Интерпретация результатов

Ломаная – это нижняя граница выигрыша, получаемого игроком А. В точке N выигрыш максимален и составляет (цена игры).

Ордината точки N определяет цену игры , а ее абсцисса – вероятность (частоту) применения игроком А чистой стратегии . Вероятность (частоту) применения игроком А чистой стратегии можно найти из условия ( ).

Замечания .

1. Для определения оптимальной смешанной стратегии игрока В, чистым стратегиям которого соответствуют столбцы матрицы А, необходимо найти отношение, в котором проекция точки N на ось OH делит отрезок .

2. При решении игровых задач графическим методом значения , и можно найти приблизительно по рисунку. Для уточнения и проверки результатов можно дополнительно решить системы[5]:

для первого игрока

для второго игрока

или воспользоваться готовыми формулами для нахождения оптимальных значений , и :

Пример

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

Игроки
	0, 3	0, 8
	0, 7	0, 4

Решение:

Игра не имеет седловой точки, т.к.

Игроки			Минимумы строк
	0, 3	0, 8	0, 3
	0, 7	0, 4	0, 4
Максимумы столбцов	0, 7	0, 8

Следовательно, игра не разрешима в чистых стратегиях.

Решим задачу графическим методом (рис. 2).

Выводы:

Коммерческое предприятие получит гарантированный средний выигрыш 0, 55 усл. ед., если будет использовать технологию продажи с вероятностью 0, 375, а технологию с вероятностью 0, 625 (или в отношении примерно 4: 6).

Из рисунка можно найти также смешанную стратегию для второго игрока (старая технология с двумя стратегиями и ). Рассмотреть самостоятельно.

Рис. 2. Графическое решение примера

3.1.2. Геометрическое решение игры 2´ n

Рассмотрим конечную матричную игру с платежной матрицей D:

Игрок А обладает двумя стратегиями: и , а игрок В – n стратегиями: , , …, . Условимся, что игра не имеет Седловой точки, поэтому решение будем искать в смешанных стратегиях. Необходимо найти смешанные стратегии игроков:

и

и цену игры , считая, что , (см. таблицу).

Игроки ….

….

….

….

Решение проводят с позиций игрока А, у которого две стратегии.

Решение игры включает следующие этапы:

1. В декартовой системе координат pOH по оси абсцисс (Ор) строим единичный отрезок. Левый конец отрезка (р=0) соответствует стратегии , правый (р=1) – стратегии . Промежуточные точки отрезка соответствуют вероятностям некоторых смешанных стратегий .

2. На оси ординат (OH) откладываются выигрыши при стратегии – (j=1, …, n). На линии, параллельной оси ординат, из точки 1 откладываются выигрыши при стратегии – (j=1, …, n).

3. Каждую пару точек, соответствующих элементам и (j=1, …, n), стоящим в j-м столбце матрицы D, соединяем отрезком .

4. Находим нижнюю огибающую семейства отрезков (ломаная линия, выпуклая вверх). Она соответствует наихудшим ситуациям для игрока А или нижней границе цены игры.

5. На нижней огибающей находим наибольшую (наивысшую) точку. Она соответствует максиминной стратегии игрока А.

6. Абсцисса этой точки есть вероятность выбора игроком А второй стратегии в оптимальной смешанной стратегии – , тогда .

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

Пример

В ходе деловой игры возникла конфликтная ситуация двух юридических лиц. У одного из них имеется две стратегии, у другого – шесть. Платежная матрица имеет вид:

Определить оптимальные смешанные стратегии игроков и цену игры.

Решение:

Данная ситуация представляет собой матричную игру порядка .

1. Исключим из платежной матрицы заведомо невыгодные стратегии:

Игроки

Стратегия является заведомо невыгодной[6] для игрока В (по сравнению, например, со стратегией , которую доминирует) и ее можно отбросить[7]. Тогда матрица будет иметь следующий вид:

Игроки

2. Определим наличие (отсутствие) седловой точки в игре:

Так как , то в игре нет седловой точки. Значит, ищем решение игры в смешанных стратегиях:

и .

При этом , т.к. стратегию исключили из рассмотрения.

3. Строим график в системе координат pOH в соответствии с описанной выше последовательностью этапов (рис.1).

Рис.1. Графическое решение примера

⇐ Предыдущая 1 2 345 6 7 Следующая ⇒