Решение и геометрическая интерпретация игр


Игра является наиболее простым случаем конечных игр. В этой игре каждый игрок имеет только две стратегии. В случае, если игрок имеет седловую точку, то его решение очевидно. Рассмотрим случай, когда игра не имеет седловой точки, т.е. . Требуется найти оптимальные стратегии игроков и и цену игры .
Т.к. в игре нет седловой точки, то обе стратегии игроков являются активными. В соответствии с теоремой об активных стратегиях, если 1 игрок будет применять свою оптимальную стратегию, то, независимо о действий второго игрока, его выигрыш будет цены игры . Пусть . Если 2-ой игрок применяет стратегию , то выигрыш первого игрока определяется из уравнения

Если 2 применяет , то выигрыш 1

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

В системе координат на оси абсцисс отложим от начала координат отрезок длинной равной единице.

Левый конец отрезка соответствует стратегии , а правый (x = 1) – стратегии . Все промежуточные точки отрезка будут изображать смешанные стратегии игрока. Длина отрезка равна вероятности стратегии . Длина равна стратегии . Через и проведем два перпендикуляра к оси абсцисс – ось I-I и ось II-II. На I-I будем откладывать выигрыш при стратегии , а на II-II – при . Если игрок 2 применит стратегию , то при выигрыш равен , а при равен . Отложим эти точки на осях I-I и II-II и обозначим их . , что соответствует одноименной стратегии 2-го игрока. Любой смешанной стратегии соответствует выигрыш, величина которого равна абсциссе точки М на прямой . Эту прямую будем называть стратегией . Аналогично можно построить стратегию . Задача состоит в определении оптимальной стратегии , при которой наш минимальный выигрыш обращался бы в максимум. Построим нижнюю границу выигрыши при стратегиях , т.е. ломанную . На этой ломанной будет лежать минимальный выигрыш A при любой смешанной стратегии. В точке М имеем максимальную цену игры . Если игра имеет седловую точку, то соответствующий график показан на рис. 2:


рис. 2

Здесь нижняя граница совпадает с отрезком . Возможна так же ситуация показанная на рис. 3:


рис. 3

Здесь оптимальная чистая стратегия .
Пример: Имеется игра

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



Решение 2 х m и n x 2
В играх порядка 2 первый игрок имеет две стратегии, а второй – m стратегий. Платежная матрица имеет вид

Причем у нее нет седловых точек.
Необходимо найти такие смешанные стратегии и и цену игры , которые удовлетворяют соотношениям






Что означают неравенства (1) и (2). Пусть игрок 1 применяет свою оптимальную стратегию , а его противник применяет чистую стратегию . Т.к. это цена игры, то она определяет нижний придел выигрыша при любых стратегиях второго игрока, в том числе смешанных. Аналогично можно объяснить неравенство (2) – верхний предел проигрыша 2-го игрока.
Не доказывая, отметим, что любая конечная игра имеет решение, в котором число активных стратегий каждого игрока не превосходит .Следовательно, у игры 2 или всегда имеется решение, содержащее не более двух активных стратегий у каждого из игроков. Если найти эти активные стратегии игроков, то игра или превращается в игру . Решение таких игр мы рассматривали.
Введем обозначение для левой части неравенств (1)
,
где – средний выигрыш первого игрока при условии, что он применяет свою смешанную стратегию, а второй – свою j чистую стратегию. Каждому значению соответствует прямая линия прямоугольной системы координат.
Цель второго игрока минимизировать выигрыш первого за счет своих альтернатив. Поэтому 2 игрок должен определить такие j, которые обеспечивают

где – нижняя граница множества ограничений (показана жирной линий).



Цель первого игрока максимизировать свой выигрыш за счет выбора , т.е. вычислить

В результате определяется оптимальная стратегия первого игрока и пара альтернативных стратегий 2 игрока, которые при пересечение образуют точку . В нашем случае это и . В результате мы свели задачу размерности , к задаче с платежной матрицей
Решая полученную игру найдем и .
Пример: Выбор с/х культуры. С/х предприятие имеет возможность выращивать две культуры. Прибыль от реализации выращенной культуры зависит от объема полученного урожая. Урожай первой культуры выше при сухо погоде, а второй – при более влажной. В летний период можно рассматривать следующие стратегии погоды:
  1. Лето жаркое сухое
  2. Лето жаркое влажное
  3. Лето теплое влажное
  4. Лето теплое сухое
  5. Лето прохладное сухое
  6. Лето прохладное влажное
Стратегии предприятия
  1. Выращивать первую культуру
  2. Выращивать вторую культуру
Предприятие 1 игрок Погода 2 игрок Расчеты прибыли предприятия в млн. руб. в зависимости от состояния погоды представлены в виде платежной матрицы

Определить оптимальные стратегии поведения с/х предприятия. В этой игре нет седловой точки. Будем использовать графический метод. – вероятность применения первым игроком стратегии – смешанная стратегия погоды. Средний выигрыш первого игрока.

Эти зависимости показаны на графике.



Активными стратегиями “погоды” является 4-ая и 6-ая. Поэтому решение игры сводится к решению следующей системы уравнений

Решение: , , , .

Решение игр m x n


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

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

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

Hosted by uCoz