Нижняя и верхняя цена игры
Найдем наилучшую стратегию игрока A, для чего проанализируем последовательно все его стратегии. Выбирая стратегию Ai, мы должны рассчитывать, что игрок B ответит на нее такой стратегией Bj, для которой выигрыш A будет минимальным. Поэтому среди чисел первой строки выбираем минимальное, обозначим его
, запишем его в добавочный столбец. Аналогично для каждой стратегии Ai выбираем 
, т.е.
αi – минимальный выигрыш при применении стратегии Ai.
В примере 1:
α1 = min {0, –1, –2} = –2;
α 2 = min {1, 0, –1} = –1;
α 3 = min {0, –1, –2} = 0.
Эти числа запишем в добавочном столбце. Какую же стратегию должен выбрать игрок A? Конечно же, ту стратегию, для которой αi максимально. Обозначим
. Это гарантированный выигрыш, который может обеспечить себе игрок A, т.е.
; этот выигрыш называется нижней ценой игры или максимином. Стратегия
Ai, обеспечивающая получение нижней цены игры, называется максиминной (перестраховочной). Если игрок A будет придерживаться этой стратегии, то ему гарантирован выигрыш ≥α при любом поведении игрока B.
В примере 1
. Это означает, что если A будет писать «3», то он хотя бы не проиграет. Игрок B заинтересован уменьшить выигрыш A.
Выбирая стратегию B1, он из соображений осторожности учитывает максимально возможный при этом выигрыш A. Обозначим 
. Аналогично при выборе стратегии Bj максимально возможный выигрыш A– 
; запишем эти числа в добавочной строке.
Чтобы уменьшить выигрыш A, надо из чисел β j выбрать наименьшее 
. Число 
называется верхней ценой игры или минимаксом. Это гарантированный проигрыш игрока B (т. е. он проиграет не больше, чем β).
Стратегия игрока B, обеспечивающая выигрыш ≥ - β, называется его минимаксной стратегией.
В примере 1:
β1=max{0,1,2}=2;
β2=max{-1,0,1}=1;
β3=max{-2,-1,0}=0;
β=min{2,1,0}=0;
Это означает, что оптимальная стратегия B – писать «3», тогда он хотя бы не проиграет.
| B↓A→ | B1 | B2 | B3 | αi |
| A1 | 0 | – 1 | –2 | –2 |
| A2 | 1 | 0 | –1 | –1 |
| A3 | 2 | 1 | 0 | 0 |
| βj | 2 | 1 | 0 | 0 |
Можно доказать, что
, т.е. α≤β.
В примере 1 α=β. Если α=β, т.е. минимакс совпадает с максимином, то такая игра называется игрой с седловой точкой. Седловая точка – это пара оптимальных стратегий ( Ai, Bj). В примере 1 игра имеет седловую точку (А3, B3). В этом случае число α = β называется (чистой) ценой игры (нижняя и верхняя цена игры совпадают). Это означает, что матрица содержит такой элемент, который является минимальным в своей строке и одновременно максимальным в своем столбце. В примере 1 это элемент 0. Цена игры равна 0.
Оптимальные стратегии в любой игре обладают важным свойством, а именно – устойчивостью. Это означает, что каждый из игроков не заинтересован в отходе от своей оптимальной стратегии, т. к. это ему невыгодно. Отклонение от оптимальной стратегии игрока А приводит к уменьшению его выигрыша, а одностороннее отклонение игрока В – к увеличению проигрыша. Говорят, что седловая точка дает положение равновесия.
Пример 2. Первая сторона (игрок А) выбирает один из трех типов вооружения – А1, А2, А3, а противник (игрок В) – один из трех видов самолетов: В1, В2, В3. Цель В – прорыв фронта обороны, цель А – поражение самолета. Вероятность поражения самолета В1 вооружением А1 равна 0,5, самолета В2 вооружением А1 равна 0,6, самолета В3 вооружением А1 равна 0,8 и т.д., т.е. элемент aij платежной матрицы – вероятность поражения самолета В j вооружением Аi. Платежная матрица имеет вид:
| В / А | Вид самолета | |||
| В1 | В2 | В3 | ||
| Тип вооружения | А1 | 0,5 | 0,6 | 0,8 |
| А2 | 0,9 | 0,7 | 0,8 | |
| А3 | 0,7 | 0,5 | 0,6 | |
Решение. В каждой строке находим минимальный элемент и записываем его в добавочном столбце. В каждом столбце находим максимальный элемент и записываем его в добавочной строке.
| В / А | В1 | В2 | В3 | α i |
| А1 | 0,5 | 0,6 | 0,8 | 0,5 |
| А2 | 0,9 | 0,7 | 0,8 | 0,7 |
| А3 | 0,7 | 0,5 | 0,6 | 0,5 |
| β j | 0,9 | 0,7 | 0,8 | 0,7 / 0,7 |
Ответ: α=β=0,7. Оптимальные стратегии – А2 и В2.
Пример 3. Игра в орлянку. Каждый игрок при своем ходе может выбирать одну из двух стратегий: орел или решка. При совпадении выбранных стратегий А получает выигрыш +1, при несовпадении B получает выигрыш 1 (т. е. А получает выигрыш –1). Платежная матрица:
| В / А | В1 (орел) | В2 (решка) |
| А1 (орел) | 1 | -1 |
| А2(решка) | -1 | 1 |
Решение.
| В1 | В2 | αi | |
| А1 | 1 | -1 | -1 |
| А2 | -1 | 1 | 1 |
| βj | 1 | 1 | -1 1 |
α = -1, β = 1, т. е. А проиграет не больше 1, и B проиграет не больше 1. Так как α ≠ β, игра не имеет седловой точки. Положения равновесия в этой игре не существует, и оптимального решения в чистых стратегиях найти нельзя.
Пример. Найдите нижнюю цену игру, верхнюю цену игры, определите седловые точки, оптимальные чистые стратегии и цену игры (если они существуют).
Найти верхнюю и нижнюю цену игры.
| Игроки | B1 | B2 | B3 | B4 | a = min(Ai) |
| A1 | 7 | 6 | 4 | 5 | 4 |
| A2 | 2 | 1 | 9 | 7 | 1 |
| A3 | 4 | 5 | 3 | 5 | 3 |
| b = max(Bi) | 7 | 6 | 9 | 7 |
Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = 4, которая указывает на максимальную чистую стратегию A1.
Верхняя цена игры b = min(bj) = 6.
Что свидетельствует об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах 4≤y≤6. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии)
Стратегия A1 доминирует над стратегией A3 (все элементы строки 1 больше или равны значениям 3-ой строки), следовательно исключаем 3-ую строку матрицы. Вероятность p3 = 0.
| 7 | 6 | 4 | 5 |
| 2 | 1 | 9 | 7 |
1. В декартовой системе координат по оси абсцисс откладывается отрезок, длина которого равна 1. Левый конец отрезка (точка х = 0) соответствует стратегии A1, правый - стратегии A2 (x = 1). Промежуточные точки х соответствуют вероятностям некоторых смешанных стратегий S1 = (p1,p2).
2. На левой оси ординат откладываются выигрыши стратегии A1. На линии, параллельной оси ординат, из точки 1 откладываются выигрыши стратегии A2.
Решение игры (2 x n) проводим с позиции игрока A, придерживающегося максиминной стратегии. Доминирующихся и дублирующих стратегий ни у одного из игроков нет.
Максиминной оптимальной стратегии игрока A соответствует точка N, лежащая на пересечении прямых B2B2 и B3B3, для которых можно записать следующую систему уравнений:
y = 6 + (1 - 6)p2
y = 4 + (9 - 4)p2
Откуда
p1 = 4/5
p2 = 1/5
Цена игры, y = 5
Теперь можно найти минимаксную стратегию игрока B, записав соответствующую систему уравнений, исключив стратегию B1,B4, которая дает явно больший проигрыш игроку B, и, следовательно, q1 = 0,q4 = 0.
6q2+4q3 = y
q2+9q3 = y
q2+q3 = 1
или
6q2+4q3 = 5
q2+9q3 = 5
q2+q3 = 1
Решая эту систему методом Гаусса, находим: q2 = 1/2, q3 = 1/2
