Седловая точка

Седловая точка – это пара оптимальных стратегий (Ai, Bj). В этом случае число a=b называется (чистой) ценой игры (нижняя и верхняя цена игры совпадают). Это означает, что матрица содержит такой элемент, который является минимальным в своей строке и одновременно максимальным в своем столбце.

Пример №1. Найдите седловую точку и чистую цену в игре двух участников с нулевой суммой, в которой платежная матрица второго игрока имеет вид.

Решение. Проверяем, имеет ли платежная матрица седловую точку. Если да, то выписываем решение игры в чистых стратегиях.

Игроки B1 B2 B3 B4 a = min(Ai)
A1 8 7 0 6 0
A2 6 8 5 10 5
b = max(Bi ) 8 8 5 10 0
Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = (0,5,0) = 5, которая указывает на максимальную чистую стратегию A2.
Верхняя цена игры b = min(bj) = (8,8,5,10) = 5.
Седловая точка (2, 3) указывает решение на пару альтернатив (A2,B3). Цена игры равна 5.
Размерность платежной матрицы x

Пример №2. Игрок 1 выбирает число х из множества Х=[0; 1], игрок 2 выбирает число y из множества Y=[0; 1]. После этого игрок 2 платит игроку 1 сумму F(x,y)=2x2-y2. Имеет ли игра седловую точку?
Решение. Поскольку игрок 2 хочет минимизировать выигрыш игрока 1, то он определяет , то есть при этом y =1. Игрок 1 желает максимизировать свой выигрыш, и поэтому определяет , который достигается при х = 1.
Итак, нижняя цена игры равна α = 1. Верхняя цена игры , то есть в этой игре α=β= 1. Поэтому цена игры v = 1, а седловая точка – (1;1).

загрузка...