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

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

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

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

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

Задача 1

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

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

A [ M , N ] y [ N ] ≤ 1 [ M ] {displaystyle A[M,N]y[N]leq 1[M]}

y [ N ] ≥ 0 [ N ] {displaystyle y[N]geq 0[N]}

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

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

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

A T [ N , M ] x [ M ] ≥ 1 [ N ] {displaystyle A^{T}[N,M]x[M]geq 1[N]}

x [ M ] ≥ 0 [ M ] {displaystyle x[M]geq 0[M]}

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

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

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

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

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

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

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