Матричная игра двух игроков с нулевой суммой может рассматриваться как следующая абстрактная игра двух игроков.
Первый игрок имеет m стратегий i = 1,2,...,m , второй имеет n стратегий j = 1,2,...,n . Каждой паре стратегий (i , j ) поставлено в соответствие число а ij , выражающее выигрыш игрока 1 за счёт игрока 2, если первый игрок примет свою i - ю стратегию, а 2 – свою j -ю стратегию.
Каждый
из игроков делает один ход: игрок 1
выбирает свою i
-ю
стратегию (i
=
),
2–
свою j
-ю
стратегию (j
=
),
после чего игрок 1 получает выигрыш а
ij
за счёт игрока 2 (если а
ij
<
0, то это значит, что
игрок 1 платит второму сумму |а
ij
|).
На этом игра заканчивается.
Каждая
стратегия игрока i
=
;
j
=
часто называется чистой стратегией.
Если рассмотреть матрицу
А
=
то проведение каждой партии матричной игры с матрицей А сводится к выбору игроком 1 i -й строки, а игроком 2 j -го столбца и получения игроком 1 (за счёт игрока 2) выигрыша а ij .
Главным
в исследовании игр является понятие
оптимальных стратегий игроков. В это
понятие интуитивно вкладывается такой
смысл: стратегия игрока является
оптимальной, если применение этой
стратегии обеспечивает ему наибольший
гарантированный выигрыш при всевозможных
стратегиях другого игрока. Исходя из
этих позиций, игрок 1 исследует матрицу
выигрышей А
следующим образом: для каждого значения
i
(i
=
)
определяется минимальное значение
выигрыша в зависимости от применяемых
стратегий игрока 2
а
ij
(i
=
)
т.е. определяется минимальный выигрыш для игрока 1 при условии, что он примет свою i -ю чистую стратегию, затем из этих минимальных выигрышей отыскивается такая стратегия i = i о , при которой этот минимальный выигрыш будет максимальным, т.е. находится
а
ij
=
=
(1)
Определение
.
Число 
,
определённое по формуле (1) называется
нижней чистой
ценой
игры
и показывает, какой минимальный выигрыш
может гарантировать себе игрок 1, применяя
свои чистые стратегии при всевозможных
действиях игрока 2.
Игрок 2 при оптимальном своём поведении должен стремится по возможности за счёт своих стратегий максимально уменьшить выигрыш игрока 1. Поэтому для игрока 2 отыскивается
а
ij
т.е. определяется max выигрыш игрока 1, при условии, что игрок 2 применит свою j -ю чистую стратегию, затем игрок 2 отыскивает такую свою j = j 1 стратегию, при которой игрок 1 получит min выигрыш, т.е. находит
a
ij
=
=
(2).
Определение
.
Число 
,
определяемое по формуле (2), называется
чистой верхней
ценой
игры
и показывает, какой максимальный выигрыш
за счёт своих стратегий может себе
гарантировать игрок 1.
Другими
словами, применяя свои чистые стратегии
игрок 1 может обеспечить себе выигрыш
не меньше 
,
а игрок 2 за счёт применения своих чистых
стратегий может не допустить выигрыш
игрока 1 больше, чем 
.
Определение
.
Если в игре с матрицей А 
=
,
то говорят, что эта игра имеет седловую
точку
в чистых стратегиях и чистую
цену
игры
=
=
.
Седловая
точка
–
это пара чистых стратегий (i
о
,
j
о
)
соответственно игроков 1 и 2, при которых
достигается равенство 
=
.
В это понятие вложен следующий смысл:
если один из игроков придерживается
стратегии, соответствующей седловой
точке, то другой игрок не сможет поступить
лучше, чем придерживаться стратегии,
соответствующей седловой точке.
Математически это можно записать и
иначе:
где i , j – любые чистые стратегии соответственно игроков 1 и 2; (i о , j о ) – стратегии, образующие седловую точку.
Таким
образом, исходя из (3), седловой элемент
является минимальным в i о -й
строке и максимальным в j о -м
столбце в матрице А. Отыскание седловой
точки матрицы А происходит следующим
образом: в матрице А последовательно в
каждой строке
находят минимальный элемент и проверяют,
является ли этот элемент максимальным
в своём столбце
.
Если да, то он и есть седловой элемент,
а пара стратегий, ему соответствующая,
образует седловую точку. Пара чистых
стратегий (i
о
,
j
о
)
игроков 1 и 2, образующая седловую точку
и седловой элемент 
,
называется решением
игры
. При
этом i
о
и j
о
называются оптимальными
чистыми
стратегиями
соответственно
игроков 1 и 2.
Пример 1
Седловой
точкой является пара (i
о
= 3;j
о
= 1), при которой =
=
= 2.
Заметим,
что хотя выигрыш в ситуации (3;3) также
равен 2 =
=
,
она не является седловой точкой, т.к.
этот выигрыш не является максимальным
среди выигрышей третьего столбца.
Пример 2
Из
анализа матрицы выигрышей видно, что
,
т.е. данная матрица не имеет седловой
точки. Если игрок 1 выбирает свою чистую
максиминную стратегию i
= 2, то игрок 2,
выбрав свою минимаксную
j
= 2, проиграет только
20. В этом случае игроку 1 выгодно выбрать
стратегию i
= 1, т.е. отклониться от своей чистой
максиминной стратегии и выиграть 30.
Тогда игроку 2 будет выгодно выбрать
стратегию j
= 1, т.е. отклониться от своей чистой
минимаксной стратегии и проиграть 10. В
свою очередь игрок 1 должен выбрать свою
2-ю стратегию, чтобы выиграть 40, а игрок
2 ответит выбором 2-й стратегии и т.д.
Рассмотрим пример. Пусть дана матрица игры (4):
Требуется найти нижнюю цену игры α, верхнюю цену игры β и минимаксные стратегии и проверить, являются ли они устойчивыми. Решение. Из анализа дополнительных столбца и строки получаем: α = 5, β = 5. Максимин равен минимаксу! Случай особый. Что же из этого следует? Возьмем пару минимаксных стратегий: К 2 и С 3 . Если оба держатся этих стратегий, то выигрыш будет равен 5. Теперь, допустим, мы узнали о поведении противника. Что будем делать? А ничего! Мы по-прежнему будем держаться стратегии К 2 , потому что любое отступление от нее нам невыгодно. Знаем мы или не знаем о поведении противника - все равно будем держаться стратегии К 2 ! То же относится и к «синим» - им нет смысла менять свою стратегию С 3 . В данном примере пара стратегий К 2 и С 3 устойчива, т. е. представляет собой положение равновесия и дает решение игры. Почему так получилось? Потому что в матрице имеется особый элемент 5; он является минимальным в своей строке и одновременно максимальным в своем столбце. Такой элемент называется седловой точкой . Если матрица имеет седловую точку (т. е. нижняя цена игры равна верхней), то игра имеет решение в чистых стратегиях: это - пара стратегий, пересекающихся в седловой точке. Сама же седловая точка дает цену игры - в нашем примере она равна 5. Класс игр, имеющих седловую точку, имеет большое значение в теории игр. В частности, доказано, что если по правилам игры каждый из игроков знает результат всех предыдущих ходов, как своих, так и противника (так называемая игра с полной информацией), то игра имеет седловую точку и, значит, имеет решение в чистых стратегиях . Примерами игр с полной информацией могут служить: шахматы, шашки, «крестики и нолики» и т. п. Приведем пример игры с полной информацией, решение которой легко найти. Два игрока - К и С - поочередно кладут одинаковые монеты на круглый стол. Положение каждой монеты выбирается произвольно, лишь бы она не перекрывалась другими. Выигрывает тот из игроков, который положит монету последним (когда места для других уже не остается). Стоит немножко подумать, чтобы убедиться, что исход этой игры всегда предрешен и что существует вполне определенная стратегия, гарантирующая выигрыш тому из игроков, который кладет монету первым (пусть это будет К). А именно К должен положить первую монету в центр стола, а далее на каждый ход С отвечать в точности симметричным относительно центра стола ходом! Бедный С может при этом вести себя как угодно, спасения ему все равно нет... Очевидно, такая игра имеет смысл только для тех, кто не знает решения. Любопытно, что совершенно так же обстоит дело и с такой популярной игрой, как шахматы! Эта игра имеет смысл только до тех пор, пока не найдено ее решение. Теоретически доказано, что решение существует и исход шахматной игры в сущности предрешен: если каждая сторона будет пользоваться своей оптимальной стратегией, то игра либо всегда будет кончаться выигрышем белых, либо всегда выигрышем черных, либо всегда ничьей! Но чем же именно? Мы пока этого не знаем, так как число возможных стратегий слишком велико, чтобы можно было построить матрицу шахматной игры и найти в ней седловую точку... Наверное, любители шахмат заинтересованы в том, чтобы шахматная игра была решена еще не скоро. Заметим в заключение, что седловых точек в матрице может быть не одна, а несколько; тог да решений игры в чистых стратегиях существует столько, сколько имеется седловых точек. Каждое из них дает выигрыш, равный цене игры.
Описание биматричной игры . Все игры которые были рассмотрены, относились к классу игр с нулевой суммой . Однако ряд конфликтных ситуаций, складывающихся в ходе действий, характерны тем, что выигрыш одной стороны не равен в точности проигрышу другой. Теоретико-игровыми моделями подобных ситуаций являются некооперативные игры с ненулевой суммой. Такие игры называются биматричными , потому что задание каждой такой игры сводится к заданию двух матриц и одинаковой формы: .
Процесс биматричной игры состоит в независимом выборе игроком I числа а игроком II - числа , после чего игрок I получает выигрыш , а игрок II - выигрыш .
Номера строк матриц и назовем чистыми стратегиями игрока
I, а номера столбцов этих матриц – чистыми стратегиями игрока
II. Тогда пары вида будут являться ситуациями в чистых стратегиях биматричной игры
, а числа и - выигрышами I и II игроков в ситуации . Соответственно, распределение вероятностей применения чистых стратегий игрока I - 
и игрока II - 
будем называть смешанными стратегиями
. Тогда пары вида представляют ситуации биматричной игры
в смешанных стратегиях
, а числа 
и 
являются математическими ожиданиями выигрыша I и II игроков.
Ситуацией равновесия биматричной игры в смешанных стратегиях будем называть такую пару , при которой:
 |
(8.2) |
где - математическое ожидание выигрыша игрока I;
Математическое ожидание выигрыша игрока II;
Оптимальная смешанная стратегия игрока I;
Оптимальная смешанная стратегия игрока II.
Задача
Построение и решение биматричной игры . Предположим, что противолодочная подводная лодка страны осуществляет поиск ракетной подводной лодки государства , которая маневрирует в строго определенной части района боевого патрулирования. В остальной части этого района действует противолодочная подводная лодка , которая осуществляет поиск противолодочной подводной лодки . Пусть каждая противолодочная лодка для обнаружения противника может использовать свою гидроакустическую станцию или в активном режиме, включая ее периодически, или только в пассивном режиме, выполняя непрерывный поиск .
Как противолодочная подводная лодка , так и ракетная подводная лодка с обнаружением сигналов гидролокатора может уклониться от противника. Однако периодичность включения гидролокатора делает обнаружение возможным, но недостоверным.
В подобной конфликтной ситуации одним из игроков является противолодочная подводная лодка , а другим - противолодочная подводная лодка .Очевидно, ракетная подводная лодка не может быть игроком, так как она имеет только один способ действий, заключающийся в скрытом маневрировании и выполнении уклонения с обнаружением сигналов гидролокаторов.
Характерным здесь является то, что каждый из игроков преследует разные, но не противоположные цели. Действительно, целью противолодочной подводной лодки является обнаружение ракетной подводной лодки, а целью противолодочной подводной лодки - обнаружение противолодочной подводной лодки . Поэтому для оценки достижения цели каждым из игроков в зависимости от выбранных способов действий (стратегий) необходимо иметь два критерия эффективности и соответственно две функции выигрыша. Тогда моделью подобной конфликтной ситуации будет конечная игра
с ненулевой суммой, описываемая двумя матрицами одинаковой формы 
и 
, называемая биматричной.
Примем за критерий эффективности противолодочной подводной лодки (игрок I) вероятность обнаружения ракетной подводной лодки , а за критерий эффективности противолодочной подводной лодки (игрок II) – вероятность обнаружения противолодочной подводной лодки . Тогда биматричная игра будет задана матрицей (рисунок 9.a) и матрицей (рисунок 9.b).
Рис. 9.a.
Рис. 9.b.
Где - использование активного режима;
Использование пассивного режима.
Если игра не имеет седловой точки, то возникают затруднения в определении цены игры и оптимальных стратегий игроков. Рассмотрим, например, игру:
В этой игре и . Следовательно, первый игрок может гарантировать себе выигрыш, равный 4, а второй может ограничить свой проигрыш 5. Область между и является как бы ничейной и каждый игрок может попытаться улучшить свой результат за счет этой области. Каковы же должны быть в этом случае оптимальные стратегии игроков?
Если каждый из игроков применяет отмеченную звездочкой стратегию (и ), то выигрыш первого игрока и проигрыш второго будут равны 5. Это невыгодно второму игроку, так как первый выигрывает больше, чем оно может себе гарантировать. Однако если второй игрок каким-либо образом раскроет замысел первого о намерении использовать стратегию , то он может применить стратегию и уменьшить выигрыш первого до 4. Правда, если первый игрок раскроет замысел второго применить стратегию , то, используя стратегию , он увеличит свой выигрыш до 6. Таким образом, возникает ситуация, когда каждый игрок должен хранить в секрете ту стратегию, которую он собирается использовать. Однако, как это сделать? Ведь если партия играется многократно и второй игрок применяет все время стратегию , то первый игрок скоро разгадает замысел второго и, применив стратегию , будет иметь добавочный выигрыш. Очевидно, что второй игрок должен менять стратегию в каждой новой партии, но делать это он должен так, чтобы первый не догадался, какую стратегию применит он в каждом случае.
Для механизма случайного выбора выигрыши и проигрыши игроков будут случайными величинами. Результат игры в этом случае можно оценить средней величиной проигрыша второго игрока. Вернемся к примеру. Так, если второй игрок использует стратегию и случайным образом с вероятностями 0.5; 0.5, то при стратегии первого игрока среднее значение его проигрыша будет:
а при стратегии первого игрока
Следовательно, второй игрок может ограничить свой средний проигрыш значением 4,5 независимо от стратегии, применяемой первым игроком.
Таким образом, в ряде случаев оказывается целесообразным не намечать заранее стратегию, а выбирать ту или иную случайным образом, используя какой-либо механизм случайного выбора. Стратегию, основанную на случайном выборе, называют смешанной стратегией , в отличие от намеченных стратегий, которые называются чистыми стратегиями .
Дадим более строгое определение чистых и смешанных стратегий.
Пусть имеется игра без седловой точки:
Обозначим частоту использования чистой стратегии первого игрока через , (вероятность использования i-ой стратегии). Аналогично обозначим частоту использования чистой стратегии второго игрока через , (вероятность использования j-ой стратегии). Для игры с седловой точкой существует решение в чистых стратегиях . Для игры без седловой точки существует решение в смешанных стратегиях, то есть когда выбор стратегии осуществляется на основании вероятностей. Тогда
Множество чистых стратегий 1-го игрока;
Множество смешанных стратегий 1-го игрока;
Множество чистых стратегий 2-го игрока;
Множество смешанных стратегий 2-го игрока.
Рассмотрим пример: пусть имеется игра
Второй игрок выбирает вероятность 
. Оценим средний проигрыш второго игрока при применении им стратегий и соответственно.
Если в игре каждый из противников применяет только одну и ту же стратегию, то про саму игру в этом случае говорят, что она происходит в чистых стратегиях , а используемые игроком А и игроком В пара стратегий называются чистыми стратегиями .
Определение. В антагонистической игре пара стратегий (А i , В j) называется равновесной или устойчивой, если ни одному из игроков не выгодно отходить от своей стратегии.
Применять чистые стратегии имеет смысл тогда, когда игроки А и В располагают сведениями о действиях друг друга и достигнутых результатах. Если допустим, что хотя бы одна из сторон не знает о поведении противника, то идея равновесия нарушается, и игра ведется бессистемно.
Рассмотрим матричную игру G (3х4)
В этом примере нижняя цена игры равна верхней: ==9, т.е. игра имеет седловую точку.
Оказывается, что в этом случае максиминные стратегии А 2 и В 2 будут устойчивыми по отношению к информации о поведении противника.
Действительно, пусть игрок А узнал, что противник применяет стратегию В 2 . Но и в этом случае игрок А будет по-прежнему придерживаться стратегии А 2 , потому что любое отступление от стратегии А 2 только уменьшит выигрыш. Равным образом, информация, полученная игроком В , не заставит его отступить от своей стратегии В 2 .
Пара стратегий А 2 и В 2 обладает свойством устойчивости, а выигрыш (в рассматриваемом примере он равен 9), достигаемый при этой паре стратегий, оказывается седловой точкой платежной матрицы.
Признак устойчивости (равновесности) пары стратегии - это равенство нижней и верхней цены игры.
Стратегии А i и В j (в рассматриваемом примере А 2 , В 2), при котором выполняется равенство нижней и верхней цены игры, называются оптимальными чистыми стратегиями, а их совокупность - решением игры. Про саму игру в этом случае говорят, что она решается в чистых стратегиях.
Величина называется ценой игры.
Если 0, то игра выгодна для игрока А, если 0 - для игрока В; при =0 игра справедлива, т.е. является одинаково выгодной для обоих участников.
Однако наличие седловой точки в игре - это далеко не правило, скорее - исключение. Большинство матричных игр, не имеет седловой точки, а следовательно, не имеет оптимальных чистых стратегий. Впрочем, есть разновидность игр, которые всегда имеют седловую точку и, значит, решаются в чистых стратегиях. Это - игры с полной информацией.
Теорема 2. Каждая игра с полной информацией имеет седловую точку, а следовательно, решается в чистых стратегиях, т.е. имеется пара оптимальных чистых стратегий, дающая устойчивый выигрыш, равный.
Если такая игра состоит только из личных ходов, то при применении каждым игроком своей оптимальной чистой стратегии она должна кончаться выигрышем, равным цене игры. Скажем, шахматная игра, как игра с полной информацией, либо всегда кончается выигрышем белых, либо всегда - выигрышем черных, либо всегда - ничьей (только чем именно - мы пока не знаем, так как число возможных стратегий в шахматной игре огромно).
Если матрица игры содержит седловую точку, то ее решение сразу находится по принципу максимина.
Возникает вопрос: как найти решение игры, платежная матрица которой не имеет седловой точки? Применение максиминного принципа каждым из игроков обеспечивает игроку А выигрыш не менее, игроку - проигрыш не больше. Учитывая что, естественно для игрока А желание увеличить выигрыш, а для игрока В - уменьшить проигрыш. Поиск такого решения производит к необходимости применять смешанные стратегии: чередовать чистые стратегии с какими-то частотами.
Определение. Случайная величина, значениями которой являются чистые стратегии игрока, называется его смешанной стратегией .
Таким образом, задание смешанной стратегии игрока состоит в указании тех вероятностей, с которыми выбираются его чистые стратегии.
Будем обозначать смешанные стратегии игроков А и В соответственно
S A =||p 1 , p 2 , ..., p m ||,
S B =||q 1 , q 2 , ..., q n ||,
где p i - вероятность применения игроком А чистой с тратегии А і ; ; q j - вероятность применения игроком В чистой стратегии B j ; .
В частном случае, когда все вероятности, кроме одной, равны нулю, а эта одна - единице, смешанная стратегия превращается в чистую.
Применение смешанных стратегий осуществляется, например, таким образом: игра повторяется много раз, но в каждой партии игрок применяет различные чистые стратегии с относительными частотами их применения, равными p i и q j .
Смешанные стратегии в теории игр представляют собой модель изменчивой, гибкой тактики, когда ни один из игроков не знает, какую чистую стратегию выберет противник в данной партии.
Если игрок А применяет смешанную стратегию S A =||p 1 , p 2 , ..., p m ||, а игрок В смешанную стратегию S B =||q 1 , q 2 , ..., q n ||, то средний выигрыш (математическое ожидание) игрока А определяется соотношением
Естественно, что ожидаемый проигрыш игрока В равен такой же величине.
Итак, если матричная игра не имеет седловой точки, то игрок должен использовать оптимальную смешанную стратегию, которая обеспечит максимальный выигрыш.
Естественно возникает вопрос: какими соображениями нужно руководствоваться при выборе смешанных стратегий? Оказывается принцип максимина сохраняет свое значение и в этом случае. Кроме того, важное значение для понимания решения игр, играют основные теоремы теории игр.
Различают
стратегии чистые и смешанные. Чистая
стратегия
первого игрока (чистая стратегия
второго игрока) – это возможный ход
первого (второго) игрока, выбранный им
с вероятностью, равной 1.
Если
первый игрок имеет m
стратегий, а второй – n
стратегий, то для любой пары стратегий
первого и второго игроков чистые
стратегии можно представить в виде
единичных векторов. Например, для пары
стратегий
,
чистые стратегии первого и второго
игроков запишутся в виде:
,
.
Для пары стратегий
,
чистые стратегии можно записать в виде:
,
.
Теорема
:
В матричной игре нижняя чистая цена
игры не превосходит верхней чистой цены
игры, т. е.
.
Определение:
Если для
чистых стратегий
,
игроковA
и В соответственно имеет место равенство
,
то пару чистых стратегий (
,
)
называют седловой точкой матричной
игры, элемент
матрицы, стоящий на пересеченииi-й
строки и j-го
столбца – седловым элементом платежной
матрицы, а число
- чистой ценой игры.
Пример: Найти нижнюю и верхнюю чистые цены, установить наличие седловых точек матричной игры
.
Определим
нижние и верхние чистые цены игры:
,
,
.
|
|
|||||
|
|
В
данном случае имеем одну седловую точку
(А 1 ;
В 2),
а седловой элемент равен 5. Этот элемент
является наименьшим в 1-й строке и
наибольшим во 2-м столбце. Отклонение
игрока А от максиминной стратегии А 1
ведет к уменьшению его выигрыша, а
отклонение игрока В от минимаксной
стратегии В 2
ведет к увеличению его проигрыша. Иными
словами, если в матричной игре имеется
седловой элемент, то наилучшими для
игроков являются их минимаксные
стратегии. И эти чистые стратегии,
образующие седловую точку и выделяющие
в матрице игры седловой элемент a 12 =5,
есть оптимальные чистые стратегии
и
соответственно игроков А и В.
Если
же матричная игра не имеет седловой
точки, то решение игры затрудняется. В
этих играх
.
Применение минимаксных стратегий в
таких играх приводит к тому, что для
каждого из игроков выигрыш не превышает
,
а проигрыш - не меньше
.
Для каждого игрока возникает вопрос
увеличения выигрыша (уменьшение
проигрыша). Решение находят, применяя
смешанные стратегии.
Определение:
Смешанной
стратегией первого (второго) игрока
называется вектор
,
где
и
(
,
где
и
).
Вектор p(q) означает вероятность применения i-й чистой стратегии первым игроком (j-й чистой стратегии вторым игроком).
Поскольку игроки выбирают свои чистые стратегии случайно и независимо друг от друга, игра имеет случайный характер и случайной становится величина выигрыша (проигрыша). В таком случае средняя величина выигрыша (проигрыша) – математическое ожидание – является функцией от смешанных стратегий р, q:
.
Определение:
Функция f(р,
q)
называется платежной функцией игры с
матрицей
.
Определение:
Стратегии
,
называются оптимальными, если для
произвольных стратегий
,
выполняется условие
Использование в игре оптимальных смешанных стратегий обеспечивает первому игроку выигрыш, не меньший, чем при использовании им любой другой стратегии р; второму игроку – проигрыш, не больший, чем при использовании им любой другой стратегии q.
Совокупность оптимальных стратегий и цены игры составляет решение игры.