Методы решения матричных игр (на примере игры «Зачет»)

и линейных уравнений

 

 

     = 1.

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

Определение 9. Стратегия  игрока I строго доминирует его стратегию , если

H (, j) >H (, j), j = 1, 2, …,n                              (18)

(стратегия  называется доминируемой).

Определение 10. Стратегия  игрока II строго доминирует его стратегию , если

-H (i, ) > - H(i, ), i = 1, 2, …, m,

Или

H(i, ) <H(i, ), i = 1, 2, …, m                             (19)

(стратегия  называется строго доминируемой).

Когда неравенства (18) и (19) для  некоторых чистых стратегий игрока I (игрока II) не являются строгими, стратегия () доминирует стратегию ().

В частности, чистая стратегия  игрока I строго доминирует его чистую стратегию , если для любого j∈B

>,

А чистая стратегия  игрока II строго доминируют его чистую стратегию , если для любого i∈A

>.

Из определений 9 и 10 следует, что доминирующая стратегия дает игроку выигрыш не меньший, чем доминируемая. Поэтому в матрице Н доминируемые стратегии (строки или столбцы) могут быть отброшены, что и приводит к матрице меньших размеров. Однако следует отметить, что исключение доминируемых стратегий может привести к потере некоторые решений; если же исключаются только строго доминируемые стратегии, то множество решений игры не изменяется. В результате применения доминирования получается игра, эквивалентная исходной в смысле следующего утверждения.

Теорема 6. Пусть (, ) – седловая точка m × n – игры Н, а (, ) – седловая точка × - игры (), полученной из Н в результате исключения доминируемых стратегий. Тогда = ,  =   и j;  = 0, = 0  для всех доминируемыхi и j;  v(H) = v().

Пример 6

Рассмотрим игру

.

Решение.

.

Первая строка строго доминирует вторую и третью, так как все  ее элементы соответственно больше элементов  второй и третьей строк. Поэтому для игрока Iстратегии { и {  ((5 4 3 4 6) и (4 3 2 3 4))  менее выгодны, чем {  ((8 6 4 7 7)), и могут быть исключены. В результате получим матрицу , в которой первый, четвертый и пятый столбцы строго доминируются вторым. Так как столбцы характеризуют стратегии игрока I (и тем самым увеличить свой выигрыш), эти стратегии заведомо невыгодны для игрока II. После их исключения получаем матрицу , в которой нет доминируемых стратегий и, следовательно, . Игра эквивалентна первоначальной игре Н, то есть оптимальные стратегии в игре Н имеют вид

)  и  , .

В результате вместо 4 5- игры Н мы можем решить 2 2- игру .

Теперь приведем общую  схему решения матричной игры:

1. Исключить в платежной матрице доминируемые стратегии;
2. Упрощенную матрицу проверить на наличие в ней седловых точек (в чистых стратегиях), что позволяет сразу же определить решение (оптимальные стратегии и значение игры) в чистых стратегиях;
3. Если седловых точек нет  (в чистых стратегиях), то перейти к определению решения в смешанных стратегиях.

Теорема 7. Если один из игроков применяет свою оптимальную смешанную стратегию, то его выигрыш равен значению игры v вне зависимости от того, с какими вероятностями будет применять второй игрок стратегии, вошедшие в оптимальную (в том числе и чистые стратегии).

 

2.2  Решение 2 × 2 – игр

Рассмотрим матричную  игру, в которой каждый из игроков  имеет по две чистые стратегии. В  общем виде 2 × 2 – игра определяется матрицей

H= .

Пусть Х – произвольная смешанная стратегия игрока I. Если х – вероятность выбора игроком I своей первой чистой стратегии в условиях X, то вероятность выбора им второй чистой стратегии есть 1-х. поэтому стратегию Х можно представить  в виде (х, 1-х). Аналогично если Y – произвольная смешанная стратегия игрока II? То она имеет вид (y, 1-y).таким образом, стратегия Х однозначно определяется числом х, а стратегия Y – числом y. В соответствии с этим мы будем обозначать ситуацию (Х, Y) как пару чисел (х, y). В силу предположения, что чистых оптимальных стратегий нет, , .

Введем следующие обозначения:

- i-я строка матрицы Н;

- j-й столбец матрицы Н.

На основании теоремы 7

Н(, j) = = v, j = 1,2,

И

Н(i, ) = = v, i = 1,2,

Или 

+ (1 - ) = v,

+ (1 - ) = v                                       (20)

И

+ (1 - ) = v,

+ (1 - ) = v                                       (21)

 

Из систем (20) и (21) следует, что при  v ≠ 0 столбцы (строки) матрицы Н не могут быть пропорциональны с коэффициентом пропорциональности, отличным от единицы. Если же коэффициент пропорциональности равен единице, то матрица примет следующий вид:

 

И игрок I (II) имеет чистую оптимальную стратегию, что противоречит предположению.

Следовательно, еслиv ≠ 0 и игроки имеют только смешанные оптимальные стратегии, определитель матрицы Н отличен от нуля. Из этого следует, что системы уравнений (20) и (21) имеют единственное решение. Решая их, находим

,  ,

                                   (22)

Или в матричной записи

,  , v = ,

Где J- вектор (1, 1).

Таким образом, для решения  матричной  2 × 2 – игры необходимо сначала проверить равенство (8). Если оно выполняется, то игроки имеют чистые оптимальные стратегии (игрок I – чистую максиминную, а игрок II – чистую минимаксную). В противном случае по формулам (22) следует найти оптимальные стратегии игроков и значение игры.

Пример 7

Решить игру Н = .

Решение. Прежде всего, проверим наличие седловой точки (в чистых стратегиях). Имеем

,,

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

,  ,

.

Таким образом, .

Пример 8

Решить игру из примера 6.

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

.

Так как    ,а ,

Седловых точек в чистых стратегиях нет. Перейдем к нахождению решения в смешанных стратегиях. По формулам (22) имеем

,  ,

,

и, следовательно,

.

 

2.3  Графический метод решения игр 2 × n  и m × 2

Предварительно докажем  одно утверждение.

Теорема 8. В равенстве (8) внутренние экстремумы достигаются  на чистых стратегиях, то есть

= = ,

= = .

Доказательство. Рассмотрим случай, когда i = 2,  j= n, то есть 2 × n – игру (в общем случае доказательство аналогично).

H(X, Y) = = .

Учитывая, что  или , получим

H(X, Y) = ,

Где .

Следовательно,  H(X, Y) можно интерпретировать как линейную комбинацию векторов    () . при любом

j∈B, мы имеем

.                                (23)

Умножив неравенство (23) на    и произведя суммирование по  j∈B , получим:

[] = (в силу того, что , знак неравенства не изменяется).

Итак,

 

Для любого Y∈ и, в частности,

.                 (24)

Но  есть число вида  (когда Y – чистая стратегия ), значит,

.                 (25)

Объединяя неравенства (24) и (25), получим

= .

Так как это неравенство  справедливо для  X∈ , должно быть

=.

Другое равенство теоремы 8 доказывается аналогично.

1. Рассмотрим игру, в которой игрок I имеет две чистые стратегии, а игрок II – произвольное число n чистых стратегий. Матрица выигрышей этой игры имеет вид

H= .                                  (26)

Произвольная смешанная  стратегия игрока I имеет вид Х = (х, 1-х), а их множество описать сегментом [0, 1]. Из теоремы 8 следует, что целью игрока I является максимизация величины

h(х) = .                              (27)

Графически зависимость  выигрыша

                  Рисунок 2                                                    Рисунок 3

От  х  изображается прямой линией. Каждой чистой стратегией  j игрока II соответствует своя прямая (Рисунок 2, 3).

Ясно, что если матрица (26) имеет одинаковые столбцы, то прямые, соответствующие таким стратегиями  игрока II? Будут совпадать. Все совпадающие столбцы будем считать за одну стратегию. Графиком функции (27) является нижняя огибающая всех прямых, соответствующих стратегиям игрока II . Максимуму функции h(х) соответствует наивысшая точка М огибающей, то есть

.

Так как 

,

По основной теореме (теорема 5)

v =

и, следовательно, абсцисса точки М является оптимальной  смешанной стратегией игрока I, а ее ордината – значением игры. Если таких точек более одной, то огибающая будет иметь наивысший горизонтальный участок и у игрока I существует бесконечное множество оптимальных смешанных стратегий, состоящее из всех абсцисс этих точек (смотрите Рисунок3).

Пусть точка М – точка  пересечения прямых и .

Тогда значение игры v и стратегию   мы найдем, решая следующую систему:

,

.

Эти величины, однако, могут  быть вычислены и с помощью  формул (22) для игры

.                                      (28)

Для полного решения задачи нам необходимо найти и оптимальную  стратегию    игрока II с помощью описанного построения. При этом могут представиться две возможности.

Во-первых, огибающая имеет верхний горизонтальный участок (см. Рисунок3), соответствующий чистой стратегии     игрока II. Очевидно, это может быть лишь при   = . В таком случае игрок II имеет единственную оптимальную стратегию, которая является чистой, то есть

.

 

Во-вторых, может оказаться, что график функции (27) имеет единственную верхнюю точку М.

Если абсциссой “пиковой”  точки являются 0 или 1, то игрок I имеет чистую оптимальную стратегию (в случае, изображенном на Рисунок4, это точка 0) и существуют прямые

,                                     (29)

подходящие к точке М, не убывая при приближении к ней. Эти прямые, очевидно, соответствуют чистым оптимальным стратегиям игрока II. Все “смеси” этих стратегий также оптимальны. Кроме того, могут иметься еще прямые (29), подходящие к точке Мубывая. Они не соответствуют оптимальным стратегиям игрока II. Однако те их “смеси” со строго убывающими прямыми, которые не убывают, также являются оптимальными стратегиями игрока II. В заключении следует перейти к выпуклой оболочке всех стратегий.

Если абсцисса точки М  лежит строго между  0 и 1 (смотритеРисунок2), то существует хотя бы одна проходящая через М прямая (29), имеющая положительный наклон, и хотя бы одна прямая, имеющая отрицательный наклон.

Пусть

,

                                   (30)

Эти прямые (соответствующие  стратегии имеют номера  ,  ). Решение уравнений (30) дает нам

   и     .

Из этого, что прямые (30) пересекаются в точке М с ординатой  v и имеют наклоны разных знаков, следует существование такого  , что “смесь” этих прямых с весами  и   является горизонтальной прямой, проходящей через данную точку.

Так как ординаты точек  пересечения горизонтальной прямой спрямыми        х = 0  и   х = 1  будут равными (в  частности, равными v), справедливо равенство

.

Решая это уравнение, получим

.                                  (31)

Смешанная стратегия игрока II, состоящая из стратегий     и   , взятая с найденными весами  и , ( , будет давать игроку I ровно v независимо оттого, как сам будет играть. Следовательно, эта смешанная стратегия игрока II является его оптимальной стратегией. Значение    можно найти, используя также формулы (22) для игры с матрицей (28). Комбинируя, таким образом, каждую прямую стратегию с отрицательным наклоном, мы получим некоторое множество оптимальных стратегий игрока II. Затем следует перейти к их выпуклой оболочке

{} = .

Пример 9

Решить игру

.

(1): H = 2*x + 4*(1 – x) = -2x + 4;

(2): H = 3*x + 1*(1 – x) = 2x + 1;

(3): H = 1*x + 6*(1 – x) = -5x + 6;

(4): H = 5*x + 0*(1 – x) = 5x.

Построим нижнюю огибающую  прямых (1) – (4) (Рисунок4). Она имеет “пиковую” точку М, которая лежит строго между 0 и 1.