Платежная матрица. Нижняя и верхняя цена игры

Теория игр - это математическая теория конфликтных ситуаций. Математическая модель конфликтной ситуации называется игрой. Конфликтная ситуация возникает тогда, когда ее участники (игроки) имеют противоположные интересы.

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

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

Задача первого игрока – максимизировать свой выигрыш. Задача второго игрока – минимизировать свой проигрыш.

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

В общем случае парную игру с нулевой суммой можно записать платежной матрицей

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

.

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

.

Величина - гарантированный выигрыш, который может обеспечить себе первый игрок, - называется нижней ценой игры.

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

,

где – верхняя цена игры.

Для матричной игры справедливо неравенство .

Если , то такая игра называется игрой с седловой точкой, а пара оптимальных стратегий – седловой точкой матрицы. В этом случае элемент , называемый ценой игры, является минимальным в -й строке и максимальным в j-м столбце.

Рассмотренные оптимальные стратегии первого и второго игроков называются соответственно максиминными и минимаксными.

Пример 1.Решить игру, заданную матрицей

А=.

Решение.Находим нижнюю и верхнюю цены игры

Так как матрица Н имеет седловую точку , то цена игры равна 0, при этом первый игрок должен выбрать третью строку, а второй игрок должен выбрать третий столбец. Отклонение от указанной стратегии приводит к уменьшению выигрыша первого игрока или к увеличению проигрыша второго игрока.