Теория игр. Часть 2. Кооперативные игры и игры в позиционной форме: Учебное пособие

Федеральное агентство по образованию Санкт-Петербургский государственный архитектурно-строительный университет

К. В. ГРИГОРЬЕВА

ТЕОРИЯ ИГР ЧАСТЬ 2. КООПЕРАТИВНЫЕ ИГРЫ И ИГРЫ В ПОЗИЦИОННОЙ ФОРМЕ Учебное пособие

Санкт-Петербург 2009 1

УДК 51 Рецензенты: канд. физ.-мат. наук Е. М. Парилина (каф. математической теории игр и статистических решений факультета прикладной математики – процессов управления Санкт-Петербургского государственного университета); канд. физ.-мат. наук, доц. К. Г. Куликов (каф. высшей математики, Санкт-Петербургский государственный технический университет)

Григорьева, К. В. Теория игр. Часть 2. Кооперативные игры и игры в позиционной форме: учеб. пособие / К. В. Григорьева; СПб. гос. архит.-строит. ун-т. – СПб., 2009. – 134 с. ISBN 978-5-9227-0161-7 Рассматриваются многошаговые игры в позиционной форме (МИПФ) с полной и неполной информацией (ПИ и НИ), представлены основные принципы кооперативной теории. Определяются понятия информационного множества в МИПФ, абсолютного равновесия по Нэшу и равновесия в стратегиях наказания в антагонистических МИПФ с ПИ, понятие равновесия в стратегиях поведения в случае одновременных антагонистических МИПФ с НИ. В качестве методов решения кооперативных игр предлагаются C-ядро, НМ-решение, вектор Шепли, индекс Банзафа, PMS-вектор. В частности, определяется PMS-вектор в ситуации равновесия по Нэшу в смешанных стратегиях в коалиционной игре. Все представленные темы снабжены примерами и типовыми расчетами. Пособие предназначено для студентов и аспирантов специальности «Прикладная математика», может быть полезным также для всех, кто интересуется теорией игр. Табл. 12. Ил. 46. Библиогр.: 11 назв. Рекомендовано Редакционно-издательским советом СПбГАСУ в качестве учебного пособия

ISBN 978-5-9227-0161-7

© К. В. Григорьева, 2009 © Санкт-Петербургский государственный архитектурно-строительный университет, 2009

2

ОГЛАВЛЕНИЕ Занятие № 1. МНОГОШАГОВЫЕ ИГРЫ С ПОЛНОЙ ИНФОРМАЦИЕЙ ....5 1.1. Введение .............................................................................................................5 1.2. Игры n лиц с полной информацией (ПИ) на древовидных конечных графах .....................................................................................................................10 1.3. Самостоятельная работа № 1 .........................................................................15 Занятие № 2. АБСОЛЮТНОЕ РАВНОВЕСИЕ ПО НЭШУ ............................16 2.1. Абсолютное равновесие по Нэшу ..................................................................16 2.2. Самостоятельная работа № 2 ........................................................................23 Занятие № 3. АНТАГОНИЧЕСКИЕ ИГРЫ (АИ) С ПИ. СТРАТЕГИИ НАКАЗАНИЯ .............................................................................................................24 3.1. Антагонические игры с ПИ ............................................................................24 3.2. Стратегии наказания .......................................................................................27 3.3. Самостоятельная работа № 3 .........................................................................42 Занятие № 4. КООПЕРАТИВНЫЕ ИГРЫ ...........................................................43 4.1 Введение .............................................................................................................43 4.2. Доминирование дележей ................................................................................47 4.3. С-ядро ...............................................................................................................49 4.4. Самостоятельная работа № 4 .........................................................................53 Занятие № 5. ДРУГИЕ ПРИНЦИПЫ ОПТИМАЛЬНОСТИ. НМ-РЕШЕНИЕ И ВЕКТОР ШЕПЛИ ..................................................................54 5.1. Игра в (0–1)-редуцированной форме .............................................................54 5.2. НМ-решение .....................................................................................................57 5.3. Самостоятельная работа № 5 ........................................................................60 5.4. Вектор Шепли. Свойства ...............................................................................60 5.5. Самостоятельная работа № 6 .........................................................................63 5.6. PMS-вектор ......................................................................................................63 Занятие № 6. МНОГОШАГОВЫЕ ИГРЫ С НЕПОЛНОЙ ИНФОРМАЦИЕЙ ......................................................................................................67 6.1. Постановка задачи ..........................................................................................67 6.2. Возможные позиции и существенные информационные множества ........71 6.3. Решение игр на оптимальность ......................................................................76 6.4. Самостоятельная работа № 7 ........................................................................85 Занятие № 7. ИГРЫ С ПОЛНОЙ И НЕПОЛНОЙ ПАМЯТЬЮ. СТРАТЕГИИ ПОВЕДЕНИЯ ...................................................................................86 7.1. Игры с полной и неполной памятью .............................................................86 7.2. Стратегии поведения .......................................................................................87 7.3. Самостоятельная работа № 8 .........................................................................92 7.4. Одновременные многошаговые игры ...........................................................93 3

ПРИЛОЖЕНИЕ 1 ....................................................................................................97 ПРИЛОЖЕНИЕ 2 ...................................................................................................117 Самостоятельная работа № 1...............................................................................117 Самостоятельная работа № 2 ...............................................................................117 Самостоятельная работа № 4 ..............................................................................128 Самостоятельная работа № 7 ..............................................................................129 Рекомендуемая литература ......................................................................................133

Занятие № 1.

МНОГОШАГОВЫЕ ИГРЫ С ПОЛНОЙ ИНФОРМАЦИЕЙ

1.1. ВВЕДЕНИЕ В большинстве игровых задач поиск оптимального поведения участников конфликта путем однократного выбора чистых стратегий как элементов пространств больших размерностей или функциональных пространств не является эффективным. В частности, это касается конфликтов, протекающих в течение некоторого времени, а не мгновенно. Так, в «шахматах» существует решение в классе чистых стратегий, однако этот результат невозможно получить, исследуя матричную игру (МИ). По этой причине математические модели конфликтов динамического характера исследуются в теории позиционных игр [1]. Игры в развернутой форме (позиционные игры) сводятся к обычным МИ. Они представляют собой выбор альтернатив или ходов на конечных древовидных графах. Для их определения потребуются элементарные сведения из теории графов [2]. Пусть X – некоторое конечное множество (рис. 1.1). f(x)

Fx2

X

0

A : Fx

x

x

Рис. 1.1

Определение 1.1. Правило f, ставящее в соответствие каждому элементу x  X элемент f  x  X , называется однозначным отображеением X в X. Определение 1.2. Многозначное отображение F множества X в X – это правило, которое каждому элементу x  X ставит в соответствие некоторое подмножество Fx  X (не исключается возможность Fx ‡ ). 4

5

Замечание 1.1. В дальнейшем под термином «отображение» будем понимать «многозначное отображение». Пусть F – отображение X в X, а A  X (рис. 1.2).

 Определение 1.5. Отображение F множества X в X называется транзитивным замыканием отображения F, если  Fx ^x`  Fx  Fx2  ...  Fxk  ... Определение 1.6. Отображение F 1, обратное отображению F, определяется как прообраз Fy :

Fx5

Fx4

Fx1

‡

^ y : Fy Š x`,

т. е. это множество всех точек y, образ которых содержит точку x. Анало-

Fx3

 k

гично определению отображения Fxk определяется отображение F 1 x : FA2

FA1

Fx2

FA1 ‰ FA2

FA

z

A1 A2

Fx

A1 ‰ A2

A

x Fx1 x0

F

F 1 2x

F 1 F 1

 x ,







2 k k 1 F 1 §¨ F 1 x ·¸ , ..., F 1 x F 1 §¨ F 1 x ·¸ . ¹ © ¹ © n  1 Утверждение 1.2. Имеет место равенство Fx Fx n . Определение 1.7. Граф Г – это пара  X , F , где X – конечное множество точек; F – точечно-множественное отображение, определенноее на X , которое некоторой точке x  X ставит в соответствие подмножеество Fx  X . Пример 1.1 (рис. 1.3). Здесь Fx1 , Fx3 , Fx6 ‡; Fx2 ^x 2 , x1 , x3 `; Fx4 ^x 2 , x6 `; Fx5 ^x 4 `. 1 3 x



Рис. 1.2

Определение 1.3. Под образом множества А будем понимать множество

FA

 Fx .

По определению полагаем F ‡ ‡ . Утверждение 1.1. Для Ai  X , i 1, n , справедливо о § n · n § n · n F ¨¨  Ai ¸¸  FAi , F ¨¨  Ai ¸¸   FAi . ©i 1 ¹ i 1 ©i 1 ¹ i 1 Определение 1.4. Если задано отображение Fx , то Fx2 – это образ образа Fx , т. е. F Fx , Fx3



F Fx2 , ..., Fxn 6

x4

x1

x A

Fx2

x2

x5

x3





F Fxn 1 .

x6

x7

Рис. 1.3

Определение 1.8. Каждый элемент множества X называется вершиной или узлом графа, а пара элементов  x, y , где y  Fx , – дугой графа. Замечание 1.2. Дуги являются ориентированными объектами, т. е. имеют направление, начало и конец. Определение 1.9. Две дуги называются смежными, если они различны и имеют общую точку. 7

Замечание 1.3. Множество дуг в графе будем обозначать Р. Задание множества дуг в графе Г  X , F определяет отображение F и наоборот, поэтому граф Г можно также записывать в виде Г  X , Р . Определение 1.10. Ребром графа Г  X , Р называется множество о из двух элементов x, y  X , для которых или  x, y  P , или  y, x  P . Замечание 1.4. В отличие от дуги для ребра ориентация роли не играет. Множество ребер будем обозначать Р. Определение 1.11. Путем в графе Г  X , F называется последовательность дуг, или ребер p  p1 , p2 , ..., pk , ... , или вершин x1 , x 2 ,..., x k , xi  Fxi 1 такая, что конец каждой предыдущей дуги совпадает с началом следующей. Определение 1.12. Длина пути p  p1 , p2 , ..., pk есть число l  p k дуг последовательности; в случае бесконечного пути р полагаем l  p f . Определение 1.13. Под цепью будем понимать последовательность ребер  p1 , p2 , ..., pk , ... , в которой у каждого ребра p k одна из граничных вершин является также граничной для p k 1, а другая – граничной для p k 1. Определение 1.14. Цикл – это конечная цепь, начинающаяся в некоторой вершине и оканчивающаяся в той же вершине (см. рис. 1.1), т. е. для последовательности x1 , x2 , ..., xk выполняются условия  i xi  Fxi 1 и Fxk x1. Определение 1.15. Граф называется связным, если любые две его вершины можно соединить цепью, т. е. это граф, множество узлов Х которого нельзя разбить на два множества Y ‰ Z : y  Y Ÿ F y  Y , z  Z Ÿ Fz  Z . Определение 1.16. Дерево, или древовидный граф – это конечный связный граф без циклов, имеющий не менее двух вершин, т. е. для любого пути x1 , x , ..., xk в графе выполняется xi  Fxi 1 для всех х i 2, k и Fxk ‡ . При построении многошаговой игры будем использовать в качестве модели древовидные графы, поэтому приведем здесь некоторые из их свойств. Утверждение 1.3. Во всяком древовидном графе существует единX. ственная вершина x : Fˆx 0

0

Определение 1.17. Вершина x0  X называется корнем дерева а или начальной вершиной графа Г, если она: 1) не имеет прообраза; 2) x  X

Определение 1.18. Длина дерева – это длина наибольшего пути в древовидном графе. Определение 1.19. Прообраз Fx1 вершины x  X – это множеество таких вершин y, что x принадлежит образу этих вершин, т. е. Fx1 y : x  Fy . Пример 1.2. Так, из рис. 1.3 следует, что Fx61 ^x 4 , x7 `. Утверждение 1.4. Для любой вершины x древовидного графа Г n x существует n x : F 1 x0 , где x0 не зависит отт x, т. е. для любого x существует обратное отображение, которое за n раз приведет в x0 . Замечание 1.5. Для любого x  X прообраз Fx1 либо содержит единственный элемент, либо является ‡. Это условие исключает наличие циклов. Замечание 1.6. В древовидном графе каждая вершина имеет единственный прообраз, кроме x0 , которая не имеет прообраза. Замечание 1.7. В случае, если граф является конечным, обязательно существует вершина x: Fx ‡ (см. рис. 1.1). На рис. 1.2 изображен древовидный граф с началом x0 . Точками x  X отмечены вершины графа. Дуги графа изображены отрезками со стрелкой, определяющей начало и конец дуги. Пример 1.3. С помощью древовидного графа можно изобразить игру в шашки или шахматы, если под вершиной графа понимать расположение фигур на доске в данный момент, указание хода и все последовательные расположения фигур на предыдущих ходах. Тогда существует единственная цепь, ведущая из начальной вершины в любую заданную, поэтому соответствующий граф игры не содержит циклов и является деревом. Пусть z  X . Определение 1.20. Подграфом Г z древовидного графа Г  X , F называется граф вида  X , F , где X z Fˆz , a Fz x Fx ˆ X z .

^

`



z

z

На рис. 1.2 линией обведен подграф, берущий начало из вершины z. В древовидном графе для всех x  X z множество Fx и множество о Fz x совпадают, т. е. отображение Fz является сужением отображения F на множество X z , поэтому для подграфов древовидного графа будем использовать обозначение Г z  X z , F .

 k

у k-й степени точки x.  k : x0  Fx1 , т. е. x0 принадлежит прообразу 8

9

1.2. ИГРЫ n ЛИЦ С ПОЛНОЙ ИНФОРМАЦИЕЙ (ПИ) НА ДРЕВОВИДНЫХ КОНЕЧНЫХ ГРАФАХ Пусть задан древовидный граф Г  X , F . На этом графе задано разбиение множества вершин X на подмножества X 1 , ..., X i , ..., X n , X n 1 : n 1

 Xi

i 1

X , где X k  X l

‡, k z l , т. е. никакие из подмножеств попар-

но не пересекаются и Fx ‡ для x  X n 1 . Определение 1.21. Множество X i , i 1, n , называется множееством очередности игрока i. Определение 1.22. Множество X n1 : Fx ‡, x  X n 1 , называется множеством окончательных позиций. На множестве окончательных позиций X n1 задана последовательность п вещественных функций H1  x , ..., H i  x , ..., H n  x , x  X n 1 . Определение 1.23. Функция H i  x , i 1 n , называется выигрышем i-ro игрока в позиции или в вершине x. Введем понятие альтернативы. Пусть существует вершина x и y i  Fx , i 1, k (рис. 1.4). Утверждение 1.5. Исходящие из x дуги можно перенумеровать по часовой стрелке единственным образом. Определение 1.24. Номера дуг, исходящих из вершины x, называются альтернативами в этой вершине.

Тогда в вершине x0 игрок i1 выбирает вершину x1  Fx0 . Если x1  X i2 , то в вершине x1 «ходит» игрок i 2 и выбирает следующую верершину x 2  Fx1 , и т. д. Таким образом, если на k-м шаге реализована вершина (позиция) x k 1  X ik , то в ней «ходит» игрок i k и выбирает следующую позицию из множества Fxk 1 . Выбор игроков осуществляется последовательно, и вся информация известна, так как предполагаем, что игрок i при совершении выбора в позиции x  X i знает эту позицию х, а также из-за древовидности графа Г может восстановить и все предыдущие позиции. Примерами игр с ПИ являются шахматы и шашки, так как в них игроки могут записывать ходы, а потому можно считать, что они знают предысторию игры при совершении каждого очередного хода. Игра прекращается, как только достигается окончательная вершина xl  X n 1 , т. е. такая, для которой Fxl ‡ . В позиции xl каждый игрок i, i 1, n , получает выигрыш H i  xl . Замечание 1.8. Так как граф древовидный, то путь x0 , , xk ,, xl , однозначно реализуемый, обязательно приводит к окончательной позиции. Определение 1.25. Путь Z, исходящий из начальной позиции x0 и достигающий одной из окончательных позиций игры xl , называется партией. Определение 1.26. Под длиной игры G будем понимать длину наи-

Пусть задано множество N ^1, 2,  , n` игроков. Игра начинаетчися из начальной позиции x0 каким-либо игроком i1 : x0  X i1 . Будем считать, что игра не окончательна, иначе не имеет смысла.

max l  p в графе Г  X , F . pP Введем понятие стратегии, используя понятие альтернативы. Стратегия здесь – это правило, которое предписывает игроку в любой позиции x из множества его очередности Xi однозначный выбор следующей позиции. Определение 1.27. Стратегия i-гo игрока – это функция  ui x , x  X i , 1 d i d n , которая каждой вершине x множества очередностей игрока i ставит в соответствие номер некоторой альтернативы, возможной в этой вершине x. Множество всевозможных стратегий игрока i будем обозначать через U i . Определение 1.28. Если каждый из игроков выбрал свои стратегии, то упорядоченный набор u  x ^u1  x , ..., ui  x , ..., un  x `, где ui  U i , называется ситуацией в игре. n Определение 1.29. Декартово произведение U – U i называется i 1 множеством ситуаций.

10

11

y2

y3

y1 x

Рис. 1.4

большего пути lmax

Замечание 1.9. Каждая ситуация u u1,, ui ,, un однозначно определяет путь в древовидном графе, а следовательно, партию в игре и выигрыши игроков. Пример 1.4. Пусть N ^1, 2`. Тогда u ^u1  x , u2  x ` , где де еx  x0 ,  , xl , xl  X n 1 . Перенумеруем позиции, входящие в множества очередностей первого игрока двойным индексом 1. i , i 1,5 , и второго – 2. j , j 1,2 . Тогда X 1 ^1.1 ,, 1. 5 `, X 2 ^2.1 , 2.2 `. Перенумеруем дуги, выходящие из каждой вершины, одним индексом. Тогда u1 1. i ^1, 2`, i 1,5 , и u 2 2. j ^1, 2`, j 1,2 – стратегии, которые указывают в каждой позиции множества очередностей номер дуги, по которой следует двигаться дальше. Очевидно, что стратегии на множестве очередностей X 1 образуютт пятимерный вектор: u1  x ^u1 1. i `, i 1,5 , а u2  x ^u2 2. j `, j 1,2 . Следовательно, количество стратегий первого игрока card U1 25 32 , второго – card U 2 22 4 . Множество U состоит из 32 u 4 128 ситуаций u. Пусть u1  x 2, 2,1,1,1 , u 2  x 2,1 . Стратегия u1  x 2, 2,1,1,1 предписывает игроку 1 выбор дуги 2 в вершинах 1.1 и 1. 2 и дуги 1 – в вершинах 1. 3 , 1. 4 , 1.5 соответственно. Для игрока 2 стратегия u 2  x 2,1 предписывает выбор дуги 2 в вершине 2.1 , дуги 1 – в вершине 2. 2 . Пусть x0 1.1 . Тогда согласно стратегии u1  x первый игрок делает выбор u1  x 0 2 , т. е. выбирает вершину 2. 2 (рис. 1.5). Второй игрок в этой вершине выбирает u2  x1 1. Соответственно следующий шаг принадлежит первому игроку u2  x2 1. Построим путь: x0 1.1 , x1 2. 2 , x 2 1. 4 , xl  X n1 . Следовательно, ^2, 2,1,1,1 , 2,1 ` o 2,1 , т. е. H1  xl 2 , H 2  xl 1. Пример 1.5. Имеем двух игроков N ^1, 2`, u ^u1  x , u2  x ` , x  x0 ,  , xl , X 1 ^1.1 , , 1.8 `, X 2 ^2.1 , , 2.7 `. Стратегии в каждой позиции множества очередностей: u1 1.1 ^1, 2, 3`, u2 2.1 ^1, 2, 3`, u1 1. 2

^1, 2`, u1 1. 3 ^1, 2`, u1 1. 4 ^1, 2, 3`, u1 1. 5 ^1, 2`, u1 1. 6 ^1, 2, 3`, u1 1. 7 ^1, 2`, u1 1.8 ^1, 2`,

12

u 2 2 . 2

^1, 2, 3`, u2 2. 3 ^1, 2`, u 2 2. 4 ^1, 2`, u 2 2. 5 ^1, 2`, u2 2. 6 ^1, 2`, u 2 2. 7 ^1, 2, 3, 4`.

§5 · ¨¨ ¸¸ © 3¹ 1

§5· ¨¨ 4 ¸¸ © ¹ 2

1

(1.2)

2

1

1

§ 0· ¨¨ ¸¸ © 5¹ 2

(1.5)

2

1

(2.1) 2

1

§1· ¨¨ ¸¸ ©0¹

2

(1.4)

(1.3) 1

§  1· ¨¨ 1 ¸¸ © ¹

§2· ¨¨ ¸¸ ©1¹

§ 1· ¨¨ ¸¸ © 1¹

§1· ¨¨ ¸¸ ©10 ¹

2 (2.2)

(1.1) Рис. 1.5

Следовательно, u1  x ^u1 1. i `, i 1,8 , u2  x ^u2 2. j `, j 1,7 , количество стратегий игрока 1 card U1 25 ˜ 33 864 , игрока 2 card U 2 2 4 ˜ 32 ˜ 41 576 . Множество U состоит из 864 u 576 497 664 ситуаций u.      Пусть u1  x 2, 2,1,1,1, 3,1, 2 , u 2  x 2, 3,1, 1,1, 2, 4 , где x – страратегия, которая реализуется в пути. На рис. 1.6 альтернативы этих стратегий выделены пунктиром. Тогда путь будет следующим: уx0 1.1 , x1 1. 2 , x 2 2. 4 , x3  1.8 , x4 1. 7 , xl  X n 1, откуда ситуация ^2, 2,1,1,1, 3,1, 2 , 2, 3,1, 1,1, 3, 4 ` приведет к выигрышу H1  xl 4 , H 2  xl 5 . Определение 1.30. Пусть ситуации u u1,  , ui ,  , u n соответствует партия x0 ,  , xk ,  , xl . Введем понятие функции выигрыша K i игрока i, значение которой в каждой ситуации u равно значению выигрыша H i в окончательной позиции соответствующей партии x0 ,  , xk ,  , xl , т. е. K i u1 , ..., u i , ..., u n H i  xl , i 1, n. Функции K i , i 1, n , определены на множестве ситуаций

U

n

–U i . i 1

Определение 1.31. Игрой в нормальной форме G называется G

N , ^U i `iN , ^ K i `iN , 13

где N ^1, ..., i, ..., n` – множество игроков; U i – множество стратегий игрока i; K i – функция выигрыша игрока i, i 1, n . § 5· § 6· § 4 · ¨¨ ¸¸ ¨¨ ¸¸ ¨¨ ¸¸ © 1 ¹ © 2 ¹ ©3 ¹

§1· ¨¨ ¸¸ ©4¹

§2· ¨¨ ¸¸ ©4¹

§ 8 · ¨¨ ¸¸ ©  5¹

§1· ¨¨ ¸¸ © 2¹

§ 5· ¨¨ ¸¸ ©1¹

§ 4· ¨¨ ¸¸ ©1 ¹

§  1· § 1· ¨¨ ¸¸ ¨¨ ¸¸ © 4 ¹ © 8¹

§ 2· ¨¨ ¸¸ § 5 · © 3¹ ¨¨ ¸¸ ©10 ¹

§0· ¨¨ ¸¸ ©5¹

§1· ¨¨ ¸¸ ©8¹

§ 2· ¨¨ ¸¸ © 8 ¹

§4· ¨¨ ¸¸ ©5¹

1.3. САМОСТОЯТЕЛЬНАЯ РАБОТА № 1 Изобразить на графе, представленном на рис. 1.5, путь x и найти выигрыши игроков (прил. 2).

§2· ¨¨ ¸¸ ©3¹

§0 · ¨¨ ¸¸ ©6 ¹

Замечание 1.10. В подыгре Gz не обязательно помнить предыдущие ходы, которые были сделаны до позиции z, так как подыгра Gz является независимой игрой из вершины z.

§3· ¨¨ ¸¸ ©5¹ §1· ¨¨ ¸¸ © 2 ¹§ 1 · ¨¨ ¸¸ ©  1¹ § 5· ¨¨ ¸¸ © 6 ¹

x0 Рис. 1.6

Пусть z  X . Рассмотрим подграф Г z  X z , F , с которым свяжем ем подыгру G z . В подыгре G z определяются множества очередности игроков Yi z X i  X z , i 1, n , множество окончательных позиций Ynz1 X n 1  X z , выигрыш i-го игрока H iz  x H i  x , x  Ynz1, i 1, n , z z X i  X z , i 1, n . стратегия i-го игрока u i  x u i  x , x  Yi Множество всех стратегий i-гo игрока в подыгре G z обозначается через U iz . В результате с каждым подграфом Г z связываем подыгру у в нормальной форме Gz N , U iz , K iz ,

^ `^ `

где функции выигрыша дении U z

K iz ,

еi 1, n , определены на декартовом произве-

n

– U iz . i 1

14

15

 x0 ,, xl

Занятие № 2.

АБСОЛЮТНОЕ РАВНОВЕСИЕ ПО НЭШУ

Докажем, что ситуация равновесия существует для игры G длины l.

2.1. АБСОЛЮТНОЕ РАВНОВЕСИЕ ПО НЭШУ Определение 2.1. Ситуация u  x u1  x ,..., ui  x ,..., u n  x называется равновесной по Нэшу (NE – Nash Equilibrium), если

x

K i u  x t K i u  x ui  x ,  i  N ,  ui  x  U i ,

Рис. 2.1

где u  x ui  x u1  x ,..., ui  x ,..., u n  x . Определение 2.2. В игре с нулевой суммой ситуация NE называется ситуацией равновесия. Замечание 2.1. В дальнейшем в тексте будет использоваться обозначение NE в качестве равновесной ситуации во всех рассматриваемых играх. Для многошаговых игр можно усилить понятие равновесия. Определение 2.3. Ситуация равновесия называется абсолютно равновесной, если ее усечение в любой подыгре G x является ситуацией равновесия в этой подыгре. Определение 2.4. Ситуация равновесия по Нэшу u * u1* , ..., u n* называется ситуацией абсолютного NE в игре G, если для любого z  X







z u1* , ...,



z un*



z ui*

из условия максимизации своего выигрыша H i  y max H i  y . Игроки y F x

получают H 1  y , , H i  y , , H n  y соответственно. Если i -й игрок отт-

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

u * z

k

 z , ..., un* z

ª u* «¬ 1

k

k

º »¼ .



§¨ ·¸ , где – сужение стратегии ui* на по© ¹ дыгру G z , является ситуацией NE в подыгре G z . Не все ситуации равновесия обладают этим свойством. Однако имеет место основная теорема. Теорема 2.1. В любой многошаговой игре с ПИ на конечном древовидном графе существует ситуация абсолютного NE. Доказательство. Докажем по индукции по длине игры l. Пусть l 1 (рис. 2.1). Предположим, что x  X i – множеству очередностей i-го игрока. Игрок i выбирает альтернативу в вершине x ситуация u

* z

Так как подыгры G z k , k 1, s , z k  Fx0 (рис. 2.2), имеют длину не более l  1, то по индукционному предположению теорема справедлива, следовательно, существует ситуация абсолютного NE


G z1

Gz 2

x0  X i0

G zs


Рис. 2.2





zk z z* ª * z* º * max K i k ª u * º . Пусть ui*1  x0 z * , где z : K i1 « u » « »¼ 1 ¬ z k Fx0 ¬ ¼ * И пусть в точке z ходит игрок i : i z i1 . Тогда игра G переходит в подыгру G z* . Но в подыгре G z * каждый i-й игрок получает выигрыш

 z* . Посколькуу ui* z* – сужение

K iz * , соответствующий ситуации NE u *

стратегии ui* на множество X i ˆ X z , то выигрыш i-го игрока в ситуации

 z* :

u * игры G равен выигрышу в ситуации u * 17



Ki u*







z* z* K iz * ª u * º t K iz * ª u * || ui º »¼ «¬ »¼ «¬ ui  U i , i 1, n, i z i1 .





K i u * || ui ,

(2.1)

i1 . Пусть ui1  U i1 – произвольда ная стратегия игрока i1 в игре G. Обозначим z0 ui1  x0 . Тогда

Аналогично доказывается, если i



K i1 u *

 z* º»¼

 z

K iz1* ª u * «¬



max K iz k ª u * 1 « z k Fx 0 ¬







k

ºt »¼

Далее решаем игры G1.3 , G1.4 , G2.3 , G1.5 , G2.4 . В подыгре G1.3 два NE, так как игроку 1 безразлично, какую альтернативу выбрать. Но при выборе игроком 1 левой альтернативы он выигрывает 1, а при выборе правой выигрывает 10. Если игрок 1 «благожелателен» и выбирает в позиции (1.3) правую альтернативу, то

v1 1.3 5 , v2 1.3 10 ,

v1 1.4 v1 2.5 6 , v2 1.4 v2 2.5 2 , v1 1.5 v1 2.6 2, v2 1.5 v2 2.6 4 ,



z0 z0 t K iz 0 ª u * º t K iz 0 ª u * || ui1 º K i1 u * || ui1 . (2.2) »¼ »¼ 1 « 1 « ¬ ¬ Утверждение теоремы следует теперь из (2.1), (2.2). Пример 2.1. Найдем ситуации абсолютного NE в игре G, представленной на рис. 2.3. Множество N состоит из двух игроков: N ^1, 2`. В вершинах, обозначенных «кружочками», ходит первый игрок, а в «квадратиках» – второй игрок. Обозначим соответственно через v1 x , v2  x их выигрыши в подыгре Gx в некоторой фиксированной ситуации абсолютного равновесия. Сначала решаем подыгры G1,6 , G1,7 , G2,7 :

v1 1.6 6, v2 1.6 2, v1 1.7 2, v2 1.7 4,

v1 2.3 0 , v2 2.3 6 , v1 2.4 3 , v2 2.4 5 .

Игрок 2 знает, что если он выберет левую дугу, то игрок 1 тоже выберет левую дугу, так как ему не выгодно получить +1 или –2 против 2. Далее решаем игры G2.1, G1.2 , G2.2 :

v1 2.1 v1 1.3 5 , v2 2.1 v2 1.3 10 , v1 1.2 v1 2.4 3 , v2 1.2 v2 2.4 5 ,

v1 2.2 5 , v2 2.2 6 . Теперь решаем игру G G1.1. Здесь v1 1.1 v1 2.1 5 , v2 1.1 v2 2.1 10 . В результате получаем ситуацию абсолютного NE u1* ,u 2* , где

v1 2.7 1, v2 2.7 8 . Далее решаем подыгры G2,5 , G2,6 , G1,8 . В подыгре G2,5 два NE, поскольку игроку 2 безразлично, какую альтернативу выбрать. Однако при выборе игроком 2 левой дуги игрок 1 выигрывает +1, а при выборе игроком 2 второй дуги +6. Если игрок 2 «благожелателен» и выбирает в позиции (2.5) правую дугу, то v1 2.5 v1 1.6 6 , v2 2.5 v2 1.6 2 ,

v1 2.6 v1 1.7 2 , v2 2.6 v2 1.7 4 , v1 1.8 2 , v2 1.8 3 .

Игроку 1 выгодно не дать ход игроку 2, так как в противном случае игрок 2 выберет стратегии, которые ему принесут K 2 2.7 8 , но игрок 1 тогда получит либо K1 2.7 1, либо K1 2.7 2 . 18

= 1, 2, 2, 2, 2, 3, 2,1 ,





(2.3) 1, 3, 2, 2, 2,1, 2 . В ситуации u1* ,u 2* игра развивается по пути x0 1.1 , x1 2.1 , 1.3 , xl  X n 1 и приводит к выигрышу 5, 10 . На рис. 2.3 стратеu1*

u 2*

x2 гии и путь обозначены пунктиром. В процессе построения было замечено, что стратегии ui* , i 1, 2 , «доброжелательны» в том смысле, что игрок i при совершении своего хода, будучи в равной степени заинтересован в выборе последующих альтернатив, выбирает ту из них, которая более благоприятна для другого игрока. В игре G существуют ситуации абсолютного равновесия, в которых выигрыши игроков будут другими. Для построения таких равновесий достаточно снять условие «доброжелательности» игроков и заменить его обратным условием «недоброжелательности».

19

§ 4· ¨¨ ¸¸ © 3¹

§5· ¨¨ ¸¸ ©1¹

§1· ¨¨ ¸¸ © 2¹

§5· ¨¨ ¸¸ 10 §5· © ¹ ¨¨ ¸¸ ©1¹

§ 2· ¨¨ 3 ¸¸ © ¹

§6· ¨¨ ¸¸ © 2¹

§1· ¨¨ 4 ¸¸ © ¹

§  1· § 1 · ¨¨ ¸¸ ¨¨ ¸¸ © 4 ¹ ©8¹

§ 2· ¨¨ 4 ¸¸ © ¹

§ 4· ¨¨ ¸¸ ©1¹ § 8 · ¨¨ ¸¸ ©  5¹ §0· ¨¨ ¸¸ ©5¹

§1· ¨¨ ¸¸ ©8¹

§  2· ¨¨ ¸¸ © 8 ¹

v1 1.3 v1 1.3 5 , v2 1.3 1,

§ 4· ¨¨ ¸¸ ©5¹

v1 1.4 2 , v2 1.4 3 ,

v1 1.5 v1 2.6 v1 1.5 2 , v2 1.5 v2 2.6 v1 2.6 4 , v1 2.3 v1 2.3 0 , v2 2.3 v2 2.3 6 ,

§ 2· ¨¨ ¸¸ © 3¹ § 0· ¨¨ ¸¸ © 6¹

v1 2.4 v1 2.4 3 , v2 2.4 v2 2.4 5 . § 3· ¨¨ ¸¸ ©5¹

Далее решаем игры G2.1 , G1.2 , G2.2 . Имеем

v1 2.1 v1 1.5 2 , v2 2.1 v2 1.5 4 ,

§1· ¨¨ ¸¸ © 2¹ §1· ¨¨ ¸¸ © 1¹ §  5· ¨¨ ¸¸ © 6 ¹

Рис. 2.3

Обозначим через v1  x , v 2  x выигрыши игроков в подыгре Gx при использовании игроками «недоброжелательного» равновесия. Тогда имеем v1 1.6 v1 1.6 6 , v2 1.6 v2 1.6 2 ,

v1 1.7 v1 1.7 2 , v2 1.7 v2 1.7 4 , v1 2.7 2 , v2 2.7 v2 2.7 8 .

Как уже отмечалось, в подыгре G2.5 два NE. В отличие от предыдущего случая предположим, что игрок 2 «недоброжелателен» и выбирает ту из вершин, в которой при его максимальном выигрыше выигрыш игрока 1 минимален. Тогда v1 2.5 1, v2 2.5 2 ,

v1 2.6 v1 1.7 2 , v2 2.6 v2 1.7 4 ,

v1 1.8 v1 1.8 2 , v2 1.8 v2 1.8 3 .

Далее ищем решение игр G1.3 , G1.4 , G1.5 , G2.3 , G2.4 . В подыгре G1.3 два NE. Как и в предыдущем случае, выберем «недоброжелательные» действия игрока 1. Тогда имеем

v1 1.2 v1 2.4 3 , v2 1.2 v2 2.4 5 ,

v1 2.2 v1 2.2 5 , v2 2.2 v2 2.2 6 , v1 1.1 v1 1.2 3 , v2 1.1 v2 1.2 5 .

Таким образом, получена новая ситуация NE u1* = 2, 2,1,1, 2, 3, 2,1 , u 2*

(2.4)

На рис. 2.3 стратегии и путь обозначены жирной линией с пунктиром. Выигрыши обоих игроков 3, 5 в ситуации (2.4) меньше, чем в ситуации (2.3). Однако ситуация (2.4) так же, как и ситуация (2.3), является ситуацией абсолютного равновесия. Кроме «доброжелательных» и «недоброжелательных» ситуаций абсолютного NE существует целое семейство промежуточных ситуаций абсолютного равновесия. Рассмотрим вопрос о том, когда можно утверждать отсутствие двух различных ситуаций абсолютного равновесия, отличающихся выигрышами игроков. Теорема 2.2. Пусть выигрыши игроков H i  x , i 1, n , в игре G таковы, что если существует такой игрок i0 и такие конечные позиции x, y, что H i0  x H i0  y , то о H i  x H i  y для всех i  N . Тогда в игре G выигрыши игроков во всех ситуациях абсолютного равновесия совпадают (рис. 2.4). Доказательство. Докажем по методу индукции по длине игры l. Пусть l 1 и в единственной позиции x ходит игрок i1 : H i1  x max H i1  xc . x cF x

20

3, 3, 2, 2,1,1, 3 .

21

^H i  y ` ^H i  x ` y

x

i0 Рис. 2.4

Если точка x единственная, то и вектор выигрышей единствен: о H  x ^H1  x , ..., H n  x ` . Если существует такая точка x z x , что H i1  x H i1  x , то имеется еще одна ситуация равновесия с выигрышами H  x ^H1  x , ..., H n  x `. Однако из условия теоремы следует, чтоо если H i1  x H i1  x , то H i  x H i  x для всехх i  N . Пусть v x ^vi (x)` – вектор выигрышей в ситуациях равновесия в одношаговой подыгре G x , который, как уже показано, определяется единственным образом. Покажем, что если для некоторого i0 выполнено равенство vi0  xc vi0  xcc , ( xc, xcc : l Gxc l Gxcc 1 , рис. 2.5), то vi  xc vi  xcc . vi(x')

Предположим теперь, что во всех подыграх G x с длиной l d k  1 (см. рис. 2.2) вектор выигрышей в ситуациях равновесия определяется единственным образом и если для каких-нибудь двух подыгр G xc , G xcc с длиной, не превосходящей k  1, vi0  xc vi0  xcc для некоторогоо i0 , то vi  xc vi  xcc для всех i  N . Пусть игра G x0 имеет длину k и в начальной позиции x0 ходит игрок i1 . По предположению индукции для всех z  Fx0 в игре Gz выигрыши в ситуациях NE определяются единственным образом. Пусть вектор выигрышей в ситуациях NE в игре G z равен ^vi (z )`. Тогда игрок i1 в вершине x0 выбирает следующую вершину z  Fx0 из условия

vi1  z

max vi1  z

zFx0

.

(2.5)

Если точка z , определяемая (2.5), единственна, то вектор vi  x0 vi  z , i 1, n , является единственным вектором выигрышей в ситуациях NE в игре G x0 . Если же существуют две вершины z, z , у для которых vi1  z vi1  z , то по предположению индукции, поскольку длины подыгр G z и G z не превосходят k  1, из равенстваа vi1  z vi1  z

ом следует равенство vi  z vi  z для всех i  N . Таким образом, и в этом

случае выигрыши vi  x0 , i  N , в ситуациях равновесия определяются ся единственным образом.

x'

2.2. САМОСТОЯТЕЛЬНАЯ РАБОТА № 2 vi(x")

x"

Рис. 2.5

да Действительно, пусть xc  X i1 , xcc  X i2 , тогда vi1  xc H i1  x c max H i1  y ,

Найти все ситуации абсолютного NE в игре G, заданной на древовидном графе и представленной на рисунках. В позициях, обозначенных «кружочками», ходит первый игрок, «квадратиками» – второй игрок (прил. 2).

yFxc

vi2  xcc H i2  x c

max H i2  y

yFxcc

и vi  xc H i  x c , vi  xcc H i  x cc для всех х i  N . Но тогда, если vi0  xc vi0  xcc , то H i0  x c H i0  x cc . Следовательно, по условию теоремы H i  x c H i  x cc для всех i  N . Отсюда vi  xc vi  xcc для всех ех i  N . 22

23

Занятие № 3.

АНТАГОНИЧЕСКИЕ ИГРЫ (АИ) С ПИ. СТРАТЕГИИ НАКАЗАНИЯ

3.1. АНТАГОНИЧЕСКИЕ ИГРЫ С ПИ Определение 3.1. Многошаговой АИ с ПИ называется многошаговая игра двух лиц с ПИ на древовидном графе Г  X , F G

^1, 2`,U1 ,U 2 , H 1 , H 2

N







v y









 y  y ¸·¹

24

  y ·¸¹ ,

y  K 2y ¨§ u1* , u 2* ©

  z ·¸¹

z max K1z §¨ u1* , u 2* zFy ©

v y

max vz . zFy

(3.1)

§ 2 · ¨¨ ¸¸ ©  2¹

v z1





K1y ¨§ u1* , u 2* ©

Пусть y  X 1 и z  Fy . Тогда (рис. 3.1) имеем

,

где H 2  x  H 1  x для всех x  X 3 ; X 3 – множество окончательных позиций. Замечание 3.1. Из условия H 2  x  H 1  x следует, чтоо лаK 2 u1, u2  K1 u1, u2 для всех u1  U1, u2  U 2 . Этим свойством обладают и все подыгры G z игры G. Определение 3.2. Пара u1* , u 2* , для которой выполняются неравенства K1 u1 , u2* d K1 u1* , u 2* d K1 u1* , u 2 для всех u1  U1, u2  U 2 , называется ситуацией NE или седловой точкой, а стратегии, образующие ситуацию равновесия, оптимальными. Определение 3.3. Значение функции выигрыша v в ситуации равновесия называется значением игры G. Из теоремы 2.1 следует, что в многошаговой АИ с ПИ на конечном древовидном графе существует ситуация абсолютного равновесия, т. е. такая ситуация u1* , u 2* , сужение которой на любую подыгру G z игры G образует в G z ситуацию равновесия. Определение 3.4. Число v y , представляющее собой значение функции выигрыша в ситуации равновесия подыгры G y , называется значением подыгры G y . Утверждение 3.1. Для любой подыгры G z можно определить ее значение v z . Определение 3.5. Значением АИ v y называется значение функции выигрыша игрока 1 в ситуации равновесия. Утверждение 3.2. Значение АИ v y определяется единственным образом для всех y  X 1 , y  X 2 и является однозначной функцией. Доказательство. Выведем функциональные уравнения для вычисления функции v y . Из определения v y следует, чтоо



  y ·¸¹ – ситуация равновесия в подыгре G y , являющаяся сужением ситуации абсолютного равновесия u1* , u 2* . § * y * где ¨ u1 , u 2 ©

vy

2

3 v z2

3

§1· ¨¨ ¸¸ ©  1¹ §1· ¨¨ ¸¸ ©  1¹ § 3 · ¨¨ ¸¸ ©  3¹

Рис. 3.1

Для y  X 2 (рис. 3.2) аналогично получаем v y

  y ·¸¹

  z ·¸¹

y  K 2y §¨ u1* , u 2* ©

 max v z zFy

min v z .

z  max K 2z §¨ u1* , u 2* zFy ©

(3.2)

zFy

Действительно, если y  X 1 , то игрок 1 (максимизирующий) должен выбрать в точке вершину z  Fy , для которой значение следующей подыгры максимально. Если же y  X 2 , то игрок 2 (минимизирующий) должен выбрать позицию z  Fy , для которой значение следующей подыгры минимально. Из (3.1), (3.2) и определения 3.5 (рис. 3.3) окончательно имеем

v y max v z , y  X 1 , zF y

(3.3)

v y

min v z , y  X 2 .

(3.4)

zF y

25

vy

§ 2 · ¨¨ ¸¸ ©  2¹

1

vz1

скольку соответствующие подыгры имеют длину не более чем k  1. Эти же формулы указывают способ построения оптимальных стратегий игроков. В случае, когда выборы игроков в многошаговой АИ чередуются (поочередная игра), уравнения (3.3), (3.4) могут быть записаны в виде одного уравнения. Действительно, рассмотрим подыгру Gx и пусть, для определенности, x  X 1 . Тогда в следующей позиции ходит игрок 2 или эта позиция является окончательной, т. е. Fx  X 2  X 3 , поэтому можно записать

§1· ¨¨ ¸¸ ©  1¹ §1· ¨¨ ¸¸ ©  1¹

1 1

vz 2

§ 3 · ¨¨ ¸¸ ©  3¹

v x max v y , x  X 1 , yFx

v y Рис. 3.2

min v z , y  Fx  X 2  X 3 . zFy

(3.6) (3.7)

Подставляя (3.7) в (3.6), получаем § 2 · ¨¨ ¸¸ ©  2¹

v z1 2

v x

§1· ¨¨ ¸¸ © 1¹ §1· ¨¨ ¸¸ © 1¹

vy 2 v z2 1

ª º max « min v z », x  X 1 . yFx ¬ zFy ¼

(3.8)

Если x  X 2 , то аналогично имеем ª º min «max v z » . (3.9) yFx ¬ zFy ¼ Уравнения (3.8), (3.9) эквивалентны и должны рассматриваться с v x

§ 3 · ¨¨ ¸¸ ©  3¹

начальным условием v z z X 3

H1  z .

Рис. 3.3

3.2. СТРАТЕГИИ НАКАЗАНИЯ Уравнения (3.3), (3.4) решаются при граничном условии

v z zX 3

H 1  z .

(3.5)

Система уравнений (3.3), (3.4) с граничным условием (3.5) позволяет осуществить обратную рекуррентную процедуру нахождения значения игры и оптимальных стратегий игроков. Действительно, пусть значения всех подыгр Gz длиной l  z d k  1 известны и равны v z . Пусть G y – некоторая подыгра длины l  y d k . Тогда если y  X 1 , то v y определяется по формуле (3.3), если же y  X 2 , то по (3.4). При этом значения функции v z в формулах (3.3), (3.4) известны, по26

При исследовании многошаговых неантагонистических игр с ПИ можно выявить множество ситуаций равновесия, сужения которых не всегда являются ситуациями равновесия во всех подыграх исходной игры. К числу таких ситуаций равновесия относятся равновесия в стратегиях наказания. Пример 3.1. Рассмотрим игру с ПИ на ситуации равновесия (рис. 3.4). Здесь u1 2,  , 2 – ситуация абсолютного равновесия, которая приводит к выигрышу K j u1 2 для любого игрока j 1, n . 27

Если хотя бы один из игроков, например игрок i, отклоняется в процессе игры (возможно, случайно, если играет очень большое количество игроков), то ситуация u2 2, , 2, 1i , 2, 2 уже не является си-





туацией NE, так как K j u2 1 i  K j u2 || u2j

1 1 j  j 1, i  1, i z 1

и K j u 2 1  K j u1 2  j 1, n , i 1.

как при отклонении любого игрока j дого игрока j 1, n увеличится: K j u 3



2

1 1

2

3

2

1

2

n

2

(1/3, 1/3, …, 1/3)

(2, 2, …, 2)

1

(1, 1, …, 1)

Рис. 3.4

Рассмотрим ситуацию, когда игрок 1 отклоняется от ситуации u2 . Тогда получаем ситуацию u 3 1, 2, , 2, 1i , 2, 2 , i z 1. Проверим этуу ситуацию на равновесность.

K j u3 1  j 1, n ;

 K12, 2,, 2, 1i , 2,  2 1 i  K1u3 1; K j u3 || u3j , j 2, i  1 K j 1, 2, , 2,1 j , 2,, 2, 1i , 2,  2 K1 u3 || u13

 u

Kj

j 3 || u 3 ,

j

i



K j 2,  , 2, 1 j , 2,  , 2, 1i , 2,  , 2

i

K j  2 3 ,  , 2, 2 i , 2,  , 2

K j u 3 || j

i  1, n







1 j ! K j u 3 1 i



2 ! K j u 3 1 i  j

K j 2 3 ,  , 2, 1i , 2,  , 2, 1 j , 2,  , 2



1, n ;

1 i t K j u 3 1 i

1, n .

Следовательно, ситуация u3 – не NE, а потому ситуация u3 не является абсолютным NE. Пусть G x0 – игра N игроков, а Gx – подыгра игры G x0 : G x  G x0 . Предположим существование обмена информации между игроками. Как строится стратегия наказания? Игроки договариваются о действиях (рис. 3.5): идем вдоль какого-либо пути Z  x0 z0 , z1, ..., zl , и если какой-либо игрок j отклонился на k-м шаге игры, а где отклонился, известно, так как игра с ПИ, то все играют против j -го игрока, начиная с k  1 -го шага (рис. 3.6). Для того чтобы построить игру против j -го игрока, с каждой игрой Gx0 свяжем N вспомогательных АИ таких, что графы игр G1x0 , , Gxn0 , Gx0 и множества их стратегий в них совпадают:

G1x0 Š G1y

K j 1, 2, , 2 1 d K j u 3 1;

i  1, n

1 d K j u 3 1

 j



1, n ;

1, n ;

K j u 3 || j  j

(1/n, …, 1/n)

K j u3 || u3j , j



1, i  1



1

1 d K j u3 1;

K j  2 3 ,  , 2, 1i , 2,  , 2 1 i  j

K j u 3 || j  j

1, i от ситуации u 3 выигрыш каж-

 .

K j 1, 2, , 2, 1i , 2, , 2,1 j , 2, 2

Gxn0 Š G yn j

Произвольная АИ G x0 строится как игра двух игроков j и ^N \ j`. Множество очередностей игрока j : X j , а игрокаа ^N \ j` :

1, n .

Следовательно, ситуация u3 – NE. Проверим ее на абсолютную равновесность. Рассмотрим подыгру G3 . Сужение u3 стратегии u3 на подыгру G3 имеет вид u3  23 , , 2, 1i , 2, , 2 . Следовательно, K j u3 1 i  j 1, n , т. е. ситуация u3 не равновесна в подыгре G3 , так ак 28

X N \^ j`

j

 X i . Найдем ситуации NE в Gx0 . Выигрыш игрокаа

iN \ ^ j`

j : K xj0 ,

игрока ^N \ j`:  K xj0 . Значение v x0 АИ и значения v yj ее подыгр показывают, какой минимальный проигрыш может себе гарантировать игрок ^N \ j` в каждой позиции пути Z независимо от поведения игрока j j

29

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

Обозначим:







* * и * * – ситуации абсолютного равновесия в АИ 9 u11 , u 21 u12 , u 22

а, G1 и G2 соответственно, где первый индекс указывает номер игрока, а второй – номер АИ; 9 G1 y , G2 y – подыгры игр G1, G2 ;

 

y

z3 z1  X j

z2

z0 Рис. 3.5

 

yª * y yª * y * yº * yº 9 v1  y K1 « u11 , u21 » , v2  y K 2 « u12 , u22 » – значения ¼ ¼ ¬ ¬

 

 

ª * y * yº ª * y * yº подыгр G1 y , G2 y , где ситуации « u11 , u 21 » и « u12 , u22 » являются тся ¼ ¬ ¼ ¬ равновесными в подыграх G1 y , G2 y соответственно. Пусть Z  x0 z0 , z1 , ... , zl – путь, реализуемый по договоруу в ситуации u~1, u~2 .

Дадим строгое определение стратегии наказания в случае неантагонистической игры двух лиц G

zk+1

U1, U 2 , K1, K 2 .

С игрой G свяжем две вспомогательные АИ G1 и G2 . Игра G1 – это АИ, построенная на основе игры G, в которой игрок 2 играет против игрока 1, т. е. K 2  K1 (см. рис. 3.8). Это означает, что игрок 1, отклоняясь от договора, выбирает пути, приносящие ему максимальный доход v1 , а игрок 2, защищаясь, минимизирует свои убытки и выбирает пути в АИ G1, которые гарантируютт ему минимальный проигрыш v1 , что бы ни делал игрок 1. В то же время, минимизируя свои убытки, игрок 2 минимизирует выигрыш до v1 и игроку 1. Таким образом, игрок 2 играет против игрока 1. Игра G2 – это АИ, построенная на основе игры G, в которой игрок 1 играет против игрока 2, т. е. K1  K 2 (см. рис. 3.9). Рассуждения здесь аналогичные. Игрок 2 выбирает пути, приносящие ему максимальный доход v2 , а игрок 1, защищаясь, минимизирует свои убытки и выбирает пути в АИ G2 , которые, гарантируют ему минимальный проигрыш v2 , что бы ни делал игрок 2. В то же время, минимизируя свои убытки, игрок 1 минимизирует выигрыш до v2 и игроку 2. Таким образом, игрок 1 играет против игрока 2.

* u~1  y u12  y для y  X1, y  Z , т. е. в вершинах zk  Z ˆ X1 стратегия предусматривает выбор игрока 1 согласно стратегии по договору, а во всех остальных вершинах игрок 1 действует согласно стратегии (3.10), которая соответствует ситуации равновесия NE в подыгре G2 и гарантирует ему минимальный проигрыш, а игроку 2 – минимальный выигрыш в случае, если игрок 2 отклонится от стратегии (3.10).

30

31

y X1  zk

Рис. 3.6

Определение 3.6. Стратегия u~1 $ называется стратегией игрокаа 1 наказания игрока 2, если (3.10) u~1  z k zk 1 для zk  Z ˆ X 1 ,

Определение 3.7. Стратегия u~2 $ называется стратегией 1 наказания игрока 2, если (3.11) 1) u~2  z k z k 1 для zk  Z ˆ X 2 , * u~2  y u 21  y для y  X 2 , y  Z . Рассуждения относительно этого определения аналогичны рассуждениям относительно определения 3.6, если заменить игрока 1 на игрока 2, а игру G2 заменить на игру G1. Замечание 3.2. Если в вершине zk  Z игрок 1 отклоняется, но далее в пути, по которому он решил идти, не существует вершины y : y  Z , y  X1, Fy  X n 1, то игрок 1 гарантированно проиграет, так как все остальные игроки начинают играть против него, чтобы наказать за то, что он отклонился. Доказать! Теорема 3.1. Пусть u~1 $ , u~2 $ – ситуация в стратегиях наказания. Для равновесности ситуации u~1 $ , u~2 $ достаточно, чтобы для всех х k 0, l  1 выполнялись неравенстваа K1 u~1 $ , u~2 $ t v1  z k , (3.12) K 2 u~1 $ , u~2 $ t v 2  z k , где z , z , ..., z – путь, реализовавшийся в ситуации u~ $ , u~ $ .

0

1

l

1

2

Доказательство. Пусть один из игроков, например игрок 1, использует стратегию u1 $ , отличную от стратегии наказания u~1 $ , для  zk  Z ˆ X 1. Из определения наказывающей стратегии u~2 $ следует,, что игрок 2 проиграет не больше значения подыгры v1  z k , а игрок 1 в АИ G1 выиграет не больше, чем значение подыгры v1  z k : (3.13) K u $ , u~ $ d v  z  z  Z ˆ X . 1

1

2

1

k

k

1

Аналогично, если игрок 2 использует стратегию u 2 $ , отличную аот стратегии наказания u~2 $ для  zk  Z ˆ X 2 , то из определения наказывающей стратегии u~1 $ следует, что игрок 1 проиграет не больше значения подыгры v2  z k , а игрок 2 в АИ G2 выиграет не больше, чем значение подыгры v2  z k : (3.14) K 2 u~1 $ , u2 $ d v2  zk  zk  Z ˆ X 2 . 1

Эта формулировка подразумевает «стратегию игрока 2 наказания игрока 1».

32

Теперь предположим, что неравенства (3.12) имеют место. Докажем, что u~1 $ , u~2 $ – NE. По определению NE K1 u~1 $ , u~2 $ t K1 u1 $ , u~2 $ , K 2 u~1 $ , u~2 $ t K 2 u~1 $ , u2 $ , но K u~ $ , u~ $ t v  z , а v  z t K u $ , u~ $  z  Z ˆ X 1

1

2

1

k

K 2 u~1 $ , u~2 $ t v2  z k , а

1

k

1

1

2

k

1

и v2  z k t K 2 u~1 $ , u2 $  zk  Z ˆ X 2 . Следовательно, определение NE выполняется и ситуация u~1 $ , , u~2 $ – NE. Теорема 3.2. В игре G всегда существует ситуация равновесия в стратегиях наказания, при этом выигрыши в этой ситуации равны * * * * $ и u 22 $ – оптимальные стратегии игK i u11 $ , u22 $ , i 1, 2 , где u11





роков 1 и 2 в АИ G1 и G2 соответственно. * * $ и u 22 $ – оптимальные стратегии Доказательство. Пусть u11 игроков 1 и 2 в АИ G1 и G2 соответственно и Z ^z0 , z1, ..., zl ` – путь, * * $ , u22 $ . Пусть стратегии наказания соответствующий ситуации u11 ~ ~ ~ * ~ ~ ~  u z о zk  Z ˆ X 1 u1 $ и u 2 $ таковы, что 1 k u11  z k для ~ ~ ~ * ~ и u 2  z k u 22  z k для zk  Z ˆ X 2 . Докажем, что ситуация u~1 $ , u~2 $ образует ситуацию NE в стратегиях наказания. Из оптимальности стра* * $ и u 22 ентегий u11 $ в играх G1 и G2 соответственно следуют неравенства ~ ~ * * K1 u~1 $ , u~2 $ K1 u11 $ , u 22 $ t v1 z k , (3.15) ~ ~ * * K 2 u~1 $ , u~2 $ K 2 u11 $ , u 22 $ t v 2  z k , k 0, l  1, что согласно теореме 3.1 является достаточным условием NE. Пример 3.2. Рассмотрим игру G (рис. 3.7) : N ^1, 2`, ситуация * u1 1, 1, 2, 2, 2 , u 2* 1, 1 абсолютно равновесна в игре G,







 





 











H1 u1* , u2* 8 , H 2 u1* , u 2* 2 . Рассмотрим ситуацию u1 2, 1, 2, 1, 2 , u 2 2, 2 . В этой ситуации выигрыши игроков равны соответственно 10 и 1, т. е. игрок 1 получает больше, чем в ситуации u1* , u 2* , поэтому ситуация u1, u2 является равновесной в игре G. Но она не является абсолютно равновесной, так как сужение ситуации u1 , u2 в подыграх G2.2 и G1.4 не является NE. Действительно, в подыгре G1.4 сужение стратегии u1 диктует игроку 1 выбор левой дуги, не оптимальной для него в позиции 1.4.



33



Этот выбор является «наказанием» игроку 2, если он отклонится от желательного для игрока 1 выбора дуги 2 в позиции 2.2. Однако наказывающий игрок 1 при этом и сам потеряет в выигрыше 5 единиц. §8· ¨¨ 2 ¸¸ © ¹

§1· ¨¨ 3 ¸¸ © ¹

1

2

§ 3· ¨¨ 2 ¸¸ © ¹

§ 5· ¨¨ 1 ¸¸ © ¹

§ 0· ¨¨ 0 ¸¸ © ¹

1

§ 5· ¨¨ 8 ¸¸ © ¹

1

1.2

2

1.3

1

§8· ¨¨ 5 ¸¸ © ¹

§10 · ¨¨ 1 ¸¸ © ¹

1

2

1.4

2

1

1.5 2

2.1

Найдем значения подыгр:



 

* 1.1 º * 1.1 , u 21 5. K11.1 ª u11 »¼ «¬ В АИ G2 (рис. 3.9) – игре против игрока 2, т. е. игрок 2 отклонился, * * 1, 2 . одно NE, где u12 2, 1, 2, 1, 2 , u22

v1 1.1

§  3· ¨¨ ¸¸ © 3 ¹

§  2· ¨¨ ¸¸ © 2 ¹

§  1· ¨¨ ¸¸ ©1¹

§  2· ¨¨ ¸¸ © 2 ¹

1.1

1

2

2

1

2

1.2 Рис. 3.7

1

Для того чтобы построить стратегии наказания, нам потребуется АИ G1 (рис. 3.8) – игра против игрока 1, т. е. игрок 1 отклонился. Здесь два NE:

§ 8 · ¨¨ ¸¸ ©  8¹

§1· ¨¨ ¸¸ ©  1¹

1

2

§ 3 · ¨¨ ¸¸ ©  3¹

§ 5 · ¨¨ ¸¸ ©  5¹

1

1

§  5· ¨¨ ¸¸ © 5 ¹

§  1· ¨¨ ¸¸ ©1¹

§0· ¨¨ ¸¸ ©0¹

§ 5 · ¨¨ ¸¸ ©  5¹

1

1.3

2

§ 8 · ¨¨ ¸¸ ©  8¹

§ 10 · ¨¨ ¸¸ ©  10 ¹

1

2

1.4

2

1

2.1 1.1 Рис. 3.8 34

1

1.5

1.4

2

1

1

2

1.1

2

2.2 2

2

Значения подыгр G2 : v 2 2.1

2, v 2 2.2

 2.2 , u22* 2.2 º»¼

* K 22.2 ª u12 «¬

1.

1.5 2

2.2 1

2

Рис. 3.9

2

1.2

1

1.3

2.1

* 1, 1, 2, 2, 2 , u21 2, 1 ; * 2, 1, 2, 2, 2 , u21 2, 1 .

* 2) u11

§  8· ¨¨ ¸¸ © 8 ¹

§ 0· ¨¨ ¸¸ © 0¹

2.2 1

* 1) u11



* 1.5 º * 1.5 , u 21 10 , K11.5 ª u11 »¼ «¬ v1 1.4 5 , v1 1.3 5 , v1 1.2 8 ,

v1 1.5

Схема построения стратегий наказания

 



* * , u 22 . 1. Построить ситуацию u11 2. Выбрать путь Z, вдоль которого будем играть. * * , u 21 . Это же решение можно получить, 3. Построить ситуацию u12 если решать все подыгры основной игры, двигаясь из множества окончательных позиций к начальной вершине таким образом, чтобы минимизировать выигрыш оппонента и максимизировать свой выигрыш.

35

4. Найти стратегии наказания: игрока 1 u~1 – игрок 1 играет вдоль пути Z, наказывая одновременно игрока 2, если тот отклонился; игрока 2 u~2 – игрок 2 играет вдоль пути Z, наказывая одновременно игрока 1, если тот отклонился. 5. Проверить, является ли ситуация u~1, u~2 NE. * * , u 22 дают два оптимальных пути. В нашем примере стратегии u11 Рассмотрим один из них: Z ^x0 1.1 , 2.2 , 1.5 `. Решим подыгры в стратегиях наказания (рис. 3.10).



§8· ¨¨ 2 ¸¸ © ¹

§ 1· ¨¨ 3 ¸¸ © ¹

1

§ 3· ¨¨ 2 ¸¸ © ¹

§5· ¨¨ 1 ¸¸ © ¹

1

2

§0· ¨¨ 0 ¸¸ © ¹

§5· ¨¨ 8 ¸¸ © ¹

1

2

1.3

1

1

1.1

1

§8· ¨¨ 5 ¸¸ © ¹

1

2

§ 5 · ¨¨ ¸¸ ©  5¹

1.5

§  1· § 1 · ¨¨ ¸¸ ¨¨ ¸¸ © 1 ¹ ©  1¹

§ 0· ¨¨ ¸¸ © 0¹

2, 1, 2, 1, 2 ,

u~2

2, 2 .

Если игрок 1 отклонится в позиции 1. 1 , то u1 1.1 1 , следовательно, K1 u1, u~2 5 d v1 1.1 5 . Таким образом, ситуация, образуемая стратегиями u~ 2, 1, 2, 1, 2

§1· ¨¨  1¸¸ © ¹

§1· ¨¨ ¸¸ ©  1¹ §  5· ¨¨ ¸¸ © 5 ¹

v1 1.4 2 , v1 1.3 5 , v1 1.2 2 , v1 1.1 2 .





* * , u 22 дают два пути. Рассмотрим Здесь оптимальные стратегии u11

один из них: Z ^1.1 , 2.1 , 1.5 , 2.6 , 1.7 `. Решим подыгры в стратегиях наказания (рис. 3.13). Тогда u~1 1, 2, 1, 2, 2, 2, 2,1 , u~2 3, 3, 2,1,1,1, 3 . Проверим, является ли ситуация u~ , u~ NE. 1

2

Если отклонение происходит в позиции: 9 1. 7 , тоо u1 1.7 1, K1 u1, u~2 1 d v1 1.7 2 ; 9 2. 6 , тоо u 2.6 2 , K u~ , u 5 d v 2.6 4 ; 2

2

1

36

§ 3 · ¨¨ ¸¸ ©  3¹

§0· ¨¨ ¸¸ ©0¹

v1 1.8 2 , v1 1.7 2 , v1 1.6 6 , v1 1.5 2 ,

2

2, 2 , является NE.

§ 2 · ¨¨ ¸¸ ©  2¹

Рис. 3.11

Если игрок 2 отклонится в позиции 2. 2 , то u2 2.2 1 , следовательно, K u~ , u 0 d v 2.2 1.

u~2

§ 8 · ¨¨ ¸¸ ©  8¹

2

Если игрок 1 отклонится в позиции 1. 5 , то u1 1.5 1 , следовательно, K1 u1, u~2 8 d v1 1.5 10 . 2

§ 2 · ¨¨ ¸¸ ©  2¹

2.2

Тогда, по определениям 3.6 и 3.7, u~1 Проверим, является ли ситуация u~1, u~2 NE.

1

§ 2 · ¨¨ ¸¸ ©  2¹ § 5 · ¨¨  5 ¸¸ © ¹

§ 4 · § 1 · §  2· § 4 · ¨¨  4 ¸¸ ¨¨ 1¸¸ ¨¨ 2 ¸¸ ¨¨  4 ¸¸ © ¹ © ¹© ¹ © ¹

2

Рис. 3.10

2

§1· ¨¨ ¸¸ © 1¹

§1· ¨¨ ¸¸ © 2¹

§10 · ¨¨ 1 ¸¸ © ¹

1.4

2

2.1

§ 4 ·§ 5 ·§ 6 · ¨¨  4 ¸¸ ¨¨  5 ¸¸ ¨¨  6 ¸¸ © ¹© ¹© ¹



2

1.2

Пример 3.3. Решим игру G (см. рис. 2.3) в стратегиях наказания. Построим АИ G1 и G2 (рис. 3.11 и 3.12).

37

1

2

2

§  3 · §  1· §  2 · ¨¨ 3 ¸¸ ¨¨ 1 ¸¸ ¨¨ 2 ¸¸ © ¹© ¹ © ¹ § 4 · ¨¨ ¸¸ © 4¹

§5· ¨¨ ¸¸ © 5¹

§  1· ¨¨ ¸¸ ©1¹

§ 4 · §  8· ¨¨ 4 ¸¸ ¨¨ 8 ¸¸ © ¹© ¹

§  3· ¨¨ ¸¸ © 3 ¹

§  5· §  6 · ¨¨ ¸¸ ¨¨ ¸¸ © 5 ¹© 6 ¹

§  5· ¨¨ ¸¸ © 5 ¹ § 2· ¨¨ ¸¸ © 2 ¹§¨ 1 ·¸ ¨  1¸ © ¹ §  6· ¨¨ ¸¸ © 6 ¹

­ 2 , K1 u1, u~2 2 9 1. 1 , тоо u1 1.1 ® d v1 1.1 2 . ~ ¯3 , K1 u1, u2 5 Таким образом, ситуация u~1, u~2 NE. Рассмотрим теперь в тех же стратегиях наказания (рис. 3.14) другой путь: Z ^1.1 , 1.2 , 2.4 `. § 4· ¨¨ ¸¸ © 3¹

§5· ¨¨ ¸¸ ©1¹

§6· ¨¨ ¸¸ © 2¹

§4· ¨¨ ¸¸ ©1¹ §1· ¨¨ 4 ¸¸ © ¹

Рис. 3.12

v1 2.7 8 , v1 2.6

4 , v1 2.5

§5· ¨¨ ¸¸ ©1¹

§4· ¨¨ ¸¸ ©1¹

§6· ¨¨ ¸¸ © 2¹

§ 5· ¨¨ ¸¸ ©1¹

§ 4· ¨¨ ¸¸ © 5¹

§ 8 · ¨¨ ¸¸ ©  5¹ §  1· § 1 · ¨¨ ¸¸ ¨¨ ¸¸ © 4 ¹ ©8¹

§  2· ¨¨ ¸¸ © 8 ¹

§4· ¨¨ ¸¸ ©5¹

§  1· § 1 · ¨¨ 4 ¸¸ ¨¨ 8 ¸¸ © ¹© ¹

§ 0· ¨¨ ¸¸ © 5¹

§ 2· ¨¨ ¸¸ ©5¹

§ 0· ¨¨ ¸¸ © 6¹

§5· ¨¨10 ¸¸ © ¹

§ 0· ¨¨ ¸¸ © 5¹

§ 0· ¨¨ ¸¸ © 6¹

§2· ¨¨ ¸¸ ©5¹

x0 § 3· ¨¨ ¸¸ © 5¹ §1· ¨¨ ¸¸ © 2¹

x0

Рис. 3.14 §1· ¨¨ ¸¸ © 1¹ §  5· ¨¨ ¸¸ © 6 ¹

ся 2, 2,1, 2, 2, 2, 2,1 , u~2 2, 3, 2, 2,1,1, 3 . Проверим, является ли ситуация u~1, u~2 NE. Тогда u~1

Если отклонение происходит в позиции: 9 2. 4 , тоо u2 2.4 1, K 2 u~1, u2 3 d v2 2.4 5 ; 9 1. 2 , тоо u1 1.2 1, K1 u1, u~2 0 d v1 1.2 2 ;

Рис. 3.13 38

§3· ¨¨ 5 ¸¸ © ¹ §1· ¨¨ ¸¸ © 2 ¹ §¨ 1 ·¸ ¨ 1¸ © ¹ §  5· ¨¨ ¸¸ © 6 ¹

§ 5· ¨¨ 1 ¸¸ © ¹

§1· ¨¨ ¸¸ © 2¹

§5· ¨¨ ¸¸ ©10 ¹

§  2· ¨¨ ¸¸ © 8 ¹

§2· ¨¨ ¸¸ ©4¹

§1· ¨¨ ¸¸ ©4¹

§ 2· ¨¨ ¸¸ © 3¹

§1· ¨¨ ¸¸ ©8¹

§ 8 · ¨¨ ¸¸ ©  5¹ § 2· ¨¨ 3 ¸¸ © ¹

§1· ¨¨ ¸¸ ©8¹

§2· ¨¨ 4 ¸¸ © ¹

§1· ¨¨ ¸¸ © 2¹

2 , v1 2.4 5 ,

v1 2.3 6 , v1 2.2 6 , v1 2.1 4 ;

§ 4· ¨¨ ¸¸ © 3¹

K1 u1, u~2 1 d v1 1.5 2 ;

­ 1, K 2 u~1 , u2 1 d v2 2.1 4 ; 9 2. 1 , тоо u 2 2.1 ® ~ ¯2 , K 2 u1, u 2 2

§ 4 · ¨¨ ¸¸ © 4¹

§ 2· ¨¨ ¸¸ © 2 ¹ §  3· ¨¨ ¸¸ © 3 ¹ §  10 · ¸¸ ¨¨ © 10 ¹

9 1. 5 , тоо u1 1.5 1 ,

§  1· §  8 · §  8 · §  5 · ¨¨ 1 ¸¸ ¨¨ 8 ¸¸ ¨¨ 8 ¸¸ ¨¨ 5 ¸¸ © ¹© ¹ © ¹ © ¹

39

9

1.1 , тоо u1 1.1

­ 1, K1 u1, u~2 1 d v1 1.1 2 . ® ~ ¯3 , K1 u1, u2 5

Таким образом, ситуация u~1, u~2 NE. Теорема 3.3. Пусть x0 ,..., xk ,..., xl – некоторый путь в игре G x0 , игра

Gxi k  i 1, n ,  k 0, l – АИ, где игрок i играет против всех, х, v i  xk – ее значение. Пусть H i  xl – выигрыш i-го игрока в окончательной позиции xl . Тогда, если имеет место H i  xl t v i  xk , k 0, l  1, то существует ет ситуация NE, в которой реализуется путь x0 ,..., xk ,..., xl с выигрышем

H i  xl .

Доказательство. Построим NE. Обозначим путь Z  x0 ,..., xl . Мы должны построить стратегии во всех позициях игры G x0. Сначала построим стратегию пути Z . Игрок i движется вдоль пути Z , следоваательно, ui  y  Z , y  Z ˆ X i ,  i 1, n . Пусть теперь y  Z , y  X i (рис. 3.15). Тогда для любой точки y на дереве существует наиболее близкий прообраз этой точки, который принадлежит пути Z , т. е.  m :



m *y1  Z ,

где де m – min.

Следовательно, существует точка yˆ

*y1 m  X k ,

yˆ  Z , в yˆ

ходит k-й игрок. Следовательно, игрок k нарушил соглашение, и его стратегия u k  yˆ z u k  yˆ . Если i z k , то i -й игрок играет в игруу G ykˆ в составе группы игроков ^N \ k` и его стратегия u i  y . Если i k , то, как он играет, не имеет значения. Докажем, что u ˜ u1,.., un – ситуация NE, т. е. выигрыш K i u ˜ H i  xl  i . Рассмотрим ситуацию K i u ˜ || ui ˜ . Если i-й игрок отклонился в той позиции, куда он никогда не попадет, то его отклонение не играет никакой роли. Если он отклонился от пути Z и первая позиции, где имеет место отклонение, yˆ  Z : ui  yˆ z ui  yˆ , то рассмотрим подыгру у G1 yˆ , где происходит отклонение (если игрок отклонился, то он рассчитывает на больший выигрыш), но максимальная величина, которую i игрок может гарантировать себе в этой позиции, vi  yˆ . Следовательно, K i u ˜ || ui ˜ d vi  yˆ , но, если vi  yˆ d H i  xl , а H i  xl K i u ˜ (выигрыш в конце пути, реализуемого в стратегиях u ˜ ), то K i u ˜ || ui ˜ d K i u ˜ , ч. т. д. Если существует траектория Z: v i  xk d v i  xk 1 k 0, l  1, i  N , то в этой игре выполняются условия теоремы 3.3. Эти неравенства означают, что выигрыши не убывают, следовательно, v i  xk 1 d H i  xl . Если такой путь существует, то это NE. Теорема 3.4. В любой конечной игре с ПИ всегда существует путь, вдоль которого гарантированные выигрыши не убывают, т. е. v i  x k d v i  x k 1  i , а значит, существует ситуация NE. i

Доказательство. Рассмотрим игру G x0 и АИ G x0, где все игроки,

y Xi

кроме i, играют против i -го игрока. Обозначим через u~ x0 $ оптимальную стратегию i -го игрока в АИ

yˆ  X k

i

Рис. 3.15 40

G xi 0

. Строим ситуацию u~˜

{u~1x0 ˜ , u~2x0 ˜ ,, u~nx0 ˜ }, т. е. каждый играет

так, как если бы все играли против него. 41

Пусть Zi  x0 ~ x0 ,, ~ xl – траектория, которая реализуется в АИ i ~ Здесь v  x0 – гарантированный выигрыш i -го игрока в позиции ~ а, x0 . Сделаем один шаг в ситуации, когда все играют против i -го игрока, i i ~ ~ тогда выигрыш увеличится: v  x0 d v  x1 . Таким образом, v i ~ x d v i ~ x x Z .

G xi . 0

k

k 1

k

i

Замечание 3.3. Ситуаций NE очень много, все исходы, которые превосходят исход u~ ˜ , будут NE. Замечание 3.4. Смысл стратегий наказания заключается в том, что игрок заставляет противника придерживаться определенного пути в игре, используя постоянную угрозу переключения на стратегию, оптимальную в АИ против него. Стратегии наказания не следует считать очень «хорошими», поскольку, наказывая партнера, игрок может еще сильнее наказать себя самого. 3.3. САМОСТОЯТЕЛЬНАЯ РАБОТА № 3 Найти ситуации NE в стратегиях наказания в играх из самостоятельной работы № 2.

Занятие № 4.

КООПЕРАТИВНЫЕ ИГРЫ

4.1. ВВЕДЕНИЕ Пусть N ^1, ... , n` – множество всех игроков. Рассмотрим бескоалиционную игру с ненулевой суммой G N , ^X i `iN , ^H i `iN , в которой условия игры допускают совместные действия игроков и перераспределение выигрыша, а вклад различных игроков в игру может быть оценен единой шкалой (трансферабельные выигрыши). В кооперативной теории игр n лиц исследуются условия, при которых объединение игроков в максимальную коалицию (в коалицию, состоящую из всех игроков) с целью получения максимального суммарного выигрыша приведет к наилучшим результатам, а отдельные игроки не будут иметь желания создавать меньшие группировки или действовать индивидуально. При этом нас будет интересовать не столько, как коалиция игроков добивается своего суммарного выигрыша, сколько, как он будет распределен между членами коалиции (кооперативный подход), поэтому кооперативная теория является нормативной, а не стратегической теорией. Определение 4.1. Любое непустое подмножество S  N называется коалицией. Введем понятие характеристической функции игры. Предположим, что n игроков перед началом игры знают или догадываются о способе поведения, который максимизирует сумму их выигрышей: max

n

n

¦ H i  x1,, xn ¦ H i x1,, xn vN .

x1 ,, xn i 1

i 1

Определение 4.2. Характеристической функцией игры n лиц будем называть вещественную функцию v, определенную на коалициях S  N , при этом для любых непересекающихся коалиций S1 , S 2 S1 , S 2  N выполняется неравенствоо (4.1) vS1  vS 2 d vS1  S 2 , v‡ 0 . Свойство (4.1) называется свойством супераддитивности. Определение 4.3. Под кооперативной игрой будем понимать пару N, v , где v – характеристическая функция, удовлетворяющая неравенству (4.1). Характеристическая функция vS интерпретируется как гарантированный выигрыш коалиции S , определяемый леммой 4.1, при условии, что коалиция действует независимо от остальных игроков. 42

43

Совместные действия игроков коалиции S (обозначим ее игроком 1) означают, что множество стратегий коалиции S – это всевозможные комбинации стратегий игроков коалиции S , т. е. это элементы декартова произведения:

XS

– Xi . iS

Выигрыш коалиции S есть сумма выигрышей игроков из S: H S x ¦ H i  x ,

где x S  X S , x N \ S  X N \ S ; GS

рение АИ GS . Тогда для всех S1, S 2  N , для которых S1 ˆ S 2 ‡ , имеет место неравенство (4.1). Доказательство. Найдем vS1 ‰ S 2 . Теорема об условии существования NE в чистых стратегиях v v может быть сформулирована дословно для смешанной стратегии. В смешанных стратегиях ситуация равновесия всегда существует, а значение игры

v

iS

где x  X N , x  x1 , ..., xn – ситуация в игре G . Если (в худшем для коалиции S случае) оставшиеся игроки из N \ S объединились в коллективного игрока 2 с интересом, диаметрально противоположным коалиции S , и с множеством стратегий X N \ S

vS1 ‰ S 2 t vS1  vS 2 , S1 ˆ S 2

G

iN \ S

xN \ S

44

j

min max ¦¦ D ij [i K j

y6 II x6 I i

j

ª º max « min H i  x1 ,..., xn » ¦ xX S1 ‰ S 2 xX N \  S1 ‰ S 2 iS ‰ S ¬ ¼ 1 2

ª ª º º min ¦ t ¦ min t max « min H i  x1 , ..., xn  ¦ H i  x1 , ..., xn » » ¦ « xX S ‰ S « xX N\  S1 ‰ S 2 iS iS 2 1 2¬ ¬ 1 ¼ ¼» t

ª º max « min H i  x1 , ..., xn  min H i  x1 , ..., xn » t ... ¦ ¦ xX N\ S1 ‰ S 2 iS xX S1 ‰ S 2 xX N\  S1 ‰ S 2 iS ¬ ¼ 1 2

Поясним последнее неравенство. Игроки коалиции N\S1 ‰ S2 выбирают такие стратегии, при которых суммы выигрышей игроков

¦ коалиций S1 и S 2 соответственно, т. е. i S

1

H i x

и i¦ S

H i x

2

, минимальны,

 x1,..., xn . А так как минимум по множеству будет не больше min f  x t min f  x минимума по его подмножеству, т. е. где x

x X N\  S1‰S2

Лемма 4.1 (о супераддитивности). Для бескоалиционной игры N , ^X i `iN , ^H i `iN построим функцию xS

x6 I y6 II i

vS1 ‰ S 2

‡.

vS max min H S  x S , x N \ S , S  N ,

max min ¦¦ D ij [i K j

и именно максминная и минимаксная стратегии образуют ситуацию равновесия в смешанных стратегиях:

– Xi ,

то выигрыш игрока 2 в ситуации х равен – H S  x . Тогда наибольшим гарантированным выигрышем коалиции S является наибольший гарантированный выигрыш коалиции S в АИ GS  X S , X N \ S , H S . Таким образом, в игре GS коалиция S выбирает свою стратегию xS  X S . Если игра конечна, то для любого S существует NE в смешанных стратегиях. Утверждение 4.1. В смешанном расширении GS  X S , X N \ S , H S игры GS гарантированный выигрыш vS коалиции S может разве лишь увеличиться по сравнению с выигрышем в игре GS . Замечание 4.1. В дальнейшем будем рассматривать смешанное расширение игры GS . Покажем, что функция vS является характеристической функцией бескоалиционной игры. Для этого достаточно показать, что функция vS супераддитивна, т. е.

 X S , X N \ S , H S – смешанное расши-

и

min

x X N\  S1‰ S2

f  x t min

x X N\S 2

x X N\S1

f  x , то справедливо продолжение

неравенства:

(4.2) 45

ª º ... t max « min ¦ H i  x1 , ..., xn  min ¦ H i  x1 , ..., xn » t xX N\S 2 iS xX S ‰ S xX N\S1 iS 1 2¬ ¼ 1 2 t max min ¦ H i  x1 , ..., xn  max min ¦ H i  x1 , ..., xn x X S xX N\S1 iS 1 1

xX S xX N\S 2 iS 2 2

4.2. ДОМИНИРОВАНИЕ ДЕЛЕЖЕЙ Из супераддитивности v получаем, что для любых непересекающихся коалиций S1 ,..., S k  N k

¦ v  S i d v  N .

vS1  vS 2 ,

где xi – смешанная стратегия игрока i . Заметим, что для каждой бескоалиционной игры, построенной выше, v‡ 0 . Действительно, по определению, H ‡  x

¦ H i x ,

i‡

но последняя сумма не содержит слагаемых, откуда H ‡  x тождественно равно нулю, поэтому и v‡ 0 . Замечание 4.2. Если значение игры существует, то минимакс супер-

макс может не являться супераддитивным. Определение 4.4. Бескоалиционная игра G N , ^X i `iN , ^H i `iN называется игрой с постоянной суммой, если

¦ H i x

iN

c

const  x  X N

¦ H i x ¦ H i P

iN

– Xi .

iN

c для всех ситуаций P

iN

в смешанных стратегиях. С другой стороны,

vS sup inf

¦ H i P S , v N \ S

c  inf sup

¦ H i P S , v N \ S

P S vN \ S iS

v N \ S P iN \ S S

¦ D i v  N ;

(4.3)

i , i 1, N , 2) D i t v^`

(4.4)

1)

Лемма 4.2. Пусть G – бескоалиционная игра с постоянной суммой, функция vS , S  N , определена, как в лемме 4.1, а игры GS , S  N , имеют значения в смешанных стратегиях. Тогда v N vS  v N \ S , S  N . Доказательство. Из определения игры с постоянной суммой получаем, что v N

i 1

Отсюда, в частности, следует, что не существует такого разбиения множества N на коалиции, чтобы суммарный гарантированный выигрыш этих коалиций превышал максимальный выигрыш всех игроков v N . Возникает проблема «оптимального» дележа: как разделить v N ? Основная задача кооперативной теории игр п лиц заключается в построении реализуемых принципов оптимального распределения максимального суммарного выигрыша v N между игроками. Определение 4.5. Вектор D D1, , D n называется дележом мв кооперативной игре, если выполняются следующие условия:

§ · sup inf ¨¨ c  ¦ H i P S , v N \ S ¸¸ PS Q N \ S © ¹ iN \ S c  v N \ S ,

iN

где v^` i – значение характеристической функции для одноэлементной коалиции S ^i`. Условие (4.3), называемое условием коллективной рациональности (КР) или оптимальности по Парето, означает, что вектор D является допустимым и все участники этой игры получат в сумме максимально возможный выигрыш, так как в случае

существует

распределение D c , при котором каждый игрок i  N получит больше, чем его доля D i , если же

¦ Di ! v N , тоо игроки из N делят между собой

iN

нереализуемый выигрыш, поэтому вектор D неосуществим. Условие (4.4) называется условием индивидуальной рациональности (ИР) и означает, что ни один игрок не согласится получить меньше, чем то, что он может обеспечить себе сам, независимо от действий других игроков, т. е. в коалиции каждый игрок получит, по меньшей мере, столько, сколько он мог бы получить, действуя самостоятельно.

что и требовалось доказать. 46

¦ D i  v N

iN

47

Утверждение 4.2. Для того чтобы вектор D D1 ,..., D n был дележом в кооперативной игре  N , v , необходимо и достаточно выполнение D i v^i`  J i , i  N , причем

J i t 0, i  N ,

v N 

¦ Ji

iN

¦ v^i` .

iN

Доказать! Определение 4.6. Игра  N , v называется существенной, если i  v  N . ¦ v^`

iN

В любой существенной игре с более чем одним игроком множество дележей бесконечно. Этот случай интересен, так как можно искать компромисс среди множества дележей. Определение 4.7. Игра  N , v называется несущественной, если

v N

n

¦ v^i` . i 1

Здесь имеется единственный дележ D i v^` i , i  N . Определение 4.8 [3]. Игрок i называется болваном, если v S ‰ i v  S  S  N , т. е. если он вносит нулевой вклад в любую коалицию, в которую входит. При этом игрок i ничего не получает и сам, т. е. v^` i 0. n

i . Утверждение 4.3. v N t ¦ v^` i 1

Доказать! Определение 4.9. Будем говорить, что D E , т. е. дележ D S доминирует дележ E по коалиции S , если выполняются следующие условия: 1) D i ! E i , i  S ; 2)

¦ D i d v  S .

iS

Первое условие означает, что дележ D лучше, чем дележ E , для всех членов коалиции S, так как все игроки получат бóльший выигрыш от дележа . Второе условие означает, что этот дележ может быть гарантирован коалицией S. 48

Определение 4.10. Будем говорить, что D E , т. е. дележ D доминирует дележ E , если существует коалиция S , по которой D доминирует E . Доминирование невозможно по одноэлементной коалиции и множеству всех игроков N. Действительно, из D E следовало бы i

E i  D i d v^` i , что противоречит условию ИР. А из D E следовало бы, N

что D i ! E i

 i  N , и поэтому

¦ D i ! ¦ Ei

iN

v N , что противоречит

iN

условию КР. 4.3. С-ЯДРО К сожалению, может существовать следующее отношение доминирования: D может доминировать E по одной коалиции, E может доминировать D по другой коалиции, но D z E . Введем понятие недоминируемого дележа. Так как если игроки в кооперативной игре  N, v пришли к такому соглашению о распределении выигрыша всей коалиции N (дележу D* ), при котором ни один из дележей не доминирует D* , то о такое распределение устойчиво в том смысле, что ни одной из коалиций S невыгодно отделиться от других игроков и распределить между членами коалиции выигрыш vS . Определение 4.11. Множество недоминируемых дележей называется С-ядром. Множество дележей может быть , не существовать, а если оно существует и игра существенная, то оно может содержать бесконечное множество дележей. Нужно выделить «лучшие» дележи. Ни одна коалиция не имеет претензий к недоминируемому дележу. Какой дележ из ядра ни взять, не найдется коалиция S, которая аргументированно сможет предложить своим участникам бóльший выигрыш. Замечание 4.3. Введем обозначение C v для C-ядра кооперативной игры  N, v . Ниже в тексте в качестве обозначения C-ядра будем использовать просто C. Теорема 4.1. Для того чтобы дележ D  C œ ¦ D i t vS  S  N , (4.5) iS

49

где C – C-ядро кооперативной игры  N , v . Количество всех подмножеств множества N равно 2 N 1, поэтому количество неравенств (4.5) такое же. Доказательство. Обозначим ядро через С. Необходимость. Пусть D D1 ,..., D n  C , но не выполняется (4.5). Следовательно, существует хотя бы одна коалиция S c :

¦ D i  vS c , т. е.

iS c

можно найти дележ E , который будет доминировать D . Действительно, построим дележ E: v S c ,

¦ Ei

i  Sc

¦

Ei i  N \Sc

· 1 § ¨ vS c  ¦ D i ¸ . Тогда да ¸ | S c | ¨© ¹ iS c

Di  J для i  S c . По определению дележа должно выполняться D i t v^i` , но D i для коалиции N \ S c должно быть минимальным, так как получено в процессе игры коалиции S c против коалиции N \ S c . Поэтому для i  N \ S c имеем D i v^` i , а следовательно, v^i` 

Ei

N \ Sc

i ¦ v^`

i  N\S c

v^i`  Z.

Из-за супераддитивности функции v N t vS c 

i ¦ v^`

i  N\S c

получаем, что Z t 0, Ei t v^` i . Покажем, что не зависит от i:

¦ Ei

i  N\S c

¦ v^i`  ¦ Z

iN\S c

iN\S c

i  v N  vS c  ¦ v^` i ¦ v^`

i  N\S c

v  N  v S c , что дает нам два свойства:

1)

¦ Ei ¦ Ei  ¦ Ei

iN

iS c

iN \ S c

50

D . Тогда E D , следовательно: S

1) E i ! D i , i  S ;

Ei

v  N – v S c 

Следовательно, мы нашли E D , что противоречит недоминиSc руемости дележа D . Достаточность. Пусть выполняется условие (4.5), но D  C , т. е. существует дележ E

v N  vS c ,

т. е. к каждому из D i добавим число J , где J

2)

v  S c  ¦ D i · § ¨ ¸ iS c ¨ ¦ Di  S c ¸  v N  vS c v  N ; Sc ¨ iS c ¸ © ¹ E i ! D i t v^` i  i  S c , по предположению.

iN\S c

2)

¦ E i d v S ,

iS

но

это

противоречит

(4.5),

так

как

vS d ¦ D i  ¦ Ei d vS , следовательно, все дележи из (4.5) iS

iS

недоминирующие. Минимальным требованием для получения согласия игроков выбрать вектор D является его ИР, т. е. условие D i t v^` i , i  N . Пусть игроки договариваются о выборе конкретного дележа D . Против выбора дележа может возражать некоторая коалиция S, требующая для себя более выгодного распределения, угрожая в противном случае нарушить общую кооперацию по достижению дохода v N . Предположим, что все остальные игроки N \ S реагируют на угрозу объединенными действиями против коалиции S. Тогда максимальный гарантированный доход коалиции S оценивается числом vS . Существование стабилизирующей угрозы со стороны коалиции N \ S в адрес коалиции S обеспечивается условием (4.5), поэтому С-ядром игры  N, v является множество устойчивых, в смысле коалиционных угроз, распределений максимального суммарного дохода v N . Следствие 4.1. С-ядро является замкнутым выпуклым подмножеством множества всех дележей. Таким образом, С-ядро представляет собой множественный принцип оптимальности, хотя и один из основных в кооперативной теории. Всегда остается открытым вопрос, какой все-таки дележ С-ядра необходимо выбрать из множества в конкретном случае. С-ядро может оказаться также пустым. 51

Пример 4.1. Рассмотрим игру «джаз-оркестр». Директор клуба обещает 100 у. е. певцу (1), пианисту (2) и ударнику (3) за совместное выступление. Дуэт певца и пианиста он оценивает в 80 у. е., ударника и пианиста – в 65 у. е. и одного пианиста – в 30 у. е. Другие дуэты и солисты не рассматриваются, поскольку присутствие фортепиано директор клуба считает обязательным. Дуэт певец – ударник зарабатывает 50 у. е., а певец – в среднем 20 у. е. за вечер. Ударник один ничего не может заработать. Таким образом, имеем кооперативную игру  N, v , где N ^1, 2, 3`,

v1, 2, 3 100 , v1, 3 50 , v1

Построим решение геометрически (рис. 4.1). Правая крайняя точка параллелепипеда имеет координаты (20; 50; 35) и сумма координат 20  50  35 105 ! 100 . Следовательно, существует сечение параллелепипеда плоскостью треугольника: D1

35 ; D 2 ;

Известно, что КР обеспечивается условием

¦ Di

(4.6)

v N . Разобьем

iN

сумму на два слагаемых согласно имеющимся коалициям v N . Из теоремы 4.1 следует, что для того, чтобы дележ

iN \ S

D принадлежал С-ядру, необходимо и достаточно выполнение неравенств

¦ Di t vS . Тогда ¦ Di

iS

iN \ S

20 , D 3

35 ; 50 ; D 3 .

20 , v1, 2 80 , v2, 3 65 , v2 30 ,

­D1 t 20, D 2 t 30, D 3 t 0, ° ®D1  D 2  D 3 100, °D  D t 80, D  D t 65, D  D t 50 . ¯ 1 2 2 3 1 3

¦ Di  ¦ Di

D1 ; 50 ; α3

v3 0 . Какое распределение максимального общего дохода следует признать разумным? у Вектор D D1 , D 2 , D 3 в игре «джаз-оркестр» принадлежит С-ядру тогда и только тогда, когда

iS

20 , D 2

v N  ¦ D i d v N  vS . Отсюда следует,, iS

что система неравенств D1  D 2 t с3 , D1  D 3 t c2 , D 2  D 3 t c1 равносильна системе неравенств D 3 d v N  c3 , D 2 d v N  c2 , D1 d v N  c1 . Тогда систему (4.6) можно переписать в виде D1  D 2  D 3 100, ­ ® ¯35 t D1 t 20, 50 t D 2 t 30, 20 t D 3 t 0 . 52

20 50

α2

35

α1 Рис. 4.1

В сумме координаты должны быть равны 100 , следовательно, найдем, что D 2 45 , D1 30 , D 3 15 . Таким образом, С-ядро – этоо множество, являющееся выпуклой оболочкой следующих трех дележей: 35 ; 45 ; 20 , 35 ; 50 ; 15 , 30 ; 50 ; 20 . Выигрыш всех игроков определяется с точностью до 5 у. е. Типичным представителем ядра является центр (среднеарифметическое крайних точек) С-ядра, а именно: D* 33,3 ; 48,3 ; 18,3 . Для дележа D* характерно, что все двухэлементные коалиции имеютт одинаковый дополнительный доход: D i  D j  v^i, j` 1,6 . Дележ D* является «справедливым» компромиссом внутри С-ядра. 4.4. САМОСТОЯТЕЛЬНАЯ РАБОТА № 4 Найти С-ядро и его центр в кооперативных играх  N , v трех лиц (см. прил. 2). 53

Занятие № 5.

ДРУГИЕ ПРИНЦИПЫ ОПТИМАЛЬНОСТИ. НМ-РЕШЕНИЕ И ВЕКТОР ШЕПЛИ

5.1. ИГРА В 0  1 -РЕДУЦИРОВАННОЙ ФОРМЕ Определение 5.1. Игра  N , v называется игрой в 0  1 редуцированной форме, если для всех i  N выполняется v^` i 0, v N 1. Теорема 5.1. Каждая существенная кооперативная игра эквивалентна некоторой игре в 0  1 -редуцированной форме. Доказательство. Пусть vcS kvS  ¦ ci , iS

где k

v N 

1

i ¦ v^`

! 0; ci

iN

v^` i . Тогда  v N  ¦ v^i`

что

v N 

i ¦ v^`

.

(5.1)

iN

Следовательно, vc^` i 0, vc N 1 , ч. т. д. Из теоремы следует, что существует 0  1 -нормализация, соответствующая функции v . Определение 5.2. Дележом в игре в 0  1 -редуцированной форме называется любой вектор D D1 ,..., D n , компоненты которогоо удовлетворяют условиям D i t 0, i  N ,

¦ Di

¦ (с i  [ i ) Пусть E i

vS  ¦ v^` i iS

3

2, ci  [ i d 1, i 1,3.

i 1

iN

vcS

Доказательство. Необходимость. Пусть C z ‡ , но c1  c2  c3 ! 2 . На основании теоремы 4.1, чтобы D  C , необходимо и достаточно выполнение следующих неравенств: D1  D 2 t с3 , D1  D 3 t c 2 , D 2  D 3 t c1 или (5.3) D 3 d 1  c3 , D 2 d 1  c 2 , D1 d 1  c1 . Складываем неравенства (5.3), получаем D1  D 2  D 3 d 3  c1  c2  c3 . Поскольку D1  D 2  D 3 1, то следует выполнение неравенства (5.2), что о противоречит предположению. Достаточность. С другой стороны, пусть C ‡ , но выполняется неравенство (5.2), тогда существуют такие неотрицательные [1 , [ 2 , [ 3 ,

ам 1  ci  [ i , i 1,3 . Числа Ei удовлетворяют неравенствам

(5.3), следовательно, дележ E E1, E 2 , E3  C , откуда верно, что C z ‡ , ч. т. д. Геометрической интерпретацией дележей в рассматриваемой игре является D АВС: D1  D 2  D 3 1, D i t 0, i 1, 3 (рис. 5.1). D3 B (0, 0, 1)

1,

iN

т. е. дележи можно рассматривать как точки n  1 -мерного симплекса,



c1  c2  c3 d 2 .

(5.2)

C (1, 0, 0)

0



порожденного ортами Z j 0, ..., 0, 1 j , 0, ..., 0 , j 1, n , пространства R n . Утверждение 5.1. Для того чтобы С-ядро было не пусто в игре трех лиц в 0  1 -редуцированной форме, где v1,2 c3 , v(1,3) c2 , v2,3 c1, 0 d ci d 1, i 1,3 , необходимо и достаточно выполнение условия

54

a3

a2

D1 A (0, 1, 0)

D2

a1 Рис. 5.1 55

Непустое С-ядро представляет собой пересечение множества дележей (D АВС) и выпуклого многогранника (параллелепипеда) 0 d D i d 1  сi , i 1,3. На рис. 5.1 через D i , i 1,3 обозначены прямые, образованные пересечением плоскостей (5.4) D i 1  ci и D1  D 2  D 3 1. Точка пересечения двух прямых D i и D j принадлежит D АВС, если k-я k z i, k z j координата этой точки неотрицательная, в противном случае она находится за пределами D АВС (рис. 5.2, 5.3). Таким образом, С-ядро имеет вид треугольника, если совместное решение любой пары уравнений (5.4) и уравнения D1  D 2  D 3 1 состоит из неотрицательных чисел. Это требование выполняется при

c1  c 2 t 1, c1  c3 t 1, c 2  c3 t 1.

(5.5)

B (0, 0, 1)

B (0, 0, 1)

D2

D2

D3

D3

C (1, 0, 0) A (0, 1, 0)

A (0, 1, 0)

5.2. НМ-РЕШЕНИЕ Хотя элементы С-ядра и не доминируются никакими другими дележами, нельзя утверждать, что для любого наперед заданного дележа D найдется в С-ядре дележ доминирующий D . Определение 5.3. Подмножество дележей М называется НМ-решением (решением Ноймана – Моргенштерна), если никакие два дележа внутри множества М не доминируют друг друга, а любой дележ вне – доминируем дележом из множества М, т. е.: 1)

 D1 , D 2  M  справедливо D1  D 2 , D 2  D1 ; векторы

2)  E  M  D  M : D E . Определение 5.4. Подмножество дележей М кооперативной игры м, если выполняются следующие усло N, v называется НМ-решением вия: 1) из D ! E следует, что либо D  M , либо E  M (внутренняя устойчивость); 2) для любого D  M E  M , чтоо E t D (внешняя устойчивость). В случае, если С-ядро не пусто и НМ-решение существует (рис. 5.4), соотношение С-ядра и НМ-решения выражается следующим далее утверждением. Утверждение 5.3. НМ-решение содержит С-ядро.

C (1, 0, 0) D1

D1

НМ

Рис. 5.2

Рис. 5.3

В зависимости от разных случаев (а всего их может быть восемь) С-ядро будет приобретать тот или иной вид. Например, если не выполняется одно из трех неравенств (5.5), то С-ядро оказывается шестиугольником (см. рис. 5.3). Для общей игры трех лиц можно доказать аналогичное утверждение. Утверждение 5.2. С-ядро имеет вид треугольника, если выполняются условия c1  c 2 t v N  v3 , c1  c3 t v N  v 2 , c 2  c3 t v N  v1 . (5.6) 56

C

Рис. 5.4 57

Доказательство. Предположим противное, т. е. что C   M Ÿ  D  С, D  M :  E  M : E D , но D не доминируем, так как D  C . Замечание 5.1. НМ-решение, как и С-ядро, является множественным принципом оптимальности. Так как НМ-решение содержит С-ядро, то предполагается, что оно не пустое. Однако можно построить игру из 10 лиц: +0 ‡ . Задача. Построить игру из 10 лиц, чтобы для нее НМ-решение было пустое. Теорема 5.2. Если для характеристической функции игры  N, v в 0  1 -редуцированной форме  N n выполняются неравенстваа 1 v S d S  N , (5.7) n  S 1 где S – число игроков в коалиции S, то С-ядро этой игры не пустоее и является ее НМ-решением. Замечание 5.2. Обратное неверно. Это достаточное условие, но не необходимое. Если условие (5.7) выполняется, то C z ‡ и C HM . Если (5.7) не выполняется, то: 1) если C ‡ , то HM ‡ ; 2) если C z ‡ , то С-ядро не является НМ-решением. Доказать! Определение 5.5. Игра  N, v в 0  1 -редуцированной форме называется простой, если для любых S  N vS принимает лишь одно из двух значений: 0 или 1. Определение 5.6. Кооперативная игра называется простой, если проста ее 0  1 -редуцированная форма. Пример 5.1. Рассмотрим простую игру трех лиц в 0  1 -редуцированной форме, в которой коалиция, состоящая из двух и трех игроков, выигрывает vS 1 , а коалиция, включающая только одного игрока, проигрывает v^` i 0 . Для этой игры рассмотрим три дележа:

тельно, не может быть более двух компонент вектора D : D i t 1 2 . Если их действительно две, то каждая из них равна 1 2 , в то время как третья равна нулю. Но это означает, что D совпадает с одним из D ij . Если жее D z D ij , то он имеет не более одной компоненты, например D i и D j , где i  j , не меньшей, чем 1 2 . Но в этом случае D ij ! D . Таким образом, ом, три дележа (5.8) образуют НМ-решение. Но это не единственное НМрешение. о Пусть c  >0,1 2@. Проверим, что множество L3,c

^ a , 1  c  a , c 0 d a d 1  c `

также является НМ-решением. Действительно, в это множество входят дележи, при которых игрок 3 получает постоянную с, а игроки 1 и 2 делят остаток во всевозможных пропорциях. Внутренняя устойчивость следует из того, что для любых дележей о D 2  E 2 . Однако домиD и E из этого множества имеем, если D1 ! E1 , то нирование по коалиции, состоящей из единственного участника, невозможно. Чтобы доказать внешнюю устойчивость L3,c , возьмем какой-либо дележ E  L3, c . Это означает, что либо E3 ! c , либо E3  c . Пусть, например, E3

м: c  H . Определим дележ D следующим образом:

D1

E1  H / 2, D 2

E 2  H / 2, D 3

c.

Тогда D  L3, c и D t E по коалиции ^1, 2`. ак Пусть теперь E3 ! c . Тогда либо E1 d 1 / 2 , либо E 2 d 1 / 2 (так как в противном случае их сумма была бы больше 1). Пусть E1 d 1 / 2 . Положим D

1 c, 0, c . Так как 1  c ! 1 / 2 t E1 , тоо

D t E по коалиции ^1,3`.

Очевидно, что D  L3,c . Если же E 2 t 1 / 2 , то можно показать аналогич-

D12 1 / 2 ; 1 / 2 ; 0 , D13 1 / 2 ; 0 ; 1 / 2 , D 23 0 ; 1 / 2 ; 1 / 2 , (5.8) не доминирующих друг друга. Кроме того, любой другой дележ доминируется одним из этих дележей Dij . Проверим этот факт.. Рассмотрим произвольный дележ D D1 ; D 2 ; D 3 . Так как игра в 0  1 -редуцированной форме, то D i t 0 и D1  D 2  D 3 1, следоваа-

но, что J t E , где J 0, 1  c, c . Таким образом, кроме симметричного НМ-решения, рассматриваемая игра имеет еще целое семейство решений, при которых игрок 3 получает фиксированное значение с из отрезка 0 d c  1/ 2 . Эти НМ-решения называются дискриминирующими, а игрок 3 дискриминирован.

58

59

В случае множества L3,0 говорят, что игрок 3 полностью дискриминирован, или исключен. Из соображений симметрии очевидно, что существуют также два семейства НМ-решений L1,c и L2,c , в которых дискриминируются игроки 1 и 2 соответственно. К сожалению, применение понятия НМ-решения на практике невозможно. Существование НМ-решений в общем случае до сих пор не доказано, некоторые частные результаты касаются существования НМ-решений для конкретных классов или определенного типа игр [4]. 5.3. САМОСТОЯТЕЛЬНАЯ РАБОТА № 5 Исследовать кооперативную игру  N, v трех лиц на наличие НМ-решения по вариантам заданий самостоятельной работы № 4. 5.4. ВЕКТОР ШЕПЛИ. СВОЙСТВА

D

Определение 5.7. Вектором Шепли называется дележ

D1 ,..., D n , определяемый следующим образом: s  1 ! n  s !>vS  vS \ ^` Di ¦ i @ ,  n! SN Sэi

(5.9)

d v ^i`

N ; s S ; i 1, n . Каждому игроку предлагается выплачивать сумму, определенную (5.9). Почему именно такую?

¦

SN iS

s  1 ! n  s ! n!

– вероятность формирования

SN iS

s  1 ! n  s ! n!

4)

n  s ! – число перестановок сзади, за игроком i; s  1 ! n  s ! 1 s  1 ! n  s ! 1 ˜ 1 n! n n C sn––11 – частота образоваn – 1 !

ния коалиции S, вероятность ее формирования. Второй сомножитель формируется следующим образом: 1) vS – гарантированный выигрыш коалиции S с игроком i; 3) vS  vS \ ^` i – гарантированный выигрыш, который привносит игрок i, сила игрока, вклад игрока в коалицию S, например влияние футболиста на команду. Так как S – случайное множество, то vS 

 vS \ ^` i – случайная величина. Следовательно, при указанном способе формирования коалиции S вектор Шепли – это математическое ожидание выигрыша игрока i по всем коалициям S, в которые входит игрок i: N

коалиции S по всему множеству N, т. е.

¦

3)

2) vS \ ^` i – гарантированный выигрыш коалиции S без игрока i;

где n

Коэффициент

Пример 5.2. Пусть n игроков становятся в очередь. Любая комбинация игроков одинакова. Образуется коалиция S: i-й игрок находится на каком-либо месте в любой перестановке (отметим момент вступления в коалицию как способ формирования коалиции). Игрок i включается в коалицию с теми, кто впереди. В скольких случаях образуется коалиция S (с игроком i)? Задание коалиции – это перечисление 1 игроков (состав). Вероятность элементарного события . Какое число n! элементарных событий дает коалиция S? Первый сомножитель – вероятность формирования коалиции S: 1) n! – общее число перестановок; 2) s  1 ! – число перестановок впереди игрока i;

s  1 ! n  s ! n!

1, а D i – усредненный вклад игрокаа i в игру.

60

¦ pi x i t0 ,

M  x .

i 1

Пример 5.3. Выбирается размер коалиции – количество членов, допустим s, в коалиции фиксируется игрок i. Остальной набор членов выбирается с равной вероятностью: S ^i, ... ` . 61

Все коалиции с равным числом элементов равновероятны. Как выбирает игрок i коалицию S? Выберем количество игроков n в коалиции с равной вероятностью 1 n . Пусть, например, 1 n 5 , следовательно, игрок вступает в коалицию из 5 человек, включая себя. Оставшиеся 4 человека выбираются с равной вероятностью. Сколько вариантов выбора? 4!n  4 ! . n! Замечание 5.3. Негативной стороной вектора Шепли является то, что он может не принадлежать С-ядру, т. е. его можно доминировать. Определение 5.8. Если в качестве вероятности формирования коаC N4 1

1

лиции S взять вероятность pS

вместо

s  1 ! n  s !

, т. е. вее2 n! роятности образования всех коалиций одинаковы, то имеем индекс Банзафа

Dci

¦

SN 2

N 1

1 N 1

>vs  vs \ ^i` @.

S i

Замечание 5.4. Индекс Банзафа не является дележом. Пример 5.4. Комитет из трех человек принимает различные решения простым большинством (два – «за»), но один его член (председатель) имеет право вето. Определить вектор Шепли для соответствующей игры. Составим характеристическую функцию, считая выигрыш коалиции при принятии предлагаемого ею решения равным 1, а при отклонении – 0 (игроку, имеющему право вето, присвоим номер 1). Имеем v^1, 2` v^1, 3` v^1, 2, 3` 1, v^1` v^2` v^3` v^2, 3` 0 . По формуле (5.9), учитывая, что отличными от нуля в данном примере являются слагаемые, в которых коалиция S i выигрывающая (получает 1), а коалиция Si \ ^` i проигрывающая (получает 0), получим

1 >v^1, 2`  v^2` @  1 >v^1, 3`  v^3` @  2!0! >v^1, 2, 3`  v^2, 3` @ D1 3! 3! 3! (по определению 0! 1);

2 3

D2 D3

1 >v^1, 2`  v^1` @ 1 ; 3! 6 1 >v^1, 3`  v^1` @ 1 . 3! 6

Заметим, что С-ядро в этом примере содержит один дележ 1, 0, 0 , т. е. вектор Шепли здесь не принадлежит ядру. Пример 5.5. Рассмотрим игру трех лиц, в которой коалиция из двух или трех игроков является выигрывающей (получает 1), а из одного игрока – проигрывающей (получает 0). Характеристическая функция (супераддитивная) определяется следующими соотношениями: v^1` v^2` v^3` 0 , v^1, 2` v^1, 3` v^2, 3` v^1, 2, 3` 1; тогда D1

1  1 !3  1 ! >v^1`  v^0` @  2  1 !3  2 ! >v^1, 2`  v^2` @ 

3! 3! 2  1 !3  2 ! >v^1, 3`  v^3` @  3  1 !3  3 ! >v^1, 2, 3`  v^2, 3` @  3! 3! 1!1! 2 1 2 1 . 3 2˜3 3

В этой игре С-ядро, очевидно, пусто; вектор Шепли равен

1/3,1/3,1/3 .

5.5. САМОСТОЯТЕЛЬНАЯ РАБОТА № 6 Найти вектор Шепли и индекс Банзафа в кооперативных играх  N, v трех лиц по вариантам заданий самостоятельной работы № 4. 5.6. PMS-ВЕКТОР Пусть имеется игра n лиц Г

^N , X 1 , ,

ной форме, где X i и H i – множество стратегий и выигрыш i-го игрокаа соответственно, и пусть задано коалиционное разбиение 6 l d n, S i ˆ S j

^S1,, Sl `,

‡  i z j , т. е. множество игроков разделены на l коа-

лиций. 62

X n , H 1 , , H n ` в нормаль-

63

Рассмотрим игру в нормальной форме Г 6

^N , X 1 , ,

Xl ,

H 1 ,, H l ` между l лицами, в которой игроками являются коалиции из ов. разбиения 6 . Рассмотрим коалицию Si , состоящую из si игроков. Обозначим множество стратегий игрока j  Si через X j

^x kj `k 1,l , j

где l j – число стратегий j-го игрока. Тогда множество стратегий коалиции S i есть X Si

– X j , т. е. декартово произведение множеств стратеjSi

гий игроков, входящих в коалицию Si .

тор Шепли в игре GS i через Sh S i

X Si

где PMSi Г 6 полагается равным Sh Si : j , если j  Si , i 1, l , [5]. Предположим теперь, что в игре Г 6 не существует NE в чистых стратегиях. Рассмотрим случай, когда множество стратегий конечно. Пусть P P1 , ... , Pl – NE в смешанных стратегиях в игре Г 6 , где смешанная стратегия коалиции S i есть вектор

Pi

ек– l j . Тогда стратегией коалиции Si в игре Г 6 является векjSi

тор xi  X Si размерности si из множества стратегий X S i , а выигрыш

l6

¦ H j . Число ситуаций в чистых стратегиях в игре Г 6 есть

jSi

– l Si .

i 1,l

Предположим, что в игре Г 6 существует NE x значим через vSi

¦ H j x1,..., xl , i

jS i

xS , ..., x S . Обо1

l

1, l , выигрыш коалиции S i в NE.

Ситуаций NE в игре может быть много, следовательно, vS1 , ...., vS l определяются неоднозначно. Рассмотрим для каждой коалиции Si  6 , i 1, l , кооперативную игру GS i в предположении, что игроки, не входящие в Si , используютт равновесные стратегии, входящие в ситуацию x . Определение 5.9. Пусть wS i : K vS i , где K  S i , i 1, l , – характеристическая функция в кооперативной игре G Si . Обозначим век64

§¨ P1 , ... , P lSi i © i

·¸ , P j t 0 , j ¹ i

1, l Si ,

l Si

¦ P ij

1.

j 1

Обозначим через vS i , i 1, l , выигрыш коалиции S i в NE, т. е.

игрока Si равен сумме выигрышей игроков, входящих в коалицию Si , т. е. H Si

si –

число элементов множества Si . Тогда PMS-вектор в игре Г 6 определяется следующим образом: PMSГ 6 PMS1 Г 6 , ... , PMSn Г 6 ,

Количество чистых стратегий у коалиции Si обозначим черезз l Si

Sh S i : 1 , ..., Sh S i : si , где

vS i

l6

¦ p k H k S i ,

k 1

где H k Si

¦ H j x1,, xl , а

jS i

pk

– Pi i , j

ji

i 1, l

1, lS i , k 1, l6 , – веро-

аятность реализации выигрыша H k S i коалиции Si при выборе игроками чистых стратегий x ji в ситуации NE в смешанных стратегиях P . Зна-

чение H k S i является случайной величиной. Ситуаций NE в игре мо-

жет быть много, следовательно, vS1 , ...., vS l определяются неоднозначно. Рассмотрим для каждой коалиции Si  6 , i 1, l , кооперативную игру GS i в предположении, что игроки, не входящие в S i , используютт равновесные стратегии, входящие в ситуацию P . Определение 5.10. Пусть wSi : K – характеристическая функция в кооперативной игре GS i , где K  Si . Разделим выигрыш wSi vSi между игроками коалиции S i согласно вектору Шепли Sh 65

Sh1, ..., Sh S : i

Sh i где s

S , sc

¦

S c S S cэi

sc  1 ! s  sc ! >wS c  wS c \ ^` i @  i s!

Занятие № 6.

1, s ,

S c – количество элементов множеств, а wS c – макси-

мальные гарантированные выигрыши по всем S c  S . Обозначим вектор Шепли коалиции S k :

Sh S k

Sh S k : 1 , ..., Sh S k : sk ,

м wSi где sk – число элементов множества S k . При этом

sk

¦ Sh Sk : j . j 1

Òî ãäà PMS-вектор в ситуации NE в смешанных стратегиях в игре

Г 6 определяется как

PMSГ 6

PMS1Г6 , ..., PMS N Г6 ,

где PMS j Г 6 Sh S i : j , j  Si , i 1, l. Примеры реализации PMS-вектора представлены в прил. 1.

МНОГОШАГОВЫЕ ИГРЫ С НЕПОЛНОЙ ИНФОРМАЦИЕЙ

6.1. ПОСТАНОВКА ЗАДАЧИ Вернемся к многошаговым играм. Напомним, что игры в развернутой форме, или позиционные игры, представляются как выбор альтернатив на конечных древовидных графах. Позиционная форма задается деревом игры, которое описывает, какая вершина следует за какой, какой игрок ходит в соответствующей вершине. Информация, которую имеют игроки, описывается с помощью информационных множеств. Определение 6.1. Множество неразличимых для игрока вершин называется информационным множеством (ИМ). Если две вершины лежат в одном ИМ (на рис. 6.1 это позиция 3), то это означает, что игрок не может сказать, какое из двух действий (I или II) в действительности произошло, т. е. не различает вершины, лежащие в одном ИМ.

3

I

II

3

2

1 Рис. 6.1

Замечание 6.1. На рис. 6.2 и 6.3 изображены недопустимые ИМ: ИМ не могут пересекаться, так как игрок не различает вершины, лежащие в объединении этих ИМ; в вершинах одного ИМ множества доступных игроку альтернатив должны совпадать (иначе игрок сможет различить вершины ИМ). 66

67

n 3 2

2

N – число игроков;

X i , i 1, n , – множество очередности игрока i, X i ˆ X j

3

2

X n 1 2

2

1

1

Рис. 6.2

Рис. 6.3

В многошаговых играх с ПИ каждый игрок в момент совершения своего хода точно знает, в какой позиции или в какой вершине дерева он находится, поэтому удалось ввести понятие стратегии игрока i как однозначной функции ui  x , определенной на множестве очередности X i со значениями в множестве Fx . Однако если игроки при совершении своих выборов не знают точно позиции, в которой они совершают ход, то реализация стратегии игрока как функции от позиции x  X i невозможна. Таким образом, усложнение информационной структуры игры приводит к изменению понятия стратегии. Определение 6.2. Стратегия игрока – это правило, которое каждому ИМ игрока ставит в соответствие некоторую альтернативу, возможную в данном ИМ. Например, S1 1, 3 -стратегия игрока 1 говорит о том, что игрок 1 выбирает альтернативу 1 в первом ИМ и альтернативу 3 – во втором ИМ. Если в первом ИМ вершины имеют 2 альтернативы, а во втором – 3, то всего возможно 6 стратегий: 1,1 , 1, 2 , 1, 3 , 2,1 , 2, 2 , 2, 3 . Если две позиции входят в одно ИМ, то игрок выбирает одну и ту же стратегию для любой из этих позиций. Дадим общее определение игры в развернутой форме. Определение 6.3. Многошаговая позиционная игра n лиц G определяется: 1) древовидным графом Г  X , F с начальной вершиной x0 , называемой начальной позицией игры; 2) разбиением множества всех вершин X

n2

 X i , где

i 1

68

^x : Fx

‡, i z j ;

‡` – множество окончательных позиций;

X n  2 – множество вершин случайного хода (случайности, не зависящие от игроков, например какие-либо природные явления, непредвиденные обстоятельства, дождь, землетрясение и т. д., а также бросок игральной кости (игра с ПИ) или сдача карт (игра с неполной информацией) (см. рис. 6.5); 3) заданием вектор-функции K  x K1  x , ..., K n  x на множествее

окончательных позиций x  X n 1 , где функция K i  x – выигрыш i-гоо игрока; 4) определением для каждого х, где x  X \ X n 1 , множества альтернатив M M  x в вершине x (конечного множества натуральных чисел от 1 до какого-либо числа, которое зависит от x : ^1, ..., M `). Эти альтернативы являются номерами дуг, исходящих из вершины х; при этом нумерация производится по часовой стрелке и первый номер присваивается крайней слева исходящей дуге (рис. 6.4);

1

2

3

Fx

x

Fx1 Рис. 6.4

5) подразбиением каждого множества очередностей X i , i 1, n , на непересекающиеся подмножества U i , называемые ИМ игрока i. Они обладают свойствами: а) U ic ˆ U icc ‡ или U ic U icc , т. е. либо не пересекаются, либо совпадают. Объединение всех ИМ совпадает с множеством Х; 69

б)  x, y U i , M  x M  y , т. е. любые две различные вершины одного и того же ИМ имеют одинаковое количество альтернатив; в) каждое ИМ пересекается только однажды с любым путем, идущим из начальной позиции (вершины) x0 ; 6) заданием для  x  X n 2 распределения вероятностей P1  x , …,

Pm  x на множестве альтернатив, исходящих из вершины x: m

¦ Pk x

k 1

Замечание 6.2. Для различных x распределение вероятностей различно. Замечание 6.3. Начальная вершина состоит только из одного ИМ. Пример 6.1. Рассмотрим древовидный граф (см. рис. 6.5). еМножество X – это множество всех узлов; X i , i 1,3 , – множество очередности игрока i; X 4 – множество окончательных позиций;

X 5 – множество очередности случайного игрока. §  1· ¨ ¸ ¨1¸ ¨1¸ © ¹

§ 3 · § 4· §7· ¨ ¸ ¨ ¸¨ ¸ ¨ 1 ¸ ¨ 2 ¸ ¨3¸ ¨ 1¸ ¨ 1 ¸ ¨ 2 ¸ © ¹ © ¹© ¹

§5· ¨ ¸ ¨3¸ ¨ 1¸ © ¹

§2· ¨ ¸ ¨1¸ ¨3¸ © ¹

1

2

1 2

1

2

I

3

I 1 II

1

§2· ¨ ¸ ¨4¸ ¨1¸ © ¹ 1

1

x0

§6· ¨ ¸ ¨ 2¸ ¨ 1¸ © ¹ 2

III

III

2

II

2

2

Рис. 6.5

В окончательной позиции заданы три числа – выигрыши игроков. Если игрок 3 не знает, что делал игрок 2, то две вершины объединяем в одно ИМ. Игру начинает «случайный игрок» в вершине x0 . В зависимости от его выбора альтернативы левая ветвь игры реализуется с вероятностью 1 3 , а правая – с вероятностью 2 3 . Например, если случайный 70

ятностью 2 3 дождя не будет, то если дождь пойдет, то реализуется левая ветвь игры, если нет, то правая ветвь игры. 6.2. ВОЗМОЖНЫЕ ПОЗИЦИИ И СУЩЕСТВЕННЫЕ ИНФОРМАЦИОННЫЕ МНОЖЕСТВА Пусть Ak – множество всех вершин x  X , имеющих ровно k аль-

1, Pk  x t 0.

§ 2· ¨ ¸ ¨ 1 ¸ ¨ 0 ¸ © ¹

игрок – «дождь» и известно, что дождь идет с вероятностью 1 3 , а с веро-

тернатив, т. е. Ak

^x : Fx

k `. Пусть I i

^X ij : X ij  X i ` – множествоо

всех ИМ игрока i. Определение 6.4. Чистой стратегией игрока i называется функция ui , отображающая I i в множество положительных чисел:

 ^1, k `, если X

ui X ij

i

j

 Ak .

При этом будем говорить, что стратегия ui выбирает альтерна-



тиву l в позиции x  X i j , если ui X i j l , где l – номер альтернативы. Напомним, что через Z мы обозначили некоторую партию в игре, т. е. такую последовательность вершин от начальной до окончательной, что каждая последующая принадлежит образу предыдущей. Утверждение 6.1. Каждой ситуации u ˜ u1 ˜ ,..., un ˜ единственным образом соответствует партия Z, следовательно, и выигрыш в окончательной позиции этой партии. Определение 6.5. Позиция x  X называется возможной для чистой стратегии ui ˜ , если существует ситуация u ˜ , содержащая эту стратегию, в которой реализуется путь Z, содержащий эту позицию. Очевидно, что партия Z возможна при данной стратегии ui ˜ тогда и только тогда, когда эта стратегия выбирает альтернативы, соответствующие этой партии во всех ИМ, которые эта партия пересекает. Отсюда следует справедливость следующей далее леммы [5, с. 212]. Лемма 6.1. Позиция x  X i j для стратегии ui ˜ является возможж-

ной тогда и только тогда, когда u i ˜ выбирает альтернативы, лежащие на отрезке партии Z x от x0 до x во всех своих ИМ, пересекающих Z x . 71

Определение 6.6. ИМ i-го игрока X i j называется существенным

при использовании стратегии ui ˜ , если оно содержит хотя бы одну вершину x  X i j , которая возможна при этой стратегии.

Множество позиций, возможных для ui ˜ , обозначим через Poos ui ˜ ,

а семейство ИМ, существенных для ui ˜ , – Rel ui ˜ . Поясним эти определения на примере. Пример 6.2. Рассмотрим стратегию игрока 1 u1 ˜ 2, 2 в АИ, изображенной на рис. 6.6. Какие позиции возможны для этой стратегии? Очевидно, что возможными позициями для этой стратегии являются позиции x1, x4 , x5 , x11, x13 , т. е. Poos ui ˜ ^x1 , x4 , x5 , x11, x13`. Тогда партии Z1  x1, y2 , x4 , x11 и Z 2  x1, y2 , x5 , x13 возможны при этой стратегии, а остальные – нет (см. рис. 6.7). –2

x6

–1

3

2

1

x7

1

–4

x8

5

x9

2

1

x3

x2 1

x10 x11

x12 x13 1

y1

I

x1

y2

6

2

x5

x4 1

1

2

2

2

II

2

I

2

II

2

Рис. 6.6

Соответственно оба ИМ игрока 1 существенны при данной стратегии, т. е. Rel u1 ˜ ^^x1`, ^x2 , x3 , x4 , x5 ``. Определение 6.7. Смешанной стратегией P i игрока i называется вероятностное распределение на множестве чистых стратегий, которое каждой его чистой стратегии ui ˜ ставит в соответствие вероятность qui ˜

qui . 72

Утверждение 6.2. Ситуация P P1 ,..., P n в смешанных стратегиях определяет распределение вероятностей на всех партиях Z (следовательно, и на окончательных позициях X n 1 ) по формуле PP Z

¦ qu1 ... qu n Pu Z , u

где Pu Z 1, если партия Z реализуется в ситуации u ˜ , и Pu Z 0 в противном случае. Предположим, что в ситуации P партия Z имеет положительную вероятность. Тогда, очевидно, что если в этой партии нет вершин, принадлежащих множеству X n  2 , т. е. нет случайных ходов в этой партии, то вероятность этой партии в ситуации u равна 1. Однако если в этой партии есть вершины, принадлежащие множеству случайных ходов X n  2 , то вероятность реализации этой партии в ситуации u равна произведению вероятностей альтернатив по множеству вершин случайного хода, принадлежащих данной партии, и направлена вдоль этой партии. §0· ¨¨ ¸¸ ©0¹ z1 –2

§0· ¨¨ ¸¸ ©0¹ z2

x6

–1 x7

1

2

§0· ¨¨ ¸¸ ©0¹ z3 3

§0· ¨¨ ¸¸ ©0¹ z4

§ 3 / 8· ¨¨ ¸¸ ©1/ 2 ¹ z5

–4 x9

x8

1

5

2

1

x11

x10 1

x3

x2

§3 /8· ¨¨ ¸¸ © 1/ 2 ¹ z6

2

2

x12 1

1

I

1

x 13

6

I

2

y2

y1

§1/ 8 · ¨¨ ¸¸ ©1 / 2¹ z8

2

x5

x4

2

II

2

§1/ 8 · ¨¨ ¸¸ ©1 / 2 ¹ z7

II

2

x1 Рис. 6.7

Пример 6.3. Пусть в рамках условий примера 6.2 дано вероятностное распределение (на рис. 6.7 вверху проставлены qu1 ˜ ) P1 q1 1,1 0, 73

q1 1, 2 0, q1 2,1 1 2 , q1 2, 2 1 2 , где q1 i, j – вероятность выбора

1-м игроком стратегии i, j .

Пусть также дано вероятностное распределение P 2

q2 1,1

1 2,

q2 1, 2 1 4 , q2 2,1 1 4 , q2 2, 2 0 . Тогда найдем распределение вероятностей на всех партиях Z, т. е. на окончательных позициях X n 1 : PP Z1 qu1 1,1 , 1,1 qu2 ˜ P˜ Z1  qu1 1, 2 , 1,1 qu2 ˜ P˜ Z1 

 qu1 2,1 , 1,1 qu2 ˜ P˜ Z1  qu1 2, 2 , 1,1 qu2 ˜ P˜ Z1 

1 7 7 3 3 1 E1 P 5 ˜  2 ˜  2 ˜  8 ˜ 3 ; E 2 P 3 . 8 8 8 8 8 8 Определение 6.8. Позиция x  X называется возможной при использовании смешанной стратегии P i , если существует ситуация P в смешанных стратегиях, содержащая P i , такая, что вероятность попадания в

 qu1 1,1 , 1, 2 qu2 ˜ P˜ Z1  qu1 1, 2 , 1, 2 qu2 ˜ P˜ Z1 

эту позицию положительна, т. е. P P  x ! 0 . Определение 6.9. Будем говорить, что партия Z возможна при использовании стратегии P i , если существует ситуация P, содержа-

 qu1 2,1 , 1, 2 qu2 ˜ P˜ Z1  qu1 2, 2 , 1, 2 qu2 ˜ P˜ Z1   qu1 1,1 , 2,1 qu2 ˜ P˜ Z1  qu1 1, 2 , 2,1 qu2 ˜ P˜ Z1 

 qu1 2,1 , 2,1 qu2 ˜ P˜ Z1  qu1 2, 2 , 2,1 qu2 ˜ P˜ Z1 

щая стратегию P i , такая, что в ней партия Z приобретает строго положительную вероятность. Определение 6.10. ИМ X i j игрока i называется существенным

 qu1 1,1 , 2, 2 qu2 ˜ P˜ Z1  qu1 1, 2 , 2, 2 qu2 ˜ P˜ Z1 

 qu1 2,1 , 2, 2 qu2 ˜ P˜ Z1  qu1 2, 2 , 2, 2 qu2 ˜ P˜ Z1

для P i , если хотя бы одна позиция x  X i j является возможной для P i .

0 ˜ 0,5  0,25 0 ; PP Z 2 0 ˜ 0,5  0,25 0 ;

Множество возможных для P i позиций обозначим через Poos P i ,

PP Z 3 0 ˜ 0,25  0 0 ;

а множество существенных для P i ИМ – через Rel P i .

PP Z 4 0 ˜ 0,25  0 0 ;

Пример 6.5. Так, в примере 6.3 Poos P1 ˜

^x1, x4 , x5 , x11, x13`, Rel P1 ˜ ^^x1`, ^x2 , x3 , x4 , x5 ``, Poos P 2 ˜ ^y2 `, Rel P 2 ˜ ^^y2 ``.

PP Z 6 1 2 ˜ 0,5  0,25 3 8 ;

Теорема 6.1. Для того чтобы партия Z имела строго положительную вероятность в данной ситуации P, необходимо и достаточно, чтобы она была возможна для всех стратегий P1 ,…, P n , входящих в данную ситуацию. Доказать! Таким образом, произвели нормализацию игры, т. е. вернулись к игре в нормальной форме

PP Z 5 1 2 ˜ 0,5  0,25 3 8 ; PP Z 7 1 2 ˜ 0,25  0 1 8;

PP Z8 1 2 ˜ 0,25  0 1 8. Лемма 6.2. Обозначим через PP  x вероятность реализации позиции x в ситуации P. Тогда имеет место формула PP Z

где PP  x – вероятность реализации окончательной позиции x в ситуации P – вычисляется по формуле (6.1). Пример 6.4. В примере 6.3

¦

^u ˜ : xPoos ui ˜ , i

1,n

`

qu1 ... qun

n

–

¦

i 1 ^ ui : xPoos ui `

qui .

(6.1)

Математическое ожидание выигрыша Ei P игрока i в каждой ситуации P Ei P ¦ Ki x PP x , (6.2) x X n 1

74

G

N , P1 , ..., Pn , K1 P , ..., K n P ,

где n – число игроков; Pi

^Pi ` – множество смешанных стратегий i-гоо

игрока, а K1 P , ..., K n P – функции выигрыша. Замечание 6.4. В случае АИ можно искать решение МИ игры в тех же терминах, что и ранее, например, NE: 75

K i P t K i P || P i  i , P i  Pi . Определение 6.11. Игра, в которой ИМ состоит из одного элемента, называется игрой с полной информацией (ПИ). Замечание 6.5. В игре с ПИ игрок, совершающий ход, знает всю предысторию. 6.3. РЕШЕНИЕ ИГР НА ОПТИМАЛЬНОСТЬ

альтернативы из множества ^1, 2`, затем игрок 1, забывая свой выбор и не зная выбора противника, делает следующий ход. На этом игра прекращается, и игрок 1 получает какой-либо выигрыш. Игрок 2 получает тот же выигрыш с противоположным знаком. Игра происходит на графе Г  X , F , представленном на рис. 6.8. Находясь в узлах x2 , x3 , x4 , x5 (на 3-м ходе игры), игрок 1 не может определить, в какой вершине он находится, так как все вершины равнозначны, но, зная очередность хода (3-й ход), он может быть уверен, что не находится в узле x1 .

–1

3

–4

2

1

2

5

х на начальном шаге, а значение D 2 включает выбор любой из четырех вершин на 3-м шаге и одинаково во всех позициях x2 , x3 , x4 , x5 , поэтому выбор числа D 2 оказывается функцией множества и может быть записан

Рассмотрим классические примеры многошаговых игр с неполной информацией [6]. Пример 6.6. Рассмотрим АИ. Пусть игрок 1 имеет в начальной позиции две стратегии ^1, 2`, игрок 2, зная выбор игрока 1, делает выбор

–2

Объединяя узлы x2 , x3 , x4 , x5 в одно множество, мы иллюстрируем факт их неразличимости для игрока 1. Таким образом, стратегия игрока 1 – это вектор-функция ИМ D1 , D 2 , D1 , D 2  ^1, 2`, где D1 – выбор

2

2

как u^x2 , x3 , x4 , x5 ` D 2 . ИМ игрока 2 не изменилось, поэтому множество его чистых стратегий то же, что и в примере 6.6, т. е. оно состоит из четырех векторов: 1, 1 , 1, 2 , 2, 1 , 2, 2 . В данной игре у обоих игроков по четыре стратегии, и матрица игры имеет вид

1,1 § ¨ 1, 2 ¨ 2,1 ¨ ¨ 2, 2 ¨©

1

x3

x2 1

2

2

II

1

y1

1

1

I

x1 Рис. 6.8 76

2

2

x5

x4 y2

2

II

2 1 5

2 1 2

3 4 5

2

6

2

5

6

5

3· ¸  4¸ 2¸ ¸ 6 ¸¹ 6

2 4 max min 2

2,

2

min max 5

6

где v 1

1,1 1, 2 2,1 2, 2

2 ; v 5 , а следовательно, нет ситуации NE в чистых стратегиях. Найдем решение этой игры:

I

1,1 § ¨ 1, 2 ¨ 2,1 ¨ ¨ 2, 2 ¨©

1,1 1, 2 2,1 2, 2 2 1 5

2 1 2

3 4 5

2

6

2

3· ¸  4¸ 2¸ ¸ 6 ¸¹

 доминируются 77

½ ¾ доминируются . ¿

Таким образом, получаем новую матрицу K

1,1,1,1,1 §  2 ¨ 1,1, 2,1,1 ¨  2 1, 2 ,1,1,1 ¨  1 ¨ 1, 2 , 2,1,1 ¨  1 2 ,1,1,1,1 ¨¨ 5 2 ,1,1,1, 2 ¨ 5 2 ,1,1, 2,1 ¨¨ 2 2 ,1,1, 2, 2 ¨© 2

1,1 1, 2 [ 1 [

 2,1  2, 2

§ 5 2· ¨¨ ¸¸ . © 2 6¹

Найдем ситуацию NE в смешанных стратегиях, решая систему

­5[  21  [ v ; ® ¯2[  61  [ v ;

3[  2 7[

 4[  6 ;

4 Ÿ [

4 7; 1 [

3 7; v

26 7 .

Поскольку матрица симметричная, то решение системы относительно переменной K будет точно таким же, следовательно, значение игры v 26 7 , оптимальная смешанная стратегия игрока 1 есть вектор

0, 0, 4 7 , 3 7 , а 4 7 , 3 7 , 0, 0 .

оптимальная смешанная стратегия игрока 2 равна

Заметим, что гарантированный выигрыш игрока 1 уменьшается по сравнению с гарантированным выигрышем того же игрока в игре с ПИ, происходящей на этом же графе. Отметим также, что здесь размер матрицы 4 u 4 , в то время как в игре с ПИ – 32 u 4 . Таким образом, уменьшение доступной информации уменьшает размер матрицы выигрышей, что облегчает решение самой игры, но при этом уменьшается и выигрыш. Пример 6.7. Изменим информационные условия примера 6.6 (рис. 6.9). Делая первый ход, игрок 1 выбирает число из множества ^1, 2`; второй ход делает игрок 2, который, не зная выбора игрока 1, выбирает число из множества ^1, 2`. Далее, совершая 3-й ход, игрок 1 выбирает число из множества ^1, 2`, зная выбор игрока 2 и помня свой выбор на первом шаге. Множества стратегий игрока 1 и игрока 2 имеют соответственно вид u1 ˜ ^D1, D 2 , D 3 , D 4 , D 5 `, u 2 ˜ E1 . Составим матрицу игры. Затем, исключив из нее одинаковые строки, получим следующую матрицу:

78

2

1

1 K

3 · ¸  4¸  3 ¸ ¸  4¸  , 2 ¸ ¸ 6 ¸ ¸ 2 ¸ 6 ¹¸ 

где знак – означает, что стратегия доминируется. Следовательно, решение существует в чистых стратегиях D 2 , 1, 1, 1, 2 , E 1;

2 , 1, 2 , 1, 2 , E 2 , 2 , 1, 1, 2 , E 2 , 2 , 2 , 1, 2 , E

D D D –2

–1

3

–4

1

2

1

2

I

x2 1

y1

1.

5

2 1

x3

I

1; 1;

2

x4

I

2

1

1

x1

I

y2

2

6 1

2

I

x5

2

II

2

Рис. 6.9

Пример 6.8. Пусть игрок 1 делает выбор из множества альтернатив ^1, 2`, игрок 2 не знает выбора игрока 1 и делает выбор 1 или 2. Далее, совершая ход, игрок 1 не знает выбора игрока 2, но помнит свой. Тогда дерево будет иметь вид (рис. 6.10) 79

–2 1

–1

3

–4

2

1

2

x4 1

5

2 1

2

x5

x6

2

1

x2

x3

2

6 1

2

x7 2

Пример 6.9. Пусть игрок 1 на 2-м шаге забывает о том, что выбрал сам, но знает о том, что выбрал противник (рис. 6.11). Здесь стратегия игрока 1 u1 $ D1, D 2 , D 3 , где D1 ^1, 2`; D 2 D 2  x 4 , x5 ^1, 2`; D 3 D 3  x6 , x7 ^1, 2`, и стратегии игрока 2 – u 2 $ E1, где E1 ^1, 2`. –2 1

1

2

x1

–1

3

–4

2

1

x2

I

D 2  x4 , x5

u2 $ E1 , где

1

1, 1, 1 §  2 ¨ 1, 1, 2 ¨  2 1, 2 , 1 ¨  1 ¨ 1, 2 , 2 ¨  1 2 , 1, 1 ¨¨ 5 2 , 1 , 2 ¨ 2 2 , 2 , 1 ¨¨ 5 2 , 2 , 2 ¨© 2

2 3 · ¸ 3 ¸  4¸  ¸  4¸  . 2 ¸ ¸ 6 ¸ ¸ 2 ¸ 6 ¹¸

Решение этой МИ было получено в примере 6.6. Таким образом, значение игры v 26 7 , оптимальная смешанная стратегия игрока 1 есть вектор 0, 0, 0, 0, 0, 0, 4 7 , 3 7 , а оптимальная смешанная стратегия игрока 2 равна 4 7 , 3 7 . 80

2

2

1

1

6 2

x5 I 2

y2

II

2

x1

I

Рис. 6.11

игра эквивалентна МИ размерностью

23 u 2 8 u 2 . МИ имеет вид

2

x4 I 1

y1

D1, D 2 , D3 , где D1 ^1, 2`, D 3  x6 , x7 ^1, 2`, а стратегия игрока 2 –

^1, 2`, D3 E1 ^1, 2`. Эта

1

2

Стратегия игрока 1 имеет вид u1 $

D2

2

I

1

Рис. 6.10

x3

5

Решить самостоятельно. Пример 6.10. Пусть игрок 1 на 2-м шаге не знает, что выбрал игрок 2, и забыл свой выбор, а игрок 2 не знает, что выбрал игрок 1 на 1-м шаге. Выигрыш определяется так же, как в игре из примера 6.6 (рис. 6.12). –2

–1

1

2 x4

3 1

–4

5

2

2

2

1

2

1

x5

1

x6 2

1

x2

6 2

x7 2

x3 1

2 x1 Рис. 6.12

Здесь множество стратегий игрока 1 u1 $ D1 ,D 2 , где D1 ^1, 2`; D 2 D 2  x 4 , x5 , x6 , x7 ^1, 2` , а множество стратегий игрока 2 – u 2 $ E1, где E1 ^1, 2`. Тогда игра в нормальной форме имеет матрицу размера 4 u 2 : 81

1 2 1.1 §  2 3 · ¨ ¸ 1.2 ¨  1  4 ¸ 2.1 ¨¨ 5 2 ¸¸ 2.2 ¨© 2 6 ¸¹ 5 6

2 4 2

2,

2

min max где v

max min

5

2 ; v 5 , а следовательно, нет ситуации NE в чистых стратегиях. Найдем решение этой игры: 1 2

1.1 §  2 3 · ¸ ¨ 1.2 ¨  1  4 ¸ 2.1 ¨¨ 5 2 ¸¸ 2.2 ©¨ 2 6 ¹¸

½ ¾ доминируются ; ¿

v

соответственно. Функция K1  x, y, z определяется таким образом:

K1 1, 1, 1 1,

K1 1, 2 , 1 7,

K1 1, 1, 2 3, K1 1, 2 , 2 9 ,

 2,1  2, 2

K1 2 , 1, 2 1, K1 2 , 2 , 2 7.

1K

1 2

получаем новую матрицу: 1[

заходит к B и предлагает ему сделать выбор из множества ^1, 2`. Если жее игрок 1 выбирает 2, то посредник предлагает игроку B сделать выбор первому. После того как три числа выбраны, игрок 1 выигрывает величину K1  x, y, z , где x, y, z – выборы игрока 1 и членов команды 2 (A и B)

K1 2 , 1, 1 5, K1 2 , 2 , 1 6 , K

[

ют, какой ход совершают. Можно построить игру, в которой игроки проявляют большее незнание. Рассмотрим АИ двух лиц, в которой игрок 1 – один человек, а игрок 2 – команда из двух человек: A и B. Все трое изолированы друг от друга (находятся в изолированных помещениях) и не могут общаться между собой. В начале игры посредник входит в помещение, где находится игрок 1, и предлагает ему выбрать число из множества ^1, 2`. Если игрок 1 выбирает 1, то посредник заходит сначала в помещение, где находится A, и предлагает ему выбрать число из множества ^1, 2`, затем

§ 5 2· ¨¨ ¸¸ . © 2 6¹

Решение этой МИ было получено в примере 6.6: значение игры 26 7 , оптимальная смешанная стратегия игрока 1 есть вектор

0, 0, 0, 0, 0, 0, 4 7 , 3 7 , а оптимальная смешанная стратегия игрока 2 равна 4 7 , 3 7 .

Из правил игры следует, что когда одному из членов команды A и B предлагается сделать выбор, он не знает, совершает ли он выбор на 2-м или на 3-м шаге игры. Структура игры изображена на рис. 6.13. Таким образом, ИМ игрока 2 содержат вершины разного уровня, что соответствует незнанию номера хода в игре. Здесь игрок 1 имеет 2 стратегии. Игрок 2 имеет 4 стратегии, они состоят из всевозможных комбинаций выборов членов команды A и B, т. е. его стратегии суть пары 1, 1 , 1, 2 ,

2, 1 , 2, 2 . Для того чтобы понять, как определяются элементы матрицы выигрышей, рассмотрим ситуацию ^2, 2, 1 `. Так как игрок 1 выбрал 2,

Замечание 6.6. В этой игре значение оказалось таким же, как и в игре из примера 6.6, т. е. оказалось, что ухудшение информационных условий игрока 2 не улучшило выигрыш игрока 1. Это обстоятельство в данном случае носит случайный характер и вызвано спецификой функции выигрыша. Пример 6.11. В предыдущем примере игроки не различают позиции, находящиеся на одном уровне дерева игры, однако они все-таки зна-

то посредник идет к B, который согласно стратегии 2, 1 выбирает 1. Далее он идет к A, который выбирает 2. Таким образом, в ситуации ^2, 2, 1 ` выигрыш K1 2, 1, 2 1.

82

83

1

3

1

2

7 1

9

5

1

2

1

2

6 1

а

7 2

1

II 1

2

1

б

2

–1 1

2

1

–1 1 1

3

2

2

Рис. 6.13

–1 1

3

1 1 2 3

1

–1 2

1 3

3

1

–1 1

2

1 3

2

2

1

2

3

1

1

Матрица выигрышей для игры в нормальной форме имеет вид

1

1 2 3

2

2

–1 1

2 1

I

1

2

II 1

1 2

Рис. 6.14

1,1 1,2  2,1  2,2

1 ª1 2 «¬5

3

7

6

1

9º . 7»¼

Значение игры v 17 5 , а оптимальные смешанные стратегии игроков 1 и 2 соответственно x* 2 5 , 3 5 , y * 3 5 , 0, 2 5 , 0 . Пример 6.12. Номера игроков, имеющих право хода, – 1, 2, 3. Игрок 1 выбирает одну из трех цифр – 1, 2 или 3. Затем игрок 2, не зная выбора игрока 1, также выбирает одну из трех цифр – 1, 2, 3. Если сумма выбранных цифр четная, то первый игрок выигрывает у второго 1. Если сумма – нечетная, то, наоборот, выигрывает второй. Дерево соответствующей игры изображено на рис. 6.14, а. На рис. 6.14, б изображена модификация этой игры, в которой игроку 2 становится известно, что либо игрок 1 выбрал цифру 2, либо, напротив, что цифру 2 он не выбрал. Замечание 6.7. Заметим, что в многошаговых играх с ПИ (теорема 2.1) существует ситуация NE в классе чистых стратегий, в случае многошаговых АИ – просто ситуация равновесия в чистых стратегиях, а в играх с неполной информацией (в большинстве случаев) ситуации NE в чистых стратегиях не существует. Однако существует равновесие в смешанных стратегиях. Замечание 6.8. Если ИМ состоит из одного элемента (т. е. если игрок все знает), то всегда существует NE в чистых стратегиях. 84

6.4. САМОСТОЯТЕЛЬНАЯ РАБОТА № 7 Дать словесное описание ИМ игроков, найти оптимальное решение позиционной игры и определить возможные позиции, партии и существенные ИМ при использовании соответствующих оптимальных стратегий (см. прил. 2).

85

Занятие № 7.

ИГРЫ С ПОЛНОЙ И НЕПОЛНОЙ ПАМЯТЬЮ. СТРАТЕГИИ ПОВЕДЕНИЯ

–2

7.1. ИГРЫ С ПОЛНОЙ И НЕПОЛНОЙ ПАМЯТЬЮ

–1

1

2

–4 1

I x2

Определение 7.1. Игра G называется игрой с полной памятью (ПП)

партия в G. Пусть x  X i j – последняя позиция в пути Z, в которой ходит игрок i, и пусть он выбирает в x дугу l  Z . Положим, чтоо Если в Z нет позиций из X i , то через Ti Z обозначим множество о всех чистых стратегий игрока i. Тогда партия Z реализуется в тех и только тех ситуациях u ˜ u1 ˜ ,, un ˜ , для которых ui  Ti Z . Пример 7.1. Рассмотрим игру с неполной памятью (рис. 7.1). Здесь игрок 1 забывает, что он выбрал на первом шаге. В ИМ В возможна позиция x2 , так как существует стратегия 1-гоо игрока, выбирающая в ИМ А левую альтернативу, при которой эта позиция возможна. А позиция x4 при этой же стратегии невозможна, хотяя другие две позиции возможны. При ПП все позиции данного ИМ при одной и той же стратегии i-го игрока возможны. Следовательно, игра, представленная на рис. 7.1, не является игрой с ПП. Покажем, что в случае ПП у всех игроков многошаговая игра с неполной информацией имеет ситуацию равновесия в стратегиях поведения. 86

1 B

x3

2 I

2

6 x5 2

1

x4

I

1 y1

2 y2

II

j

x  Poos ui . Из определения ПП следует, что если ИМ существенно при данной стратегии, т. е. если хотя бы одна его позиция возможна при данной стратегии, то и все его позиции возможны при данной стратегии. Термин «ПП» указывает на то, что в любом своем ИМ i-й игрок может точно восстановить, какие альтернативы он выбирал во всех своих предыдущих ходах. Игра с ПП для всех игроков превращается в игру с ПИ, если все ее ИМ содержат по одной вершине. Лемма 7.1. Пусть G – игра с ПП для всех игроков, Z – некоторая

^ui : X ij  Rel ui , ui X ij l`.

2

2

ИМ, и вершины x из условий X i  Rel ui и x  X i следует, чтоо

Ti Z

5

2 I

1

для i-го игрока, если для любых стратегии ui ˜ , ИМ X i j , где j – номер j

3

1

2

x1

I

A

Рис. 7.1 7.2. СТРАТЕГИИ ПОВЕДЕНИЯ В общем случае строить стратегию не как заранее фиксированное правило выбора во всех ИМ, а формировать ее по мере попадания в соответствующее ИМ нельзя. Рассмотрим класс игр с неполной информацией, где такое упрощение возможно. Введем понятие стратегии поведения. Определение 7.2. Под стратегией поведения Ei игрока i будем понимать правило, которое каждому ИМ X i j  Ak игрока i ставит в со-





ответствие систему из k чисел b X i j , l t 0, l

¦ bX ij , l

1, k , j – номер ИМ игрока i:

1,

l

т. е. E i игрока i.

­­ ° j ®®b X i , l , l °¯¯







1, k



¦b X i ,l j

l



m

½ 1¾ ¿j

½ ° где m – количество ИМ ¾, 1° ¿



Числа b X i j , l могут интерпретироваться как вероятности выбора альтернативы l в ИМ X i j  Ak , каждая позиция которого содержит ровно k альтернатив. 87

Пример 7.2. Рассмотрим АИ, где ИМ X i j  A2 , i 1, 2 , j 1, 3 для

Здесь произведение берется по всем X i j и l таким, что X i j  Z z ‡ ,

игрока 1, и j 1 для игрока 2. Тогда для стратегии поведения E1 имеем систему из шести чисел (рис. 7.2):

и выбор в точке X i j  Z альтернативы с номером l приводит в позицию, принадлежащую пути Z. Ожидаемый выигрыш Ei E в игре G для ситуации E E1,..., E n в стратегиях поведения определяется как математическое ожидание





 p , b X , 2 1  p , bX ,1 p , bX , 2 1  p , а для стратегии поведения E 2 – из двух: b X 21 ,1 p , b X 21 , 2 1  p . b X 11 ,1



p1 , b X 11 , 2



1  p1 , b X 12 ,1

3 1

3 1

3

2 1

2

2

3

Стратегии поведения зависят только от ИМ. Вероятность выбора чистой стратегии u1 ˜

1, 2 , 1

q1 u1

p1 1  p2 p3 . Смешанную стратегию P1 дает вектор вероятностей

^q u , j 1

j

1, 2 `, т. е. из стратегий поведения мы строим смешанную 3

стратегию. Обратное не всегда возможно, поскольку классы игр не эквивалентны, что, однако, верно при игре с ПП (см. далее теорему Куна). –2 p2

–1

3

1  p2

–4

5

1  p2

p2

x4

x5

1

2

2 1  p3

p3

I

6 p3

x6

x7

1

2

y2

y1 p1

2

X i  Z z‡ lZ

некоторую стратегию поведения Ei . Определение 7.3. Стратегией поведения Ei , соответствующей

^ `

смешанной стратегии P i qui игрока i, называется стратегия поведения, определенная следующим образом: если X i j  Rel P i , тоо



­ u : X j Rel u , u § X j · l ½ ® i i i i¨ i ¸ ¾ ¹ ¿ © ¯

¦

­ u : X j Rel u ½ ® i i i¾ ¯ ¿

qui

qui ;

лить произвольным, отличным от (7.2), образом. (В случае X i j  Rel P i знаменатель в выражении (7.2) обращается в нуль.) Для определенности будем полагать, что

(7.1)



b X ij , l



¦j

qui .

^ui : ui X i l `

Лемма 7.2. Пусть E i – стратегия поведения игрока i, а P i смешанная стратегия, определяемая формулой qui

–j bX i j , ui X i j . Xi

Тогда E i – стратегия поведения, соответствующая P i . 88

(7.2)

деесли X i j  Rel P i , то на множестве X i j стратегию Ei можно опреде-

II

Утверждение 7.1. Любой набор E E1 ,..., E n стратегий поведения для n игроков определяет вероятностное распределение на партиях игры и окончательных позициях следующим образом:

– bX i j , l .

В игре с ПП каждой смешанной стратегии P i можно сопоставить



I

j

i 1, N ,

где Z x – партия, завершающаяся позицией x  X n 1 .

b X ij , l

I

Рис. 7.2

PE Z

¦ K i x PE Z x ,

xX n 1

¦

1  p3

1  p1

x1

Ei E

89

(7.3) {qui } –

Теорема 7.1 (Куна). Пусть E – ситуация в стратегиях поведения, соответствующая ситуации в смешанных стратегиях P в игре G (в которой все позиции имеют по крайней мере две альтернативы). Тогда для того чтобы Ei E Ei P , i 1, n , необходимо и достаточно, чтобы игра G была игрой с ПП для всех игроков. Из теоремы 7.1, в частности, следует, что для нахождения ситуации равновесия в играх с ПП достаточно ограничиться классом стратегий поведения. Пример 7.3. Решим игру из примера 7.2 в стратегиях поведения. Сначала найдем оптимальное решение в смешанных стратегиях. Поскольку рассматриваемая игра – с ПП, то затем найдем стратегии поведения. Смешанная стратегия игрока 2

4/7

3/7

Чистые стратегии игрока 2 Чистые стратегии игрока 1

1

2

0 0

111 112

–2 –2

3 3

0 0

121 122

–1 –1

–4 –4

2/7 3/14

211 212

5 2

2 6

2/7 3/14

221 222

5 2

2 6

Смешанная стратегия игрока 2

Смешанная стратегия игрока 2 Смешанная стратегия игрока 2

0 0

[ 47 1 [ 3 7

K 47

1 K 3 7

Отсюда следует, что смешанные стратегии игроков 1 и 2 такие:

P1

q1,1,1

0 , q1,1, 2 0 , q1, 2,1 0 , q1, 2, 2 0 ,

q2,1,1 2 7 , q2,1, 2 3 14 , q2, 2,1 P2

q1

2 7 , q2, 2, 2 3 14 ;

4 7 , q2 3 7 .

Очевидно, X 11, X 13  Rel P1 , X 12  Rel P1 , X 12  Rel P 2 . Тогда

¦ qu1 1 1 ^ :  Rel u X u1 , u1 X 1 1 ` 0  0  0  0 1 1 bX 11,1 0; qu1 1 ¦ ^u1: X11Rel u1 ` ¦ qu1 1 1 ^u1: X1 Rel u1 , u1 X 1 2 ` 2 7  3 14  2 7  3 14 bX 11, 2 1 ¦ qu1 1 ^u1: X1 Rel u1 ` 2 bX 1 ,1 ¦ qu1 0  0  2 7  3 14 1 2 ; ^u1:u1 X 12 1` bX 12 , 2 ¦2qu1 0  0  2 7  3 14 1 2 ; ^u1 :u1 X1 2` ¦ qu1 3 3 ^  u : X Rel u1 , u1 X 1 1 ` 2 72 7 1 1 bX 13 ,1 2 7  3 14  2 7  3 14 ¦ qu1 ^u1: X 13Rel u1 ` ¦ qu1 3 3 ^ :  Rel u X u1 , u1 X 1 2 ` 3 14  3 14 1 1 bX 13 , 2 2 7  3 14  2 7  3 14 ¦ qu1 3 ^u1: X1 Rel u1 `

Доминируемость

Чистые стратегии игрока 2 Чистые стратегии игрока 1

1

2

(1,1,1); (1,1,2) (1,2,1); (1,2,2) (2,1,1); (2,2,1) (2,1,2); (2,2,2)

–2 –1 5 2

3 –4 2 6

90

Доминируема Доминируема – –





b X 12 ,1

¦ qu1 ^u2 : X 12 Rel u2 , u 2 X 12 1 ` ¦ qu1 1 ^u2 : X 2 Rel u2 ` 91

47 4 73 7

4 7;

1;

4 7;

3 7;

^



b X 12 , 2

`

¦q

7.4. ОДНОВРЕМЕННЫЕ МНОГОШАГОВЫЕ ИГРЫ

u1 u 2 : X 12 Rel u 2 , u 2 X 12

^

 2`

37 4 73 7

¦ qu1 1

^u 2 : X 2 Rel u2 `

3 7.

Проверим, что стратегии поведения найдены верно (рис. 7.3). Ожидаемый выигрыш 16 12 9 80  48  54 5 5  2˜2˜  6˜ 3 ; E 2 E 3 . 49 49 49 49 7 7 Теорема 7.1 о стратегиях поведения в общем случае не дает возможности непосредственно решать многошаговые игры с ПП, однако при простой структуре ИМ она обосновывает вывод функциональных уравнений для значения игры и основанные на этих уравнениях методы нахождения оптимальных стратегий. Наиболее простыми играми с ПП, не считая игр с ПИ, являются так называемые одновременные многошаговые игры. Выведем функциональное уравнение для значения таких игр и рассмотрим несколько примеров [7, 8], где эти уравнения поддаются решению. E1 E 5 ˜

0 –2

0 –1

0 3

0 –4

16/49 5

12/49 2

12/49 2

9/49 6

Одновременная многошаговая игра представляет собой многошаговую АИ, в которой на каждом шаге игры игроки 1 и 2 выбирают свои действия одновременно, т. е. не имея информации о выборе противником позиции в этот момент. После того как выборы сделаны, они становятся известными обоим игрокам, и игроки вновь совершают одновременный выбор и т. д. Условно такую игру будем изображать с помощью графа, имеющего одно из двух представлений (рис. 7.4, а, б). Граф изображает поочередную игру с четным числом ходов, в которой ИМ игрока, совершающего первый ход, являются одноэлементными, а ИМ другого игрока двухэлементными. В такой игре G оба игрока обладают ПП, поэтому в ней согласно теореме 7.1 при отыскании ситуации NE можно ограничиться классом стратегий поведения. а

б

II

II I

1/2

1/2

1/2 x4

x5

2

4/7

4/7

1/2

3/7 x6

I

4/7

3/7

y2

y1 0

x7

1

Рис. 7.3

7.3. САМОСТОЯТЕЛЬНАЯ РАБОТА № 8

I II

I

I II

I

I II

II

II I

I

3/7 II

I

II I

I

II Рис. 7.4

1 x1

I

3/7

4/7 3

II

Пусть в G первым ходит игрок 1. С каждым x  X 1 связывается подыгра G x с той же информационной структурой, что и игра G. Нормальная форма любой конечношаговой АИ с неполной информацией представляет собой МИ, поэтому во всех подыграх G x , x  X 1 (включая игру G

Gx0 ) существует ситуация NE в классе смешанных стратегий.

На примере игр из самостоятельной работы № 7 определить, является ли представленная игра игрой с ПП, и если да, то найти ситуацию равновесия в стратегиях поведения и ожидаемый выигрыш.

Согласно теореме 7.1 такая ситуация NE существует и в классе стратегий поведения, и значения игры (т. е. значения функции выигрыша в си-

92

93

туации равновесия в классе смешанных стратегий и в классе стратегий поведения) равны между собой. Обозначим значение игры G x через v x , x  X 1 и составим функциональные уравнения для v x . Для каждого x  X 1 следующая позиция xc , в которой ходит игрок 1 (если таковая существует), принадлежит множеству Fx2 . Позиция x c реализуется в результате двух последовательных выборов: игроком 1 – дуги, инцидентной к вершине x, и игроком 2 – дуги в позициях y  Fx , образующих ИМ игрока 2, поэтому можно считать, что позиция xc получается в результате отображения Tx , зависящего от выборов D, E игроков 1 и 2, т. е. x c Tx D, E . Так как число различных альтернатив D и E конечно, то можно рассмоттреть для каждого x  X 1 МИ с матрицей выигрышей Ax E*I  x

^v>D, E@`. Пусть

^bI* x, D `, E*II x ^bII* x, E ` – оптимальные смешанные страте-

гии в игре с матрицей Ax . Тогда имеет место следующая далее теоремаа о структуре оптимальных стратегий в игре Gx . Теорема 7.2. В игре G оптимальная стратегия поведения игрока 1 в точке x (каждое ИМ игрока 1 в игре G состоит из одной позиции x  X 1 ) предписывает каждой альтернативе D вероятность в соответствии со смешанной оптимальной стратегией игрока 1 в МИ Ax , т. е. b1  x, D bI*  x, D .

^ 

Оптимальная стратегия поведения b2 X 2j , E

` игрока 2 в игре G пред-

с граничным условием v x x X 3



b2 X 2j , E где x

Fy1 ,

если



bII*  x, E ,

y  X 2j .

(7.5)

(Здесь Val A – значение игры с матрицей А.) Пример 7.4. (Игра инспектирования). Игрок Е (нарушитель) хочет совершить некоторое запрещенное действие. Имеется N периодов времени, в которые это действие может быть осуществлено. Игрок P (инспектор), желающий предотвратить это действие, может провести только одну инспекцию в любой из этих периодов времени. Обозначим такую N-шаговую игру через GN . В первом периоде каждый игрок имеет две альтернативы (рис. 7.5). Игрок E может предпринимать действие или не предпринимать его; игрок P может инспектировать или не инспектировать. Если игрок E действует и игрок P инспектирует, то игра заканчивается и выигрыш игрокаа E равен –1. Если игрок E действует, а игрок P не инспектирует, то игра заканчивается и выигрыш равен 1. Если игрок E не действует, а игрок P инспектирует, то выигрыш равен нулю. Если игрок E не действует,, а игрок P не инспектирует, то переходят к следующему шагу игры, который отличается от предыдущего только тем, что до конца игры остается меньшее количество времени, т. е. попадают в подыгру GN 1 . Следовательно, матрица для 1-го шага игры выглядит следующим образом:

Н

–1

1

писывает каждой альтернативе E вероятность в соответствии с оптимальной смешанной стратегией игрока 2 в игре с матрицей Ax , т. е.

H  x .

И Д НД 1 º ª 1 «0 v » N 1 ¼ ¬

Д НД

0 –

+

(7.6)

–

+ Р

Р +

–

Значение игры удовлетворяет следующему функциональному уравнению: (7.4) v x Val^ v>Tx D, E @ `, x  X 1 ,

Рис. 7.5

94

95

Е

ПРИЛОЖЕНИЕ 1

Уравнение (7.4) в этом случае принимает вид 1 º ª 1 Val« ». ¬ 0 v N 1 ¼

vN

(7.7)

Здесь v x одинаково для всех позиций игры одного уровня и зависит

Постановка задачи. Дана игра N лиц, разделенных на две коалиции S и N \ S , каждая из которых действует как один игрок. Для каждого игрока определено множество стратегий

только от числа периодов до конца игры, поэтому вместо v x записано

v N . Найдем ситуацию равновесия в смешанных стратегиях в игре

На множестве стратегий

i

x

1, mi , i 1, N .

j1 j2 jn 1 , x2 , , xn

ситуацию игры.

определены выигрыши игроков K i  x

– Xi

для всех i  N . Выигрыш коалиции S  N \ S равен сумме выигрышей

v N 1  1 ,  v N 1  3 которое вместе с начальным условием

(7.8)

игроков из коалиции S  N \ S . Тогда имеем матричную модель выигрышей игроков из коалиции S размерности

– mi u – mi

iS

0

1 . Получим новое рекуррентное уравнение t N vN  1

условии t1 1. Это уравнение имеет очевидное решение t N откуда имеем

(табл. 1).

iN \ S

(7.9)

Таблица 1

определяет v N . Преобразуем уравнение (7.8) с помощью подстановки tN

ji

iN

vN

§ 1 1· Val¨¨ ¸¸ © 0 0¹

i

Обозначим через вектор x

1 º [ ª 1 « 0 v », 1– [¬ N 1 ¼ откуда получаем рекуррентное уравнение

v1

^x `, где j

Xi

1 t N 1  при 2

1 ª 1 º игры. Действительно, матрица игры (7.7) принимает вид « », ¬ 1 ( N  2) / N ¼

Количество столбцов mi i  N \ S

  x1S 1 ,, x1N    xSmS11 ,, x Nm N



The strategies of coalition N \ S

i

Коли 1 ­ 1 чество ° x1 ,, x S строк ®   ° mi ¯ x1m1 ,, x SmS



– iS





Sj







^K x ,, x ` ^K x ,, x `

( N  1) / 2,

N 1 . vN (7.10) N 1 Теперь можно вычислить оптимальные стратегии на каждом шаге

–

The strategies of coalition S

1 1

1 N

1 1

i 1: S

1 N

… …



…

…

…

…

S j S

…

^K x ,, x ` ^K x ,, x ` i

Sj

m1 1

m1 1

mN N

mN N

i 1: S S j S

оптимальные стратегии поведения таковы: b1N

b2N

N · § 1 , ¸. ¨ © N  1 N  1¹

96

Аналогично определяется модель для выигрышей игроков из коалиции N \ S (табл. 2).

97

NE в смешанных стратегиях в игре G  A, B с вектором равновесных вы-

Таблица 2 Количество столбцов mi iS 

 x11 ,, x1S    x1m1 ,, xSm S



The strategies of coalition N \ S

^ 

Ki x11,, x1N

Коли -



–

i N \ S

^ 







` `

i S 1: N

…





…

K S j x11,, x1N S j N \S



1 ­ 1 чество ° x S 1 ,, x N строк ®   ° mi ¯ xSmS11 ,, x Nm N

игрышей v1, v2 . Будем рассматривать тот случай, когда матрицы из табл. 1–2

–

The strategies of coalition S

…

^  ^K x

K i x1m1 ,, xNm N

…

Sj

Эта матрица имеет размерность

~ A

…

…

…



` `

mN m1 1 ,, x N

.

i S 1: N S j N \S

Алгоритм решения задачи 1. Решим коалиционную игру, т. е. найдем ситуацию равновесия по Нэшу (NE) в смешанных стратегиях, используя следующую далее теорему 1 [9]. Теорема 1. Пусть G  A, B – биматричная m u m -игра и матрицы А, В – невырожденные. Если игра G  A, B имеет вполне смешанную ситуацию равновесия, то она единственная и вычисляется по формулам

где









v1 1 uA1u ; v2 1 uB 1u ; u

1, ,1 .

Обратно, если для векторов x , y  R m , определяемых равенствами x

v2uB 1, y

ует v1 A1u , справедливо x t 0, y t 0 , то пара  x, y образует 98

m

i 1

m



· ¸ ¸ ¸, ¸ ¸ ¸ ¹



¦ K i x1m1 ,, x S S , x S S11 ,, x N N



¦ K i x11 ,, x1S , x S S11 ,, x N N

~ ~ dim A dim B

S

m

m

m

i 1

N

m

i S 1

m



· ¸ ¸ ¸, ¸ ¸ ¸ ¹

¦ K i x1m1 ,, xSmS , x SmS11 ,, x NmN N

i S 1

– mi u – mi , iS

iN \ S

можно свести к квадратным матрицам A и B таким, что о det A z 0, det B z 0 . Ситуаций NE в игре может быть много [10], тогда решение коалиционной игры определяется неоднозначно. 2. Вычислим значение игры в смешанных стратегиях в ситуации NE: E  x , y >vS , v N \ S @, где

y

v1 A 1u ,

S



iS

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

v 2 uB 1 ; y



– mi u – mi .

iN \ S

x





~ B

¦ K i x11 ,, x1S , x S S11 ,, x N N



§ S ¨ ¦ K i x11 , , x1S , x1S 1 , , x1N  ¨ i1 ¨   ¨S ¨ ¦ K i x1m1 , , x SmS , x1S 1 , , x1N  ¨i 1 © § N ¨ ¦ K i x11 , , x1S , x1S 1 , , x1N  ¨ i S 1 ¨   ¨ N ¨ ¦ K i x1m1 , , x SmS , x1S 1 , , x1N  ¨ i S 1 ©

v S

^K j `jX

¦ ¦

aij [i K j ; iX S jX N \ S N \S

v N \ S

¦ ¦

bij [i K j , iX S jX N \ S

. Можно показать, что vS t

¦ vi , где vi

iS

x

^[i `iX S ,

– максимальль-

ный гарантированный выигрыш i-го игрока, i  S , при условии, что игроки из коалиции N \ S используют смешанную стратегию в ситуации NE. Это следует из леммы о супераддитивности характеристической функции, определенной как максимальный гарантированный выигрыш коалиции S. 99

3. В занятии 5 приведены определения 5.9 и 5.10 PMS-вектора (дележа) в чистых и смешанных стратегиях. Найдем PMS-вектор в смешанных стратегиях как вектор Шепли значения игры в смешанных стратегиях в ситуации NE: E  x , y >vS , v N \ S @. 4. Выигрыши коалиций S и N \ S , имеющие положительную веероятность в ситуации NE, разделим пропорционально PMS-вектору:

PMS j S

O j S

¦ PMSi S

PMS j  N \ S

, O j N \ S

iS

¦ PMSi N \ S

.

iN \ S

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

K 3 7 1 K 4 7 1 2

[ 1 [

I

1

II

1

III

1

The payoffs I

4

II

2

The payoffs The NE strategies The coalitions of coalitions I, II , III I, II III I II III III 1

1,1 ,1

6

1 1

1

1

2

1

2

2

1,1 , 2

3

2

1

2

1

3

1

5

1, 2 ,1

4

5

1

2

2

5

1

3

1, 2 , 2

6

3

2

1

1

5

3

1

2,1 ,1

8

1

2

1

2

1

2

2

2,1 , 2

3

2

2

2

1

0

4

3

2, 2 ,1

4

3

2

2

2

0

4

2

2, 2 , 2

4

2

1

y

1

2

y

2

1

y

2

2

y

§3· ¨ ¸ ¨7¸ ¨¨ 4 ¸¸ ©7¹ §3· ¨ ¸ ¨7¸ ¨¨ 4 ¸¸ ©7¹ §3· ¨ ¸ ¨7¸ ¨¨ 4 ¸¸ ©7¹ §3· ¨ ¸ ¨7¸ ¨¨ 4 ¸¸ ©7¹

II

III

2 7

2

1

1

6 3 7

3 7

1

4 7

4

2

3 7

2

1 4 7

2

5 7

0

2

100

uA 1u

4 7

1. Составим и решим коалиционную игру, т. е. найдем NE в смешанных стратегиях в игре:

>3, 2@ >4, 2@ >6, 3@ >3, 2@.

1 §A E · E

 A  ·¸ §¨ ¨ 4 6 1 0¸ 1 0  1 12 1 6 ¸ ¸ oo ¨ S :¨ ; ¨ 0 1 2 9 1 9¸ ¨8 3 0 1¸ ¨ ¸ ¨ ¸ © ¹ © ¹

The NE payoffs I

 1, 1  2, 2

Очевидно, что первая строка доминируется последней, а вторая – третьей. Найдем обратную матрицу A1, число v1 и вектор y:

Таблица 3 The strategies

>6, 1@ >4, 3@ 1 3  1, 2 >4, 5@ 2 3  2, 1 >8, 1@

0 0

1 1 §¨¨

 1 12

© 29

y

v1 A 1u

1 6 ·§1· ¸¨ ¸  1 9 ¸¹¨©1¸¹

¦ aij ij



7 ; v1 36

36 §  1 12 1 6 ·§1· ¨ ¸¨ ¸ 7 ¨© 2 9  1 9 ¹¸¨©1¸¹

1 uA 1u

§3 ¨¨ ©4



36 ; 7



7 ; 3

7· ¸. 7 ¸¹

Найдем обратную матрицу B 1, число v2 и вектор x: B 1  · §B E · E

 §¨ ¸ ¨5 3 1 0¸ 1 0 2 7  3 7¸ ¨ ¸ oo N \ S :¨ ; ¨ 0 1 1 7 5 7 ¸ ¨1 2 0 1 ¸ ¨ ¸ ¨ ¸ © ¹ © ¹

uB 1u

2 7  3 7 ·§1· ¸¸¨¨ ¸¸ ©  1 7 5 7 ¹©1¹

1 1 §¨¨ x

следовательно, y

v 2 uB 1

3 7

¦ bij ij

 1 12 1 6 · 7 1 1 §¨¨ ¸¸ 3 © 2 9 1 9¹ 4 7 ; x

0 101



3 ; v2 7

1 uB 1u

§1 3 · ¨¨ ¸¸ ; © 2 3¹

0 1 3 2 3 .

Тогда вероятность реализации выигрыша коалиций S и N \ S в ситуации NE в смешанных стратегиях при выборе игроками своих чистых стратегий имеет вид K1

K2

[1

0

0

[2

0 1 7 2 7

0

[3 [4

4 8

21

Sh 1 Аналогично для i

21

1 >4, 5@  2 >8,1@  4 >6, 3@  8 >3, 2@ ª« 36 , 7 º» ª«5 1 , 2 1 º» . 21 21 7 7 ¬ 7 3 ¼ ¬ 7 3¼ Перепишем табл. 3 в табл. 4, соответствующую табл. 1–2. Комментарий к табл. 4. В табл. 4 справа по горизонтали даны стратегии коалиции N \ S и ее смешанная стратегия y , по вертикали – стратегии коалиции S и ее смешанная стратегия x ва даны выигрыши игроков коалиции и их суммарный выигрыш. E  x, y

Strategies of S

Таблица 4

x 0,00 0,00 0,33 0,67

The strategies of N\S, the payoffs of S y 0,43 0,57 1 S 2 S 1, 1 4 2 6 1 2 3 1, 2 3 1 4 5 1 6 2, 1 5 3 8 1 2 3 2, 2 0 4 4 0 4 4 v1 v2 v1 v2 min 1 3 2 1 2 min 2 0 1 0 1 max 3 2 1 2

2. Разделим значение игры в смешанных стратегиях в ситуации равновесия в соответствии с вектором Шепли (5.9). 102

1 >v^I, II`  v^II`  v^I`@. 2 2 имеем

v^I` 

1 >v^I, II`  v^II`  v^I`@. 2 Найдем гарантированные выигрыши v1 и v2 игроков I и II . Для этого зафиксируем смешанную стратегию игрока III y3 3 7 4 7 . Комментарий к табл. 4 (продолжение). В табл. 4 слева находится математическое ожидание выигрышей игроков коалиции S по смешанной стратегии коалиции N \ S в ситуации NE (далее, в расчетах в скобках учитывается третий элемент – математическое ожидание игрока III ): Sh 2

.

Вычислим значение игры в смешанных стратегиях:

МАТ. ОЖИД. 2,286 2,000 4,143 1,000 2,714 2,429 0,000 4,000 v1 v2 2,286 2,000 0,000 1,000 2,286 2

Коалиция состоит из двух игроков S ^I, II`, следовательно, s 2 . Для i 1 имеем S c ^^I, II`; ^I``. Тогда компонента вектора Шепли для игрока 1 имеет вид

v^II` 

4 3 4 3 4 · § 2 4· §3 vS 1,1  y ¨ ˜ 4  ˜ 1; ˜ 2  ˜ 2 ; ˜ 1  ˜ 2 ¸ ¨ 2 ; 2 ; 1 ¸ ; 7 7 7 7 7 ¹ © 7 7¹ ©7

6· § 1 ¨ 4 ;1; 3 ¸ ; 7¹ © 7 § 5 3 4· ¨ 2 ; 2 ;1 ¸ ; © 7 7 7¹ 4 3 4 3 4 · § 3· §3 ¨ ˜ 0  ˜ 0 ; ˜ 4  ˜ 4 ; ˜ 3  ˜ 2 ¸ ¨ 0; 4 ; 2 ¸ . 7 7 7 7 7 ¹ © 7¹ ©7

4 3 4 3 4 · §3 vS 1, 2  y ¨ ˜ 3  ˜ 5 ; ˜1  ˜1; ˜ 5  ˜ 3 ¸ 7 7 7 7 7 ¹ ©7 4 3 4 3 4 · §3 vS 2,1  y ¨ ˜ 5  ˜ 1; ˜ 3  ˜ 2; ˜ 1  ˜ 2 ¸ 7 7 7 7 7 ¹ ©7 v S  2, 2  y

Тогда (см. табл. 3 или табл. 4) 2 ­ 2 1½ min K1  x1 1, x2 , y3 min ®2 ; 4 ¾ 2 ; 7 ¯ 7 7¿ v1 ­ 5 ½ min K1  x1 2, x2 , y3 min ®2 ; 0¾ 0; ¯ 7 ¿

3½ ­ min K 2  x1, x2 1, y3 min ®2; 2 ¾ 2 ; v2 7¿ ¯ min K 2  x1, x2 2, y3 min^1; 4` 1; 103

2 ­ 2 ½ max ®2 ; 0¾ 2 ; 7 ¯ 7 ¿

max^2;1` 2.

2 Таким образом, максмин у 1-го игрока v^I` 2 , у 2-го игрока – 7 v^II` 2 . Следовательно, 2 1§ 1 2 5 · Sh 1  y3 2  ¨5  2  2¸ 2 ; 7 2© 7 7 7 ¹ 3 3 Sh 2  y 3 2  2 . 7 7 Соответственно PMS-вектор игроков и коалиции принимает следующие значения: 1§ 1 · v1  ¨ 5  v1  v 2 ¸ 2© 7 ¹

3 1 5 PMS1 2 ; PMS 2 2 ; PMS3 2 . 7 3 7 Теперь разделим выигрыши коалиции S в чистых стратегиях, имеющих положительную вероятность реализации, т. е. входящих в NE, в пропорциях, соответствующих PMS-вектору: 5 3 2 PMS1 PMS 2 7 19 ; O 7 17 . O1 2 PMS1  PMS 2 5 1 36 PMS1  PMS2 5 1 36 7 7 Следовательно, матрицы выигрышей игроков I и II коалиции S имеют вид 2

AI

AII

O1 A

O2 A

19 § 4 6 · ¨ ¸ 36 ¨© 8 3 ¸¹ 17 § 4 6 · ¨ ¸ 36 ¨© 8 3 ¸¹

1· § 1 3 ¸ ¨2 6 ¸; ¨ 9 2 7 ¨¨ 4 1 ¸¸ © 9 12 ¹ 5· § 8 2 ¸ ¨1 6 ¸, ¨ 9 ¨¨ 3 7 1 5 ¸¸ © 9 12 ¹

1 [

104

23

 2,1

Пример 2. Пусть в игре участвуют 6 игроков, разделенных на две коалиции S1 и S 2 . В каждой коалиции по двое игроков имеют по двее стратегии и по одному игроку – по три стратегии. Сформируем табл. 5, в которой по горизонтали расположим стратегии коалиции S1, а по вертикали – стратегии коалиции S 2 . Размер таблицы получается 12 u 12 , каждая ячейка которой имеет размер 2 u 3 . В каждой ячейке на пересечении выбранных стратегий обоими коалициями находятся: в первой строке индивидуальные выигрыши игроков коалиции S1; во второй строке – вспомогательные вычисления для нахождения гарантированных выигрышей коалиций из коалиции S1, состоящих из двух игроков (сумма выигрышей игрока 1 и игрока 2, игрока 1 и игрока 3, игрока 2 и игрока 3 соответственно). Ячейки разделяет между собой столбец, в котором помещен суммарный выигрыш игроков коалиции S1 с фиксированными стратегиями обеих коалиций. Аналогично составляем табл. 6, в которой по горизонтали расположим стратегии коалиции S 2 , а по вертикали – стратегии коалиции S1. Соответственно выигрыши здесь помещены для игроков коалиции S 2 . Обе таблицы будут использоваться для определения гарантированных выигрышей. Выпишем формулы для вычисления вектора Шепли: Sh 1 Sh 2 Sh 3

а матрица игры вид

 1, 2

[ 13

K 37 1 K 4 7 ª§ 1 8 · º ª§ 1 5 · º «¨© 2 9 ,1 9 ¸, 5» «¨ 3 6 , 2 6 ¸, 3» ¹ ¼ ¹ ¼ ¬ ¬© 5· º ª§ 2 7 · º ª§ 7 «¨ 4 9 , 3 9 ¸ ,1» «¨112 , 112 ¸, 2» . ¹ ¼ ¬© ¹ ¼ ¬©

1 >v^1, 2, 3`  v^2, 3`  v^1`@  1 >v^1, 2`  v^1, 3`  v^2`  v^3`@; 3 6 1 >v^1, 2, 3`  v^1, 3`  v^2`@  1 >v^1, 2`  v^2, 3`  v^1`  v^3`@; 3 6 1 >v^1, 2, 3`  v^1, 2`  v^3`@  1 >v^1, 3`  v^2, 3`  v^1`  v^2`@. 3 6

105

стратегию

x1,S1

Таблица 5 (для коалиции S1)

Поясним вычисление гарантированных выигрышей. Пусть, например, зафиксирован выбор стратегии игроком 1 при условии, что коалиция противника договорилась играть определенные стратегии. При этом условии игрок 1 выбирает минимальное из значений выигрыша, если он будет играть в своей коалиции стратегию со значением, например, 1, 2 или 3 соответственно. Затем из полученных трех значений выбирается максимальное. Аналогично получаются гарантированные выигрыши для коалиций из двух игроков. Фиксируются стратегии, которые будут играть эти двое, и выбирается минимальное из значений выигрыша, которое они могут получить, если будут играть в своей коалиции с выбранными стратегиями. Максимальное из значений, получаемых при выборе различных комбинаций своих стратегий, будет являться гарантированным выигрышем. Зафиксируем стратегию коалиции противника, например, 1, 2,1 . Найдем гарантированные выигрыши игроков коалиции S1: v1 , v2 , v3 . Игрок 1 гарантирует себе минимум из выигрышей, которые он может получить, играя в коалиции S1 стратегию x1,S1 1 : min^5, 3, 4, 4, 3, 8` 3, 2 : min^ 16, 0, 1,  3, 9, 9` 16 . Следовательно,

max^3,16` 3 . Аналогично находим v2 и v3 . Для нахождения гарантированных выигрышей коалиций, состоящих из двух игроков, используем вторую строку в каждой ячейке и фиксируем уже не стратегию игрока, а стратегию подмножества из двух игроков коалиции S1. Например, пусть коалиция противника S 2 выбирает v1

стратегию 1, 2,1 . Тогда, если игроки 1 и 2 из коалиции выбирают стратегию x1, 2, S1

(1, 1) , то их гарантированный выигрыш составит

min ^6, 4,  6` 6 , если x1,2, S1 x1,2, S1

(1, 2) , то – min^ 8,  3, 11` 8 , если сли

(2, 1) , то – min^ 14, 0, 1` 14 , если x1,2, S1

min ^1, 2,  9` 9 , v12

(2, 2) , тоо –

max ^6,  8,  14,  9` 6 . Аналогично нахоо-

дятся v13 и v23 . Для вычисления PMS-вектора, однако, будем использовать гарантированные выигрыши в смешанных стратегиях в ситуации NE (столбец «мат. ожид.» слева, построение столбца аналогично построению в табл. 4, к примеру 1 – см. комментарий к табл. 4). 106

107

108 109

Таблица 6 (для коалиции S2)

Таблица 5 (окончание)

Таблица 6 (окончание)

Теперь составим матрицу А выигрышей коалиции S1 и найдем обратную к ней матрицу (табл. 7–8). Таблица 7

111 112 113 121 122 123 211 212 213 221 222 223

Matrix A, the strategies of coalition S2 111 121 131 211 221 231 112 122 132 212 222 232 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 -5 -4 -3 -2 -1 0 1 2 3 4 5 -6 -4 -3 -2 -1 0 1 2 3 4 5 -6 -5 -3 -2 -1 0 1 2 3 4 5 -6 -5 -4 -2 -1 0 1 2 3 4 5 -6 -5 -4 -3 -1 0 1 2 3 4 5 -6 -5 -4 -3 -2 0 1 2 3 4 5 -6 -5 -4 -3 -2 -1 1 2 3 4 5 -6 -5 -4 -3 -2 -1 0 2 3 4 5 -6 -5 -4 -3 -2 -1 0 1 3 4 5 -6 -5 -4 -3 -2 -1 0 1 2 4 5 -6 -5 -4 -3 -2 -1 0 1 2 3 5 -6 -5 -4 -3 -2 -1 0 1 2 3 4

Таблица 8 111 -0,1 -0,01 -0,01 -0,01 -0,01 -0,01 -0,01 -0,01 -0,01 -0,01 -0,01 0,07

121 -0,01 -0,01 -0,01 -0,01 -0,01 -0,01 -0,01 -0,01 -0,01 -0,01 0,07 -0,1

131 -0,01 -0,01 -0,01 -0,01 -0,01 -0,01 -0,01 -0,01 -0,01 0,07 -0,1 -0,01

211 -0,01 -0,01 -0,01 -0,01 -0,01 -0,01 -0,01 -0,01 0,07 -0,1 -0,01 -0,01

221 -0,01 -0,01 -0,01 -0,01 -0,01 -0,01 -0,01 0,07 -0,1 -0,01 -0,01 -0,01

A 231 -0,01 -0,01 -0,01 -0,01 -0,01 -0,01 0,07 -0,1 -0,01 -0,01 -0,01 -0,01

–1

112 -0,01 -0,01 -0,01 -0,01 -0,01 0,07 -0,1 -0,01 -0,01 -0,01 -0,01 -0,01

122 -0,01 -0,01 -0,01 -0,01 0,07 -0,1 -0,01 -0,01 -0,01 -0,01 -0,01 -0,01

132 -0,01 -0,01 -0,01 0,07 -0,1 -0,01 -0,01 -0,01 -0,01 -0,01 -0,01 -0,01

212 -0,01 -0,01 0,07 -0,1 -0,01 -0,01 -0,01 -0,01 -0,01 -0,01 -0,01 -0,01

222 -0,01 0,07 -0,1 -0,01 -0,01 -0,01 -0,01 -0,01 -0,01 -0,01 -0,01 -0,01

232 0,07 -0,1 -0,01 -0,01 -0,01 -0,01 -0,01 -0,01 -0,01 -0,01 -0,01 -0,01

Также составим матрицу В в тех же стратегиях и найдем обратную к ней матрицу (табл. 9, 10).

110

111

The strategies of coalition S1

Таблица 9 Matrix B, the strategies of coalition S2 111 121 131 211 221 231 112 122 132 212 222 232 111 5 0 0 0 0 0 0 0 0 0 0 0 112 0 3 0 0 0 0 0 0 0 0 0 0 113 0 0 1 0 0 0 0 0 0 0 0 0 121 0 0 0 3 0 0 0 0 0 0 0 0 122 0 0 0 0 5 0 0 0 0 0 0 0 123 0 0 0 0 0 7 0 0 0 0 0 0 211 0 0 0 0 0 0 9 0 0 0 0 0 212 0 0 0 0 0 0 0 11 0 0 0 0 213 0 0 0 0 0 0 0 0 13 0 0 0 221 0 0 0 0 0 0 0 0 0 15 0 0 222 0 0 0 0 0 0 0 0 0 0 17 0 223 0 0 0 0 0 0 0 0 0 0 0 19

Таблица 10 B–1 111

121

131

211

221

231

112

122

132

212

222

0,20 0 0 0 0 0 0 0 0 0 0 0 0,33 0 0 0 0 0 0 0 0 0 0 0 1,00 0 0 0 0 0 0 0 0 0 0 0 0,33 0 0 0 0 0 0 0 0 0 0 0 0,20 0 0 0 0 0 0 0 0 0 0 0 0,14 0 0 0 0 0 0 0 0 0 0 0 0,11 0 0 0 0 0 0 0 0 0 0 0 0,09 0 0 0 0 0 0 0 0 0 0 0 0,08 0 0 0 0 0 0 0 0 0 0 0 0,07 0 0 0 0 0 0 0 0 0 0 0 0,06 0

0

0

0

0

0

0

0

0

0

0

232 0 0 0 0 0 0 0 0 0 0 0 0,05



v1 1 uA1u



x



0,375 ; u

1,,1 ;

v2uB 1

0,08; 0,13; 0,38; 0,13; 0,08; 0,05; 0,04; 0,03; 0,03; 0,03; 0,02; 0,02 ; y

v1 A1u

0,08; 0,08; 0,08; 0,08; 0,08; 0,08; 0,08; 0,08; 0,08; 0,08; 0,08; 0,08 T . Составим матрицу С распределения вероятностей реализации выигрышей коалиций S1 и S 2 в ситуации NE в смешанных стратегиях при выборе игроками своих чистых стратегий: С x 0,08 0,13 0,38 0,13 0,08 0,05 0,04 0,03 0,03 0,03

y 111 121 131 211 221 231 112 122 132 212

0,08 111 0,006 0,010 0,031 0,010 0,006 0,004 0,003 0,003 0,002 0,002

0,08 112 0,006 0,010 0,031 0,010 0,006 0,004 0,003 0,003 0,002 0,002

0,08 113 0,006 0,010 0,031 0,010 0,006 0,004 0,003 0,003 0,002 0,002

0,08 121 0,006 0,010 0,031 0,010 0,006 0,004 0,003 0,003 0,002 0,002

0,08 122 0,006 0,010 0,031 0,010 0,006 0,004 0,003 0,003 0,002 0,002

0,08 123 0,006 0,010 0,031 0,010 0,006 0,004 0,003 0,003 0,002 0,002

0,08 211 0,006 0,010 0,031 0,010 0,006 0,004 0,003 0,003 0,002 0,002

0,08 212 0,006 0,010 0,031 0,010 0,006 0,004 0,003 0,003 0,002 0,002

0,08 213 0,006 0,010 0,031 0,010 0,006 0,004 0,003 0,003 0,002 0,002

0,08 221 0,006 0,010 0,031 0,010 0,006 0,004 0,003 0,003 0,002 0,002

0,02

222

0,002

0,002

0,002

0,002

0,002

0,002

0,002

0,002

0,002

0,02

232

0,002

0,002

0,002

0,002

0,002

0,002

0,002

0,002

0,002

0,08 222 0,006 0,010 0,031 0,010 0,006 0,004 0,003 0,003 0,002 0,002

0,08 223 0,006 0,010 0,031 0,010 0,006 0,004 0,003 0,003 0,002 0,002

0,002

0,002

0,002

0,002

0,002

0,002

Вычислим значение игры E  x, y в смешанных стратегиях: E > C , A ; C , B @ > 0,5 ; 0,375@, где $, $ – сумма скалярных произведений векторов соответствующих матриц. Найдем PMS-вектор как вектор Шепли выигрышей коалиций S1 и S 2 , т. е. PMS1 S1 0,111; PMS 2 S1

Найдем числа v1 , v2 и векторы x и y:



0,5 ; v2 1 uB 1u

PMS1 S 2

PMS 2 S 2

1,556 ;

PMS 3 S1 0,944 ;

2,487 ; 2,564 ;

PMS 3 S 2 0,452 .

Таким образом, PMS( N ) 0,111;  1,556; 0,944; 2,487;  2,564; 0,452 . 112

113

Теперь разделим выигрыши коалиций S1 и S 2 в чистых стратегиях, имеющих положительную вероятность реализации, т. е. входящих в NE, в пропорциях, соответствующих PMS-вектору:

O j S k

PMS j S k

, k

3

1, 2, j

Матрица A3 = O3A, стратегии коалиции S2, выигрыш игрока 3 коалиции S1 111 112 113 121 122 123 211 212 213 221 222 223

1, 3.

¦ PMSi S k i 1

Следовательно, матрицы выигрышей игроков 1, 2 и 3 коалиции S1 имеют вид

Матрица A1 = O1A, стратегии коалиции S2, выигрыш игрока 1 коалиции S1 111 112 113 121 122 123 211 212 213 221 222 223

111 1,33 1,11 0,89 0,67 0,44 0,22 0,00 -0,22 -0,44 -0,67 -0,89 -1,11

121 1,11 0,89 0,67 0,44 0,22 0,00 -0,22 -0,44 -0,67 -0,89 -1,11 1,33

131 0,89 0,67 0,44 0,22 0,00 -0,22 -0,44 -0,67 -0,89 -1,11 1,33 1,11

211 0,67 0,44 0,22 0,00 -0,22 -0,44 -0,67 -0,89 -1,11 1,33 1,11 0,89

221 0,44 0,22 0,00 -0,22 -0,44 -0,67 -0,89 -1,11 1,33 1,11 0,89 0,67

231 0,22 0,00 -0,22 -0,44 -0,67 -0,89 -1,11 1,33 1,11 0,89 0,67 0,44

112 0,00 -0,22 -0,44 -0,67 -0,89 -1,11 1,33 1,11 0,89 0,67 0,44 0,22

122 -0,22 -0,44 -0,67 -0,89 -1,11 1,33 1,11 0,89 0,67 0,44 0,22 0,00

132 -0,44 -0,67 -0,89 -1,11 1,33 1,11 0,89 0,67 0,44 0,22 0,00 -0,22

212 -0,67 -0,89 -1,11 1,33 1,11 0,89 0,67 0,44 0,22 0,00 -0,22 -0,44

222 -0,89 -1,11 1,33 1,11 0,89 0,67 0,44 0,22 0,00 -0,22 -0,44 -0,67

111 11,33 9,44 7,56 5,67 3,78 1,89 0,00 -1,89 -3,78 -5,67 -7,56 -9,44

111 112 113 121 122 123 211 212 213 221 222 223

121 -15,56 -12,44 -9,33 -6,22 -3,11 0,00 3,11 6,22 9,33 12,44 15,56 -18,67

131 -12,44 -9,33 -6,22 -3,11 0,00 3,11 6,22 9,33 12,44 15,56 -18,67 -15,56

211 -9,33 -6,22 -3,11 0,00 3,11 6,22 9,33 12,44 15,56 -18,67 -15,56 -12,44

221 231 -6,22 -3,11 -3,11 0,00 0,00 3,11 3,11 6,22 6,22 9,33 9,33 12,44 12,44 15,56 15,56 -18,67 -18,67 -15,56 -15,56 -12,44 -12,44 -9,33 -9,33 -6,22

112 0,00 3,11 6,22 9,33 12,44 15,56 -18,67 -15,56 -12,44 -9,33 -6,22 -3,11

114

122 3,11 6,22 9,33 12,44 15,56 -18,67 -15,56 -12,44 -9,33 -6,22 -3,11 0,00

132 6,22 9,33 12,44 15,56 -18,67 -15,56 -12,44 -9,33 -6,22 -3,11 0,00 3,11

212 9,33 12,44 15,56 -18,67 -15,56 -12,44 -9,33 -6,22 -3,11 0,00 3,11 6,22

222 12,44 15,56 -18,67 -15,56 -12,44 -9,33 -6,22 -3,11 0,00 3,11 6,22 9,33

131 7,56 5,67 3,78 1,89 0,00 -1,89 -3,78 -5,67 -7,56 -9,44 11,33 9,44

211 5,67 3,78 1,89 0,00 -1,89 -3,78 -5,67 -7,56 -9,44 11,33 9,44 7,56

221 3,78 1,89 0,00 -1,89 -3,78 -5,67 -7,56 -9,44 11,33 9,44 7,56 5,67

231 112 1,89 0,00 0,00 -1,89 -1,89 -3,78 -3,78 -5,67 -5,67 -7,56 -7,56 -9,44 -9,44 11,33 11,33 9,44 9,44 7,56 7,56 5,67 5,67 3,78 3,78 1,89

122 -1,89 -3,78 -5,67 -7,56 -9,44 11,33 9,44 7,56 5,67 3,78 1,89 0,00

132 -3,78 -5,67 -7,56 -9,44 11,33 9,44 7,56 5,67 3,78 1,89 0,00 -1,89

212 -5,67 -7,56 -9,44 11,33 9,44 7,56 5,67 3,78 1,89 0,00 -1,89 -3,78

222 -7,56 -9,44 11,33 9,44 7,56 5,67 3,78 1,89 0,00 -1,89 -3,78 -5,67

232 -9,44 11,33 9,44 7,56 5,67 3,78 1,89 0,00 -1,89 -3,78 -5,67 -7,56

Матрицы выигрышей игроков 1, 2 и 3 коалиции S 2 :

232 -1,11 1,33 1,11 0,89 0,67 0,44 0,22 0,00 -0,22 -0,44 -0,67 -0,89

Матрица B1 = O1B, стратегии коалиции S1, выигрыш игрока 1 коалиции S2 0 111 112 113 121 122 123 211 212 213 221 222 223

111 33,16 0 0 0 0 0 0 0 0 0 0 0

Матрица A2 =O2A, стратегии коалиции S2, выигрыш игрока 2 коалиции S1 111 -18,67 -15,56 -12,44 -9,33 -6,22 -3,11 0,00 3,11 6,22 9,33 12,44 15,56

121 9,44 7,56 5,67 3,78 1,89 0,00 -1,89 -3,78 -5,67 -7,56 -9,44 11,33

232 15,56 -18,67 -15,56 -12,44 -9,33 -6,22 -3,11 0,00 3,11 6,22 9,33 12,44

121 0 19,90 0 0 0 0 0 0 0 0 0 0

131 0 0 6,63 0 0 0 0 0 0 0 0 0

211 0 0 0 19,90 0 0 0 0 0 0 0 0

221 0 0 0 0 33,16 0 0 0 0 0 0 0

231 0 0 0 0 0 46,43 0 0 0 0 0 0

112 0 0 0 0 0 0 59,70 0 0 0 0 0

122 0 0 0 0 0 0 0 72,96 0 0 0 0

132 0 0 0 0 0 0 0 0 86,23 0 0 0

212 0 0 0 0 0 0 0 0 0 99,49 0 0

222 0 0 0 0 0 0 0 0 0 0 112,76 0

232 0 0 0 0 0 0 0 0 0 0 0 126,03

Матрица B2 = O2B, стратегии коалиции S1, выигрыш игрока 2 коалиции S2 0 111 112 113 121 122 123 211 212 213 221 222 223

111 -34,19 0 0 0 0 0 0 0 0 0 0 0

121 0 -20,51 0 0 0 0 0 0 0 0 0 0

131 0 0 -6,84 0 0 0 0 0 0 0 0 0

211 0 0 0 -20,51 0 0 0 0 0 0 0 0

221 0 0 0 0 -34,19 0 0 0 0 0 0 0

231 0 0 0 0 0 -47,86 0 0 0 0 0 0

112 0 0 0 0 0 0 -61,53 0 0 0 0 0

115

122 0 0 0 0 0 0 0 -75,21 0 0 0 0

132 0 0 0 0 0 0 0 0 -88,88 0 0 0

212 0 0 0 0 0 0 0 0 0 -102,56 0 0

222 0 0 0 0 0 0 0 0 0 0 -116,23 0

232 0 0 0 0 0 0 0 0 0 0 0 -129,91

ПРИЛОЖЕНИЕ 2

Матрица B3 = O3B, стратегии коалиции S1, выигрыш игрока 3 коалиции S2 0 111 112 113 121 122 123 211 212 213 221 222 223

111 6,02 0 0 0 0 0 0 0 0 0 0 0

121 0 3,61 0 0 0 0 0 0 0 0 0 0

131 0 0 1,20 0 0 0 0 0 0 0 0 0

211 0 0 0 3,61 0 0 0 0 0 0 0 0

221 0 0 0 0 6,02 0 0 0 0 0 0 0

231 0 0 0 0 0 8,43 0 0 0 0 0 0

112 0 0 0 0 0 0 10,84 0 0 0 0 0

122 0 0 0 0 0 0 0 13,25 0 0 0 0

132 0 0 0 0 0 0 0 0 15,66 0 0 0

212 0 0 0 0 0 0 0 0 0 18,06 0 0

222 0 0 0 0 0 0 0 0 0 0 20,47 0

232 0 0 0 0 0 0 0 0 0 0 0 22,88

Самостоятельная работа № 1 Изобразить на графе, представленном на рис. 1.5, путь

x

 x0 , , xl и найти выигрыши игроков: 1. ^2, 1, 1, 1, 1, 3, 2, 2 , 2, 3, 1, 1, 1, 1, 4 ` o ? 2. ^3, 2, 1, 3, 1, 3, 1, 1 , 2, 1, 1, 2, 1, 2, 4 ` o ? 3. ^2, 1, 1, 2, 1, 3, 1, 2 , 1, 3, 2, 1, 2, 1, 4 ` o ? 4. ^1, 2, 1, 3, 1, 3, 1, 2 , 2, 3, 1, 2, 1, 1, 4 ` o ? 5. ^3, 2, 1, 3, 1, 3, 1, 2 , 3, 3, 1, 1, 1, 2, 4 ` o ? 6. ^3, 2, 2, 1, 1, 3, 2, 2 , 1, 2, 1, 2, 1, 2, 4 ` o ? 7. ^1, 1, 2, 2, 1, 3, 1, 1 , 2, 2, 1, 2, 2, 2, 4 ` o ? 8. ^1, 2, 2, 1, 2, 3, 1, 2 , 3, 1, 1, 1, 1, 1, 1 ` o ? 9. ^1, 1, 1, 1, 1, 3, 2, 2 , 1, 2, 1, 1, 1, 1, 4 ` o ? 10. ^2, 2, 2, 2, 1, 3, 2, 1 , 1, 2, 1, 1, 1, 1, 2 ` o ? 11. ^1, 2, 2, 1, 2, 3, 2, 1 , 2, 2, 2, 2, 1, 2, 4 ` o ? 12. ^2, 2, 2, 1, 1, 3, 2, 2 , 2, 2, 2, 2, 2, 2, 2 ` o ? 13. ^1, 2, 1, 2, 1, 2, 1, 2 , 2, 2, 2, 2, 2, 2, 3 ` o ? 14. ^1, 2, 2, 2, 2, 3, 2, 2 , 3, 2, 1, 2, 1, 1, 3 ` o ? 15. ^1, 2, 1, 2, 1, 3, 2, 2 , 2, 3, 1, 2, 1, 2, 3 ` o ? 16. ^2, 2, 1, 3, 2, 3, 2, 2 , 1, 3, 2, 1, 1, 1, 1 ` o ? 17. ^2, 2, 2, 1, 1, 3, 2, 2 , 1, 1, 1, 1, 1, 1, 2 ` o ? 18. ^1, 1, 1, 3, 2, 3, 1, 2 , 3, 1, 1, 2, 1, 2, 3 ` o ? 19. ^1, 2, 2, 2, 2, 1, 2, 2 , 2, 2, 1, 2, 2, 1, 3 ` o ? 20. ^1, 2, 2, 2, 1, 3, 2, 2 , 1, 3, 1, 2, 1, 2, 3 ` o ?

Самостоятельная работа № 2 Найти все ситуации абсолютного NE в игре G, заданной на древовидном графе и представленной на рисунках. В позициях, обозначенных «кружочками», ходит первый игрок, в «квадратиках» – второй игрок. 116

117

118 119

Вариант 2

Вариант 1

120 121

Вариант 4

Вариант 3

122 123

Вариант 6

Вариант 5

124 125

Вариант 8

Вариант 7

126 127

Вариант 10

Вариант 9

Самостоятельная работа № 7

Самостоятельная работа № 4 1.

Найти С-ядро и его центр в кооперативных играх  N , v трех лиц: v N 9 , v1, 2 4 , v1, 3 4 , v2, 3 7 , v1 0 , v2 0 ,

v3 0 . 2.

v N 8 , v1, 2 6 , v1, 3 6 , v2, 3 6 , v1 0 , 1.

3.

v2 0 , v3 0 . v N 21 , v1, 2 5 , v1, 3

Дать словесное описание ИМ игроков, найти оптимальное решение позиционной игры и определить возможные позиции, партии и существенные ИМ при использовании соответствующих оптимальных стратегий: Вариант 1

4 , v2, 3 8 , v1 1 , v2 2 ,

–3

–2

2

1

4

–5

1

5

4

1

1

v3 0 . 4.

v N 18 , v1, 2 15 , v1, 3 v2, 3 12 , v1 v2 v3

5.

v N 15 , v1, 2 v1, 3 6 , v2, 3 10 , v1 3 , v2 v3 0 .

6.

II

2.

I II

v N 7 , v1, 2 6 , v1, 3 5 , v2, 3 3 , v1 0 , v2 0 ,

I

v3 1 .

7.

v N 14 , v1, 2

4 , v1, 3

4 , v2, 3 10 , v1 v2 v3

8.

v N 10 , v1, 2 5 , v1, 3

4 , v2, 3 6 , v1 0 , v2 3 ,

v N 29 , v1, 2 14 , v1, 3 v2, 3 12 , v1 v3 0 , v2 10 .

10. v N

–3 –2 2 3

1 1

5

I

I

4

I

2

II

4 , v1, 3 6 , v2, 3

15. v N 8 , v1, 2

4 , v1, 3 v2, 3 4 , v1 v2 v3 0 .

4 , v1 v2 v3 0 .

1

1

5

II

II I

2

1 1

Вариант 3

I

–5

I

3

II

2 I

4

1 1

I

I II

5

4

1

1 129

1 3

II 2

1 II

128

4

II

II –3 –2 2

14. v N 8 , v1, 2

1

4

I

v3 1 .

I

–5

v3 0 .

2 , v1 v2 0 ,

II

Вариант 2

11. v N 7 , v1, 2 3 , v1, 3 5 , v2, 3 6 , v1 0 , v2 0 ,

13. v N 7 , v1, 2 6 , v1, 3 5 , v2, 3

II

3

II

1

20 , v1, 2 6 , v1, 3 5 , v2, 3 7 , v1 v2 v3 2 .

2 , v1 v2 v3 0 .

2

I

II

I

12. v N 7 , v1, 2 6 , v1, 3 5 , v2, 3

I

2.

v3 3 .

9.

2

5

5 II

I

Вариант 7

Вариант 4

–3 –2 2 –3 –2

2

–5

4

1

1

5

4

1

1

2

I I

I

2

II

2

I

I

II

II

II

I

–5

I

3

II

2 I

1 1

I

I

5

4

1

1

I

I

2 2

II

–3 –2 2

2

I

1

1

5

3 II

II

II

I

1

–5

4

1

1

I

3

5

I

II

4

1

1

5

II

II 3

II

I

I 1

I 1

1

II

Вариант 9

4

1 1

I

I

5

4 II

II

1

1 3

II I

5

–3 –2 2 I

–5

4

2 I

1

1

II

2

I 1

I

4

1

I

1 1

131

1

II 3 II 3

II

II

130

5 I

I

1 II

4

1

I 2

2

5

2

1

–5

3

II

I

II

II

II

5

Вариант 6 –2 2

I

Вариант 8

4

II –3

I

I

Вариант 5 –3 –2 2

1 1

I

1

II

4

II

1

I

–5

5

5

Рекомендуемая литература

Вариант 10 –3 –2

2

2

I 2

–5

4

I

I

1

1 3

II

5 I

II

4

II

I

1

132

1 II

II 3

1

I

1

5

1. Петросян, Л. А. Игры в развернутой форме. Оптимальность и устойчивость / Л. А. Петросян, Д. В. Кузютин. – СПб.: СПбГУ, 2000. 2. Бернс, К. Теория графов и ее применение / К. Бернс. – М.: ИЛ, 1962. 3. Печерский, С. Л. Теория игр для экономистов. Вводный курс / С. Л. Печерский, А. А. Беляева. – СПб.: Изд-во Европейского университета, 2001. 4. Дюбин, Г. Н. Введение в прикладную теорию игр / Г. Н. Дюбин, В. Г. Суздаль. – М.: Наука, 1981. 5. Petrosjan, L. Dynamic Games with Coalitional Structures / L. Petrosjan, S. Mamkina // Intersectional Game Theory Review, vol. 8, № 2, pp. 295–307, 2006. 6. Коваленко, А. А. Сборник задач по теории игр / А. А. Коваленко. – Львов, 1974. 7. Мак-Кинси, Дж. Введение в теорию игр / Дж. Мак-Кинси. – М., 1960. 8. Ашманов, С. А. Линейное программирование / С. А. Ашманов. – М., 1981. 9. Петросян, Л. А. Теория игр / Л. А. Петросян, Н. А. Зенкевич, Е. А. Семина. – М.: Высшая школа, 1998. 10. Nash, J. Non-cooperative Games. Ann. Mathematics. 54, pp. 286–295, 1951. 11. Shapley, L. S. A Value for n-Person Games, in H. W. Kuhn and A. W. Tucker (eds.), Contributions to the Theory of Games (Princeton University Press), pp. 307–317, 1953.

133

ДЛЯ ЗАПИСЕЙ

Учебное издание

Григорьева Ксения Владимировна ТЕОРИЯ ИГР Часть 2 КООПЕРАТИВНЫЕ ИГРЫ И ИГРЫ В ПОЗИЦИОННОЙ ФОРМЕ Учебное пособие Редактор А. В. Афанасьева Корректоры К. И. Бойкова, А.Г. Лавров Компьютерная верстка И. А. Яблоковой Подписано к печати 24.09.09. Формат 60 84 1/16. Бум. офсетная. Усл. печ. л. 7,8. Уч.-изд. л. 8,4. Тираж 200 экз. Заказ 101. «С» 46. Санкт-Петербургский государственный архитектурно-строительный университет. 190005, Санкт-Петербург, 2-я Красноармейская ул., 4. Отпечатано на ризографе, 190005, Санкт-Петербург, 2-я Красноармейская ул., 5.