close

Вход

Забыли?

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

?

Prokofeva Osnovy teorii igr2014

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