Решение игры в чистых стратегиях. Игры с седловой точкой

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

Стратегия выбираемая игроком сознательно исходя из анализа сложившейся обстановки называется личной (или чистой).

Стратегия игрока называется оптимальной, еслиона обеспечивает данному игроку (обычно игроку А) при многократном повторении игры максимально возможный средний выигрыш или минимально возможный средний проигрыш независимо от поведения противника (могут быть использованы и другие показатели оптимальности).

Партия игры – это однократная возможная реализация правил игры (стратегий) игроками.

Матричной игрой называется парная игра, осуществляемая по следующим

правилам:

1. В игре участвуют два игрока - А и В;

2. Каждый из игроков обладает конечным набором стратегий (для игрока А - это стратегии А₁, А₂, …..А_m, а для игрока В - это стратегии В₁,В₂,…….В_n);

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

5. И выигрыш, и проигрыш выражаются числами а_ij,которые являютсяэлементами, так называемой платежной матрицы. В частности, выигрыш для игрока А при выборе стратегии А_i, и игроком В – стратегии В_j равен а_ij, а для игрока В – он равен в_ij =-а_ij, то есть является проигрышем.

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

Если условие в_ij =-а_ij не выполняется, то есть каждый из игроков имеет свою платежную матрице, тогдаэтапарная игра является игрой с ненулевой суммой и называется биматричной игрой.

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

Решение игры связано с матрицей (а_ij) и следующими понятиями:

Нижняя цена игры α=max_imin_j а_ij (сначала находится минимум в каждой строке, а

потом из полученных минимумов находится максимум). Это гарантированный выигрыш игрока А при любой стратегии игрока В.

Верхняя цена игры β=min_jmax_i а_ij (сначала находится максимум в каждом столбце,

а потом из полученных максимумов находится минимум). Это гарантированный проигрыш игрока В при любой стратегии игрока А.

Очевидно α<= β. В случае α=β говорят о цене игры ν=α=β. Соответствующие цене игры стратегии являются оптимальными, а сама игра есть игра с седловой точкой.

В случае, когда α<β седловой точки не существует. В этом случаерешение игры ищестся в смешанных стратегиях. Доказано (Дж. Фон Нейман), что конечная матричная игра имеет, по крайней мере, одно оптимальное решение, возможно в смешанных стратегиях.