Приведение матричной игры к задаче линейного программирования

Нахождение решения игры в смешанных стратегиях сводится к решению задачи линейного программирования, точнее говоря к решению пары взаимосопряженных задач.

Пусть А - платежная матрица игры размерности , т.е.

Так как в смешанных стратегиях всегда существует оптимальная стратегия первого игрока и цена игры, то для нее должно выполняться неравенство

(4)

Это означает, что при любой чистой стратегии 2-го игрока (т.е. любого столбца матрицы ) его проигрыш будет не меньше цены игры (т.е. максимина). Предположим для определенности, что Введем обозначение

тогда условие (справедливое для вектора вероятностного распределения) можно переписать в виде Разделив обе части неравенства (4) на , получаем

Поскольку целью 1-го игрока является максимизация величины , т.е. минимизация величины , то нахождение его оптимальной смешанной стратегии сводится к решению следующей задачи линейного программирования:

при ограничениях:

Находя решение этой задачи, переходим к решению по формулам

Рассуждая совершенно аналогично получим, что задача нахождения оптимальной смешанной стратегии 2-го игрока сводится к нахождению вектора являющегося решением следующей задачи линейного программирования:

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

Находя решение этой задачи, переходим к решению по формулам

Пример 4 Для матрицы из предыдущего примера имеем следующие задачи. Для 1-го игрока

при ограничениях:

Для второго игрока

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

 

Как следует из симплекс-метода, легче решить задачу для 2-го игрока. Для этого даже не потребуется введения искусственных переменных. За исходный базис можно принять дополнительные переменные, необходимые для перехода к канонической форме задачи. Опуская расчеты, приведем последнюю симплекс-таблицу, которая получена на четвертом шаге.

 

Базис
		-1/10			13/50	-3/25	-1/10	0,04
		61/5 0			-3/250	18/125	1/50	0,152
		27/50			21/250	1/125	7/50	0,064
		33/50			41/250	4/125	3/50	0,256

 

Таким образом , при том, что Отсюда

Проверив, что убеждаемся в правильности полученного ответа.

Из этой же таблицы находим решение двойственной задачи. Получаем, что

при том же Отсюда получаем

и

Таким образом, смешанные оптимальные стратегии 1-го игрока U* и 2-го игрока Z найдены, также как и цена игры v.

 

Игра с природой

 

Кроме антогонистических рассматривают так называемые неантогонистические игры. В этом случае предполагают, что действия противника не носят характер строгого противостояния. Его интересы могут быть разными и в общем случае не совпадающими с нашими, однако они не являются «злонамеренно» направленными против нас. Простейшим примером такой ситуации является следующая.

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

Пусть торговое предприятие имеет т стратегий: и имеется n возможных состояний природы: . Так как природа не является заинтересованной стороной, исход любого сочетания поведения сторон можно оценить выигрышем первой стороны для каждой пары стратегий и . Все показатели игры заданы платежной матрицей размерности

По платежной матрице можно принять ряд решений. Например, оценить возможные исходы: минимальный выигрыш

т.е. наименьшая из величин в каждой -й строке как пессимистическая оценка; максимальный выигрыш – то наилучшее, что дает выбор -го варианта

При анализе «игры с природой» вводится показатель, по которому оценивают, насколько то или иное состояние «природы» влияет на исход ситуации. Этот показатель называют риском.

Риск при пользовании стратегией и состоянии «природы» оценивается разностью между максимально возможным выигрышем при данном состоянии «природы» и выигрышем при выбранной стратегии :

Исходя из этого определения можно оценить максимальный риск каждого решения:

Решения могут приниматься по результатам анализа ряда критериев.