Решение игр без седловых точек

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

Применение минимаксных стратегий каждым из игроков обеспечивает первому выигрыш не меньше α, а 2^ому проигрыш не больше β. Учитывая, что α < β, естественно, что для игрока I желание увеличить выигрыш, а для игрока II – уменьшить проигрыш. Поиск такого решения приводит к применению сложной стратегии, состоящей в случайном применении 2^х и более чистых стратегий с определенными вероятностями. Такая сложная стратегия называется смешанной. Смешанные стратегии – это применение чистых стратегий с вероятностями. Смешанные стратегии игроков будем обозначать соответственно p_A=(p₁,p₂,…,p_m) и q_B=(q₁,q₂,…,q_n) где p_i, q_j ≥ 0 – вероятности применения чистых стратегий A_i и

M m

B_j при этом ∑ p_i=1, ∑q_j=1.

i=1 i=1

В основной теореме теории игр (Джон фон Нейман) утверждается, что " конечная игра 2^х лиц с нулевой суммой имеет, по крайней мере, одно решение, возможно, в смешанных стратегиях. Таким образом, из основной теоремы следует, что каждая конечная игра имеет цену.

Обозначим ее так же, как чистую цену игры через γ. Цена игры γ – средний выигрыш, приходящийся на одну партию, - всегда удовлетворяет условию α ≤ γ ≤ β, т.е. лежит между нижней ценой игры α и верхней ценой игры β. Следовательно, каждый игрок при многократном повторении игры, придерживаясь смешанных стратегий, получает более выгодный для себя результат.

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

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