Матричные игры

Часть I матричные игры

            Рассмотрим игру, в которой участвуют два игрока, причем каждый из игроков имеет конечное число стратегий. Обозначим для удобства одного из игроков через А, в другого — через В.

            Предположим, что игрок А имеет m стратегий — А₁, А₂, ..., А_m, а игрок В имеет n стратегий В₁, В₂, ..., В_n.

            Пусть игрок А выбрал стратегию A_i, а игрок В стратегию В_k. Будем считать, что выбор игроками стратегий A_i и В_k однозначно определяет исход игры — выигрыш а_ik игрока А и выигрыш b_ik игрока В, причем эти выигрыши связаны равенством

(отрицательный выигрыш на бытовом языке обычно называют проигрышем).

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

            Если нам известны значения а_ik выигрыша при каждой паре стратегий (в каждой ситуации) { A_i, В_k }, i = 1, 2,..., m, k = 1, 2,..., n, то их удобно записывать или в виде прямоугольной таблицы, строки которой соответствуют стратегиям игрока А, а столбцы – стратегиям игрока В:

или в виде матрицы

            Полученная матрица имеет размер m x n и называется матрицей игры, или платежной матрицей (отсюда и название игры — матричная).

            Рассматриваемую игру часто называют игрой m x n или m x n игрой.

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

Пример 1. Каждый из двух игроков А и В одновременно и независимо друг от друга записывает на листе бумаги любое целое число. Если выписанные числа имеют одинаковую четность, то игрок А получает от игрока В 1 рубль, а если разную, то наоборот – игрок А платит 1 рубль игроку В.

            У игрока А две стратегии: А₁ – записать четное число и А₂ – записать нечетное число. У игро­ка В такие же две стратегии: В₁ – записать четное число и В₂ – записать нечетное число. Выбор игроками соответственно стратегий А_i и В_k однозначно определяет исход игры – выигрыш игрока А.

Матрица этой 2x2 игры имеет следующий вид

(здесь строки соответствуют стратегиям игрока А, а столбцы — стратегиям игрока В).

1. Равновесная ситуация

            Рассмотрим следующий пример.

            Пример 2. Два игрока А и В, не глядя друг на друга, кладут на стол по картонному кружку красного (г), зеленого (g) или синего (b) цветов, сравнивают цвета кружков и расплачиваются друг с другом так, как покапано в матрице игры

(напомним, что у этой 3 х 3-матрицы строки соответствуют стратегиям игрока А, а столбцы - страте­гиям игрока В).

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

            Начнем с последовательного анализа стратегий игрока А, не забывая о том, что, выбирая страте­гию игрока А, должно принимать в расчет, что его противник В может ответить на нее той из своих стратегий, при которой выигрыш игрока А будет минимальным.

            Так, на стратегию А, он ответит стратегией В_r, (минимальный выигрыш равен -2, что на самом деле означает проигрыш игрока А, равный 2), на стратегию А_g – cстратегией  B_g или В_b (минимальный выигрыш игрока А равен 1), а на стратегию A_b – стратегией B_g (минимальный выигрыш игрока А равен -3).

            Запишем эти минимальные выигрыши в правом столбце таблицы:

            maxmin. Неудивительно, что игрок А останавливает свой выбор на стратегии А_g, при которой его минимальный выигрыш максимален (из трех чисел -2, 1 и -3 максимальным является 1):

maxmin = 1.

            Если игрок А будет придерживаться этой стратегии, то ему гарантирован выигрыш, не меньший 1, при любом поведении противника в игре.

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

            Выбирая свою стратегию, игрок В должен учитывать, что при этом стратегией его противника А может оказаться та, при которой выигрыш игрока А будет максимальным. Так, на стратегию В_r он отве­тит стратегией A_b (максимальный выигрыш игрока А равен 3), на стратегию B_g – стратегией A_r (мак­симальный выигрыш игрока А равен 2), а на стратегию B_b – стратегией А_g или A_b (максимальный выигрыш игрока А равен 1). Эти максимальные выигрыши записаны в нижней строке таблицы

            minmax. Неудивительно, вели игрок В остановит свой выбор на стратегии B_b, при которой максимальный выигрыш игрока А минимален (из трех чисел 3, 2 и 1 минимальным является 1):

minmax = 1.

Если игрок В будет придерживаться этой стратегии, то при любом поведении противника он проиграет не больше 1.

            В рассматриваемой игре числа maxmin и minmax совпали:

maxmin = minmax = 1

(соответствующие элементы в таблице

выделены жирным шрифтом).

            Выделенные стратегии A_g и B_b являются оптимальными стратегиями игроков А и В,

A_g = A_opt, B_b = B_opt

в следующем смысле:

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

В самом деле, если игрок А будет придерживаться не стратегии A_opt, а выберет иную стратегию, на­пример, А_r, то вряд ли стоит рассчитывать на то, что игрок В этого не заметит. Конечно, заметит и не преминет воспользоваться своим наблюдением. Ясно, что в этом случае он отдаст предпочтение стратегии В_r. А на выбор A_b игрок В ответит, например, так – B_g. В результате отказа от страте­гии A_g, выигрыш игрока А уменьшится.

Если же от стратегии B_opt отказывается игрок В, выбирая, например, стратегию В_r, то игрок А
может ответить на это стратегией A_b и, тем самым, увеличить свой выигрыш. В случае стратегии B_g ответ игрока А – А_r .

Тем самым, ситуация { A_g, В_b } оказывается равновесной.

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

            Матрица выплат игроку В получается из матрицы игры заменой каждого ее эле­мента на противоположный по знаку.

            Рассмотрим теперь произвольную матричную игру

(строки заданной m x n-матрицы соответствуют стратегиям игрока А, а столбцы -  стратегиям игрока В) и опишем общий алгоритм, посредством которого можно определить, есть ли в этой игре ситуация равновесия или ее нет.

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

Действия игрока А

1-й шаг. В каждой строке матрицы А ищется минимальный элемент

, i = 1, 2, … , m.

Полученные числа

α₁, α_{2, …} , α_m

приписываются к заданной таблице в виде правого добавочного столбца

Пояснение. Выбирая стратегию А_i, игрок А вправе рассчитывать на то, что в результате разумных действий противника (игрока В) он выиграет не меньше чем а_i.

2-й шаг. Среди чисел

α₁, α_{2, …} , α_m

выбирается максимальное число

или, подробнее,

            Специально отметим, что выбранное число α является одним из элементов заданной матрицы А.

            Пояснение. Действуя наиболее осторожно и рассчитывая на наиболее разумное поведение противника, игрок А должен остановиться на той стратегии A_i, для которой число а_i, является максимальным.

            Если игрок А будет придерживаться стратегии, Выбранной описанным выше спосо­бом, то при любом поведении игрока В игроку А гарантирован выигрыш, не меньший α.

            Число α называется нижней ценой игры.

            Принцип построения стратегии игрока А, основанный на максимизации минимальных выигрышей, называется принципом максимина, а выбираемая в соответствии с этим принципом стратегия А_i⁰ — максиминной стратегией игрока А.

Действия игрока В

1 шаг. В каждом столбце матрицы А ищется максимальный элемент

, k = 1, 2, … , n.

Полученные числа

β₁, β₂, … , β_n

приписываются к заданной таблице в виде нижней добавочной строки

Пояснение. Выбирая стратегию В_k, игрок В должен рассчитывать на то, что в результате разумных действий противника (игрока А) он проиграет не больше чем β_k.

2-й шаг. Среди чисел

β₁, β₂, … , β_n

выбирается минимальное число

или, подробнее,

Выбранное число β также является одним из элементов заданной матрицы А.

Пояснение. Действуя наиболее осторожно и рассчитывая на наиболее разумное поведение противника, игрок В должен остановиться на той стратегии В_k*, для которой число β_k является минимальным.

            Если игрок В будет придерживаться стратегии, выбранной описанным выше способом, то при любом поведении игрока А игроку В гарантирован проигрыш, не боль­
ший β.

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

            Принцип построения стратегии игрока B, основанный на минимизации максимальных потерь, называется принципом минимакса, а выбираемая в соответствии с этим принципом стратегия B_k⁰ – минимаксной стратегией игрока В.

            Нижняя цена игры α и верхняя цена игры β всегда связаны неравенством

           

Замечание. Реализация описанного алгоритма требует 2mn - 1 сравнений элементов матрицы А:

(n - 1)m + m - 1 = mn - 1

сравнений для определения α,

(n - 1)m + m - 1 = mn - 1

сравнений для определения β и одно сравнение полученных чисел α и β.

Если

,

или, подробнее,

,

то ситуация {А_i⁰, В_k⁰} оказывается равновесной, и ни один из игроков не заинтересован в том, чтобы ее нарушить (в этом нетрудно убедиться путем рассуждений, подобных проведенным при анализе игры в примере 2).

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

            Цена игры совпадает с элементом  матрицы игры А, расположенным на пересечении i⁰-й строки (стратегия  игрока А) и k⁰-го столбца (стратегия  игрока В) – минимальный в своей строке и максимальный в своем столбце.

            Этот элемент называют седловой точкой матрицы А, или точкой равновесия, а про игру говорят, что она имеет седловую точку.

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

            Замечание. Седловых точек в матричной игре может быть несколько, но все они имеют одно и то же значение.

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

.

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

            Пример 3. Рассмотрим 3 x 3 игру, заданную матрицей

.

Применив предложенный алгоритм

находим нижнюю цену игры α = -2 и соответствующую ей стратегию А₂, верхнюю цену игры β = 2 и соответствующую ей стратегию B₂.

            Нетрудно убедиться в том, что пока игроки придерживаются этих стратегий, средний выигрыш при многократном повторений игры равен 1. Он больше нижней мены игры, но меньше верхней цены.

            Однако если игроку В станет известно, что игрок А придерживается стратегии А₂, он немедленно ответит стратегией В₁ и сведет его выигрыш к проигрышу -2. В свою очередь, на стратегию В₁ у игрока А имеется ответная стратегия А₁, дающая ему выигрыш 4.

Тем самым, ситуация { А₂, В₂} равновесной не является.

2. Смешанные стратегии

            В случае, когда нижняя цена игры α и верхняя цена игры β не совпадают,

,

игрок А может обеспечить себе выигрыш, не меньший α, а игрок В имеет возможность
не дать ему больше, чем β. Возникает вопрос – а как разделить между игроками разность

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

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

– во-первых, обеспечивается наибольшая скрытность выбора стратегии (результат выбора не может стать известным противнику, поскольку он неизвестен самомуигроку),

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

            Случайная величина, значениями которой являются стратегии игрока, называется его смешанной стратегией.

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

Основные определения

            Рассмотрим произвольную m х n игру, заданную m х n-матрицей

            Так как игрок А имеет m чистых стратегий, то его смешанная стратегия может, быть описана набором m неотрицательных чисел

сумма которых равна 1,

.

            Смешанная стратегия второго игрока В, имеющего п чистых стратегий, описыва­ется набором п неотрицательных чисел

сумма которых равна 1,

.

            Замечание. Каждая чистая стратегия является частным случаем смешанной стратегии: в частности, чистая стратегия A_i является смешанной стратегией, описываемой набором чисел  Рев котором p₁, p₂, … , p_m, в котором

  

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

            Таким образом, задав два набора

    

мы оказываемся в ситуации в смешанных стратегиях. В этих условиях каждая обычная ситуация (в чистых стратегиях) {А_i, B_k} по определению является случайным событием и, ввиду независимости наборов Р и Q, реализуется с вероятностью p_iq_k. В этой ситуации {А_i, B_k} игрок А получает выигрыш a_ik. Тем самым, математическое ожидание выигрыша игрока А в условиях ситуации в смешанных стратегиях (Р, Q) равно

.

            Это число и принимается за средний выигрыш игрока А при смешанных стратегиях

   

            Определение. Стратегии

   и  

называются оптимальными смешанными стратегиями игроков А и В соответственно, если выполнено следующее соотношение

.

Пояснение. Выписанные неравенства означают следующее:

левое неравенство – отклонение игрока А от оптимальной стратегии Р⁰ при условии, что игрок В придерживается стратегии Q⁰, приводит к тому, что выигрыш отклонившегося игрока А может только уменьшиться,

правое неравенство – отклонение игрока В от оптимальной стратегии Q⁰ при условии, что игрок А придерживается стратегии Р⁰, приводит к тому, что выигрыш игрока А может только возрасти, и значит, выигрыш игрока В – только уменьшиться.

Приведенное условие оптимальности равносильно тому, что[1]

Величина

,

определяемая последней формулой, называется ценой игры.

            Набор (Р⁰, Q⁰, ν), состоящий из оптимальных смешанных стратегий игроков А и В и цены игры, называется решением матричной игры.

            Пример 4. Рассмотрим 2 x 2 матричную игру из примера 1. Матрица этой игры имеет следующий вид

.

Как нетрудно убедиться, седловой точки у нее нет.

            Смешанные стратегии игроков А и В могут быть описаны парами чисел

P = {p, 1 - p}   и   Q = {q, 1 - q}

соответственно.

            Средний выигрыш игрока А вычисляется так

?

откуда легко следует, что

Последнее удобно записать так

.

Рис. 1

            Полученная формула показывает, что если игрок А в половине случаев записывает на листе бумаге четное (нечетное) число (выбирает р = 1/2), то независимо от того, что делает игрок В, ожидаемый (средний) вы­игрыш игрока А в каждой партии будет нулевым.

            Если же игрок А выберет р > 1/2 (так что разность р-1/2 будет положительной), то узнав об этом, игрок В может выбрать q < 1/2 (так что разность q - 1/2 будет отрицательной) и, тем самым, сделать средний выигрыш игрока А отрицательным, то есть заставит его проиграть. Если же игрок А выберет р < 1/2 (так что разность р -1/2 будет отрицательной) и игрок В узнает об этом, то он может выбрать q > 1/2 (так что разность q -1/2 бу­дет положительной) и вновь сделать выигрыш игрока А отрицательным, то есть опять заставит его проиграть.

            Исследуем теперь эту формулу с точки зрения игро­ка В.

            Если игрок А выбирает р = 1/2, то ожидаемый (средний) выигрыш игрока B независимо от его дей­ствий будет нулевым в каждой партии. Но если игрок В выберет q > 1/2 (так что разность q - 1/2 будет положительной), то, узнав об этом, игрок А может выбрать р < 1/2 (так что разность р - 1/2 будет отри­цательной), и тогда игрок В будет проигрывать в каждой партии. Если же игрок В выберет q < 1/2 (так что разность q -1/2 будет отрицательной) и игрок А узнает об этом, то он может выбрать р > 1/2 (так что разность р -1/2 будет положительной) и вновь заставит игрока В проиграть.

Тем самым наборы

,

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

ν = 0.

            Замечание. На рисунке 1 показано, как устроена поверхность, описываемая функцией

Точка

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

            Естественно возникают два ключевых вопроса:

            1-й – какие матричные игры имеют решение в смешанных стратегиях?

            2-й – как находить решение матричной игры, если оно существует?

            Ответы на эти вопросы дают следующие две теоремы.

Основная теорема матричных игр

            Теорема 1 (Дж. фон Нейман). Для матричной игры с любой матрицей А величины

 

равны между собой,

            Более того, существует хотя бы одна ситуация в смешанных стратегиях (Р⁰, Q⁰), для которой выполняется соотношение

            Иными словами, любая матричная игра имеет решение в смешанных стратегиях. По­иск этого решения опирается на следующие установленные факты.      

Основные свойства оптимальных смешанных стратегий  

Теорема 2. Пусть

 и

- оптимальные смешанные стратегии и ν – цена игры,

            Оптимальная смешанная стратегия Р⁰ игрока А смешивается только из тех чистых стратегий А_i, i = 1, 2,..., m, то есть отличными от нуля могут быть вероятности p_i

только с теми номерами i = 1,2, ... , m, для которых выполнены равенства

.

            Это означает, что смешиваются не все чистые стратегии. Аналогично, в оптимальной смешанной стратегии Q⁰ игрока В отличных от нуля могут быть только те вероятности q_k, для номеров k = 1,2, ... , n, которых выполнены равенства

.

            Кроме того, имеют место соотношения

.

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

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

            Наши рассмотрения мы начнем с матричных игр, число стратегий хотя бы одного из игроков в которых равно двум.

            Для построения решений 2 х n и m х 2 игр существует эффективный метод, осно­ванный на простых геометрических соображениях. Этот метод, называют графическим.

           

 2 x n игры

Пусть

- платежная матрица 2 х n игры.

            Согласно теореме о двойном описании игры (теорема 2) нахождение цены игры и оптимального значения р⁰ для игрока А равносильно разрешению уравнения

.

            Опишем общую схему, приводящую к искомому результату.

Максимум функции

                                                (*)

проще всего найти, построив ее график. Для этого поступают следующим образом.

            Предположим, что игрок А выбрал смешанную стратегию Р = {р, 1 - р}, а игрок В - k-ю чистую стратегию, k = 1, 2, ... , n. Тогда средний выигрыш игрока А в ситуации {Р, k} оказывается равным

(k):    .

            На плоскости (р, ω) уравнение (k) описывает прямую. Тем самым, каждой чистой стратегия игрока B на этой плоскости соответствует своя прямая.

            Поэтому сначала на плоскости (ω, р) последовательно и аккуратно рисуются все
прямые

(k):    ,  k = 1, 2, ... , n

(рис.2). Затем для каждого значения р, 0 £ р £ 1, путем визуального сравнения соответствующих ему значений ω на каждой из построенных прямых определяет­ся и отмечается минимальное из них (рис. 3).  В результате описанной процедуры получается ломаная, которая и является графиком функции (*) (выделена жирным на рис. 4). Эта ломаная как бы огибает снизу все семейство построенных прямых,

                               Рис.2                               Рис.3                               Рис.4

и по этой причине ее принято называть нижней огибающей этого семейства. Верхняя  точка построенной нижней огибающей определяет и цену игры – v  и оптимальную стратегию игрока А – Р⁰ = {р⁰, 1 - р⁰} (рис. 5).

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

            Опробуем описанную схему решения 2 х n игры на конкретном примере.

           

            Пример 5. Рассмотрим игру, заданную 2 x 6 матрицей

            Решение.

1-й шаг. Анализ игры на наличие седловой точки.

            Нижняя цена игры равна -1, верхняя цена игры равна 1. Седловой точки нет. Решение игры нужно искать в смешанных стратегиях.

2-й шаг. Вычисление средних выигрышей игрока А (проводится при условии, что игрок В выбирает только чистые стратегии).

Из таблицы

легко получаем:

(1): ω = 6p - 2(1 - p),

(2): ω = 4p -   (1 - p),

(3): ω = 3p +  (1 - p),

(4): ω =   p ,

(5): ω = 6p - 2(1 - p),

(6): ω =         4(1 - p),

3-й шаг. Построение нижней огибающей.

            Аккуратно строим на координатной плоскости (р, ω) все шесть прямых, уравнения которых полу­чены на 2-м шаге (рис. 6), и находим их нижнюю огибающую.

4-й шаг. Отыскание цены игры и оптимальной смешанной стратегии игрока А.

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

ω =  р,

ω = -p + 5(l - p), ,

получаем

,

(рис.7).

                        Рис.5                                 Рис.6                                 Рис.7

Тем самым, цена игры ν и оптимальная стратегия Р⁰ игрока A соответственно равны

, .

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

           

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

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

            Как ищется оптимальная смешанная стратегия игрока А, мы уже описали. Покажем теперь, как отыскать оптимальную смешанную стратегию игрока В.

            Здесь, в зависимости от формы нижней огибающей, может представиться несколь­ко случаев.

            А. Нижняя огибающая имеет ровно одну наивысшую точку (р⁰, ω⁰):

            1) Если р⁰ = 0 (оптимальная стратегия игрока А – чистая стратегия А₂), то игро­ку В выгодно применять чистую стратегию, соответствующую номеру прямой, проходящей через точку (0, ω⁰) и имеющей наибольший отрицательный наклон (рис. 8).

                               Рис.8                                 Рис.9                             Рис.10

            2) Если p⁰ == 1 (оптимальная стратегия игрока А — чистая стратегия А₁), то опти­мальной для игрока В является чистая стратегия, соответствующая номеру прямой, проходящей через точку (1, ω⁰) и имеющей наименьший положительный наклон (рис. 9).

            3) Если 0 < p⁰ < 1, то в наивысшей точке нижней оги­бающей пересекаются, по меньшей мере, две прямые, одна из которых (k-я) имеет положительный наклон, а другая (l-я) — отрицательный (рис. 10), и оптимальная смешан­ная стратегия игрока В получается, если положить

q_k = q, q_l = 1 - q, q_j = 0, j ≠ k, l.

где q – решение уравнения

.

            Б. Нижняя огибающая содержит горизонтальный участок, соответствующий чистой стратегии k⁰ игрока B, которая и является оптимальной для него (рис. 11).

Рис. 11

Пример 5 (продолжение). Покажем теперь, как найти полное решение игры, то есть еще и оптимальную смешанную стратегию

игрока В.

Для этого поступают так:

1) полагают

(выделяя тем самым из шести чистых стратегий игрока В стратегии В₄ и B₅. которым соответствуют прямые (4) и (5), определяющие наивысшую точку нижней огибающей),

2) приравнивают любой из двух средних выигрышей игрока В (игрок А выбирает только чистые стратегии), отвечающих предложенной смешанной стратегии

к цене игры

,

3) получают (в обоих случаях), что

.

Полное решение игры имеет следующий вид

, , .

Замечание. Ситуация с наличием лишь двух конкурирующих стратегий игрока А нельзя считать на­думанной. Она возникает сравнительно часто. Например, в случае, если нужно сравнить два образца некоторого изделия (скажем, старого и модернизированного) с целью выяснения возможности замены, это весьма удобно сделать при помощи платежной матрицы 2 х n.

 m х 2 игры

            Пусть теперь в матричной игре две чистые стратегии имеет игрок В, а число чистых стратегий у игрока А произвольно (равно m). Это означает, что платежная матрица такой игры имеет вид

.

            Анализ такой игры во многом напоминает рассуждения, описанные для игры 2 х n.

Пусть Q = {q, 1 - q} — произвольная смешанная стратегия игрока В. Если игрок А выбирает i-ю чистую стратегию, i = 1, 2, ... , n, то средний выигрыш игрока В в ситуации {i, Q} будет равным

 (i):  i = 1, 2,..., m.                                  (*)

            Зависимость этого выигрыша от переменной q описывается прямой.

            Графиком функции

является верхняя огибающая семейства прямых (*), соот­ветствующих чистым стратегиям игрока А (рис. 12).

Рис.12

            Абсциссой нижней точки полученной ломаной будет значение q⁰, определяющее оптимальную смешанную стра­тегию игрока В, а ординатой ω⁰ – цена игры.

Замечание. Отыскание оптимальной смешанной стратегии игрока А проводится по той же схеме, которая позволяет находить оптимальную смешанную стратегию игрока В в игре 2 х n.

            Рассмотрим конкретный пример.

Пример 6.  3 х 2 игра задана матрицей

.

Решение.

1 шаг. Анализ игры на наличие седловой точки.

Нижняя цена игры равна 0, верхняя цена игры равна 3. Седловой точки нет. Решение игры нужно искать в смешанных стратегиях.

2-й шаг. Вычисление средних выигрышей игрока В (проводится при условии, что игрок А выбирает только чистые стратегии).

Из таблицы

получаем:

(1): ω = 3q –   (1 - q)

(2): ω = -q + 3(1 - q)

(3): ω =  q

3-й шаг. Построение верхней огибающей.

Построим на координатной плоскости (q, ω) все три прямых, а за­тем и их верхнюю огибающую (рис. 13).

Рис. 13

4-й шаг. Отыскание иены игры и оптимальной смешанной стратегии игрока В.

Нижняя точка верхней огибающей является точкой пересечения прямых (1) и (2). Решая систему уравнений

ω = 3q –   (1 - q),

ω = -q + 3(1 - q),

получаем

, .

5-й шаг. Отыскание оптимальной смешанной стратегии игрока А.

Полагая

приравниваем средние выигрыши игрока А, соответствующие чистым выигрышам игрока В,

и находим р⁰ = 1/2.  

Таким образом, цена игры и оптимальные смешанные стратегии игроков А и В соответственно

.

 m х n игры

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

Правило доминирования

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

            Опишем одну из таких возможностей более подробно.

— произвольная m х n-матрица. Будем говорить, что i-я строка матрицы А

a_i1  a_i2   …   a_in

не больше j -и строки этой матрицы

a_j1  a_j2   …   a_jn ,

если одновременно выполнены следующие n неравенств

При этом говорят также, что j -я строка доминирует i-ю строку, или что стратегия A_j игрока А доминирует стратегию А_i.

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

Если в матрице А одна из строк (j -я) доминирует другую строку (i-ю), то число строк в матрице А можно уменьшить путем отбрасывания доминируемой строки (i-й). Далее, будем говорить, что k-й столбец матрицы А

не меньше l-го столбца этой матрицы

если одновременно выполнены следующие m неравенств

При этом говорят также, что 2-й столбец доминирует k-й столбец, или что стратегия В_l игрока В доминирует стратегию В_k.

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

Если в матрице А один из столбцов (l-й) доминирует другой столбец (k-й), то число столбцов в матрице А можно уменьшить путем отбрасывания доминируемого столбца (k-го).

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

Пример 7. Рассмотрим игру с матрицей

.

            Сравнивая строки матрицы, видим, что 1-я строка совпадает с 4-й строкой, или, что то же, стратегия А₄ дублирует стратегию А₁. Тем самым, одну из этих, строк можно вычеркнуть, не нанося ущерба решению

.

            Поэлементна сравнивая 1-ю и 2-ю строки, замечаем, что 1-я строка доминирует 2-ю строку, или, что то же, стратегия А₁ доминирует стратегию А₂. Это вновь позволяет уменьшить число строк матрицы

            Замечая, что 4-й столбец полученной матрицы доминирует ее 3-й столбец, приходим к игре с 2 х 3-матрицей

            Решая эту 2 х 3 игру графическим методом, находим ее решение – цену игры и оптимальные смешанные стратегии игроков А и В:

.

Возвращаясь к исходной 4 x 4 игре, получаем окончательный ответ:

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

Аффинное правило

При поиске решения матричных игр часто оказывается полезным следующее свойство.

Допустимые преобразования матрицы игры и ее цена. Оптимальные стратегии у матричных игр, элементы матриц А и С которых связаны равенствами

с_ik = λа_ik + μ,    i = 1, 2, ... , m;    k = l, 2, ... , n,

 где λ > 0, a μ – произвольно, имеют одинаковые равновесные ситуации (либо в чистых
либо в смешанных стратегиях), а их цены удовлетворяют следующему условию

.

Пример 8. Элементы матриц

 и

связаны равенством

с_ik = 3а_ik + 5,      i= 1, 2;      k = 1, 2, 3.

Поэтому цена игры с матрицей С легко вычисляется

(см. пример 7).

Основные этапы поиска решения матричной игры

            1-й этап – проверка наличия (или отсутствия) равновесия в чистых стратеги­ях (при наличии равновесной ситуации указываются соответствующие оптимальные стратегии игроков и цена игры).

            2-й этап – поиск доминирующих стратегий (в случае успеха этого поиска – отбрасывание доминируемых строк и столбцов в исходной матрице игры).

            3-й этап – замена игры на ее смешанное расширение и отыскание оптимальных  смешанных стратегий и цены игры.

 Итерационный метод решения матричных игр

            Опишем метод отыскания решения матричной игры — цены игры и оптимальных смешанных стратегий, в известной степени верно отражающий некоторую реальную ситуацию накоплении опыта постепенной выработки игроками хороших стратегий в ре­зультате многих повторений конфликтных ситуаций. Основная идея этого метода заключается в том, чтобы мысленно как бы смоделировать реальное практическое «обучение» игроков в ходе самой игры, когда каждый из игроков на собственном опы­те прощупывает способ поведения противника и старается отвечать на него наиболее выгодным для себя образом. Иными словами, всякий раз при возобновлении тигры игрок выбирает наиболее выгодную для себя стратегию, опираясь на предыдущий выбор противника.

            Проиллюстрируем этот метод на примере игры, заданной матрицей

(здесь maxmin = 0, minmax = 2 → седловой точки нет).

            Опишем правила выбора ходов игроками, предположив, для определенности, что начинает игрок А:

ход игрока А — стратегия А₁ — (2   0   3);

игрок В выбирает свою стратегию так, чтобы выигрыш игрока А был минимален (отмечен полужирным шрифтом)

ход игрока В — стратегия В₂ —

игрок А выбирает свою стратегию так, чтобы его выигрыш при стратегии B₂ игрока В был максимален (отмечен полужирным шрифтом):

ход игрока А — стратегия А₂ — (1   3 - 3);

игрок В выбирает свою стратегию так, чтобы «накопленный» выигрыш игрока А при стратегиях А₁ и А₂,

(2   0   3) + (1   3  -3) = (3   3   0),

был минимален:

ход игрока В — стратегия В₃ — ;

игрок А выбирает свою стратегию так, чтобы его «накопленный» выигрыш при стратегиях B₂ и B₁ игрока В,

был максимален:

ход игрока А — стратегия А₁ — (2   0   3);

игрок В выбирает свою стратегию так, чтобы «накопленный» выигрыш игрока А при стратегиях A₁, A₂ и A₁,

(3   3   0) + (2   0   3) = (5   3   3),

был минимален:

ход игрока В — стратегия B₂ —

и т.д.

Разобьем последовательные ходы игроков А и В на пары

(ход игрока А, ход игрока В)

и запишем результаты в таблице

требующей некоторых пояснений.

Описание таблицы

            Решение игры определяется приближенно по окончании любого из шагов.

            Например, за приближенную цену игры можно взять среднее арифметическое ν(n), полученное на n-м шаге. Смешанные стратегии противников определяются частотами появления чистых стратегий.

            После 9-го шага имеем

ν(9) = l,00.

            При этом игрок А 6 раз использовал стратегию А₁ и 3 раза стратегию А₂. В свое очередь игрок B 6 раз применял стратегию В₂, 3 раза стратегию В₃, а стратегией В₁ не пользовался вообще. Отсюда получаем, что

,  

Соответственно, после 10-го шага получаем —

.

Данная игра легко решается графически. Вот точный ответ:

.

Сравнивая результаты, полученные на 9-м, 10-м, а также 11-м и 12-м шагах:

замечаем, что по мере увеличения числа шагов значения все меньше отличаются от точных.

Сделаем несколько замечаний.

            Замечание 1. При увеличении числа шагов все три величины v_*(n), v*(n) и v(n) будут приближаться к цене игры v, но среднее арифметическое v(n) будет приближаться к v сравнительно быстрее.

            Замечание 2. Хотя сходимость итераций весьма медленна, тем не менее, даже такой небольшой расчет всегда дает возможность находить ориентировочное значение цены игры и доли чистых стратегий.

            Замечание 3. Сравнительно медленная скорость сходимости можно объяснить целым рядом причин. Укажем одну из них, психологически наиболее интересную. Если, к примеру, игрок А уже получил оптимальную смешанную стратегию, то он не склонен останавливаться на ней.  Отнюдь нет — он продолжит попытки выиграть у противника В побольше, особенно если последний еще не достиг оптимальной смешанной стратегии. Тем самым, игрок А может невольно ухудшить свое положение.

            Замечание 4. Отметим два основных преимущества описанного метода:

1) итерационный метод прост и одновременно универсален (при его помощи можно легко найти приближенное решение любой матричной игры),

2) объем и сложность вычислений сравнительно слабо растут по мере увеличения числа стратегий игроков (размеров матрицы игры).

Сведение матричной игры к задаче линейного программирования

            Рассмотрим m x n игру с платежной матрицей

A = (a_ik).

            Без ограничения общности будем считать, что все элементы матрицы А положительны (этого всегда можно добиться, пользуясь аффинным правилом, преобразую­щим заданную матрицу игры, но не изменяющим оптимальных смешанных стратегий игроков). Тем самым, искомая цена игры v — положительное число.

           

            Интересы игрока А

            Из теоремы о свойствах оптимальных смешанных стратегий игроков вытекает, что при любой чистой стратегии В_k игрока В, k = 1, 2, ... , n, оптимальная смешан­ная стратегия Р = {p₁, p₂, … , p_m} игрока А обеспечивает его средний выигрыш, не меньший v. Иными словами, выполняются соотношения

которые с учетом обозначений

можно записать так

            Поскольку игрок А стремится сделать гарантированный выигрыш макси­мально возможным, то задача отыскания решения матричной игры сводится к следу­ющей задаче:

найти неотрицательные величины х₁, x₂, ... , х_m, удовлетворяющие неравенствам

и такие, что их сумма минимальна

.

Интересы игрока B

            Аналогичным образом заключаем, что оптимальная смешанная стратегия Q = {q₁, q₂, … , q_n} игрока В при любой чистой Стратегии А₁ игрока A, i = 1, 2,... , m, обеспечивает его средний проигрыш, не больший v. Иными словами, выполняются соотно­шения

которые с учетом обозначений

можно записать так

            Поскольку игрок В стремится сделать свой гарантированный проигрыш мини­мально возможным, то задача отыскания решения матричной игры сводится к следу­ющей задаче:

            найти неотрицательные величины у₁,у₂, ... , у_n, удовлетворяющие неравенствам

и такие, что их сумма максимальна

            Тем самым, мы получаем следующий важный результат.

            Теорема 3. Решение матричной игры с положительной платежной матрицей (а_ik) равно­сильно решению двойственных задач линейного программирования

(A)                ,     

(B)                ,    

            При этом цена игры

,

где Θ — величина, обратная общему значению оптимальных сумм,

а оптимальные значения  и  связаны с оптимальными  и  посредством равенств

            Алгоритм решения матричной игры

            1-й шаг. Ко всем элементам исходной матрицы игры прибавляется одно и то же положительное число γ так, чтобы все элементы новой матрицы были строго положи­тельны.

            2-й шаг. Решаются двойственные задачи линейного программирования (А) и (В) (например, симплекс-методом, или как-нибудь иначе). Находятся наборы , и число Θ.

            3-й шаг. Строятся оптимальные смешанные стратегии игроков А и В соответствен­но

            4-й шаг. Вычисляется цена игры

            Пример 9. Рассмотрим 2 x 2 игру с матрицей

Соответствующие ей задачи линейного программирования имеют вид

            Решение.

            1-й шаг. Все элементы платежной матрицы положительны.

            2-й шаг. Строим решения обеих задач линейного программирования, пользуясь графическим ме­тодом. В результате получаем, что

            3-й шаг.

            4-й шаг.

4. Примеры задач, сводимых к матричным играм

            В чистом виде антагонистические конфликты встречаются редко (разве только в бо­евых действиях и в спортивных состязаниях).  Однако довольно часто конфликты» в которых интересы сторон противоположны, при допущении, что множество спосо­бов действия сторон конечно, можно моделировать матричными играми.

            Рассмотрим несколько конкретных ситуаций.

            Пример 10. «Планирование поема» . Сельскохозяйственное предприятие имеет возможность выращивать две культуры — А₁ и А₂. Необходимо определить, как сеять эти культуры, если при прочих равных, условиях их урожаи зависят от погоды, а план посева должен обеспечить наибольший доход (прибыль от реализации выращенной культуры определяется полученным объемом). В зоне рискованного земле­делия (а таковой является большая часть России) планирование посева должно осуществляться с учетом наименее благоприятного состояния погоды.

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

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

            Налицо антагонистический конфликт, в котором у игрока А две стратегии — А₁ и А₂, а у игрока В три — В₁ (засушливое лето), В₂ (нормальное лето) и В₃ (дождливое лето).

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

.

            Нетрудно заметить, что седловой точки у этой матрицы нет. Поэтому оптимальная стратегия игрока А будет смешанной. Применяя графический метод, получаем

.

            Замечание. Здесь мы столкнулись со сравнительно редкой ситуацией, когда оптимальная смешан­ная стратегия одного из игроков допускает так называемую «физическую» реализацию. Полученное решение сельскохозяйственное предприятие может использовать так:

            на  всех площадей выращивать культуру А₁,

            на  всех площадей выращивать культуру A₂

и получать прибыль в размере, не меньшем  млрд руб.

            Пример 11. «Переговоры о заключении контракта между профсоюзом и администрацией» . Рассмотрим фир­му, администрация которой ведет переговоры с профсоюзом рабочих и служащих о заключении кон­тракта.

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

            Выплаты указаны в центах в час и представляют собой среднюю зарплату служащего фирмы вместе со всеми добавками. Тем самым, заданная матрица описывает прибыль профсоюза (игрок А) и затраты администрации фирмы (игрок В).

            Ясно, что профсоюз стремится максимизировать доходы рабочих и служащих, в то время как ад­министрации хотелось бы минимизировать собственные потери.

            Нетрудно заметить, что седловой точки у платежной матрицы нет. Кроме того, для дальнейшего анализа существенными являются лишь стратегии А₁ и А₄ игрока А и стратегии В₃ и В₄ игрока В (в этом нетрудно убедиться, воспользовавшись правилом доминирования стратегий). В результате со­ответствующего усечения получим матрицу

.

            Элементы матрицы

связаны с элементами предыдущей матрицы соотношениями

65 + 5 х 4 + 45,   45 = 5 х 4 + 45,   50 = 5 х 1 + 45,   55 = 5 х 2 +45.

            Воспользовавшись графическим методом, в итоге получим

            Тем самым, профсоюзу следует выбирать стратегию А₁ в 20 % случаев и стратегию А₄ в 80 %. Что касается администрации, то ей следует выбирать стратегию В₃ с вероятностью 0,4 и стратегию В₄ с вероятностью 0,6. При этом ожидаемая цена игры равна 53.

            Замечание. Следует отметить, что если процесс переговоров будет повторяться много раз, то среднему должно сходиться к ожидаемому значению 53. Если же переговоры пройдут лишь единожды, то ре­альный результат подучится при выборе каждым игроком некоторой своей чистой стратегии. Поэтому один из игроков, профсоюз или администрация, будет неудовлетворен.

            Пример 12. «Локальный конфликт». Рассмотрим войну между двумя небольшими государствами А и В, которая ведется в течение 30 дней.

            Для бомбардировки небольшого моста — важного военного объекта страны В — страна А исполь­зует оба имеющихся у нее самолета. Разрушенный мост восстанавливается в течение суток, а каждый самолет совершает один полет в день по одному из двух воздушных маршрутов, соединяющих эти стра­ны. У страны В есть два зенитных орудия, при помощи которых можно сбивать самолеты страны А. Если самолет собьют, то некая третья страна в течение суток поставит стране А новый самолет.

            Страна А может послать самолеты либо по одному маршруту, либо по разным. Страна В может поместить либо обе зенитки на одном маршруте, либо по одной зенитке на каждый маршрут.

            Если один самолет летит по маршруту, на котором расположена одна зенитка, то этот самолет бу­дет сбит. Если два самолета летят по маршруту, на котором расположены две зенитки, то оба самолета будут сбиты. Если два самолета летят по маршруту, на котором расположена одна зенитка, то сбит будет только один самолет. Если самолет доберется до цели, то мост будет уничтожен.

            У страны А есть две стратегии:

послать самолеты по разным маршрутам — А₁,

послать самолеты по одному маршруту — А₂.

У страны В — также две стратегии:

поместить зенитки на разных маршрутах — В₁,

поместить зенитки на одном маршруте — В₂.

            Если страна А выберет стратегию А₁, а страна В — стратегию В₁, то страна А получит нулевой выигрыш, так как ни один из самолетов не достигнет цели.

            Если страна А выберет стратегию А₂, а страна В — стратегию В₁, то хота бы один самолет достигнет цели и вероятность разрушения моста будет равна 1.

            Если страна А выберет стратегию А₁, а страна В — стратегию В₂, то вновь хотя бы один самолет достигнет цели и вероятность разрушения моста будет равна 1.

            Если страна А выберет стратегию А₂, а страна В — стратегию В₂, то страна А с вероятно­стью 1/2 выберет маршрут, на котором установлены зенитки, и, следовательно, цель будет уничтожена с вероятностью 1/2.

            Оформим результаты проведенного анализа в стандартной игровой форме:

            При помощи графического метода получаем оптимальные смешанные стратегии игроков и цену игры

            Это означает, что если страна А будет посылать самолеты по разным маршрутам в течение десяти дней из тридцати, отпущенных на войну (и, значит, по одному маршруту в течение двадцати дней), то в среднем страна А будет иметь 66,7 % удачных случаев (мост будем находиться в нерабочем состо­янии). Воспользовавшись для своих зениток предложенным выбором, страна В не позволит бомбить мост чаще, чем в 66,7 % случаев.

Несколько слов в заключение

            Матричные игры моделируют конфликтные ситуации, в которых каждая из сторон-участниц делает свой ход одновременно со второй стороной. При этом наибольший интерес представляет случай, когда игра не заканчивается сразу же после совершения игроками одной такой пары одновременных ходов, а повторяется многократно. При­чем считается, что перед каждым возобновлением игры игроки не получают никаких новых сведений ни о конфликте, ни о возможных действиях противной стороны. Ины­ми словами, при многократном повторении матричной игры каждая из сторон всякий раз оказывается перед выбором некоторой стратегии из одного и того же множества стратегий, неизменного у каждого из игроков.

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

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

            Если игра повторяется много раз, то некоторые дополнительные сведения — какие именно стратегии выбирает противная сторона и какими правилами выбора стратегий она руководствуется — игрок все же получает. На основании этих сведений и резуль­татов предварительного анализа игры он может довольно точно оценить противника и, если тот не придерживается компромиссного максиминного подхода, внести соот­ветствующие изменения в собственную линию поведения и увеличить выигрыш.

6. О классификации игр

            Реальные конфликтные ситуации приводят к различным видам игр. К настоящему времени общепризнанной классификации игр пока не сложилось. Тем не менее, легко заметить, что игры различаются по целому ряду признаков: по количеству участвующих в них игроков, по количеству возможных стратегий, по характеру взаимоотношений между игроками, по характеру выигрышей, по виду функций выигрышей, по количеству ходов, по характеру информационной обеспеченности игроков и т. д.

            Остановимся на этих различиях чуть подробнее.

            В зависимости от количества игроков определяют игры трех типов: игры одного  игрока (в теории игр, как правило, не рассматриваются), игры двух игроков (наиболее  изученный класс игр) и игры n игроков (успехов в изучении которых сравнительно немного вследствие возникающих принципиальных трудностей).

            По количеству стратегий игроков игры делятся на конечные (каждый из игроков  имеет конечное число возможных стратегий) и бесконечные (где хотя бы один из игроков имеет бесконечное количество возможных стратегий).

            По характеру взаимоотношений между игроками игры делятся на бескоалиционные (в которых игроки не имеют права вступать в соглашения и образовывать коалиции), коалиционные (в которых игроки могут вступать в соглашения и образовывать коа­лиции) и кооперативные (в которых соглашения, связывающие игроков, определены наперед и обязательны):

            По характеру выигрышей различают игры с нулевой суммой (общий капитал игроков не изменяется, а просто перераспределяется между игроками в зависимости от полу­чающихся исходов) и игры с ненулевой суммой.

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

            По виду функций выигрышей игры делятся на: матричные игры (рассмотренные выше), биматричные игры, игры типа дуэлей, непрерывные игры, выпуклые игры и др.

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

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

Обратите внимание на лекцию "23 Туберкулезный плеврит".

            Существуют, разумеется, и другие виды игр.

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

            Впрочем, возможны и иные подходы к разбиению игр.

            Далее мы рассмотрим некоторые из указанных видов игр, а именно позиционные и биматричные игры.

---

[1] Экстремальные величины   всегда существуют вследствие того, что функция  является непрерывной на замкнутом множестве

,  ,  ,  .