WikiSort.ru - Не сортированное

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

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

Пусть матричная игра задана множеством стратегий первого игрока ${\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

Для улучшения этой статьи желательно: Проверить достоверность указанной в статье информации.