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

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

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

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

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

Задача 1

Найти максимум $1^{T}[N]y[N]$

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

$A[M,N]y[N]\leq 1[M]$

$y[N]\geq 0[N]$

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

Найти минимум $1^{T}[M]x[M]$

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

$A^{T}[N,M]x[M]\geq 1[N]$

$x[M]\geq 0[M]$

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

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

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

$x[M]$ и $y[N]$ — оптимальные решения,

то $1/v=1^{T}[N]y[N]=1^{T}[M]x[M]$

и $1^{T}[N]y[N]$, $1^{T}[M]x[M]$ будут оптимальными смешанными стратегиями игроков.

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

Ссылки

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