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

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

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

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

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

Задача 1

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

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

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

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

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

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

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

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

$x[M]\ge 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