Понятие игры

Игра задается матрицей

а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- седловой элемент.