Решение матричной игры

Решение матричной  игры

Игроки	B1	B2	a = min(Ai)
A1	0	3	0
A2	5	2	2
b = max(Bi)	5	3

Находим гарантированный  выигрыш, определяемый нижней ценой  игры a = max(ai) = 2, которая указывает на максимальную чистую стратегию A2. 
Верхняя цена игры b = min(bj) = 3. 
Что свидетельствует об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах 2 <= y <= 3. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии) 

Решим задачу геометрическим методом, который включает в себя следующие этапы: 
1. В декартовой системе координат по оси абсцисс откладывается отрезок, длина которого равна 1. Левый конец отрезка (точка х = 0) соответствует стратегии B₁, правый - стратегии B₂ (x = 1). Промежуточные точки х соответствуют вероятностям некоторых смешанных стратегий S₁ = (p₁,p₂). 
2. На левой оси ординат откладываются выигрыши стратегии B₁. На линии, параллельной оси ординат, из точки 1 откладываются выигрыши стратегии B₂. 
Решение игры (m x 2) проводим с позиции игрока B, придерживающегося максиминной стратегии. Доминирующихся и дублирующих стратегий ни у одного из игроков нет. 
Максиминной оптимальной стратегии игрока B соответствует точка N, лежащая на пересечении прямых A₁A₁ и A₂A₂, для которых можно записать следующую систему уравнений: 
y = 0 + (3 - 0)q₂ 
y = 5 + (2 - 5)q₂ 
Откуда 
q₁ = ¹/₆ 
q₂ = ⁵/₆ 
Цена игры, y = 2¹/₂ 
Теперь можно найти минимаксную стратегию игрока A, записав соответствующую систему уравнений 
5p₂ = y 
3p₁+2p₂ = y 
p₁+p₂ = 1 
или 
5p₂ = 2¹/₂ 
3p₁+2p₂ = 2¹/₂ 
p₁+p₂ = 1 
Решая эту систему методом обратной матрицы, находим: 
p₁ = ¹/₂ 
p₂ = ¹/₂

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

Считаем, что  игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию  так, чтобы минимизировать выигрыш  игрока I.

Игроки	B1	B2	a = min(Ai)
A1	0	3	0
A2	5	2	2
b = max(Bi)	5	3

 

Находим гарантированный  выигрыш, определяемый нижней ценой  игры a = max(a_i) = 2, которая указывает на максимальную чистую стратегию A₂.

Верхняя цена игры b = min(b_j) = 3.

Что свидетельствует  об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах 2 ≤ y ≤ 3. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии).

2. Проверяем платежную матрицу  на доминирующие строки и доминирующие  столбцы.

Иногда на основании простого рассмотрения матрицы  игры можно сказать, что некоторые  чистые стратегии могут войти  в оптимальную смешанную стратегию  лишь с нулевой вероятностью.

Говорят, что i-я стратегия 1-го игрока доминирует его k-ю стратегию, если a_ij ≥ a_kj для всех j Э N и хотя бы для одного j a_ij > a_kj. В этом случае говорят также, что i-я стратегия (или строка) – доминирующая, k-я – доминируемая.

Говорят, что j-я стратегия 2-го игрока доминирует его l-ю стратегию, если для всех j Э M  a_ij ≤ a_il и хотя бы для одного i a_ij < a_il. В этом случае j-ю стратегию (столбец) называют доминирующей, l-ю – доминируемой.

В платежной  матрице отсутствуют доминирующие строки.

В платежной  матрице отсутствуют доминирующие столбцы.

Так как игроки выбирают свои чистые стратегии случайным  образом, то выигрыш игрока I будет  случайной величиной. В этом случае игрок I должен выбрать свои смешанные  стратегии так, чтобы получить максимальный средний выигрыш.

Аналогично, игрок II должен выбрать свои смешанные  стратегии так, чтобы минимизировать математическое ожидание игрока I.

3. Находим решение игры в смешанных  стратегиях.

Математические  модели пары двойственных задач линейного  программирования можно записать так:

найти минимум  функции F(x) при ограничениях:

5x₂ ≥ 1

3x₁+2x₂ ≥ 1

F(x) = x₁+x₂ → min

найти максимум функции Ф(y) при ограничениях:

3y₂ ≤ 1

5y₁+2y₂ ≤ 1

Ф(y) = y₁+y₂ → max

Решаем эти  системы симплексным методом.

Решение симплекс-методом доступно в расширенном  режиме.

Цена игры будет равна g = 1/F(x), а вероятности применения стратегий игроков:

p_i = g*x_i; q_i = g*y_i.

Цена игры: g = 1 : ²/₅ = 2¹/₂

p₁ = 2¹/₂ • ¹/₅ = ^½ p₂ = 2¹/₂ • ¹/₅ = ¹/₂

Оптимальная смешанная стратегия игрока I:

P = (¹/₂; ¹/₂)

q₁ = 2¹/₂ • ¹/₁₅ = ¹/₆  q₂ = 2¹/₂ • ¹/₃ = ⁵/₆

Оптимальная смешанная стратегия игрока II:

Q = (¹/₆; ⁵/₆) Цена игры: v=2¹/₂

4. Проверим  правильность решения игры с  помощью критерия оптимальности стратегии.

∑a_ijq_j ≤ v

∑a_ijp_i ≥ v

M(P₁;Q) = (0•¹/₆) + (3•⁵/₆)  = 2.5 = v M(P₂;Q) = (5•¹/₆) + (2•⁵/₆)  = 2.5 = v M(P;Q₁) = (0•¹/₂) + (5•¹/₂)  = 2.5 = v M(P;Q₂) = (3•¹/₂) + (2•¹/₂)  = 2.5 = v

Все неравенства  выполняются как равенства или  строгие неравенства, следовательно, решение игры найдено верно.