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

Если матрица игры содержит седловую точку, то ее решение находится по принципу минимакса (матричная игра решается в чистых стратегиях). Если же платежная матрица не имеет седловой точки, т. е. a < b, то решением для каждого игрока будет сложная стратегия, состоящая в случайном применении им двух и более чистых стратегий.

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

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

Смешанной стратегией игрока А называется вектор (p ₁; p ₂; …, p_m), где p_i – вероятность, с которой игрок A выбирает свою чистую стратегию A_i. Компоненты вектора р удовлетворяют условиям: .

Смешанной стратегией игрока B называют вектор , где q_i – вероятность применения игроком B его чистой стратегии B_j. При этом .

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

Ценой игры g при решении в смешанных стратегиях называется величина среднего выигрыша игрока A (среднего проигрыша B), приходящегося на одну партию. Стратегии игроков, входящие в их оптимальные смешанные стратегии, называются активными.

Можно показать, что цена игры всегда удовлетворяет условию:

.

Следовательно, если каждый игрок придерживается своих смешанных стратегий при многократном повторении игры, то он получает более выгодный для себя результат, чем применяя “перестраховочные” стратегии, соответствующие a и b. Каждый из игроков не заинтересован в отходе от своей оптимальной стратегии, так как ему это невыгодно.