close

Вход

Забыли?

вход по аккаунту

?

Prokofeva Osnovy teorii igr2017

код для вставкиСкачать
С. И. ПРОКОФЬЕВА, Э. Е. ПАК
ОСНОВЫ ТЕОРИИ ИГР
Министерство образования и науки
Российской Федерации
Санкт-Петербургский государственный
архитектурно-строительный университет
С. И. ПРОКОФЬЕВА, Э. Е. ПАК
ОСНОВЫ ТЕОРИИ ИГР
Учебное пособие
Санкт-Петербург
2017
1
УДК 519.83
Рецензенты: канд. физ.-мат. наук, доцент В. Г. Пак (СПбГПУ);
канд. физ.-мат. наук, доцент Л. Е. Морозова (СПбГАСУ)
Прокофьева, С. И.
Основы теории игр: учеб. пособие / С. И. Прокофьева,
Э. Е. Пак. – 2-е изд., испр. и доп.; СПбГАСУ. – СПб., 2017. – 72 с.
ISBN 978-5-9227-0741-1
Представлены три раздела теории игр: матричные игры, биматричные
игры, игры с природой. Теоретический материал подкреплен решением задач
экономического содержания. Также предлагаются задачи для самостоятельного решения.
Предназначено для студентов экономических специальностей.
Ил. 12. Библиогр.: 9 назв.
Рекомендовано Учебно-методическим советом СПбГАСУ в качестве
учебного пособия.
ISBN 978-5-9227-0741-1
© С. И. Прокофьева, Э. Е. Пак, 2017
© Санкт-Петербургский государственный
архитектурно-строительный университет, 2017
2
Введение
Теория игр – раздел математики, который сформировался
в середине XX века. Основоположником теории игр является американский математик Джон фон Нейман. Одной из первых работ по
теории игр можно считать его статью «К теории стратегических
игр», которая была напечатана в 1928 году [1] и в которой он,
в частности, дал определение игры n лиц с нулевой суммой. Также
в этой работе Нейман представил доказательство своей знаменитой
теоремы о существовании решения в смешанных стратегиях для
так называемых матричных игр при n  2 . Сегодня эта теорема общеизвестна под названием теоремы о минимаксе. Принято считать,
что теория игр как самостоятельная математическая дисциплина
сформировалась после публикации в 1944 году Дж. фон Нейманом
и О. Моргенштерном книги «Теория игр и экономическое поведение» [2]. В настоящее время методы теории игр чаще всего используется в экономике, но также находят обширное применение в социологии, политологии, юриспруденции и других общественных
науках.
В последние годы значение теории игр существенно возросло.
В экономике она применима не только для решения общехозяйственных задач, но и для анализа стратегических проблем предприятий, разработок организационных структур и систем стимулирования.
Методы теории игр применяются, например, при организации
промышленного производства, в процессах торговли, при организации торгов и аукционов. Аппарат теории игр послужил основой
для создания современных теорий международной торговли, налогообложения и общественных благ, монетарной экономики, теории
производственных организаций. В [3] показано, как аппарат теории
игр применяется при анализе влияния законов на поведение людей,
партий и т. д.
К настоящему времени по данной проблематике опубликовано
множество статей и монографий, но они обычно рассчитаны на
специалистов в этой области. В то же время базовый математический аппарат теории игр вполне доступен студенту, изучившему
3
стандартный курс высшей математики в объеме технического университета.
В данном пособии основы теории игр изложены языком,
наиболее понятным студентам младших курсов экономических
специальностей. Как правило, в качестве примеров разбираются
игры, описывающие конкретные (весьма разнообразные) экономические ситуации.
Введем определение игры.
Определение. Игрой называется модель конфликтной ситуации:
1) в которой участвует некоторое (конечное или бесконечное)
число игроков;
2) заранее заданы правила игры, то есть способ выбора решения (стратегии) игроком;
3) определены количественные величины выигрышей (проигрышей) участников игры.
Игроками могут выступать люди, производственные предприятия, торговые фирмы, целые государства, военные армии и даже
природные стихии.
В данном пособии основное внимание уделено играм экономического характера, однако в качестве модельных примеров рассматриваются и некоторые абстрактные игры.
Игры можно разбить на группы следующим образом:
1) по количеству игроков: в парной игре число участников
равно двум, а в множественной игре – более двух;
2) по количеству стратегий: если у всех игроков конечное число стратегий, то игра называется конечной; в противном случае игра называется бесконечной;
3) по информированности игроков: в играх с полной информацией игроки знают, и какие ходы были сделаны ранее, и возможные
стратегии противника; в играх с неполной информацией игроки не
знают достоверно о ранее сделанных шагах и намерениях противника;
4) по свойствам функции выигрыша: матричные, биматричные (об этих играх более подробно поговорим далее в пособии),
а также выпуклые игры (функция выигрышей выпуклая) и сепарабельные игры (функция выигрышей может быть разделена на сумму произведений функций одного аргумента);
5) по характеру взаимоотношений между игроками: бескоалиционные (то есть игроки не вступают в коалиции, не заключают
между собой никаких соглашений), коалиционные (заключаются
некоторые соглашения) и кооперативные игры (участники заранее
образуют коалиции с целью увеличить свои выигрыши).
Анализ теоретического решения игры (конфликтной ситуации) помогает исследователю смоделировать процесс и возможные
результаты будущего конфликта еще до его фактического начала.
По результатам моделирования будущей игры можно принять решение о целесообразности участия и оптимальном поведении в реальном конфликте, также можно сэкономить не только денежные
средства, но и другие ресурсы. Ценность теории игр состоит в том,
что она позволяет прогнозировать развитие конфликтов.
В данном ознакомительном курсе будут рассмотрены только
следующие наиболее простые игры:
а) конечные бескоалиционные матричные игры двух игроков;
б) конечные бескоалиционные биматричные игры двух игроков;
в) игры с природой.
4
5
§ 1. Понятие матричной игры
Перейдем непосредственно к изложению основных понятий
теории игр.
Пусть игрок A имеет возможность сделать свой ход m различными способами. В этом случае говорят, что он имеет m различных
стратегий: A1, A2,…, Am. Игрок B имеет возможность сделать свой ход
n различными способами, то есть имеет n стратегий: B1, B2,…, Bn.
Такая игра называется игрой m  n .
Определение. Матричная игра – это игра со следующими
правилами:
а) в игре участвуют два игрока (игрок A и игрок B);
б) каждый игрок обладает конечным набором стратегий;
в) каждый игрок, не зная о действиях противника, выбирает
одну из своих возможных стратегий;
г) выигрыш игроков зависит от выбранных ими стратегий,
причем эти выигрыши противоположны.
Замечание. Матричная игра еще называется игрой с нулевой
суммой, или антагонистической игрой.
В дальнейшем предполагается, что в результате выбора игроками стратегий Ai и Bj, i  1, m , j  1, n , выигрыш игрока A составляет величину cij .
Определение. Матрица C размера m  n , состоящая из чисел
cij , i  1, m , j  1, n , которая описывает величины выигрышей игрока A, называется платежной матрицей или матрицей выигрышей:
 c11 c12

 
C   ci1 ci 2

 
c
 m1 cm 2
 c1 j  c1n 

   
 cij  cin  .

   
 cmj  cmn 
6
Замечание. В случае матричной игры выигрыши игрока B
равны cij .
Пример 1.1. Игра в «открывание пальцев». Игроки A и B одновременно из сжатого кулака открывают по несколько пальцев.
Если сумма пальцев обоих игроков четная, то игрок A выигрывает
столько очков, каково общее количество пальцев, а если нечетная,
то столько же выигрывает игрок B. Составить платежную матрицу
(игрока A ).
Решение. Игрок А имеет пять стратегий: A1, A2, A3, A4, A5, где
стратегия Ai состоит в открывании i пальцев, i  1,5 . У игрока B
также пять стратегий: B1, B2, B3, B4, B5. Это игра 5 5 . Составим
таблицу выигрышей игрока A
A1
A2
A3
A4
A5
B1
2
–3
4
–5
6
B2 B3
–3 4
4 –5
–5 6
6 –7
–7 8
B4
–5
6
–7
8
–9
B5
6
–7
8
–9
10
Тогда матрица выигрышей C игрока A (платежная матрица игры) имеет вид
4 5
6
 2 3


4 5
6  7
3
C  4 5
6 7
8 .


6 7
8  9
 5
 6 7
8  9 10 

Замечание. Очевидно, что условие aij  bij  0 , i  1, m , j  1, n ,
где aij – это выигрыш игрока A, а bij – выигрыш игрока B, можно
заменить условием aij  bij  const .
Пример 1.2. Каждая из фирм X и Y посылает свою автолавку
в один из пунктов: A, B или C, – расположение которых указано
на рис. 1. Там же указано количество покупателей в этих пунктах.
7
Цель каждой из фирм –
привлечь наибольшее количество покупателей. Предпочтения покупателей таковы: если
17 км
12 км
обе лавки приезжают в один
и тот же пункт, то в автолавку X
обращаются 60 % всех покупателей. Если лавки приезжают
B (4 тыс.)
5 км
C (2 тыс.) в разные пункты и автолавка X
находится к данному пункту
Рис. 1
ближе, чем автолавка Y, то в автолавку X обращаются 80 % покупателей, а если она расположена
дальше, чем Y, то в нее обращаются только 40 % покупателей.
Необходимо составить платежную матрицу игры для фирмы X,
считая выигрышем каждой из фирм общее количество покупателей,
обратившихся в их автолавку (тысяч человек).
Решение. Описанная ситуация имеет явно игровой (конфликтный) характер. Выигрышем для каждой из фирм считается общее
количество всех покупателей, которые обращаются в их автолавку.
Очевидно, что сумма выигрышей постоянна и равна 7 (тысяч человек). Каждая из фирм имеет столько стратегий, сколько имеется
пунктов: 1-я стратегия – послать автолавку в пункт A, 2-я – в пункт
B, а 3-я – в пункт C. Вычислим элементы платежной матрицы. Элементы xii , i  1, 2, 3 , соответствующие нахождению автолавок в одном и том же пункте: xii  0,6  7  4,2 . Элемент x12 отвечает ситуации, когда автолавка X находится в пункте A, а автолавка Y находится в пункте B. По условию задачи, в автолавку X обратятся 80 %
покупателей из этого пункта и 40 % покупателей пунктов B и C (так
как эти пункты расположены ближе к автолавке Y). Таким образом,
в данной ситуации в автолавку X обращаются 0,8  1  0,4  6  3,2 тысяч покупателей, то есть x12  3,2 . Аналогичным образом (вычисления предлагается проделать самостоятельно) вычисляются
и остальные элементы платежной матрицы. В результате получим
платежную матрицу для фирмы X
A (1 тыс.)
Проверь себя. Игрок A может записать одну из цифр 2, 4 либо 7;
игрок B может записать 1, 3, 4 либо 8. Если обе цифры окажутся
одинаковой четности, то игрок A получает столько очков, какова
сумма записанных цифр; если разной четности, то сумма очков достается игроку B. Составить платежную матрицу игры.
6
10 
3 5


Ответ: C    5  7
8
12  .
 8 10  11  15 


 4,2 3,2 3,2 


 5,2 4,2 4,4  .
 5,2
4 4,2 

8
9
такую стратегию Bj, при которой величина его проигрыша была бы
наименьшей.
§ 2. Нижняя и верхняя цены игры
Определение. Число
Пусть игрок A выбирает стратегию игры Ai, i  1, m . В зависимости от выбора стратегии Bj, j  1, n , игроком B игрок A будет
иметь выигрыши ci1 , ci 2 , ci 3 ,  , cin . Это элементы, стоящие в i-й
строке платежной матрицы C:
 c11 c12

 
C   ci1 ci 2

 
c
 m1 cm 2
 c1n 

 
 cin  .

 
 cmn 
При выборе стратегии Ai игрок A в наихудшем для себя случае выигрывает: min cij . Следовательно, для получения в наихудшем слу1 j  n
чае наибольшего выигрыша игроку A надо выбрать такую стратегию, для которой число min cij будет максимальным.
1 j  n
Определение. Число
  max min cij
1 i  m 1 j  n
называется нижней ценой игры, а стратегия игрока A, соответствующая этому числу, называется максиминной.
Какую бы стратегию ни выбрал игрок B, игрок A гарантированно будет иметь выигрыш не менее  .
Рассмотрим теперь поведение игрока B. Если он выбирает
стратегию Bj, j  1, n , то его проигрыш в зависимости от стратегии
игрока A может принимать значения c1 j , c2 j , c3 j ,  , cmj . Это элементы платежной матрицы, стоящие в ее j-м столбце. Наихудший
исход для игрока B будет в случае, когда игрок A выбирает стратегию, соответствующую max cij . Поэтому игроку B следует выбрать
  min max cij
1 j  n 1 i  m
называется верхней ценой игры, а стратегия игрока B, соответствующая числу  , называется минимаксной.
Если игрок B применит свою минимаксную стратегию, то при
любых действиях игрока A игрок B проиграет не более чем  .
Принцип, по которому игрок A выбирает максиминную стратегию, а игрок B – минимаксную, называется принципом минимакса, а соответствующие стратегии называются минимаксными. Другими словами, необходимо выбирать ту стратегию, чтобы при
«наихудшем поведении» противника получить максимальный выигрыш.
Пример 2.1. Две строительные фирмы привлечены к строительству жилого комплекса. Фирма A выставила на конкурс три варианта проекта: A1, A2, A3, а фирма B приготовила четыре варианта:
B1, B2, B3, B4. Заказчик анализирует проекты. Средства распределяют между фирмами пропорционально набранным баллам, причем
общее количество набранных фирмами баллов всегда равно десяти.
Предположим, что матрица выигрышей игрока A (значения выражены в баллах) имеет вид
7 2 5 2


C   6 5 5 5 .
 0 6 8 2


Найти нижнюю и верхнюю цены игры.
Решение. Для каждой строки матрицы C найдем ее наименьший элемент min cij , который запишем справа от строки. Для каж1 j  n
дого столбца матрицы C найдем его наибольший элемент max cij ,
1 i  m
который запишем снизу от столбца. В результате получим расширенную матрицу
1 i  m
10
11
7

6
0

7
2 5 2 2

5 5 5 5
6 8 2  0
6 8 5
Выбирая из последнего столбца его наибольший элемент, находим
нижнюю цену игры:
  max2; 5; 0  5.
Выбирая из последней строки ее минимальный элемент, находим
верхнюю цену игры:
  min7; 6; 8; 5  5.
Итак, в данной задаче верхняя и нижняя цены игры совпадают
и равны пяти.
Замечание. В общем случае  не обязательно совпадает с .
Значения  и  не зависят от выбора игроками конкретных стратегий, а определяются исключительно платежной матрицей.
Проверь себя. Игроки A и B одновременно и независимо друг
от друга записывают одно из трех чисел: 5, 10 или 15. Если сумма
записанных чисел четная, то B отдает эту сумму в условных единицах игроку A; если она нечетная, то, наоборот, A платит эту сумму.
Составить платежную матрицу игры и найти ее верхнюю и нижнюю цены.
Ответ:   15 ,   20 .
12
§ 3. Игры с седловой точкой
Определение. Игра называется игрой с седловой точкой, если
нижняя и верхняя цены этой игры совпадают, то есть
  max min cij    min max cij .
1 i  m 1 j  n
1 j  n 1 i  m
Элемент ci0 j0 платежной матрицы, для которого ci0 j0     ,
называется седловым элементом, а соответствующая этому элементу пара стратегий ( Ai0 , B j0 ) – седловой точкой игры.
Определение. Для игр с седловой точкой число v    
называется ценой игры.
В примере 2.1 цена игры v  5 . Максиминной стратегией игрока A является стратегия A2, а минимаксной стратегией игрока B
является стратегия B4. Причем элемент c24  5 является седловым
элементом.
При наличии в игре седловой точки ( Ai0 , B j0 ) выбор игроком
A стратегии Ai0 , а игроком B стратегии B j0 является самым разумным (оптимальным). Такой выбор обеспечивает игроку A выигрыш
не менее v , а игроку B проигрыш не более v , то есть выигрыш не
менее  v . Отклонение от этих стратегий невыгодно обоим игрокам: выигрыш для игрока A может только уменьшиться, а проигрыш для игрока B – только увеличиться.
Поясним название «седловая точка». Рассмотрим в пространстве поверхность, заданную уравнением z  y 2  x 2 (рис. 2).
13
Эта поверхность получается при скольжении параболы AOB
по параболе COD (см. рис. 2) и называется гиперболическим параболоидом. Из рисунка видно, что точка O (0, 0, 0) является максимумом функции по переменной x в плоскости XOZ (то есть y  0 ).
Одновременно точка O является минимумом функции по переменной y в плоскости YOZ ( x  0 ). Как видно из рисунка, геометрически поверхность напоминает седло. Отсюда и произошло название
точки O – «седловая точка».
Замечание. В игре может быть несколько седловых точек, то
есть таких точек ( Ai , B j ) , для которых cij  v .
Проверь себя. 1. Найти цену игры с платежной матрицей
2  1
5  3


а) C   3
1  4 0 ,
1
2
6
1

Ответы: а) vC  1 ; б) vD  1,5 .
 5

 1,2 0,3 
3
6


2
5 

б) D  1,1
.

3
6 
 5

1,9 1,5 

 3

2. Найти все седловые элементы в игре с платежной матрицей
0 4
1
8


2
3
2
5
.
E 
2
2
5
2


7  2 
4  3
Какие стратегии следует выбирать игрокам в одноразовой игре?
Ответ: ( A2 , B2 ) , ( A2 , B4 ) , ( A3 , B2 ) , ( A3 , B4 ) . Максиминными
стратегиями игрока A являются стратегии A2 и A3, а минимаксными
стратегиями игрока B – стратегии B2 и B4.
§ 4. Игры без седловой точки
Очевидно, что не всякая матричная игра будет иметь седловую точку.
Пример 4.1. Рассмотрим игру двух игроков A и B с платежной
матрицей
1
3  2
.
C  
0  1
3
Вычислим для нее наименьшие элементы в строках и наибольшие в столбцах. Имеем
1  2
3  2


0  1  1
3
3
0 1
Тогда нижняя цена игры
  max min cij  max 2;  1  1.
i 1, 2 j 1, 2,3
Верхняя цена игры
  min max cij  min3; 0; 1  0.
j 1, 2,3 i 1, 2
Таким образом, в этой игре   1, а   0 , то есть нижняя и верхняя цены игры не совпадают, а значит, в ней нет седловой точки.
Здесь стратегия A2 является максиминной для игрока A, а стратегия
B2 будет минимаксной для игрока B.
Теорема. Для любой антагонистической игры с матрицей выигрышей C  (cij ), i  1, m, j  1, n , выполняется неравенство
max min cij  min max cij ,
1 i  m 1 j  n
1 j  n 1 i  m
то есть    .
14
15
Доказательство. Рассмотрим элементы c1 j , c2 j , c3 j , , cmj j-го
столбца матрицы C. Так как любой элемент этого столбца не превосходит максимального в этом столбце, то очевидно, что при любых значениях i справедливо неравенство
cij  max cij .
1 i  m
Так как это неравенство выполняется при всех j, то, беря минимум
от обеих частей неравенства по индексу j, получим
min cij  min max cij .
1 j  n
1 j  n 1 i  m
Последнее неравенство выполняется при всех i. Беря максимум от
обеих частей неравенства по индексу i, получим
max min cij  min max cij .
1 i  m 1 j  n
1 j  n 1 i  m
Таким образом, из определений нижней и верхней цен игры и последнего неравенства следует, что    . Теорема доказана.
Замечание. Для матричной игры без седловой точки справедливо строгое неравенство    .
Проверь себя. Определить максиминную и минимаксную
стратегии для одноразовой игры, заданной платежной матрицей
3 7 2
6


C   3  1 4 1 .
 1 4 4 5


§ 5. Многократно повторяемые игры. Смешанные стратегии
В предыдущих параграфах рассматривались так называемые
одноразовые игры. Стратегии игроков A и B, однозначно выбираемые игроками в этих играх, называют чистыми стратегиями.
В одноразовых играх выгоднее всего придерживаться принципа
«минимакса». При этом безразлично, имеет ли игра седловую точку
или нет.
Возникает вопрос: если такая игра будет повторяться многократно, то каких стратегий игрокам лучше всего придерживаться?
Если игра имеет седловую точку, то игрокам невыгодно менять свои стратегии. Но если игра без седловой точки, то повторение минимаксной стратегии одним из игроков становится невыгодным для него. Поясним это на примере.
Пример 5.1. Рассмотрим игру с платежной матрицей
 4  3 0
.
C  
2 3 
 1
Для нахождения нижней и верхней цен игры составим таблицу
 4  3 0  3


2 3   1
 1
4
2 3
Ответ: максиминной стратегией для игрока A является стратегия A1, а минимаксной стратегией для игрока B – стратегия B2.
Из этой таблицы находим нижнюю и верхнюю цены игры:
  max 3;  1  1,   min4; 2; 3  2 . Значит, максиминной
стратегией для игрока A будет стратегия A2, а минимаксная стратегия для игрока B – это стратегия B2. Так как c22  2  0 , то для игрока A игра разрешится его выигрышем, равным 2. Допустим, что
при следующей игре игрок A опять применит стратегию A2, а игрок
B будет об этом информирован. Тогда игрок B может применить,
например, стратегию B1. Так как c21  1 < 0, то игрок B вместо
проигрыша будет иметь выигрыш, равный  c21  1. Отсюда можно
сделать вывод о том, что при многократном повторении игры, если
16
17
известны намерения другого игрока, то можно увеличить свой выигрыш, сделав его больше  , и уменьшить свой проигрыш, сделав
его меньше, чем .
Доказано, что при многократном повторении игры без седловой точки для обеспечения суммарного выигрыша, большего  ,
игроку A следует непредсказуемо менять свои стратегии. Аналогично, чтобы сделать свой проигрыш меньшим , игрок B также
должен случайным образом менять свои стратегии. Так возникает
идея об использовании так называемых смешанных стратегий,
то есть таких стратегий, которые игроки будут выбирать случайно
с некоторыми вероятностями.
Определение. Смешанной стратегией игрока называется вероятностное распределение на множестве его чистых стратегий.
То есть смешанные стратегии – это комбинированные стратегии, состоящие в применении нескольких чистых стратегий, выбираемых случайным образом с определенными вероятностями.
Обозначим через SA смешанную стратегию игрока A. Запишем
SA в виде матрицы, в первой строке которой записаны все возможные стратегии Ai, i  1, m , а во второй указаны вероятности pi , с которыми игрок A выбирает соответствующие стратегии:
A
S A   1
 p1
Здесь pi  0 , i  1, m , и
A2  Am 
.
p2  pm 
m
 pi  1.
i 1
Смешанная стратегия для игрока B имеет вид
B
S B   1
 q1
где q j  0 , j  1, n , и
B2  Bn 
,
q2  qn 
n
 q j  1.
Пусть теперь игроки выбирают пару стратегий ( Ai , B j ) с вероятностями pi и q j соответственно. Как и ранее, предполагаем,
что при таком выборе стратегий величина выигрыша составляет cij .
Тогда средний выигрыш игрока A есть математическое ожидание
случайной величины, равной выигрышу игрока A и заданной на
множестве пар стратегий ( Ai , B j ) :
m
n
v (C , P, Q)    cij pi q j ,
i 1 j 1
где обозначили P  ( p1 , p2 , , pm ) и Q  (q1 , q2 ,  , qn ) – векторы
вероятностей. Следующее понятие является важнейшим в теории игр.
Определение. Стратегии с вероятностями P 0  ( p10 , p20 ,  , pm0 )
и Q 0  (q10 , q20 ,  , qn0 ) называются оптимальными смешанными
стратегиями игроков, если выполняется двойное неравенство
v (C , P, Q 0 )  v (C , P 0 , Q 0 )  v (C , P 0 , Q)
при любых pi , q j  0 ,
m
n
i 1
j 1
 pi  1,  q j  1 .
Для антагонистической игры левое неравенство в (5.1) означает, что отклонение от стратегии P 0 для игрока A неразумно, так как
его выигрыш при этом может только уменьшиться (при условии,
что игрок B придерживается оптимальной стратегии Q 0 ). Правое
неравенство в (5.1) означает, что отклонение от стратегии Q 0 неразумно для игрока B, так как при отклонении от этой стратегии его
проигрыш может только увеличиться (при условии, что игрок A
придерживается оптимальной стратегии P 0 ).
Условие оптимальности (5.1) можно представить в виде
max min v (C , P, Q)  v (C , P 0 , Q 0 )  min max v (C , P, Q).
j 1
(5.1)
P
Q
Q
P
(5.2)
Заметим, что любая чистая стратегия – это частный случай
смешанной стратегии. В этом случае она применяется с вероятностью 1, а остальные стратегии – с вероятностью 0.
Величина v (C , P 0 , Q 0 )  v называется ценой игры, а набор
( P 0 , Q 0 , v) – решением матричной игры.
18
19
Следующая теорема дает положительный ответ на естественный вопрос о существовании решения в играх со смешанными стратегиями. Доказательство этой теоремы можно найти, например, в [1].
Теорема 5.1 (Дж. фон Неймана). Для матричной игры с произвольной матрицей выигрышей C величины max min v (C , P, Q)
Q
P
и min max v (C , P, Q) существуют и равны между собой. При этом
Q
P
существует хотя бы одна пара стратегий ( P 0 , Q 0 ) , для которой выполняется равенство
max min v (C , P, Q)  min max v (C , P, Q)  v (C , P 0 , Q 0 )  v.
P
Q
Q
P
Иными словами, теорема утверждает, что любая матричная
игра имеет по крайней мере одно оптимальное решение, в общем
случае среди смешанных стратегий.
Следующая теорема используется для нахождения этого решения. Вначале заметим, что в оптимальную смешанную стратегию игрока могут входить не все исходные стратегии, а только некоторые из них. Те стратегии, которые входят в состав оптимальных стратегий с ненулевыми вероятностями, назовем активными
стратегиями.
Рассмотрим игру m  n с матрицей выигрышей C  (cij ),
i  1, m, j  1, n .
Теорема 5.2 (об активных стратегиях). 1. В оптимальной
смешанной стратегии игрока A активными будут только те из стратегий Ai, i  1, m, для которых выполняется равенство
n

j 1
cij q 0j
 v.
(5.3)
2. В оптимальной смешанной стратегии игрока B активными
будут только те из стратегий Bj, j  1, n, для которых выполняется
равенство
m
 cij pi0  v.
(5.4)
i 1
3. Справедливы равенства
m
m
n
 max  cij q 0j .
i
Другими словами, если один из игроков придерживается своей
оптимальной смешанной стратегии, то выигрыш остается неизменным и равным цене игры v , если второй игрок не выходит за пределы своих активных стратегий.
Теорема 5.2, доказательство которой приведено в [4], является
основой для различных методов решения матричных игр.
Условия, при которых применяются смешанные стратегии,
следующие:
а) игра не имеет седловой точки;
б) игра повторяется много раз в одинаковых условиях;
в) во время игр игроки не информированы о намерениях друг
друга;
г) выигрыш вычисляется усреднением результатов игр.
Проверь себя. 1. Вычислить средний выигрыш для игры, заданной платежной матрицей
 1  2 3

C  
3 0 
2
в случае, когда игроки используют следующие смешанные стратегии:
P  (0,4; 0,6) , Q  (0,2; 0,4; 0,4) .
Ответ: v (C , P, Q)  1,2.
2. Вычислить средний выигрыш для игры, заданной платежной матрицей
3 7 2
6


D   3 1 4 5
 4 5 2 1


в случае, когда игроки используют следующие смешанные стратегии:
P  (0,3; 0,1; 0,6) , Q  (0,2; 0,3; 0,1; 0,4) .
Ответ: v ( D, P, Q)  3,09 .
n
v  min  cij pi0  max min  cij pi  min max  cij q j 
j
i 1
P
j
i 1
20
Q
i
(5.5)
j 1
j 1
21
Следовательно,
p10 
§ 6. Решение матричной игры 2×2 в смешанных стратегиях
Рассмотрим простейшую игру 2  2 , которая описывается матрицей выигрышей
c 
c
C   11 12  .
 c21 c22 
Предполагаем, что в этой игре отсутствует седловая точка, а сама
игра повторяется многократно (игры с седловой точкой были разобраны в § 3).
Пусть смешанные стратегии игроков A и B имеют вид
A
S A   1
 p1
A2 
B
 , S B   1
p2 
 q1
(6.1)
При этом вероятности p10 и p20 удовлетворяют условиям
0  p10  1, 0  p20  1.
Поэтому, приравнивая левые части первых двух уравнений и учитывая, что из последнего уравнения p20  1  p10 , получим
или
c11 p10  c21 (1  p10 )  c12 p10  c22 (1  p10 ),
p20  1  p10  1 
c22  c21
c11  c12

.
c11  c22  (c12  c21 ) c11  c22  (c12  c21 )
Теперь, зная значения p10 и p20 , найдем цену игры, используя,
например, первое уравнение системы (6.1):

где p1  p2  1; q1  q2  1 .
Найдем оптимальные стратегии, для чего вычислим p10
и p20  1  p10 игрока A и цену игры v . Так как p10 и p20 удовлетворяют равенствам (5.4), то
c11 p10  c21 p20  v,

0
0
c12 p1  c22 p2  v,
 0
0
 p1  p2  1.
Тогда, подставляя это выражение в последнее уравнение системы
(6.1), найдем:
v  c11 p10  c21 p20  c11 
B2 
,
q2 
(6.2)
c22  c21
.
c11  c22  (c12  c21 )
c22  c21
c11  c12
 c21 

c11  c22  (c12  c21 )
c11  c22  (c12  c21 )
c11c22  c12c21
.
c11  c22  (c12  c21 )
Таким образом, получено решение системы (6.1)
 0
c22  c21
 p1  c  c  (c  c ) ,
11
22
12
21

 0
c11  c12
,
 p2 
c11  c22  (c12  c21 )


c11c22  c12c21
.
v 
c11  c22  (c12  c21 )

(6.3)
Используя найденное значение цены игры v , можно вычислить оптимальную смешанную стратегию игрока B. Исходя
из условия (5.3), имеем
c11q10  c12 q20  v .
Учитывая, что q20  1  q10 , получим
p10 (c11  c21  c12  c22 )  c22  c21 .
c11q10  c12 (1  q10 )  v ,
22
23
откуда
q10 (c11
 c12 )  v  c12 .
Следовательно,
 0 v  c12
q1  c  c ,

11
12

q20  1  q10  1  v  c12  c11  v ,

c11  c12 c11  c12
(6.4)
где с11  с12 .
Для игры 2  2 можно рассмотреть и графический вариант решения. Чтобы решить игру графически, выберем систему координат ( p, y ) и выполним следующие построения (рис. 3):
y
рока при стратегии A2. Число c11 , отложенное на вертикальной
прямой p  1, является величиной выигрыша при использовании
стратегии A1.
3. Соединим полученные пары точек с координатами (0; c21 )
и (1; c11 ) , (0; c22 ) и (1; c12 ) .
4. Из формулы (6.2) следует, что цена игры v равна ординате
точки пересечения прямых, а абсцисса этой точки равна вероятности p10 оптимальной смешанной стратегии игрока A.
Аналогично в системе координат (q, y ) можно построить прямые y  c11q  c12 (1  q ) и y  c21q  c22 (1  q ) . При этом абсцисса
точки пересечения прямых будет равна вероятности q10 оптимальной смешанной стратегии игрока B, а ордината совпадет с ценой
игры v , полученной ранее.
Замечание. Следует иметь в виду, что графический способ
решения дает лишь приближенное значение цены игры v .
Пример 6.1. Решить игру с платежной матрицей
 2 4
 .
C  
3 1
y  c12 p  c22 (1  p )
c12
c21
Решение. Найдем верхнюю и нижнюю цены игры. Имеем
v
c22
0
c11
p10
1
p
Рис. 3
1. На оси абсцисс отложим отрезок единичной длины p  1.
2. Построим прямые y  c11 p  c21 (1  p ) и y  c12 p  c22 (1  p ) .
Используем обычный метод построения прямой линии по двум
точкам. При этом выберем значения p  0 и p  1. Соответствующими значениями ординат для первой прямой будут c21 и c11 , а для
второй прямой будут c22 и c12 . Следует отметить, что число c21 ,
отложенное на оси ординат, соответствует выигрышу первого иг24
 2 4 2


3 1 1
3 4
y  c11 p  c21 (1  p )
Следовательно, нижняя цена игры   max2; 1  2 , а верхняя цена
игры   min3; 4  3 . Так как    , то игра не имеет седловой
точки. Найдем оптимальные смешанные стратегии игроков
при многократном повторении игры. Используя формулы (6.3),
находим:
p10 
1
1 3
2 1  3  4
 0,5 ; p20  1   0,5 ; v 
 2,5 .
2  1  (3  4)
2
2  1  (3  4)
25
Для игрока B по формулам (6.4) найдем:
q10 
2,5  4
 0,75; q20  1  q10  0,25 .
24
Рассмотрим еще один способ решения матричной игры 2  2 .
Вспомним, что цена игры v вычисляется по формуле
m
Графическое решение задачи для игрока A представлено на рис. 4.
y
c12  4
c21  3
v  2,5
c11  2
c22  1
0
p10  0,5
1
p
Рис. 4
(6.5)
i 1 j 1
В итоге получаем оптимальные стратегии обоих игроков
B2 
 A A2 
 B
 , S B   1
 , v  2,5 .
S A   1
 0,5 0,5 
 0,75 0,25 
n
v (C , P, Q )    cij pi q j .
Рассмотрим игру 2  2 без седловой точки с матрицей выигрышей
c 
c
C   11 12 .
 c21 c22 
Для игры 2  2 смешанные стратегии игроков можно представить в виде
A2 
B2 
A
B
 и S B   1
S A   1
 .

 p 1 p
 q 1 q
Тогда функцию выигрышей (6.5) можно записать как произведение трех матриц:
v (C , p, q )  P  C  QT ,
q 
где P  ( p, 1  p ) – матрица-строка; QT  
 – матрица-столбец.
1  q 
Таким образом, функция выигрышей становится функцией
двух переменных p и q . Тогда из равенств (5.2) следует, что эта
функция удовлетворяет условиям
Возникает вопрос: как должны поступать игроки, исходя из
полученного результата? При многократном повторении игры игрок A может, например, выбирать стратегии A1 или A2, подбрасывая
монету, у которой, как известно, «герб» или «решетка» выпадают
с одинаковой вероятностью 0,5. Игрок B, для того чтобы поступать
в соответствии с рекомендуемой стратегией SB, может подбрасывать две монеты: если выпадут два «герба», то игрок B должен выбирать стратегию B2, в противном случае выбирается стратегия B1.
Замечание. Следует обратить внимание на важность построения разумного механизма случайного выбора конкретных стратегий с учетом полученных вероятностей в смешанных стратегиях.
Из теории математического анализа известно, что точка
( p , q 0 ) , удовлетворяющая условиям (6.6), определяется из системы уравнений
26
27
v (C , p 0 , q 0 )  min v (C , p 0 , q ),
q
0
0
v (C , p , q )  max v (C , p, q 0 ).
(6.6)
p
0
 v
 p  0,

 v  0 .
 q
(6.7)
Пример 6.2. Решим пример 6.1, используя систему (6.7).
 2 4
Так как C  
 , то
3 1
 2 4  q 
  2q  3 p  4 pq  1.
  
v (C , p, q )  P  C  QT  ( p, 1  p )  
 3 1  1  q 
Находя частные производные функции v (C , p, q ) по переменным
p и q:
v
v
 3  4q ,
 2 4p,
p
q
получим систему уравнений для нахождения значений p 0 и q 0
Полученный результат совпадает с решением данной задачи
предыдущим методом.
Проверь себя. Найти оптимальные смешанные стратегии игроков A и B и их средние выигрыши всеми тремя способами, рассмотренными в этом параграфе, если платежная матрица имеет вид:
 1 3 
 7 0
 .
а) C  
 ; б) D  
 1  5
  2 2
Придумать механизм случайного выбора стратегий с учетом полученных вероятностей.
 A A2 
 B B2 
 ; v A  0,2 ;
Ответы: а) S A   1
 ; S B   1
 0,6 0,4 
 0,8 0,2 
vB  0,2 ;
 A1 A2 
 B1 B2 
3
3
б) S A   4 7  ; S B   2 9  ; v A  1 ; vB  1 .




11
11
 11 11 
 11 11 
3  4q 0  0,

2  4 p 0  0.
Отсюда находим
q 0  0,75,
 0
 p  0,5.
Таким образом, получаем оптимальные смешанные стратегии
B2 
 A A2 
 B
 , S B   1
 .
S A   1
 0,5 0,5 
 0,75 0,25 
При этом функция выигрышей
v (C , p 0 , q 0 )  2  0,75  3  0,5  4  0,5  0,75  1  2,5.
28
29
l1 : y  c11 p  c21 (1  p ),
l2 : y  c12 p  c22 (1  p ),
§ 7. Матричные игры 2×n
l3 : y  c13 p  c23 (1  p )
Рассмотрим многоразовую игру 2  n с матрицей выигрышей
находим точку ( p10 , v) , которая и будет являться решением игры.
 c1n 
c
c
 .
C   11 12
 c21 c22  c2 n 
В такой игре игрок A имеет две стратегии: A1 и A2, а игрок B – n
стратегий: B1, B2, …, Bn. Пусть смешанные стратегии игроков A и B
имеют вид
A2 
B
A
 , S B   1
S A   1
 p 1 p
 q1
B2  B n 
,
q2  qn 
и их нижнюю огибающую L  min{l1 , l2 , l3} (рис. 5). Из рисунка
y
n
c22
j 1
v
 q j  1.
Предполагаем, что седловая точка в игре отсутствует. В силу равенства (5.5), имеем
0
v  min (c1 j p  c2 j (1  p ))  max min (c1 j p  c2 j (1  p )),
0  p 1
j
j
где j  1, n . Для нахождения max min (c1 j p  c2 j (1  p )) используем
0  p 1
j
графический метод. Для этого в плоскости ( p, y ) построим прямые
l j : y  c1 j p  c2 j (1  p ) , j  1, n . Здесь p  (0,1) – независимая переменная, а y  y ( p ) – переменная, зависящая от p . Далее построим
ломаную L  min{ l j } , огибающую снизу все эти прямые для
j
p  (0,1) . Тогда ордината y верхней точки ломаной L даст значение
y  v , в которой и достигается max min (c1 j p  c2 j (1  p )) . Это зна0  p 1
j
чение v и будет ценой игры.
В качестве примера рассмотрим случай n  3 . Построим три
прямые:
30
c11
c12
c21
0
0
l1
c23
l2
c13
p10
1
Рис. 5
l3
p
Найдем теперь оптимальную стратегию игрока B. Для этого
снова используем теорему 5.2. При нахождении оптимальной стратегии игрока B необходимо учитывать как расположение точки
( p10 , v) на плоскости, так и ее единственность (или неединственность).
Рассмотрим возможные варианты [5], [6], [7]:
1. Точка ( p10 , v) единственна. В этом случае точка максимума
огибающей L является точкой пересечения двух прямых. Например,
на рис. 5 такими прямыми являются прямые l1 и l2 , которые соответствуют первому и второму столбцу матрицы выигрышей C . По
теореме 5.2 активными будут только стратегии B1 и B2, а их вероятности войдут в уравнение (5.3) для нахождения оптимальной смешанной стратегии игрока B.
2. Точка ( p10 , v) не является единственной, то есть нижняя
огибающая L содержит целый горизонтальный участок, например,
31
как на рис. 6. Тогда для игрока B оптимальной является стратегия
Bk 0 , соответствующая прямой lk 0 , а для игрока A существует бесконечно много оптимальных смешанных стратегий, в которых вероятности p10 находятся между значениями p1 и p1 (см. рис. 6).
Решение. Для нахождения нижней и верхней цен игры составим таблицу
 1 3 4 1


 2 1 0 0
2
3
4
y
Тогда   max{1; 0}  1,   min{2; 3; 4}  2 . Так как    , то игра не
имеет седловой точки. Найдем оптимальные смешанные стратегии
игроков при многократном повторении игры. Составим матрицы
смешанных стратегий
lk 0
A
S A   10
 p1
0
p1
p1
1
p
Рис. 6
A2 
B
и S B   01
0

p2 
 q1
B2
q20
B3 
.
q30 
Будем решать задачу графически. Вычислим средний выигрыш игрока A при условии, что игрок B выбирает только чистые
стратегии. Имея в виду формулы (5.5), находим:
c12 p  c22 (1  p )  1  p  2  (1  p )  2  p ,
Пример 7.1. В новом микрорайоне имеются две автомойки,
прибыль которых зависит от количества обратившихся в них автовладельцев, проживающих в данном районе. Причем суммарная
прибыль обеих автомоек остается неизменной и равной 5 млн р.
в год. Стратегии ценовой политики автомойки выбирают один раз
в неделю. У первой автомойки (игрока A) две стратегии: A1 – поддерживать одинаковый уровень цен для всех клиентов, A2 – установить систему скидок для постоянных клиентов при увеличении
стоимости услуг на 10 % для остальных. У второй автомойки (игрока B) три стратегии. Причем стратегии B1 и B2 аналогичны стратегиям A1 и A2 соответственно, а стратегия В3 заключается в установлении дополнительных бонусов: например, каждая пятая мойка
машины для автовладельца будет бесплатной. Найти оптимальные
стратегии игроков, если платежная матрица имеет вид
 1 3 4
C  
 .
 2 1 0
Матрица C характеризует прибыль, получаемую первой автомойкой при применении i-й стратегии ( i  1, 2 ) при условии, что вторая
автомойка придерживается j-й стратегии ( j  1, 2, 3 ).
дет ординатой наивысшей точки ( p10 , ) ломаной L.
Ломаная L выделена на рис. 7 жирной линией. Из рисунка
видно, что точка ( p10 , ) является точкой пересечения прямых l1
и l3 , поэтому ее координаты удовлетворяют системе линейных
уравнений
y  2  p ,

 y  4 p.
32
33
c11 p  c21 (1  p )  3  p  1  (1  p )  1  2 p ,
c13 p  c23 (1  p )  4  p  0  (1  p )  4 p.
Теперь построим в системе координат ( p; y ) три прямые:
l1 : y  2  p ;
l2 : y  1  2 p ;
l3 : y  4 p
и нижнюю огибающую L  min{l1 , l2 , l3} (рис. 7). Цена игры v бу-
y
4
l3
3
l2
2
v
l1
1
0
3
, то есть в 60 % случаев, не снижать цену. В то же время
5
4
вторая автомойка с вероятностью , то есть в 80 % случаев, должна
5
1
придерживаться системы скидок, а с вероятностью , то есть при5
мерно в 20 % случаев, придерживаться бонусной системы. Этой автомойке стратегию B2 использовать не рекомендуется. При таком
выборе стратегий выигрыш (прибыль) автомойки A составит
1,6 млн р. в год. А так как суммарная прибыль автомоек – 5 млн р.,
то прибыль автомойки B составит 3,4 млн р. в год.
ностью
p10
1
p
Рис. 7
3
2
2 3
Решение этой системы: p10  , v  1 . Тогда p20  1  p10  1   .
5
5
5 5
Таким образом, оптимальная стратегия игрока A имеет вид
 A1
SA   2

5
A2 
3 .

5
Найдем теперь оптимальные стратегии для игрока B.
Поскольку решением является точка пересечения прямых l1 и l3 ,
то из трех стратегий игрока B активными являются стратегии B1
и B3, то есть в данной игре q20  0. Тогда, используя первое уравнение системы (5.3), будем иметь q10  4q30  v . Учитывая, что теперь
4
3
q10  q30  1, получаем q10  4(1  q10 )  v . Так как v  1 , то q10  ,
5
5
4 1
0
0
q3  1  q1  1   . Следовательно, оптимальная стратегия игро5 5
ка B имеет вид
 B1 B2 B3 
SB   4
1.


0
5
 5
2
Таким образом, первая автомойка должна с вероятностью , то
5
есть в 40 % случаев, придерживаться политики скидок, а с вероят34
Проверь себя. Найти оптимальные стратегии и средний выигрыш в игре с платежной матрицей:
  1 2  3
 5  2 0  4
;
а) C  
 ; б) D  
2 1
8 
4
 3 1
 4
 1 1,5 4 
в) E  
 .
 3 1,5  1
 A A2 
 B B2 B3 
Ответы: а) S A   1
 , v  0,5 ;
 , S B   1
 0,5 0,5 
 0 0,7 0,3 
 B1
 A1 A2 
б) S A   6 7  , S B   4



 13 13 
 13
A
в) S A   10
 p1
B2
9
13
B4 
, v  2 ;
0
0
13

B3
A2 
1 3
, где p10 лежит между и , а p20  1  p10 ;
0

p2 
2 4
 B B2 B3 
S B   1
 , v  1,5.
1 0 
 0
35
Пример 8.1. Упростить платежную матрицу
§ 8. Доминирующие и доминируемые стратегии
Иногда платежная матрица C  (cij ) , i  1, m , j  1, n , имеет такую структуру, что игра может быть упрощена отбрасыванием
в этой матрице некоторых строк (столбцов).
Рассмотрим матричную игру двух игроков: A и B. Пусть игрок
A имеет стратегии A1, A2, …, Am, а у игрока B имеются стратегии
B1, B2, …, Bn.
Определение. Будем говорить, что стратегия Ai доминирует
над стратегией Ak (стратегия Ak доминируется стратегией Ai), если
для элементов платежной матрицы C выполняются неравенства
cij  ckj , j  1, n ,
то есть элементы k-й строки матрицы C не превосходят соответствующих элементов ее i-й строки и хотя бы для одного значения j
неравенство является строгим.
Будем говорить, что стратегия Bj доминирует над стратегией Bl
(стратегия Bl доминируется стратегией Bj), если
cij  cil , i  1, m ,
то есть элементы j-го столбца матрицы C не превосходят соответствующих элементов ее l-го столбца и хотя бы для одного значения i
неравенство является строгим.
Справедливо очевидное утверждение.
Утверждение 8.1. Если платежная матрица C имеет доминируемые стратегии (строки или столбцы), то оптимальное решение
такой игры совпадает с оптимальным решением игры с платежной
матрицей C*, полученной из матрицы C отбрасыванием доминируемых строк (столбцов).
Замечания. 1. При отбрасывании доминируемых строк (столбцов) размер матрицы C уменьшается. Этот процесс упрощения игры можно продолжать до тех пор, пока не останется доминируемых
стратегий.
2. Если платежная матрица содержит несколько одинаковых
строк (столбцов), то оставляют только одну из таких строк (столбцов), а остальные отбрасывают.
36
0 2 4
 5


C    1  2 1 3 .
 4
7 3 6 

Решение. В данной матрице все элементы первой строки
(стратегия A1) больше соответствующих элементов второй строки
(стратегия A2). Поэтому стратегия A1 доминирует над стратегией A2,
а значит, в матрице C можно вычеркнуть вторую строку. Получим
матрицу
 5 0 2 4
C   
 .
 4 7 3 6
Так как элементы первого и четвертого столбцов больше соответствующих элементов третьего столбца, то игроку B, стремящемуся
проиграть как можно меньше, выгоднее использовать стратегию B3,
чем B1 и B4. Поэтому можно вычеркнуть первый и четвертый
столбцы. В итоге получается матрица
 0 2
C   
 .
7 3
Справедливо следующее утверждение.
Утверждение 8.2. Если элементы двух платежных матриц
C  (cij ) и D  (d ij ) , где i  1, m ; j  1, n , связаны соотношениями
cij  d ij   ,
где   0 ; γ – произвольное число, то оптимальные стратегии этих
игр совпадают, а цены игр связаны равенством
vC  vD  .
(8.1)
Пример 8.2. Рассмотрим две игры 2  3 с платежными матрицами
 1 5 3
 4 16 10 
C  
 и D  
 .
 4 1 2
13 4 7 
Требуется найти цены vC и vD этих игр.
37
Решение. Для игры с платежной матрицей C составим таблицу:
 1 5 3 1


 4 1 2 1
4 5 3
Отсюда находим:   max{1, 1}  1;   min{4, 5, 3}  3 . Так как
   , то в данной игре седловая точка отсутствует.
Будем искать оптимальные смешанные стратегии
A2 
B
A
и S B   01
S A   10
0

 p 1 p 
 q1
q20
игроков A и B. Для решения используем графический метод. Построим прямые:
l1 : y  c11 p  c21 (1  p)  1  p  4  (1  p)  4  3 p ,
l2 : y  c12 p  c22 (1  p)  5  p  1  (1  p)  1  4 p,
l3 : y  c13 p  c23 (1  p )  3  p  2  (1  p)  2  p
и нижнюю огибающую L  min{l1 , l2 , l3} (рис. 8).
3
v
2
l3
1
l1
p10
1
 A1
SA   1

2
Теперь найдем цену игры D. Заметим, что элементы матриц C
и D связаны соотношением d ij  3cij  1, i  1, 2 , j  1, 2, 3 . Тогда по
формуле (8.1) находим цену второй игры:
vD  3vC  1  3  2,5  1  8,5.
p
2
 1
Ответ: 
 .
 1  3
Рис. 8
38
A2 
1 .

2
2  3 1 0
1


4 1
2 1
3
C  2
0
1  3 6 .


4 1
2 1
3
1 2
1  4 3 

4
0
Таким образом, оптимальная стратегия игрока A имеет вид
Проверь себя. Упростить платежную матрицу
l2
5
1
1
1
p 0  , 1  p 0  , v  4  3 p  4  3   2,5 .
2
2
2
B3 

q30 
B2
y
Из рис. 8 видно, что оптимальная точка – это точка пересечения прямых l1 и l3 , то есть она определяется из системы
 y  4  3 p,

 y  2  p.
Решив систему, получим:
39
и перепишем неравенства (9.1) в виде
§ 9. Применение методов линейного программирования
при решении матричных игр m  n
Рассмотрим игру двух лиц с платежной матрицей (матрицей
выигрышей игрока A) C  (cij ) , i  1, m , j  1, n . Не ограничивая
общности, можем считать, что матрица C положительна. В противном случае к элементам матрицы C следует добавить одно и то же
положительное число, применяя утверждение 8.2.
Пусть смешанная стратегия игрока A имеет вид
A
S A   1
 p1
m
 cij pi .
m
i 1
Тогда выполняются неравенства
pi
, i  1, m ,
v
40
Следовательно, функцию F ( X ) надо минимизировать. Таким образом, приходим к следующей далее задаче линейного программирования. Найти минимум функции
(9.1)
(9.3)
i 1
при следующих ограничениях:
m
 cij xi  1, j  1, n,
i 1
 x  0, i  1, m.
 i
v  min  cij pi .
xi 
1
.
F(X )
F ( X )   xi  min
Обозначим через v минимальный средний выигрыш игрока A при
любой чистой стратегии игрока B, то есть
Введем новые переменные
i 1
m
i 1
m
 cij pi  v, j  1, n,
i 1
m
 p  1, p  0, i  1, m.
i
i

i 1
m
v  max . Введем в рассмотрение функцию F ( X )   xi , где
v
Тогда средний выигрыш игрока A при использовании игроком B
чистой стратегии Bj составит
(9.2)
Задача игрока A – максимизировать свой выигрыш, то есть
X  ( x1 ,..., xm ) . В силу (9.2)
A2  Am 
.
p2  pm 
j
m
 cij xi  1, j  1, n,
i 1
m
 x  1 , x  0, i  1, m.
i
i

v
i 1
(9.4)
Рассмотрим теперь игру игрока B. Его смешанная стратегия
обеспечит ему средний проигрыш, не больший чем v , при любой
чистой стратегии игрока A, то есть
n
  cij q j  v, i  1, m,
 j 1
n
 q  1, q  0, j  1, n.
j
j

 j 1
41
(9.5)
Таким образом, приходим к результату, представленному
в теореме 9.1.
Теорема 9.1. Решение матричной игры с положительной матрицей выигрышей C  (cij ) , i  1, m , j  1, n , равносильно решению
двойственных задач линейного программирования (9.3)–(9.4), (9.7)–
(9.8). При этом цена игры v удовлетворяет равенству
Вводя новые переменные
yj 
qj
v
,
j  1, n,
преобразуем систему (9.5) к виду
n
  cij y j  1, i  1, m,
 j 1
n
 y  1 , y  0, j  1, n.
j
j


 j 1
v
(9.6)
а
n
Рассмотрим функцию G (Y )   y j , где Y  ( y1 ,..., yn ) . В силу (9.6)
оптимальные
1
.
G (Y )
Так как для игрока B его проигрыш v надо минимизировать,
то функцию G (Y ) надо, напротив, максимизировать. Приходим
к задаче линейного программирования: найти максимум функции
n
G (Y )   y j  max
(9.7)
j 1
при следующих ограничениях:
n
  cij y j  1, i  1, m,
 j 1
 y  0, j  1, n.
 j
pi0
0
yj
xi0

, q 0j 
.
0
F(X )
G (Y 0 )
Алгоритм решения матричной игры с помощью решения
двойственных задач линейного программирования следующий:
1. Ко всем элементам платежной матрицы C прибавим одно
и то же положительное число γ так, чтобы все ее элементы стали
положительными.
2. Составим пару двойственных задач линейного программирования (9.3)–(9.4) и (9.7)–(9.8) и найдем их решения xi0 , y 0j . В качестве контроля правильности решения задач можно использовать
равенство
F ( X 0 )  G (Y 0 ) .
3. Построим оптимальные смешанные стратегии игроков:
0
pi0 
yj
xi0
0
, i  1, m , j  1, n .
,

q
j
F(X 0)
G (Y 0 )
(9.9)
4. Вычислим цену игры:
v
42
Q0 
и
(9.8)
Из курса линейного программирования известно (см. также [8]),
что задачи (9.3)–(9.4) и (9.7)–(9.8) представляют собой пару двойственных задач и имеют оптимальные решения X 0  ( x10 , x20 ,  , xm0 )
и Y 0  ( y10 , y20 ,  , yn0 ) .
P 0  ( p10 , p20 ,  , pm0 )
вероятности
 ( q10 , q20 ,  , qn0 ) определяются формулами
j 1
v
1
1
,

0
F ( X ) G (Y 0 )
1
1
 
 .
0
F(X )
G (Y 0 )
43
(9.10)
Пример 9.1. Решить матричную игру из примера 7.1 методами
линейного программирования с матрицей выигрышей
 1 3 4
D  
 .
 2 1 0
Будем искать решение в смешанных стратегиях. Составим
прямую и двойственную задачу линейного программирования.
Прямая задача имеет вид
2 x1  3x2  1,
4 x  2 x  1,
 1
2

5
x
x

 1 2  1,
 x1  0, x2  0.
 
p10 
Решение. В примере 7.1 было получено:   1 ,   2 . Прибавим
число   1 ко всем элементам матрицы D и рассмотрим матрицу
 2 4 5
C  
 .
 3 2 1
F  ( X )  x1  x2  min,
Решение задачи (9.11)–(9.12) дает следующий результат:
5
2
3
x10  , x20  , причем F  X 0  . По формулам (9.9) получаем:
13
13
13
(9.11)
(9.12)
x10
2
3
x20
0
,


 .
p
2
2
2
5
5
 xi0
 xi0
i 1
i 1
Таким образом, оптимальная смешанная стратегия игрока A будет
иметь вид
 A1 A2 
SA   2 3  .


5 5
4
При решении задачи (9.13)–(9.14) получаем y10  , y20  0 ,
13
1
5
y30  , при этом G  Y 0  . Тогда по формулам (9.9) вычисляем:
13
13
 
q10 
y10
4
1
y20
y30
0
0
,
,



0

 .
q
q
2
3
3
3
3
5
5
 y 0j
 y 0j
 y 0j
j 1
j 1
j 1
Значит, оптимальная смешанная стратегия игрока B
Двойственная задача имеет вид
G  (Y )  y1  y2  y3  max,
(9.13)
2 y1  4 y2  5 y3  1,

3 y1  2 y2  y3  1,
 y  0, y  0, y  0.
 1
2
3
(9.14)
 B1
SB   4

 5
B3 
1 ,

0
5
B2
а цена игры, как следует из формулы (9.10):
v
1
1
13
3
    0    1  1 .
0
5
5
F (X )
G (Y )

Для решения задачи можно использовать симплекс-метод.
Компьютерная реализация симплекс-метода имеется во многих
программах и прикладных пакетах, например Excel, Mathcad,
Maple, Mathematica и др.
В заключение отметим совпадение результатов при решении
матричной игры из примера 7.1 разными способами.
44
45
Проверь себя. 1. Решить матричную игру с матрицей выигрышей
4
1 3
D  
.
1  2 
0
1
3 7
 3 2
Ответ: P 0   ,  , Q 0   0, ,  , v   .
5
 10 10 
 5 5
2. Решить задачу с платежной матрицей из примера б) в разделе «Проверь себя» § 7, используя методы линейного программирования. Сравнить полученный результат.
§ 10. Биматричные игры
Не всегда интересы двух игроков противоположны, как это
имеет место в антагонистических играх. Часто встречаются ситуации, в которых интересы участников взаимодействия не являются
противоположными. Проиллюстрируем это на классическом примере, называемом «Дилемма заключенного» (см., например, [9]).
Дилемма заключенного 1. Двое подозреваемых (A и B) в совершении преступления арестованы, помещены в одиночные камеры и не имеют возможности передавать друг другу какие-либо
сообщения. Их допрашивают поодиночке. Если оба признаются
в совершении преступления, то им грозит (с учетом их признания)
тюремное заключение сроком по 6 лет каждому. Если оба не признаются, то они получат по 1 году тюремного заключения. Если же
один из них сознается, а другой – нет, то первый, за содействие
следствию, будет вовсе освобожден от наказания, тогда как второй
будет приговорен к максимально возможному за данное преступление наказанию – 10-летнему тюремному заключению.
Описанная ситуация может быть представлена следующей игрой с матрицами выигрышей для заключенных A и B соответственно:
0
  1  10 
 1
 .

 и 
 0  6
  10  6 
Здесь первые строки матриц выигрышей соответствуют стратегии
заключенного A «молчать», а вторые строки – стратегии «сознаться». При этом первые столбцы матриц выигрышей соответствуют
стратегии заключенного B «молчать», а вторые столбцы – стратегии «сознаться».
Очевидно, что стратегия «молчать» является строго доминируемой для каждого игрока (так как ни один из них не знает, что
предпримет другой), поэтому каждый игрок выберет стратегию
«сознаться». В результате оба заключенных получат по 6 лет тюремного заключения. При этом мы сразу же сталкиваемся с очевидной проблемой: получающийся результат игры очень плохой –
он дает максимальный суммарный срок заключения. Этот факт послужил толчком к многочисленным исследованиям данной игры,
46
47
поскольку, например, естественным желанием было бы получить
в качестве результата игры (или ее модификаций) выбор стратегий
«молчать», дающий каждому заключенному лишь по одному году
заключения.
Такая же проблема возникает и в следующей экономикополитической задаче (в силу схожести специфики с предыдущей
задачей мы сохраняем прежнее название).
Дилемма заключенного 2. Рассмотрим нефтедобывающие
страны A и B. Эти страны могут кооперироваться, договариваясь об
объемах ежедневной добычи нефти, ограничиваясь, например, добычей 2 млн баррелей нефти в день для каждой страны. Но страны
могут действовать и некооперативно, добывая, например, по 4 млн
баррелей в день. Таким образом, считаем, что у игроков A и B по
две стратегии: A1, B1 – договориться об ограничениях по добыче
нефти; A2, B2 – добывать нефть без всяких ограничений. Такая ситуация может быть представлена игрой со следующими матрицами
выигрышей для стран A и B соответственно:
для игроков A и B соответственно. В этом случае игру называют
биматричной. Очевидно, что антагонистические игры являются
частным случаем биматричных игр в случае, когда bij  aij для
 46 26 
 42 44 

 .
 и 
 52 32 
 22 24 
с элементами (aij , bij ) . Случай, когда aij  bij  const , i  1, m ,
В матрицах указаны прибыли (млн долларов в день) стран
в зависимости от их объемов добычи нефти. Очевидно, что у каждой страны есть стимул отклониться от договора, чтобы за счет
увеличения объемов производства получить дополнительную прибыль. Мы видим, что и здесь у каждого из игроков есть доминирующая стратегия – «не кооперироваться». В итоге страны получают
прибыль 32 и 24 (млн долларов в день), что гораздо меньше, чем
в ситуации кооперативного поведения.
Таким образом, мы сталкиваемся с ситуацией, аналогичной
предыдущей: оба игрока выбирают свои доминирующие стратегии,
увеличивая тем самым свои выигрыши, но исход для каждого из
них хуже, чем в ситуации, когда оба следуют доминируемым стратегиям.
Рассмотрим конфликт, в котором участвуют игроки A и В.
Пусть игрок A имеет стратегии A1, A2, …, Am, а игрок B – стратегии
B1, B2, …, Bn. При этом выбранной игроками стратегии { Ai , B j } со48
ответствуют выигрыши aij и bij игроков A и B соответственно. Вообще говоря, aij  bij . Таким образом, в такой игре существуют две
различные матрицы выигрышей:
A  (aij ) и B  (bij ) , i  1, m , j  1, n ,
всех i  1, m , j  1, n . Иногда биматричную игру представляют одной матрицей
 (a11 , b11 ) (a12 , b12 )  (a1n , b1n ) 


 (a21 , b21 ) (a22 , b22 )  (a2 n , b2 n ) 

 





 (am1 , bm1 ) (am 2 , bm 2 )  (amn , bmn ) 
j  1, n , соответствует матричной игре.
Рассмотрим смешанные стратегии игроков при многократном
повторении игры
A
S A   1
 p1
A2  Am 
B
 и S B   1
p2  p m 
 q1
B2  Bn 
.
q2  qn 
Средние выигрыши игроков определяются математическими
ожиданиями
H A ( P, Q)   aij pi q j и H B ( P, Q)   bij pi q j .
i, j
i, j
Определение. Будем говорить, что пара ( P 0 , Q 0 ) векторов
P 0  ( p10 , p20 ,  , pm0 ) и Q 0  (q10 , q20 , , qn0 ) определяет равновесную
ситуацию (точку равновесия), если при любых векторах
49
P  ( p1 , p2 ,..., pm ) и Q  (q1 , q2 ,..., qn ) , элементы которых удовлетворяют условиям
m
n
i 1
j 1
 pi  1 и  q j  1, выполняются неравенства
H A ( P, Q 0 )  H A ( P 0 , Q 0 ) и H B ( P 0 , Q )  H B ( P 0 , Q 0 ) .
Для биматричных игр 2  2 справедлива следующая теорема.
Теорема 10.2. Неравенства (10.1) для равновесных ситуаций
эквивалентны следующей системе неравенств:
 H A (0, q 0 )  H A ( p 0 , q 0 ),

0
0 0
 H A (1, q )  H A ( p , q ),

0
0 0
 H B ( p , 0)  H B ( p , q ),

0
0 0
 H B ( p ,1)  H B ( p , q ).
(10.1)
Неравенства (10.1) означают, что отклонение игроков от равновесной ситуации ( P 0 , Q 0 ) может только уменьшить их выигрыши. Возникает вопрос: всегда ли существует равновесная ситуация?
Положительный ответ на этот вопрос дает следующая теорема.
Теорема 10.1 (Дж. Нэш). Любая биматричная игра имеет хотя
бы одну точку равновесия в чистых или смешанных стратегиях.
Замечание. Равновесие по Нэшу в биматричных играх – это
обобщение понятия седловой точки (оптимального решения) в играх с нулевой суммой.
Рассмотрим примеры нахождения точки равновесия. Сначала
изучим самую простую биматричную игру 2  2 с матрицами выигрышей
a 
b 
a
b
A   11 12  и B   11 12  .
 a21 a22 
 b21 b22 
(10.3)
Теорема 10.2 означает, что для нахождения равновесной пары
( P , Q 0 ) , где P 0  ( p 0 ,1  p 0 ) ; Q 0  (q 0 ,1  q 0 ) , достаточно проверить справедливость неравенств (10.1) не для всех значений вероятностей p и q, а только для чистых стратегий каждого из игроков.
Преобразуем функции выигрышей (10.2) к виду, удобному для
применения теоремы 10.2,
0
H A ( p, q )  (a11  a12  a 21  a 22 ) pq  (a12  a 22 ) p 
 (a21  a22 )q  a22 .
(10.4)
Полагая в (10.4) p  0 и p  1 , получим
H A (0, q )  (a21  a22 )q  a22 ,
Пусть смешанные стратегии игроков имеют вид
H A (1, q )  (a 11  a12  a21  a22 )q  a12  (a21  a22 )q.
A2 
B2 
A
B
 и S B   1
S A   1
 .
 p 1 p
 q 1 q
Следовательно,
Тогда средние выигрыши HA и HB игроков A и B будут зависеть
только от двух переменных: p и q. При использовании стратегий S A
и S B средние выигрыши игроков
H A ( p, q )  a11 pq  a12 p(1  q )  a21 (1  p)q  a22 (1  p)(1  q),
H A ( p, q )  H A (1, q )  (a11  a12  a21  a22 )q ( p  1) 
 (a12  a22 )( p  1),
(10.5)
H A ( p, q )  H A (0, q )  (a11  a12  a21  a22 ) pq  (a12  a22 ) p.
Если ввести обозначения
(10.2)
H B ( p, q )  b11 pq  b12 p(1  q)  b21 (1  p)q  b22 (1  p)(1  q).
50
C  a11  a12  a21  a22 ,

c  a22  a12 ,
51
(10.6)
то формулы (10.5) примут вид
H A ( p, q )  H A (1, q )  Cq ( p  1)  c( p  1),
H A ( p, q )  H A (0, q )  Cpq  cp  p (Cq  c).
Так как в точке равновесия ( P 0 , Q 0 ) выполняются неравенства
(10.3), то получаем систему неравенств
( p  1)(Cq  c)  0,

 p (Cq  c)  0.
Аналогичным образом, рассматривая разности H B ( p, q )  H
)  H B ( p,1) , H B ( p, q )  H B ( p,0) и вводя обозначения
 D  b11  b12  b21  b22 ,

d  b22  b21 ,
(10.7)
получим систему неравенств
Пример 10.1 (Заказчик – исполнитель). Строительная компания (игрок A) сдает дом, который принимает заказчик (игрок B).
У строительной компании две стратегии: A1 – безупречно подготовить дом к сдаче, исправив все недостатки, и стратегия A2 – замаскировать некоторые недостатки и попытаться «договориться» с заказчиком принять дом в таком виде.
У заказчика тоже две стратегии: B1 – подписать все документы
о сдаче дома, B2 – не подписывать документы, требуя устранить все
недоделки. Требуется решить данную биматричную игру. Сначала
формализуем ситуацию.
Исход игры для заказчика:
Дом безупречно
построен
Много недоделок
Подписывает
документ о сдаче
Все довольны
Или дали себя
обмануть, или сами
нечестные люди
Не подписывает
документ
Слишком
придирались
Надо ждать
устранения
недоделок
Исход игры для исполнителя:
(q  1)( Dp  d )  0,

q ( Dp  d )  0.
Дом сдан комиссии
В итоге пара ( P 0 , Q 0 ) определяет равновесную ситуацию
в биматричной игре 2  2 тогда и только тогда, когда выполняется
система неравенств
( p  1)(Cq  c)  0,
 p (Cq  c)  0,

(q  1)( Dp  d )  0,
q ( Dp  d )  0,

0  q  1, 0  p  1,
(10.8)
Дом безупречно
построен
Много недоделок
Все довольны
Удалось обмануть
комиссию или
«договориться»
Оценка заслужена
Количественно выигрыши игроков можно выразить в виде матриц,
например, так:
 2  1
 1  3
A  
 .
 , B  
 1 0
  2  1
Игру можно задать также матрицей
где C , c , D , d вычисляются по формулам (10.6) и (10.7) и могут
принимать любые значения.
52
Дом не сдан
комиссии
Очень обидно
53
 (2; 1) (1;  3) 
 .

 (1;  2) (0; 1) 
Решим теперь вторую систему:
Вычислим параметры C, c, D, d по формулам (10.6) и (10.7):
C  2  (1)  1  0  2 ; c  0  1  1;
D  1  (2)  (3)  1  5 ; d  1  (2)  1 .
Графически решение второй системы показано на рис. 10 также
в виде ломаной, выделенной жирно.
Тогда неравенства (10.8) примут следующий вид:
(q  1)(5 p  1)  0,

q (5 p  1)  0.
( p  1)(2q  1)  0,

 p (2q  1)  0;
1
1) если q  1, то 5 p  1  0 , откуда p  ;
5
1
2) если q  0 , то 5 p  1  0 , откуда p  ;
5
1
3) если 0  q  1, то p  .
5
q
1
Решим первую систему:
1
1) если p  1 , то 2q  1  0 , откуда q  ;
2
1
2) если p  0 , то 2q  1  0 , откуда q  ;
2
1
3) если 0  p  1, то q  .
2
0
Найденные решения первой системы показаны на плоскости
( p, q ) (рис. 9) в виде ломаной, выделенной жирно.
q
1
5
1
p
Рис. 10
Таким образом, решения системы (10.8) – это точки M1, M2, M3
пересечения ломаных, построенных на рис. 9 и 10 (рис. 11).
q
1
1
1
2
M3
1
2
1
0
Рис. 9
54
p
M2
M1
0
1
5
1
Рис. 11
55
p
Так как ломаные пересекаются в трех точках, то имеются три
равновесные ситуации. Найдем выигрыши игроков для каждой
равновесной точки.
1. Рассмотрим точку равновесия M 1 (0, 0) . Ей соответствуют
стратегии игроков
 A A2 
 B B2 
S A   1
 .
 и S B   1
0 1
0 1
То есть игроки каждый раз применяют свои чистые стратегии
A2 и B2, следовательно, их средние выигрыши H A (0, 0)  a22  0 ,
H B (0, 0)  b22  1.
1 1
2. Точке M 2  ,  соответствуют смешанные стратегии
5 2
 A1 A2 
 B1 B2 
S A   1 4  и SB   1 1  .




2 2
5 5
В данном случае средние выигрыши находим по формулам
1 1
1 1
(10. 2): H A  ,   0,5 ; H B  ,   1,4 .
5 2
5 2
3. Точке M 3 (1, 1) соответствуют чистые стратегии A1 и B1,
а значит, H A (1, 1)  a11  2 , H B (1, 1)  b11  1.
Получаем, что наибольший выигрыш обе стороны будут
иметь при p  q  1, то есть когда весь дом будет полностью построен и принят заказчиком.
Замечание. В задачах такого рода имеется очевидная трудность перехода от качественных оценок к количественным. Если
матрицы A и B изменить, то получатся, вообще говоря, другие точки равновесия игры.
Пример 10.2 (Борьба за рынки) [9]. Фирма (игрок) A хочет
продать партию товара на одном из двух рынков, которые уже захвачены другой крупной фирмой (игроком) B. Для реализации своего плана фирма A разворачивает рекламную компанию на одном
56
из этих рынков. Фирма B вполне может воспрепятствовать этому на
одном из рынков. Если фирма A встречает противодействие, то она
терпит поражение на этом рынке. В противном случае она захватывает рынок.
Предположим, что захват первого рынка для фирмы A более
выгодный, но и поражение на нем принесет бóльшие убытки, чем
на втором рынке. Допустим, что эта ситуация может повторяться
многократно.
Решим биматричную игру. Каждая из фирм имеет по две стратегии: A1 и A2 – захват фирмой A первого и второго рынков соответственно; B1 и B2 – захват фирмой B этих рынков.
Оценки сложившейся ситуации могут быть выражены, например, платежными матрицами
3
8
 5  2
A  

 и B  
1
 2  2
 1
или одной матрицей
 (8; 5) (3;  2) 
 .

 (2; 1) (2; 1) 
Из условия задачи видно, что если обе фирмы выберут один
и тот же рынок, то выиграет фирма B. Если же фирмы выбирают
разные рынки, тогда в выигрыше окажется фирма A. Найдем равновесные ситуации в смешанных стратегиях игроков. Для этого вычислим значения C, c, D, d по формулам (10.6) и (10.7):
C  8  3  2  2  15 ; c  2  3  5 ;
D  5  (2)  (1)  1  9 , d  1  (1)  2 .
Неравенства (10.8) при условии, что 0  p  1, 0  q  1, имеют вид
(q  1)(9 p  2)  0,
( p  1)(15q  5)  0,
и 

q (9 p  2)  0.
 p (15q  5)  0
57
Из первой системы имеем:
оптимальные
1
1) если p  1, то  15q  5  0 , откуда q  ;
3
1
2) если p  0 , то  15q  5  0 , откуда q  ;
3
1
3) если 0  p  1, то q  .
3
2 7
P0   ,  ,
9 9
2
H A ( p 0 , q 0 )  a11 pq  a12 p (1  q )  a21 (1  p )q  a22 (1  p )(1  q )   ,
3
1
H B ( p 0 , q 0 )  b11 pq  b12 p (1  q )  b21 (1  p )q  b22 (1  p )(1  q )  .
3
Графически решения систем в плоскости ( p, q ) показаны на
рис. 12 (жирные ломаные).
q
1
1
3
1
p
Рис. 12
Из рисунка видно, что точка равновесия в данной игре только
2
1
одна. Для нее p  , q  . Таким образом, получаем следующие
9
3
Проведем анализ полученных результатов с экономической
точки зрения. Если возможен многократный захват рынков в опи2
санных условиях, то фирма A должна с вероятностью , то есть
9
примерно в 22 % случаев, пытаться проникнуть на первый рынок,
а в остальных 78 % – на второй. При этом в среднем она не проиг2
рает больше чем условных единиц. В то же время фирма B долж3
1
на с вероятностью , то есть примерно в 33 % случаев, противо3
действовать фирме A на первом рынке, а в остальных 67 % – на
втором. При этом средний выигрыш фирмы B составит не менее
1
условных единиц.
3
Заметим, что в данной задаче – одна точка равновесия. Но, конечно, в других ситуациях таких равновесных точек может быть
и больше. В этом случае выбор одной из них должен осуществляться из каких-то других качественных условий конфликта. Такой выбор бывает сделать довольно сложно, и это представляет собой
определенную проблему в экономической науке.
В данной задаче можно также заметить, что точка равновесия
определяется числами C, c, D, d, а именно:
p0 
58
игроков:
Соответствующие средние выигрыши фирм A и B:
2
1) если q  1, то 9 p  2  0 , откуда p  ;
9
2
2) если q  0 , то 9 p  2  0 , откуда p  ;
9
2
3) если 0  q  1, то p  .
9
2
9
стратегии
1 2
Q0   ,  .
3 3
Из второй системы имеем:
0
смешанные
d
c
, q0  .
D
C
59
Причем в равновесной ситуации выбор одного игрока полностью
определяется матрицей выигрышей другого и не зависит от собственной матрицы. Другими словами, равновесная ситуация определяется усилиями игроков держать под контролем другого игрока.
Проверь себя. Решить биматричную игру с матрицей выигрышей
 (2; 1) (1; 1) 
 (3; 0) (1; 1) 
а) 
 ; б) 
 .
 (4;  2) (3; 0) 
 (4; 1) (5;  3) 
Ответы:
а)
1 1
P0   ,  ,
 2 2
 2 3
Q0   ,  ,
 5 5
1
H A ( p0 , q0 )   ,
5
1
H B ( p0 , q0 )   ;
2
б) P 0  1,0  , Q 0  1,0  , H A ( p 0 , q 0 )  3 , H B ( p 0 , q 0 )  0 .
§ 11. Игры с природой
Во всех примерах, рассмотренных в предыдущих параграфах,
оба игрока принимают решения, то есть выбирают свои стратегии
осознанно, с целью получения наибольшего выигрыша или
наименьшего проигрыша. Но так бывает не всегда. В экономической практике при принятии решений можно столкнуться с неопределенными силами. Эта неопределенность не связана с сознательным целенаправленным противодействием противника. Часто
встречается ситуация, в которой лицо, принимающее решение, недостаточно информировано об объективных внешних условиях.
Неопределенность такого вида может порождаться различными
причинами: нестабильностью экономической ситуации, рыночной
конъюнктурой, курсом валют, уровнем инфляции, изменяющимся
покупательским спросом, природными условиями и т. д. В таких
играх только один из игроков действует осознанно. Другим игроком является незаинтересованная объективная действительность:
покупательский спрос, стихийные природные условия, сложившаяся стихийно экономическая обстановка и т. д. Эта вторая сторона
не противодействует первому игроку как противник, а действует
случайным образом. Такие игры принято называть играми с природой. Пусть у игрока A имеется m стратегий: A1, A2,…, Am. У игрока П
(природы) имеется n возможностей находиться в одном из состояний: П1, П2,…, Пn, которые можно назвать стратегиями природы.
Матрица выигрышей игры с природой состоит из элементов cij , соответствующих паре ( Ai , П j ) , i  1, m , j  1, n . Такую игру, с одной
стороны, можно считать частным случаем антагонистической игры.
С другой стороны, отличие состоит в том, что величины cij не являются проигрышами природы. За эти проигрыши платить будет
какая-то третья сторона, например жители данной местности, работники конкретной фирмы и т. д.
В играх с природой по-другому дело обстоит и с отношением
доминирования. Именно, принципом доминирования можно пользоваться только по отношению к игроку A, который действует осознанно. Но по отношению ко второму игроку (природе) этот прин-
60
61
цип неприменим, поскольку свои стратегии природа «выбирает»
случайно.
Далее будем считать, что доминируемые строки из матрицы
выигрышей удалены. Требуется выбрать такую стратегию игрока A,
которая является предпочтительной по сравнению с другими стратегиями. Возникает вопрос, как оценить удачность выбора какойлибо стратегии Ai, i  1, m , игроком A при состоянии природы Пj,
j  1, n , в условиях полной неопределенности. Надо ввести показатель степени этой удачности. Для этого вводится понятие «риск».
Определение. Риском rij игрока A при применении стратегии
Ai в условиях состояния природы Пj называется разность между
выигрышем, которую он получил бы, если бы знал состояние природы Пj, и выигрышем, который он получит в тех же условиях,
применяя стратегию Ai:
rij  (max cij )  cij , i  1, m , j  1, n .
i
Матрица рисков R  (rij ) , i  1, m , j  1, n , имеет ту же размерность, что и матрица выигрышей C  (cij ) . Риск rij выражает упущенную возможность максимального выигрыша при данном состоянии природы. Величина риска – это плата за неинформированность о действительном состоянии объективной реальности.
Пример 11.1. Планируется застройка нового микрорайона при
неизвестных условиях рыночного спроса, о котором можно сделать
три предположения: П1, П2, П3. Ожидаемая прибыль от застройки
при этих условиях выражается матрицей выигрышей
5 1 5 


C  9 8 1  .
4 3 2 


(11.1)
Построим матрицу рисков для этой игры. Для этого вычтем каждый
элемент матрицы cij из максимального значения каждого из столбцов матрицы C. Например, в первом столбце максимальным является элемент c21  9 . Вычитая поочередно из этого значения эле62
менты первого столбца, получим 4, 0, 5. Поступая аналогично со
вторым и третьим столбцами, получим матрицу рисков
4 7 0 


R  0 0 4  .
5 5 3 


(11.2)
Эта матрица хорошо иллюстрирует суть игры с природой. При
выборе первой стратегии игроком A величины выигрышей:
c11  c13  5 , то есть одинаковы. Но эти выигрыши не являются равноценными, так как величины рисков, то есть упущенные возможности, у них существенно отличаются. Из матрицы (11.2) находим:
r11  4 , r13  0 . Это означает, что при состоянии П1 игрок A мог бы
выиграть 9 условных единиц (у. е.), а выиграл всего 5 у. е. или, что
то же самое, проиграл r11  4 у. е. При состоянии природы П3 риск
r13  0 , то есть игрок A выиграл по максимуму и не упустил своих
возможностей. Таким образом, выбор стратегии A1 по отношению
к состоянию П3 более предпочтителен, чем по отношению к состоянию П1.
Поставим задачу выбрать чистую или смешанную стратегию,
которая была бы наиболее выгодной по сравнению с другими. Если
неизвестны вероятности состояний природы Пj, то мы имеем дело
с условиями полной неопределенности. Если же эти вероятности
даны априорно, то возникает ситуация принятия решения в условиях
риска.
Рассмотрим сначала условия полной неопределенности. В таких моделях при выборе оптимальной стратегии используется ряд
критериев.
1. Критерий максимакса
Это критерий крайнего оптимизма, максимизирующий максимальные выигрыши игрока A при различных состояниях природы.
При этом наилучшей считается стратегия, при которой достигается
максимальный выигрыш,
M  max max cij .
i
j
63
Например, для матрицы (11.1) этот принцип дает
M  max5; 9; 4  9 , что соответствует стратегии A2. Этот критерий
ориентирует игрока A на наилучшее состояние природы. Таким
критерием в экономике пользуются либо безоглядные оптимисты,
либо лица, поставленные в безвыходное положение, у которых
только и остается, что «поставить на карту все».
сильнее подстраховаться, то надо выбирать значение   0,5 . Если
предпочтений нет, то можно выбрать «золотую середину»:   0,5 .
Найдем в примере 11.1 оптимальную стратегию по критерию
Гурвица при   0,7 .
M  max(0,7  min cij  0,3  max cij ) 
i
2. Максиминный критерий Вальда
В этом случае оптимальной считается такая стратегия, которая
обеспечивает максимум минимального выигрыша при различных
состояниях природы, то есть стратегия, гарантирующая при любых
условиях выигрыш, не меньший, чем максимин:
M  max min cij .
i
j
При этом критерии природа рассматривается как агрессивно
настроенный противник и предполагается самое неблагоприятное
ее состояние. В частности, для матрицы (11.1) получим
M  max1; 1; 2  2 , что соответствует выбору стратегии A3. Такую
позицию можно назвать позицией крайнего пессимизма. Часто
в экономике ее используют те, кто руководствуется поговоркой:
«Береженого бог бережет». Такое решение практически исключает
риск, поэтому критерий Вальда является одним из основных критериев при решении экономических или технических задач.
3. Критерий Гурвица
Этот критерий рекомендует «не впадать в крайности», то есть
не вдаваться в крайний оптимизм или крайний пессимизм, а выбрать ту стратегию, которая дает промежуточный результат:
M  max(  min cij  (1  )  max cij ),
i
j
j
где числовой параметр   [0; 1] можно назвать степенью пессимизма.
При   1 получим пессимистический критерий Вальда, а при
  0 – максимаксный критерий крайнего оптимизма.
Выбор конкретного значения параметра  определяется субъективными факторами и конкретной ситуацией. Если необходимо
64
j
j
 max0,7  1  0,3  5; 0,7  1  0,3  9; 0,7  2  0,3  4 
 max2,2; 3,4; 2,6  3,4.
Этот элемент соответствует второй стратегии, то есть оптимальной
является стратегия A2.
4. Критерий Сэвиджа
Это критерий минимального риска, который тоже можно отнести к критериям полного пессимизма. Выбирается такая стратегия, при которой величина риска в наихудшем случае минимальна:
M  min max rij .
i
j
В
примере
11.1
из
матрицы
(11.2)
получим:
M  min7; 4; 5  4 , поэтому наилучшей считается стратегия A2.
Замечания. 1. Несмотря на то, что критерии Вальда и Сэвиджа
считаются критериями крайнего пессимизма, они могут приводить
к выбору разных стратегий. Это хорошо видно на примере 11.1.
2. Конкретных рекомендаций по применению того или иного
критерия не существует. Лицо, принимающее решение, должно
оценивать степень риска в конкретной ситуации. Можно выбирать
разные критерии поочередно, а потом сделать окончательный выбор в пользу той или иной стратегии. Если различные критерии
приводят к выбору одной и той же стратегии, то именно ее можно
выбрать в качестве оптимальной в неопределенных условиях природы.
Рассмотрим теперь ситуацию частичной или неполной информированности игрока A, то есть случай принятия решения
в условиях риска.
65
M 1  0,2  70  0,3  20  0,5  30  35;
Предположим, что игрок A имеет сведения о вероятности
наступления состояний природы П:
p j  p ( П  П j ) , j  1, n ,
M 2  0,2  35  0,3  85  0,5  20  42,5;
n
 p j  1.
M 3  0,2  80  0,3  10  0,5  35  36,5.
j 1
Рассмотрим несколько критериев принятия решений в игре
с природой в условиях риска.
5. Критерий Байеса
Согласно этому критерию, показателем эффективности стратегии Ai, i  1, m , является математическое ожидание (среднее значение) выигрыша с учетом вероятностей всех возможных состояний природы Пj:
n
M i   p j cij , i  1, m .
j 1
При этом оптимальной среди чистых стратегий считается стратегия
с максимальным показателем эффективности
1 i  3
вод, что оптимальной является стратегия A2.
6. Критерий Лапласа
Это частный случай предыдущего критерия. В некоторых
условиях можно считать, что все n состояний природы Пj равновероятны, то есть
1
p j  p( П  П j )  .
n
Тогда критерий Лапласа рекомендует выбрать такую стратегию,
при которой достигается максимум:

1 n
M  max   c ij  .
1 i  m n j 1


M  max M i .
1 i  m
Пример 11.2. На промышленном предприятии выпуск новых
видов продукции A1, A2, A3 зависит от степени обеспеченности производства материальными ресурсами: П1, П2, П3. Каждой паре
( Ai , П j ) , i  1,3 , j  1,3 , соответствует определенный выигрыш –
эффективность выпуска новых видов продукции. Возможные выигрыши выражаются численно матрицей
 70 20 30 


C   35 85 20  .
 80 10 35 


Тогда M  max M i  max35; 42,5; 36,5  42,5 . Отсюда делаем вы-
Вычислим это значение для матрицы (11.3) из примера 11.2.
Имеем
1
1

1
M  max  (70  20  30); (35  85  20); (80  10  35) 
3
3

3
2
 140 125 
;
 max 40;
  46 .
3
3 
3

(11.3)
Следовательно, по критерию Лапласа рекомендуется выбрать стратегию A2.
Необходимо найти оптимальную стратегию по критерию Байеса,
если известны вероятности состояний природы: p1  0,2 ; p2  0,3 ;
p3  0,5 .
Решение. Вычислим средние выигрыши, то есть показатели
эффективности каждой из стратегий:
7. Критерий Гермейера
По этому критерию считается, что так как природа может оказаться в одном из состояний с вероятностью p j , j  1, n , то игрок A,
применив стратегию Ai, получит свой выигрыш cij только с этой
вероятностью, то есть рассматривают элементы Гермейера cij p j .
Матрица Гермейера имеет вид
66
67
 c11 p1 c12 p2


 

C  ci1 p1 ci 2 p2


 
c p c p
 m1 1 m 2 2
 c1n pn 


 
 cin pn  .


 
 cmn pn 
При выборе стратегий игрок A предполагает, что природа будет
находиться в самом неблагоприятном для него состоянии, при котором элемент Гермейера будет минимальным при выбранной
стратегии. Таким образом, максимальным показателем эффективности служит число
M  max M i ,
1 i  m
где
M i  min cij p j , i  1, m.
1 j  n
Для матрицы выигрышей (11.3)
матрицу Гермейера:
 0,2  70 0,3  20

C   0,2  35 0,3  85
 0,2  80 0,3  10

или
6
14

C   7 25,5
16
3

из примера 11.2 составим
0,5  30 

0,5  20  ,
0,5  35 
15 

10  .
16,5 
Тогда показатели эффективности стратегий имеют следующий вид:
M 1  min14; 6; 15  6;
M 2  min7; 25,5; 10  7;
M 3  min16; 3; 16,5  3.
68
Отсюда вычисляем максимальный показатель эффективности
M  max6; 7; 3  7 .
Следовательно, оптимальной будет стратегия A2.
Подводя итог всему вышесказанному в этом параграфе, следует отметить, что при недостаточной информированности о состояниях природы рекомендуется проведение экспериментов для уточнения вероятностей различных состояний природы. Стоимость экспериментов также должна учитываться при будущих расчетах.
Проверь себя. Дана матрица выигрышей
 1 3 4


C  5
0 1 .
 2  4 6


1. Найти оптимальные стратегии игрока A, руководствуясь
следующими критериями принятия решений в условиях неопределенности:
а) Вальда;
б) максимакса;
в) Гурвица (при   0,6 );
г) Сэвиджа.
2. Найти оптимальные стратегии игрока A, применяя критерии
принятия решений в условиях риска:
а) Байеса, если известны вероятности состояний природы
p1  0,4 ; p2  0,1; p3  0,5 ;
б) Лапласа;
в) Гермейера при тех же значениях вероятностей, что и в пункте 2а).
Ответы: 1а) A3 ; 1б) A2 ; 1в) A2 ; 1г) A2 ;
2а) A3 ; 2б) A1 и A2 ; 2в) A2 .
69
Вопросы для повторения
Рекомендуемая литература
1. Предмет и цель теории игр.
2. История возникновения теории игр.
3. Основные понятия теории игр: игра, стратегия, оптимальная
стратегия.
4. Классификация игр.
5. Матричная игра, чистая стратегия, платежная матрица.
6. Примеры матричных игр.
7. Нижняя и верхняя цены игры, максиминная и минимаксная стратегии.
8. Принцип минимакса.
9. Седловой элемент, цена игры.
10. Решение матричной игры в чистых стратегиях.
11. Многократно повторяемые игры, смешанные стратегии.
12. Оптимальные смешанные стратегии, средний выигрыш.
13. Теорема Неймана о решении матричной игры.
14. Доминирующие стратегии.
15. Теорема о доминирующих стратегиях.
16. Упрощение платежной матрицы.
17. Теорема об активных стратегиях в матричной игре.
18. Решение матричной игры аналитическими способами.
19. Решение матричной игры графическим способом.
20. Связь матричных игр с задачами линейного программирования.
21. Определение биматричной игры.
22. Точки равновесия по Нэшу.
23. Теорема Нэша для биматричных игр.
24. Примеры биматричных игр.
25. Решение биматричной игры.
26. Вычисление среднего выигрыша в биматричных играх.
27. Игры с «природой».
28. Матрица рисков.
29. Критерии принятия решений в условиях неопределённости:
а) Вальда; б) максимакса; в) Гурвица; г) Сэвиджа.
30. Критерии принятия решений в условиях риска:
а) Байеса; б) Лапласа; в) Гермейера.
1. Нейман Дж. фон. К теории стратегических игр / Дж. фон Нейман //
Матричные игры. – М. : Физматгиз, 1961.
2. Neumann J. von. The Theory of Games and Economic Behavior / J. von
Neumann, O. Morgenstern. – Princeton : Princeton University Press, 1947.
3. Baird D. Game «Theory and the Law» / D. Baird, R. Gertner, R. Picke. –
Harvard, 1994.
4. Вентцель Е. С. Исследование операций / Е. С. Вентцель. – М. : Советское радио, 1972.
5. Самаров К. Л. Математика : учеб. пособие по разделу «Элементы
теории игр» / К. Л. Самаров. – М. : Учеб. центр «Резольвента», 2009.
6. Садовин Н. С. Основы теории игр: учеб. пособие / Н. С. Садовин,
Т. Н. Садовина. – Йошкар-Ола : Мар. гос. ун-т, 2011.
7. Колобашкина Л. В. Основы теории игр: учеб. пособие / Л. В. Колобашкина. – М. : БИНОМ. Лаборатория знаний, 2012.
8. Красс М. С. Математика для экономического бакалавриата : учебник /
М. С. Красс, Б. П. Чупрынов. – М. : Инфра-М., 2012.
9. Печерский С. Л. Теория игр для экономистов. Вводный курс : учеб.
пособие / С. Л. Печерский, А. А. Беляева. – СПб. : Изд-во Европ. ун-та, 2001.
70
71
Оглавление
Введение…………………………………………………………………………...3
§ 1. Понятие матричной игры. …………………………...………………………6
§ 2. Нижняя и верхняя цены игры………………………………………………10
§ 3. Игры с седловой точкой…………………………………………………….13
§ 4. Игры без седловой точки…………………………………………………...15
§ 5. Многократно повторяемые игры. Смешанные стратегии………………..17
§ 6. Решение матричной игры 22 в смешанных стратегиях…………………22
§ 7. Матричные игры 2n………………………………………………………..30
§ 8. Доминирующие и доминируемые стратегии……………………………...36
§ 9. Применение методов линейного программирования при решении
матричных игр mn ……………………………………………………………..40
§ 10. Биматричные игры………………………………………………………...47
§ 11. Игры с природой…………………………………………………………...61
Вопросы для повторения………………………………………………………..70
Рекомендуемая литература……………………………………………………...71
Учебное издание
Прокофьева Светлана Ивановна,
Пак Элла Ефимовна
ОСНОВЫ ТЕОРИИ ИГР
Учебное пособие
Редактор А. В. Афанасьева
Корректор К. И. Бойкова
Компьютерная верстка И. А. Яблоковой
Подписано к печати 15.08.2017. Формат 6084 1/16. Бумага офсетная.
Усл. печ. л. 4,2. Тираж 100 экз. Заказ 64. «С» 45.
Санкт-Петербургский государственный архитектурно-строительный университет.
190005, Санкт-Петербург, 2-я Красноармейская ул., д. 4.
Отпечатано на ризографе. 190005, Санкт-Петербург, ул. Егорова, д. 5/8, лит. А.
72
Документ
Категория
Без категории
Просмотров
2
Размер файла
567 Кб
Теги
igr2017, osnovy, teoria, prokofeva
1/--страниц
Пожаловаться на содержимое документа