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

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

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

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

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

Задача 1

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

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

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

${\displaystyle y[N]\geq 0[N]}$

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

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

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

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

${\displaystyle x[M]\geq 0[M]}$

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

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

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

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

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

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

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

Ссылки

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