Меню Главная Случайная статья Настройки Матричные игры Материал из https://ru.wikipedia.org Матричные игры представляют собой математические модели конфликтных ситуаций, в которых стороны конфликта (игроки) обладают конечным или бесконечным количеством стратегий (способов действия). Простейшим случаем является игра двух лиц с нулевой суммой, имеющих конечное число стратегий. В этом случае выигрыш одного игрока равен проигрышу другого, т. е. сумма выигрышей игроков равна нулю. Выигрыш определяется матрицей игры (матрицей платежей), она же является Нормальной формой игры. В общем случае в игре участвует любое количество сторон, а игра имеет произвольную сумму. При этом игроки могут образовывать коалиции с целью увеличения своего выигрыша. Матричная игра и линейное программирование Пусть матричная игра задана множеством стратегий первого игрока ${\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