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

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

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

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

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

Задача 1

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

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

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

$y[N] \ge 0[N]$

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

Найти минимум $1^T[N]x[N]$

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

$A^T[N,M]x[M] \ge 1[M]$

$y[N] \ge 0[N]$

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

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]$ будут оптимальными смешанными стратегиями игроков.

Ссылки

1. Карлин С. Математические методы в теории игр, программировании и экономике М., «Мир», 1964

2. Оуэн Г. Теория игр. М. «Мир», М., 1971