2.4. Методы решения матричных игр.

Теорема Неймана о минимаксе, гарантируя каждому игроку успех на пути отыскания оптимальной стратегии, тем не менее, ни слова не говорит о том, как эти стратегии найти. В этом параграфе мы рассмотрим несколько конструктивных методов нахождения оптимальных стратегий игроков.

Сразу заметим, что первым этапом поиска решения любой матричной игры является анализ игры на наличие седловой точки (см. п.2.1). Только при отсутствии таковой переходят к более тонким методам нахождения решения. Среди таких методов имеются как универсальные, которые применимы к любой матричной игре, так и частные, используемые для отдельных классов игр

1. Игра 2х2.

Пусть игра задана матрицей

.

Предположим, что седловая точка отсутствует. Однако, согласно теореме Неймана, оптимальное решение игры существует и определяется парой смешанных стратегий S_A*=(p₁*,p₂*), S_B*=(q₁*,q₂*). Используя свойство 3 решения игр и элементарные алгебраические преобразования (подробный вывод мы опускаем), приходим к следующим формулам:

р₁=(а₂₂–а₂₁)/(а₁₁+а₂₂–а₁₂–а₂₁), р₂=1–р₁,

q₁=(a₂₂–a₁₂)/(a₁₁+a₂₂–a₁₂–a₂₁), q₂=1–q₁, (2.7)

v_S=(a₂₂·a₁₁-a₁₂·a₂₁)/(a₁₁+a₂₂–a₁₂–a₂₁).

При этом отсутствие седловой точки в игре гарантирует необращение в 0 знаменателей в приведенных формулах.

Пример 2.4. Найдем решение в смешанных стратегиях игры, рассмотренной в примере 2.1 о двух игроках с двумя монетами. Платежная матрица этой игры имеет вид:

Нижняя и верхняя цены этой игры =–3 и =2. Следовательно, седловая точка отсутствует.

Найдем оптимальные стратегии игроков и цену игры, применяя формулы (4.1.). Имеем:

р₁=(4–(–3))/(2+4–(–3)–(–3))=7/12, р₂=1–7/12=5/12,

q₁=(4–(–3))/(2+4–(–3)–(–3))=7/12, q₂=5/12,

v_S=(42–(–3)(–3))/(2+4–(–3)–(–3))=–1/12.

Итак, решением игры является пара смешанных стратегий S_A*=(7/12,5/12), S_B*=(7/12,5/12), цена игры v_S=–1/12. Это означает, что оптимальная стратегия каждого игрока состоит в том, чтобы чередовать свои чистые стратегии случайным образом, выбирая 1-ю стратегию (положить 1 руб.) с вероятностью 7/12, а 2-ю стратегию (положить 2 руб.) – с вероятностью 5/12.

Отрицательная цена игры v_S=–1/12 показывает, что при использовании игроками своих оптимальных стратегий, первый игрок проигрывает второму в каждой партии «в среднем» 1/12 рубля. Тем самым можно говорить об изначальной несправедливости условий игры.

2. Упрощение игр с помощью отбрасывания доминируемых стратегий.

Стратегия А_i игрока А называется доминирующей над стратегией А_k (а стратегия А_k доминируемой стратегией А_i), если все элементы i-й строки платежной матрицы не меньше соответствующих элементов k-й строки, т. е. а_i1a_k1, a_i2a_k2, …, a_ima_km (в том же смысле можно говорить и о доминировании строк).

Стратегия В_j игрока В называется доминирующей над стратегией В_l (а стратегия В_l - доминируемой стратегией В_j), если все элементы j-го столбца платежной матрицы не больше соответствующих элементов l-го столбца, т. е. a_1ja_1l, a_2ja_2l,…, a_mja_ml (здесь также можно говорить и о доминировании столбцов платежной матрицы).

Доминируемая стратегия является заведомо невыгодной для игрока, ее выбирающего, и потому при дальнейшем исследовании игры может быть отброшена. В оптимальную смешанную стратегию она войдет с нулевой вероятностью. Следует также заметить, что при отбрасывании доминируемых стратегий некоторые из оптимальных стратегий игроков могут быть потеряны. Однако цена игры не изменится, и по усеченной матрице может быть найдена, по крайней мере, одна пара оптимальных смешанных стратегий.

Пример 2.5. Найдем оптимальное решение игры, заданной платежной матрицей

Результаты процесса отбрасывания доминируемых стратегий отобразим в таблице:

	В1	В2	В3	В4
А1	3	-2	5	-1
А2	4	0	6	1
А3	2	-1	3	2
А4	1	3	7	4

Комментарии:

1) Строка А₂ доминирует над строкой А₁ (43, 0–2, 65, 1–1); следовательно, строку А₁ отбрасываем (вычеркиваем).

2) В оставшейся части матрицы столбец В₂ доминирует над столбцами В₃ и В₄ (06, –13, 37 и 01, –12, 34); следовательно, вычеркиваем столбцы В₃ и В₄.

3) Наконец, в полученной матрице строка А₂ доминирует над строкой А₃ (42, 2–1); вычеркиваем строку А₃.

_{Оставшаяся матрица}

_{не имеет доминируемых стратегий и относится к классу игр 2х2.}

Используя формулы (2.7), найдем оптимальные смешанные стратегии игроков в полученной игре, а также ее цену:

=(3–1)/(4+3–1–0)=2/6=1/3, =1–1/3=2/3, =(3–0)/(4+3–1–0)=1/2,

=1–1/2=1/2, =(43–01)/(4+3–1–0)=2.

Итак, =(1/3,2/3),=(1/2,1/2) – оптимальное решение игры, заданной матрицей. Учитывая вычеркнутые доминируемые стратегии игроков, запишем оптимальное решение исходной игры:S_A*=(0,1/3,0,2/3), S_B*=(1/2,1/2,0,0). Цена игры - та же v*=2.