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

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

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

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

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

Задача 1

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

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

$\text{[math]}$ $\text{[math]}$ $A[M,N]y[N]\leq 1[M]$

$\text{[math]}$ $\text{[math]}$ $y[N]\geq 0[N]$

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

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

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

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

$\text{[math]}$ $\text{[math]}$ $x[M]\geq 0[M]$

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

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

2. Задачи 1 и 2 разрешимы, при этом, если $\text{[math]}$ $\text{[math]}$ $v$ — цена игры,

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

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

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

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

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

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