Элементы теории матричных игр

Каждый игрок во время своего хода независимо от другого выбирает одну из трех стратегий, называемых «камень», «ножницы» и «бумага». Выбранные стратегии сравниваются. Если они совпадают, выигрыш первого игрока составляет 0 (ничья), в противном случае побеждает игрок с более сильной стратегией. «Камень» считается сильнее «ножниц», которые, в свою очередь, сильнее «бумаги», которая сильнее «камня». Выигрыш победившего игрока составляет 1, проигравшего −1. Платежная матрица в этом случае имеет следующий вид:

Пример 5.2(«вооружение и самолет»). Первый игрок выбирает один из трех типов вооружения i = 1, 2, 3, другой – один из трех видов самолетов  j = 1, 2, 3. Платежная матрица задана таблицей

Элементами a_ij платежной матрицы являются вероятности поражения самолета  вида j  вооружением  типа i. Целью первого игрока является поражение самолета, второго – прорыв обороны противника. 

5.1.  Решение матричной игры в чистых стратегиях

Заметим, что в игре из примера 5.1 ни у кого из игроков нет  причины предпочесть одну из стратегий другой, поскольку на каждую стратегию одного игрока найдется контрстратегия другого, обеспечивающая его выигрыш (при условии, что он знает или угадал стратегию первого). В примере 5.2 ситуация иная. Для обоих игроков целесообразным является использование чистых стратегий i = 2 для первого и j = 2 для второго. Отклонение любого из игроков от указанных стратегий может только уменьшить его выигрыш. Разница в приведенных примерах объясняется наличием  во второй платежной матрице седловой точки.

Определение 5.2. Седловой точкой матрицы(a_{ij m n}) _× называется такая пара (i_{0 0}, j ) номеров строки и столбца, что для любых i = 1, …, m и j = 1, … , n выполняются неравенства

aij0 ≤ai j0 0 ≤ai j0 .

Таким образом, элемент ^a_{i j}0 0 в матрице с седловой точкой (i₀, j₀) является одновременно максимальным в своем столбце и минимальным в своей строке, что и объясняет нецелесообразность выбора любым из игроков другой стратегии.

При решении матричных игр используется принцип минимакса.

Принцип минимакса. Предположим, что противник заранее знает все ходы соперника. Тогда на каждую стратегию i = 1, …, m он отвечает наилучшей контрстратегией j(i), для которой a_{ij i( )} ≤a_ij для всех j = 1, …, n.

Обозначим αi⁰ =aij i( ) = minaij, i = 1, …, m. В описанной ситуации наи-

1≤ ≤j n

лучшей чистой стратегией первого игрока является стратегия i, максимизирующая α_i⁰, которая называется максиминной стратегией. Величину

назовем нижней ценой игры в чистых стратегиях. Если первый игрок поступает в соответствии с максиминной стратегией, он гарантированно получит выигрыш не менее α⁰ независимо от действий второго игрока.

Однако второй игрок, руководствуясь аналогичными соображениями и оставаясь в рамках чистых стратегий, должен поступать так, чтобы минимизировать величину

                                                 max           .

При таком выборе стратегии j₀ (минимаксной стратегии второго игрока) он гарантированно проиграет не более minmax    .

1≤ ≤j n 1≤≤i m

Величина β⁰ называется верхней ценой игры в чистых стратегиях.

В примере 5.1 имеем α⁰ =−1, β⁰ =1, т. е. нижняя цена меньше верхней. В примере 5.2 получаем следующие значения:

                            α⁰ = maxα_i⁰ = max{0,5,   0,7,   0,5}= 0,7 =α₂⁰,

i β⁰ = minβ⁰_j = min{0,9,        0,7,         0,8}= 0,7 =β₂⁰.

j

Имеем совпадение верхней и нижней цен игры и седловую точку (i₀, j₀) = (2, 2).

Заметим, что нижняя цена игры не может быть больше верхней в силу следующей леммы.

Лемма 5.1 (о максимине и минимаксе). Для любой функции f(x, y), x∈ ∈X y Y, справедливо неравенство

maxmin f (x y, ) ≤ minmax f x y( , ) .

                                          x X∈ y Y∈                           y Y∈ x X∈

Из этой леммы вытекает утверждение.

Утверждение 5.1. Необходимым и достаточным условием равенства нижней и верхней цен матричной игры в чистых стратегиях является существование седловой точки в платежной матрице (a_ij )_{m n×} .

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

Пример 5.3.  Найти решения в чистых стратегиях, если они существуют, для игр со следующими платежными матрицами:

                                                                                       ⎛1    2     3     4      5 ⎞

⎛− 2 0 1 ⎞ ⎛1 2 3 − 4⎞ ⎜ ⎟ ⎜ ⎟ ⎜ ^⎟ ⎜3 2 1 0 −1⎟

               а) ⎜ 3      4       5 ⎟; б) ⎜4      3       2 −1⎟; в) ⎜1       3     5     4      2 ⎟.

                   ⎜ 2       7 − 2⎟⎠       ⎜⎝0    3     1 −3⎟⎠       ⎝⎜⎜3    1 −1     0    2 ⎟⎟⎠

⎝

Решение.а) Найдем нижнюю и верхнюю цены игры в чистых стратегиях: