Игра задается матрицей
а12 • alj • а1п
а22 • a2j • а2п
ai2 . а у . ain
"a m2 • а mj • а mn
Здесь
ay - платежи столбцевого игрока при выборе им j - й стратегии строчному, если последний выбирает i-ю стратегию; ац > 0 - столбцевой игрок платит строчному; ац < 0 - строчный игрок платит столбцевому; ау = 0 - никто никому не платит.
Для выбора оптимальной стратегии строчный игрок сначала в каждой строке выбирает минимальный элемент. За оптимальную стратегию он выбирает ту, для которой СИ наибольшее
а = max а;.
а - нижняя цена игры.
Аналогично столбцевой игрок сначала в каждом столбце выбирает наибольшее число
|3j= maxaij
и оптимальную стратегию выбирает по
P=min|3j,
где Р - верхняя цена игры. Всегда ос < (3.
Если а = |3, то игра называется игрой с седловой точкой. Элемент, для которого aik= а = Р, называется седловым элементом.
Не всякая игра имеет седловую точку. Но если седловая точка имеется, то стратегии игроков определяются однозначно. Разработаны методы определения оптимальных стратегий и для игр, не имеющих седловых точек.
Пример 7.1. Найти седловую точку в матричной игре.
|
-51 |
31 -Г |
|
-2 -5 |
-62 -4 |
|
4 4 |
6 [3] 5 |
|
-6 3 |
-1 -3 6 |
Находим нижнею цену игры
ol =min(-5, 1, 3, 1,-1) = -а = min( - 2, - 5, - 6, 2, - 4) = a =min( 4, 4, 6, 3, 5) = 3, а =min(-6, 3,-1,-3, 6) = -
а = max(-5,-6,3,-6)=3
Находим верхнюю цену игры
Р1 =тах(-5,-2, Р2=тах( 1,-5, Р =тах( 3,-6, р4=тах( 1, 2, Р =тах(-1,-4,
Р = min(4,4,6,3,4) =3
Следовательно, ос = Р = Зи а34=3- седловой элемент.