Действия игрока В

1-й шаг. В каждом столбце матрицы А ищется максимальный элемент b_k = max a_ik, k=1,2,…,n

Полученные числа b₁,b₂,…,b_n приписываются к заданной таблице в виде нижней добавочной строки

2-й шаг. Среди чисел b₁,b₂,…,b_n выбирается минимальное, т.е. b=minb_k

Если игрок В придерживается стратегии, выбранной описанным выше способом, то при любом поведении игрока А игроку В гарантирован проигрыш, не больший b.

Число b называется верхней ценой игры.

Принцип построения стратегии игрока В, основанный на минимизации максимальных потерь, называется принципом минимакса, а выбираемая в соответствии с этим принципом стратегия – минимаксной стратегией игрока В.

Нижняя цена и верхняя всегда связаны равенством a≤b.

Пример: Рассмотрим 3´3 игру, заданную матрицей

А =

Применив предложенный алгоритм, получим:

a = -2, соответствующая стратегия А₂

b = 2, соответствующая стратегия В₂

Если a = b, или подробнее, max min a_ik = min max a_ik,

то ситуация {A_i, B_k} оказывается равновесной, и ни один из игроков не заинтересован в том, чтобы ее нарушить.

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

Цена игры совпадает с элементом a_ik матрицы игры, расположенным на пересечении i-той строки (стратегия A_i игрока А) и k-го столбца (стратегия B_k игрока В) – минимальным в своей строке и максимальным в своём столбце.

Этот элемент называют седловой точкой матрицы игры, или точкой равновесия, а про игру говорят, что она имеет седловую т очку.

Стратегии А_i и В_k соответствующие этой седловой точке, называются оптимальными, а совокупность оптимальных ситуаций и цена игры – решением матричной игры с седловой точкой.

Пока игроки придерживаются этих стратегий, средний выигрыш равен 1 (-2<1<2).

Однако если игроку В станет известно, что игрок А придерживается стратегии А₂, он немедленно ответит стратегией В₁ и сведёт его выигрыш к проигрышу – 2. В свою очередь, на стратегию В₁ у игрока А есть стратегия А₁, дающая ему выигрыш 4.

Для построения решений 2´n и m´2 игр существует эффективный метод, основанный на простых геометрических соображениях. Этот метод называют графическим. Рассмотрим его на примере:

Пример: Дана 2´6 игра, заданная матрицей

Решение: Составляем таблицу вида:

, где р – оптимальное значение.

На основе таблицы составим уравнения, графиками которых будут прямые:

(1): w = 6р – 2(1 – р),

(2): w = 4р – (1 – р),

(3): w = 3р + 5(1 – р),

(4): w = р,

(5): w = -р + 5(1 – р),

(6): w = 4(1 – р).

т. С является наивысшей точкой огибающей, точкой пересечения прямых (5) и (4), т.е.

Тем самым цена игры u=, а оптимальная стратегия

р = {p, 1- p} = {; }.