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

Пусть мы имеем игру с платежной матрицей

В₁ … В_m

.

Если -цена игры, то, обозначая х₁,…, х_n вероятности применения первым игроком стратегий А₁,…,А_n, получим систему уравнений, каждое из которых соответствует применению вторым игроком чистых стратегий В₁,…, В_m:

(1)

Будем считать, что ( в противном случае можно прибавить ко всем коэффициентам платежной матрицы одинаковое число С, что приведет к увеличению на С цены игры, но не изменит оптимальные стратегии игроков)

Разделим каждое из неравенств системы на и обозначим . Получим систему неравенств

(2)

Кроме того,

(3)

Так как , то . Так как первый игрок должен максимизировать цену игры, то ему нужно минимизировать величину .

Поэтому критерий качества для первого игрока имеет вид

f= (4)

Таким образом, игра свелась к задаче линейного программирования : минимизировать критерий качества (4) при ограничениях (2) и (3).

61