Матричные игры

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

Матричная игра и линейное программированиеПравить

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

Рассмотрим две задачи линейного программирования

Задача 1

Найти максимум  

При ограничениях

 

 

Задача 2 (двойственная)

Найти минимум  

При ограничениях

 

 

Известно, что следующие утверждения эквивалентны

1. Матричная игра имеет положительную цену игры

2. Задачи 1 и 2 разрешимы, при этом, если   — цена игры,

  и   — оптимальные решения,

то  

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


Замечание: При   можно прибавить ко всем элементам матрицы (достаточно большую) константу, что не меняет стратегии игроков. Можно, например, найти минимальный элемент (отрицательный) и использовать его абсолютное значение в качестве добавки.

СсылкиПравить

  • Карлин С. Математические методы в теории игр, программировании и экономике М., «Мир», 1964
  • Оуэн Г. Теория игр. М. «Мир», М., 1971