Оптимизация ресурсов, Пример 3. Матричная игра.

Матричная игра.

Типичный пример - борьба за рынок сбыта, где существенна повторяемость действий участников. Игрок 1 имеет N способов действий-стратегий, а игрок 2 - M стратегий. При выборе первым игроком I-й стратегии, а вторым игроком К-й стратегии первый игрок получает известный выигрыш A(I,K), а второй столько же проигрывает. Полный набор выигрышей называется платежной матрицей А. Выбор первым игроком стратегии наибольшего выигрыша может быть парирован вторым игроком.

Считается практически оправданной стратегия гарантированного выигрыша. Она максимизирует выигрыш, минимальный по всем стратегиям 2-го игрока, то есть выбирается лучший вариант при самых неблагоприятных действиях противника. Хорошо, если и 2-й игрок, поступая аналогично, выберет то же самое сочетание стратегий. Это будет устойчивым решением игры, так называемой седловой точкой. Однако, практически считается разумным вносить элемент случайности, выбирая различные (так называемые смешанные) стратегии и используя тот же критерий. То есть, если X(I) -вероятность выбора I-й стратегии, то ищется максимум наименьшей из сумм SA(K)= A(1,K)*X(1)+...A(I,K)*X(I)+...A(N,K)*X(N), K=1,...M. Дж. Нейман доказал фундаментальную теорему о том, что у любой матричной игры (при любой матрице А) существует устойчивое решение (седловая точка) в смешанных стратегиях.

Формулировка матричной игры для ее решения методами оптимизации имеет следующий вид: вводим переменную X(N+1)<=SA(K) и максимизируем ее при очевидных ограничениях на вероятность, - диапазон от 0 до 1 и сумма вероятностей равна 1: 0<=X(I)<=1 и X(1)+...X(N)=SX=1. То есть, находим искомые вероятности по равенству SX=1, которое в расчетах фигурирует в виде двух неравенств SX>=1-e, SX<=1, гдет е - достаточно малое число, и по М неравенствам с N+1 переменной каждое, коэффициентами которых являются элементы А(I,K) платежной матрицы.

Иллюстрация. Два конкурирующих бизнесмена имеют торговые точки. В борьбе за рынок они могут увеличить количество точек (стратегия 1), перейти на круглосуточную торговлю (стратегия 2) или расширить ассортимент (стратегия 3). Платежная матрица А имеет следующий вид:

10 4 1
8 5 17
-3 2 11

Позиции 1-го игрока сильнее, поэтому он почти всегда выигрывает, но размер выигрыша зависит от решений его и конкурента. Например, если он переходит на круглосуточную торговлю, а конкурент на расширение ассортимента, то его выигрыш максимален и равен 17. Эта платежная матрица имеет седловую точку в чистых стратегиях. Нетрудно проверить, что это 2-я стратегия для обоих игроков. Выигрыш равен 5.
----------
Результаты расчетов

*** Оптимизация ресурсов. optim.dat ***

переменных 4

ограничений 5

функций 1

** Значение 1-й функции: 5

*** переменные и ограничения***

стратегия 1 **1 0 **5 0

стратегия 2 **2 1 **6 0.000100017

стратегия 3 **3 0 **7 3 **4 5 **8 0 **9 12

Действительно, вероятность второй стратегии 1, а остальных 0.