Использование линейной оптимизации при решении матричных игр
Пусть игра 
не имеет оптимального решения в чистых стратегиях, т.е. седловая точка отсутствует 
.
Будем считать, что все элементы платежной матрицы неотрицательны (если это не так, то можно ко всем элементам матрицы добавить некоторое число L, переводящее платежи в область неотрицательных значений - очевидно, при этом цена игры увеличится на L, а решение задачи не изменится). Таким образом, предполагаем, что 
>0.
Будем искать решение игры в смешанных стратегиях:
; 
Применение игроком I оптимальной смешанной стратегии 
гарантирует ему, независимо от поведения игрока II, выигрыш, не меньший цены игры 
.
Пусть игрок II применяет свою активную чистую j-ю стратегию, а игрок I - свою оптимальную стратегию . Тогда средний выигрыш игрока I будет равен
Учитывая, что 
не может быть меньше , запишем условия:
|
Разделив левую и правую части каждого из неравенств (4.4) на цену игры >0, получим:
(4.5)
При использовании обозначений
(4.6)
неравенства (4.5) примут вид:
|
где, очевидно, все 
, так как 
.
Из равенства 
и в силу определения (4.6) следует, что переменные (
) удовлетворяют условию
Учитывая, что игрок I стремится максимизировать , получаем линейную функцию
(4.8)
Таким образом, задача решения игры свелась к следующей задаче линейной оптимизации: найти неотрицательные значения переменных 
минимизирующие линейную функцию (4.8) и удовлетворяющие ограничениям (4.7).
Из решения задачи линейной оптимизации легко найти цену игры и оптимальную стратегию
игрока I:
В свою очередь, оптимальная стратегия игрока II 
может быть найдена из выражения
где 
- неотрицательные переменные задачи линейной оптимизации:
,
которая является двойственной по отношению к задаче, представленной условиями (4.7) и (4.8).
В этой системе неравенств переменные 
Таким образом, оптимальные стратегии 
и игры с платежной матрицей 
(
) могут быть найдены путем решения симметричной пары двойственных задач линейной оптимизации.
| Исходная задача | Двойственная задача | |
| 
|
Цена игры и вероятности применения стратегий игроками I и II равны:
Еще по теме Использование линейной оптимизации при решении матричных игр:
- Решение матричных игр в смешанных стратегиях с помощью Excel
- Использование информационных технологий при решении задач нелинейной оптимизации
- Решение парных матричных игр с нулевой суммой.
- Матричный метод решения систем линейных уравнений.
- Лекция 4. Использование оптимизационных моделей при принятии решений
- Линейные модели оптимизации в управлении
- 5.7. Использование власти при принятии стратегических решений
- в главе анализируется проблема решения задачи обеспечения навигационной информацией БКУ НКА с использованием сигналов создаваемых спутниковыми радионавигационными системами. Проводится сравнение навигационных полей от двух глобальных СРНС GPS (США) и не полностью развернутой СРНС ГЛОНАСС (Россия). Анализируется структура НБО при использовании спутниковой радионавигации. Формулируется задача обработки измерений от навигационного приемника при возникновении перерывов в их поступлении.
- Лекция 7. Информационные технологии решения задач векторной оптимизации
- Теория игр в контексте теории принятия решений
- Теория игр и принятия решений
- Оценка риска с помощью дерева решений (позиционных игр)
- 1.7. Решение систем нелинейных уравнений и задач оптимизации
- Теория игр и принятие решений., 2017
- Краткий обзор методов решения задачи векторной оптимизации
- Решение произвольных систем линейных уравнений.
- 7.3. Графическое решение задачи линейного программирования
- Оптимизация режимов ротационной обработки цапф мельниц с использованием приставного станка
- Тема 4 Решение систем линейных уравнений.