Чистые стратегии. Седловая точка

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

Если верхняя и нижняя цены игры совпадают, то общее значение верхней и нижней цены игры а = β = υ называется чистой ценой игры, или ценой игры. Минимаксные стратегии, соответствующие цене игры, являются оптимальными стратегиями, а их совокупность — оптимальным решением, или решением игры. В этом случае игрок А получает максимальный гарантированный (не зависящий от поведения игрока В) выигрыш υ, а игрок В добивается минимального гарантированного (вне зависимости от поведения игрока А) проигрыша υ. Говорят, что решение игры обладает устойчивостью, т.е. если один из игроков придерживается своей оптимальной стратегии, то для другого не может быть выгодным отклониться от своей оптимальной стратегии.

Пара чистых стратегий A_i и B_j дает оптимальное решение игры тогда и только тогда, когда соответствующий ей элемент a_ij является одновременно наибольшим в своем столбце и наименьшим в своей строке. Такая ситуация, если она существует, называется седловой точкой (по аналогии с поверхностью седла, которая искривляется вверх в одном направлении и вниз – в другом).