Решение матричной игры: графическим методом, методом линейного программирования
Решение матричной игры
Цена игры, седловая точка
Примеры решений Метод Брауна Системы массового обслуживания Матрица рисков Седловая точка Платежная матрица Цена игры Смешанные стратегии Матричная игра онлайн Чистые стратегии

Нижняя и верхняя цена игры

Найдем наилучшую стратегию игрока 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», тогда он хотя бы не проиграет.
 BA 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
В добавочном столбце находим максимальный элемент &alpha=max αi=0,7, в добавочной строке находим минимальный элемент β= min βj=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. Так как α ≠ β, игра не имеет седловой точки. Положения равновесия в этой игре не существует, и оптимального решения в чистых стратегиях найти нельзя.

Пример. Найдите нижнюю цену игру, верхнюю цену игры, определите седловые точки, оптимальные чистые стратегии и цену игры (если они существуют).

Найти верхнюю и нижнюю цену игры.

ИгрокиB1B2B3B4a = min(Ai)
A176454
A221971
A345353
b = max(Bi)7697

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = 4, которая указывает на максимальную чистую стратегию A1.
Верхняя цена игры b = min(bj) = 6.
Что свидетельствует об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах 4≤y≤6. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии)
Стратегия A1 доминирует над стратегией A3 (все элементы строки 1 больше или равны значениям 3-ой строки), следовательно исключаем 3-ую строку матрицы. Вероятность p3 = 0.
7645
2197
Решим задачу геометрическим методом, который включает в себя следующие этапы:
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
Профессии будущего
РБК Тренды изучили прогнозы российских и зарубежных футурологов, и составили список самых востребованных профессий в ближайшие 30 лет. Это профессии из 19 отраслей: от медицины и транспорта до культуры и космоса
Подробнее
Налоговый вычет на обучение
√ 120 тыс. руб. - максимальная сумма расходов на обучение
√ вычет от государства
√ вычет от работодателя
Подробнее
Требуются авторы студенческих работ!
  • регулярный поток заказов;
  • стабильный доход
Подробнее
Курсовые на заказ