Шикин Е.В., Чхартишвили А.Г. Математические методы и модели в управлении: Учеб. пособие
Подождите немного. Документ загружается.
ГЛАВА 19. БИМАТРИЧНЫЕ ИГРЫ
Первая из таблиц описывает выигрыш игрока А, а вторая — вы-
игрыш игрока В. Обычно эти таблицы записывают в виде матриц:
\bml • • •
b
m
k
• . .
b
mn
/
Здесь A — платежная матрица игрока
А,
а В — платежная ма-
трица игрока В.
При выборе игроком А
г-й
стратегии, а игроком В —
/с-й
страте-
гии их выигрыши находятся в матрицах выплат на пересечении
г-х
строк и к-х столбцов:
в матрице А это элемент
а^,
а в матрице В — элемент
Ьц..
Таким образом, в случае, когда интересы игроков различны (но
необязательно противоположны), получаются две платежные мат-
рицы: одна — матрица выплат игроку А, другая — матрица выплат
игроку В. Поэтому совершенно естественно звучит название, которое
обычно присваивается подобной игре, — биматричная.
Замечание. Рассмотренные ранее матричные игры, разумеется,
можно отнести и к биматричным, где матрица выплат игроку В про-
тивоположна матрице выплат игроку
А:
или
371
ГЛАВА 19. БИМАТРИЧНЫЕ ИГРЫ
Тем не менее в общем случае биматричная игра — это игра с
ненулевой суммой.
Нам кажется вполне естественным время от времени сопостав-
лять наши рассмотрения с рассуждениями, приведенными ранее для
матричных игр (особенно при попытках разрешения сходных про-
блем). Подобные сопоставления часто оказываются одновременно и
удобными и полезными. Конечно, класс биматричных игр значите-
льно шире класса матричных (разнообразие новых моделируемых
конфликтных ситуаций весьма заметно), а значит, неизбежно уве-
личиваются и трудности, встающие на пути их успешного разреше-
ния. Впрочем, мы надеемся, что часть этих трудностей мы сумеем
преодолеть уже в настоящем издании.
19.1. Примеры биматричных
игр
Примеры этого раздела описывают некоторые типические конф-
ликтные ситуации, приводящие к биматричным играм. Сначала мы
обсудим вопросы, связанные с формализацией рассматриваемых
конфликтов (построение платежных матриц), а
позднее
- с реко-
мендациями по их разрешению.
19.1.1. Борьба за рынки
Небольшая фирма (игрок
А)
намерена сбыть партию товара на од-
ном из двух рынков, контролируемых другой, более крупной фирмой
(игрок В). Для этого фирма
А
готова сделать на одном из рынков
соответствующие приготовления (например, развернуть рекламную
кампанию). Господствующая
на
рынках фирма В может попытаться
воспрепятствовать этому, приняв на одном из рынков предупреди-
тельные меры (разумеется, в рамках закона). Не встречая противо-
действия на рынке, фирма А захватывает его; при наличии препят-
ствий — терпит поражение.
Будем считать для определенности, что проникновение фирмы А
на первый рынок более выгодно для нее, нежели на второй. Есте-
ственно также считать, что и борьба за первый рынок потребует
вложения больших средств. Например, победа фирмы А на первом
рынке принесет ей вдвое больший выигрыш, чем победа на втором,
но зато и поражение при попытке освоиться
на
первом рынке пол-
ностью ее разорит, а фирму В избавит от конкурента.
372
19.1. ПРИМЕРЫ БИМА ТРИЧНЫХ ИГР
Что же касается второго рынка, то при поражении фирмы А ее
потери будут не столь разорительны, но и победа принесет не много.
Таким образом, у фирмы А две стратегии:
Ai
— выбор первого рынка,
А
2
— выбор второго рынка.
Такие же стратегии и у фирмы
В:
Bi
— выбор первого рынка,
В
2
— выбор второго рынка.
Для того чтобы составить платежные матрицы игроков, нужны
расчетные количественные показатели, которые мы приведем здесь
в условных единицах:
Посмотрим на выписанные матрицы выплат. Из сказанного выше
ясно, что если оба игрока выберут один и тот же рынок, то победа
останется за более сильной фирмой В.
То, что в ситуации
(Ai,Bi)
выигрыш игрока В равен 5, а в си-
туации
(А
2
,В
2
)
— 1, подчеркивает, что первый рынок более выго-
ден (удобно расположен, хорошо посещаем и т. п.), чем второй. Вы-
игрыш (—10) игрока А в ситуации
(A\,Bi)
(а точнее, проигрыш) в
сопоставлении с его выигрышем (—1) в ситуации
(А
2
,
В
2
)
выглядит,
разумеется, вполне сокрушительно. Что же касается ситуации, ко-
гда фирмы уделяют основное внимание разным рынкам —
(Ai,B
2
)
и
(А
2
,
В\),
то здесь фирму А ждет настоящий выигрыш, больший на
более выгодном рынке. Потери, которые при этом несет фирма В,
оказываются прямо противоположными.
Замечание. Ясно, что точно рассчитать выгоду и ущерб сторон в
этом конфликте заранее довольно трудно. Зато в следующей конф-
ликтной ситуации размеры выигрышей игроков известны им со всей
определенностью.
19.1.2. Дилемма узников
Игроками являются два узника, находящиеся в предварительном за-
ключении по подозрению в совершении преступления. При отсутст-
вии прямых улик возможность их осуждения в большой степени за-
висит от того, заговорят они или будут молчать.
Если оба будут молчать, то наказанием будет лишь срок предва-
рительного заключения (потери каждого из узников составят (—1)).
Если сознаются, то получат срок, учитывающий признание как смяг-
373
ГЛАВА 19. БИМАТРИЧНЫЕ ИГРЫ
чающее обстоятельство (потери каждого из узников составят в этом
случае (—6)). Если же заговорит только один из узников, а дру-
гой будет молчать, то в этом случае заговоривший будет выпущен
на свободу (его потери равны 0), а сохраняющий молчание получит
максимально возможное наказание (его потери будут равны (—9)).
Эта конфликтная ситуация приводит к биматричной игре, в кото-
рой каждый из игроков имеет по две стратегии — молчать (М) или
говорить (Г).
Выигрыши игроков А
и
В соответственно описываются так:
19.1.3. Семейный спор
Два партнера договариваются о проведении одного из двух действий,
(1) и (2), каждое из которых требует их совместного участия.
В случае осуществления первого из этих двух действий выигрыш
первого
партнера
(игрок А) будет вдвое выше выигрыша второго
партнера (игрок В). Напротив, в случае осуществления второго из
этих двух действий выигрыш игрока А будет вдвое меньше выигры-
ша игрока В. Если же партнеры выполнят различные действия, то
выигрыш каждого из них будет равен нулю.
Эта конфликтная ситуация приводит к биматричной игре, в кото-
рой каждый из игроков имеет по две стратегии. Выигрыши игроков
А
и
В соответственно описываются таблицами следующего вида:
Пояснение. Понятно, что
различные
конфликтные ситуации мо-
гут иметь одну и ту же формализацию. В частности, рассмотренная
биматричная игра часто интерпретируется как одновременный вы-
бор супругами совместного развлечения: посещение оперного спек-
такля или хоккейного матча. При этом в посещении оперного театра
жена заинтересована в большей степени, чем муж, а при посещении
стадиона наблюдается обратная картина. В случае же непреодоли-
мости разногласий, возникших при выборе, день оказывается вообще
испорченным.
Отсюда и название, вынесенное в заголовок.
374
19.1.4. Студент - преподаватель
Рассмотрим следующую ситуацию. Студент (игрок А) готовится к
зачету, который принимает преподаватель (игрок В). Можно счи-
тать, что у студента две стратегии — подготовиться к сдаче зачета
(+) и не подготовиться (—). У преподавателя также две стратегии —
поставить зачет [+] и не поставить зачета [—].
В основу значений функций выигрыша игроков положим следу-
ющие соображения:
Количественно это можно выразить, например, так:
19.2. Смешанные стратегии
В приведенных примерах (позже мы вернемся к подробному рассмо-
трению каждого) описаны ситуации, в которых интересы игроков не
совпадают. Естественно встает вопрос о том, какие рекомендации не-
обходимо дать игрокам для того, чтобы моделируемая конфликтная
ситуация разрешилась.
Иными словами, что мы будем понимать под решением биматри-
чной игры?
Попробуем ответить на этот вопрос так: вследствие того что ин-
тересы игроков не совпадают, нам нужно построить такое (компро-
миссное) решение, которое бы в том или ином, но в одинаковом смы-
сле удовлетворяло обоих игроков.
Иначе говоря, попробуем найти некую равновесную ситуацию, яв-
ное отклонение от которой уменьшает выигрыш игрока.
Подобный вопрос мы ставили и при рассмотрении матричных игр.
Напомним, что возникавшее при разработке минимаксного подхода
375
ГЛАВА 19. БИМАТРИЧНЫЕ ИГРЫ
понятие равновесной ситуации приводило нас к поиску седловой точ-
ки, которая, как оказалось, существует далеко не всегда, конечно,
если ограничиваться только чистыми стратегиями игроков А и В,
т. е. стратегиями
Естественно ожидать, что в более сложном случае биматричной
игры дело вряд ли будет обстоять проще.
В матричных играх эта трудность была преодолена путем пере-
хода к смешанным стратегиям, т. е. к такому поведению игроков,
при котором они чередуют (чистые) стратегии
А\,..., А
т
,
В\,...
,В
п
(конечно, свои собственные):
игрок А — стратегии
А\,
...,
А
т
,
игрок В — стратегии
В\,
...
...,в
п
с определенными частотами:
игрок А — стратегии
А\,
...,
А
т
с частотами
pi,
...,
р
т
,
где
771
Pl
>
0, . . .,
р
т
^ 0,
^Рг
= 1,
г=1
а игрок В — стратегии
В\,
...,
В
п
с частотами
<7i,
...,
^п
;
где
и оказалось, что в смешанных стратегиях равновесная ситуация су-
ществует всегда.
Иными словами, любая матричная игра в смешанных стратегиях
разрешима.
Поэтому, рассматривая здесь биматричные игры, разумно попро-
бовать сразу же перейти к смешанным стратегиям игроков. Тем са-
мым мы предполагаем, что каждая игра может быть повторена в
неизменных обстоятельствах многократно.
В матричном случае смешивание стратегий приводило к расши-
рению возможности выплат в том смысле, что расчет строился на
вычислении средних выигрышей игроков А
и
В, которые определя-
лись по элементам платежной матрицы А и вероятностям
p
t
и
q^.
376
19.3. 2 х 2-БИМАТРИЧНЫЕ ИГРЫ. СИТУАЦИЯ РАВНОВЕСИЯ
При смешанных стратегиях в биматричных играх также естестве-
нно возникают средние выигрыши игроков А
и
В,
вычисляемые по
правилам, в которых уже нет никакой дискриминации игрока
В:
19.3. 2 X 2-биматричные игры. Ситуация
равновесия
Мы предполагаем уделить основное внимание случаю, когда у каж-
дого из игроков имеется ровно две стратегии, т. е. случаю т
=
п = 2.
Поэтому нам кажется уместным выписать приведенные выше фор-
мулы именно для такого случая.
В 2 х 2-биматричной игре платежные матрицы игроков имеют сле-
дующий вид:
°11
а
12
\ В = I
^21
0,22)
'
\Ь
2
1
&22
вероятности
Pi
=
Р, Р2 =
1
- Р,
9i
=
Q,
42
—
1
-
q,
а средние выигрыши вычисляются по формулам
где
Сформулируем основное определение.
Определение. Будем говорить, что пара чисел
определяет равновесную ситуацию, если для любых р и
q,
подчи-
ненных условиям
О^р^1,О^д^1,
одновременно выполнены
следующие неравенства:
(1)
25
3ак.
7492
277
ГЛАВА 19. БИМАТРИЧНЫЕ ИГРЫ
Пояснение. Выписанные неравенства (1) означают следующее: си-
туация, определяемая смешанной стратегией
(p*,q*),
является рав-
новесной, если отклонение от нее одного из игроков при условии, что
другой сохраняет свой выбор, приводит к уменьшению выигрыша
первого. Тем самым получается, что если равновесная ситуация су-
ществует, то отклонение от нее невыгодно самому игроку.
Но может ли быть подобная ситуация равновесия в биматричной
игре?
Ответ на поставленный вопрос дает следующее утверждение.
ТЕОРЕМА
(Дж. Нэш). Всякая
биматричпая
игра
имеет
хотя
бы
одну равновесную ситуацию (точку
равновесия)
в смешанных стра-
тегиях.
Заметим, что весьма похожее утверждение мы уже встречали при
изучении вопроса разрешимости матричных игр.
Напомним также, что в соответствующем разделе после форму-
лировки аналогичного утверждения о существовании равновесной
ситуации описывался и способ отыскания точки равновесия.
Та же проблема встает перед нами и здесь.
Итак, равновесная ситуация существует. Но как ее найти?
Если предполагается, что некоторая пара чисел (p*,q*) опреде-
ляет ситуацию равновесия, то для того, чтобы подтвердить или опро-
вергнуть это предположение, необходимо проверить справедливость
неравенств (1) для любого р в пределах от 0 до 1 и для любого q в
пределах от 0 до
1.
В общем случае число таких проверок бесконечно. И следователь-
но, действенный способ определения равновесной ситуации должен
быть
иным.
Для его обоснования сошлемся на следующий теоретический ре-
зультат.
ТЕОРЕМА. Выполнение неравенств
H
A
(p,q*)
^
H
A
(p*,q*),
H
B
(p*,q)
<C
H
B
{p\q*)
равносильно выполнению неравенств
H
A
(0,q*)
<
H
A
(p\q*),
H
B
(p\0)
<:
H
B
(p\if),
(2)
3
I-7Q
(О
ГЛАВА 19. БИМАТРИЧНЫЕ ИГРЫ
Поэтому окончательно получаем