Теоретико-игровые модели организационного управления: Методические указания по специальному курсу. Часть 1. Игры в нормальной форме

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Федеральное государственное образовательное учреждение высшего профессионального образования «ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»

Угольницкий Г.А.

МЕТОДИЧЕСКИЕ УКАЗАНИЯ по специальному курсу «Теоретико-игровые модели организационного управления» для студентов факультета математики, механики и компьютерных наук Часть 1. Игры в нормальной форме

Ростов-на-Дону 2007 1

Методические указания разработаны доктором физико-математических наук, профессором кафедры прикладной математики и программирования

Г.А.

Угольницким

Ответственный редактор

канд. физ.-мат. наук А.Б. Усов

Компьютерный набор и верстка

ст. лаборанта Евдокимовой И.В.

Печатается в соответствии с решением кафедры прикладной математики и программирования факультета математики, механики и компьютерных наук ЮФУ, протокол №2 от 25 октября 2007 г.

2

СОДЕРЖАНИЕ 1

Понятие игры в нормальной форме

3

2

Изолированное поведение

6

3

Сложное поведение

11

4

Равновесие по Штакельбергу

19

5

Равновесие по Нэшу

21

6

Стабильные соглашения

29

Литература

38

3

1 ПОНЯТИЕ ИГРЫ В НОРМАЛЬНОЙ ФОРМЕ Хорошо известна классическая постановка задачи оптимизации

f ( x ) → max, x ∈ X

(1)

смысл которой – поиск максимума (или минимума) целевой функции f на множестве X . В этом случае имеется один субъект принятия решения, цель которого максимизация единственного критерия оптимальности (целевой функции). А если у субъекта несколько критериев оптимальности (как обычно бывает в жизни)? Моделью принятия решения в этом случае служит задача многокритериальной оптимизации f i ( x ) → max, x ∈ X , i ∈ N

(2)

Однако не менее распространенной является и другая постановка задачи принятия решений – наличие нескольких субъектов, каждый из которых стремится максимизировать свою целевую функцию: f i ( x ) → max, xi ∈ X i , i ∈ N

(3)

Модель (формула (3)) – так называемая игра в нормальной форме – служит предметом рассмотрения в настоящих методических указаниях. Они представляют собой адаптированную версию работы [3] с рядом авторских изменений и дополнений. Более подробно с материалом можно ознакомиться в [1, 2, 4, 5]. Определение 1.1 Игрой в нормальной форме называется набор

G = N , {X i }i∈N , {ui }i∈N .

(4)

Здесь N = {1, 2, ... , n} – конечное множество так называемых игроков – субъектов принятия решения, имеющих свои цели (интересы) и определенные возможности их достижения (реализации). В различных ситуациях в качестве игроков могут выступать хозяйствующие субъекты (индивидуальные предприниматели, предприятия, объединения), политические субъекты (избиратели, партии), частные лица и т.д.

4

Каждый игрок i ∈ N имеет множество допустимых стратегий X i Элемент xi ∈ X i (допустимая стратегия игрока i ) – это конкретное действие, совершаемое игроком. После того, как все игроки множества N выбрали свои допустимые стратегии, образуется вектор x = ( x1 , ... , xn ) – игровая ситуация (исход игры). Множество всех игровых ситуаций обозначено через X . Очень удобно следующее обозначе-

ние: xiˆ = (x1 , ... , xi −1 , xi +1 ,K , xn ), т.е. вектор допустимых стратегий всех игроков из N , кроме игрока i .

Наконец, в модели (формула (4)) для каждого игрока i ∈ N определена функция выигрыша ui : X → R , сопоставляющая каждой ситуации x ∈ X некоторое вещественное число ui ( x ) – выигрыш игрока i в ситуации x . Содержательно это число может означать прибыль (убытки), доход (затраты), число голосов на выборах и т.п. В случае двух игроков ( N = {1, 2}) очень удобно представлять игру в виде матрицы, строки которой обозначают стратегии первого игрока, столбцы – стратегии второго, а в каждой клетке содержатся два числа – выигрыши игроков в ситуации, образованной соответствующими стратегиями. Пример 1.1 Игра «Дилемма заключенного» А А М

М

1

3 1

0

0 2

3

2

Здесь X 1 = X 2 = {A, M }, т.е. каждый игрок имеет две стратегии – A («агрессия») и М («миролюбие»). Соответственно, u1 ( A, A) = u2 ( A, A) = 1, u1 ( A, M ) = 3,

u 2 ( A, M ) = 0 , u1 (M , A) = 0,

u 2 (M , A) = 3,

u1 (M , M ) = u2 (M , M ) = 2 . Подробный

анализ игры «Дилеммы заключенного» можно найти в [2]. 5

Пример 1.2 Игра «Семейный спор» Ф Ф Б

2

Б 0

1 0

0 1

0

2

Упражнение 1.1 Выписать множества допустимых стратегий и функции

выигрыша игроков в игре «Семейный спор». Основным постулатом теории игр в нормальной форме считается следующее утверждение: интересы каждого игрока целиком и полностью описываются стремлением максимизировать свою функцию выигрыша (так называемый постулат экономической рациональности). Принятие этого постулата оставляет за рамками модели (формула (4)) такие мотивы человеческого поведения, как следование традиционным образцам, действия в состоянии аффекта, месть, глупость и т.д., но зато позволяет построить содержательную математическую теорию в экономике, политике, управлении организациями и других областях. Подчеркнем специфику модели игры в нормальной форме (формула (4)) с учетом постулата экономической рациональности. Каждый игрок стремится максимизировать свою функцию выигрыша ui , но при этом он может распоряжаться только одной переменной xi ∈ X i , в то время как ui зависит от векторной переменной x = (xi , xiˆ ) . Поэтому результат максимизации будет зависеть не только от действия игрока i , но и от действий всех остальных игроков из множества N \ { i }.

Именно это обстоятельство предопределяет необходимость поиска компромисса при принятии решения в игровых моделях, а с математической точки зрения – наличие нескольких подходов к определению решения (принципов оптимальности).

6

2 ИЗОЛИРОВАННОЕ ПОВЕДЕНИЕ Рассмотрение теоретико-игровых принципов оптимальности начнем с простейшего случая изолированного поведения, когда игроки действуют независимо от интересов других игроков (в частности, могут просто их не знать). Определение 2.1 Стратегия xi доминирует стратегию yi ( xi f yi ) ,

если ∀xiˆ ∈ X iˆ u i (xi , xiˆ ) ≥ u i ( yi , xiˆ ) , ∃xiˆ ∈ X iˆ ui ( xi , xiˆ ) > ui ( yi , xiˆ ) . Обозначим через Д i множество недоминируемых стратегий i -го игрока. Лемма 2.1 Пусть множество X i компактно, функция ui непрерывна. Тогда

множество Д i не пусто. Доказательство: [3, с. 17-18]. Упражнение 2.1 Найти множества недоминируемых стратегий обоих игро-

ков в играх «Дилемма заключенного» и «Семейный спор» (примеры 1.1, 1.2). Определение 2.2. Стратегия xi называется доминирующей стратегией иг-

рока i , если ∀yi ∈ X i ∀xiˆ ∈ X iˆ ui (xi , xiˆ ) ≥ ui ( yi , xiˆ ) Обозначим множество доминирующих стратегий игрока i через Di . Если для всех игроков i ∈ N множество Di не пусто, то существует хотя бы одна ситуация x ∈ D1 × ...× Dn , которая называется равновесием в доминирующих стратегиях в игре (4). Преимущества доминирующей стратегии очевидны, поэтому вполне естественно принять равновесие в доминирующих стратегиях в качестве принципа оптимальности (решения игры) при изолированном поведении игроков. Но всегда ли можно реализовать этот принцип оптимальности? Определение 2.3 Стратегии xi и yi эквивалентны ( xi ~ yi ) ,

если ∀xiˆ ∈ X iˆ ui (xi , xiˆ ) = ui ( yi , xiˆ ) .

7

Упражнение 2.2 Найти равновесие в доминирующих стратегиях в игре

«Дилемма заключенного». Существует ли равновесие в доминирующих стратегиях в игре «Семейный спор»? Лемма 2.2 Пусть Di ≠ Ø. Тогда эквивалентны следующие утверждения:

1) Di ≠ Ø; 2) все стратегии из множества Д i эквивалентны; 3) Di = Д i . Упражнение 2.3 Доказать лемму 2.2.

Заметим, что лемма 2.2 определяет дихотомическое разбиение всех игр в нормальной форме. В первый класс этого разбиения попадают игры, для которых ∀i ∈ N Di ≠ Ø. В этом случае в качестве принципа оптимальности (решения игры) можно брать равновесие в доминирующих стратегиях, а в качестве элементов этого равновесия – любые недоминируемые (они же доминирующие) стратегии. В играх второго класса ∃i ∈ N Di = Ø : тогда равновесие в доминирующих стратегиях не существует, и приходится искать иные подходы к определению решения игры. Вернемся к игре «Дилемма заключенного» (пример 1.1). Заметим, что ситуация (M , M ) не является равновесием в доминирующих стратегиях, но в этой ситуации оба игрока получают большие выигрыши, чем при выборе доминирующей стратегии А . Определение 2.4 Ситуация x оптимальна по Парето ( x ∈ PO ) , если не су-

ществует такой ситуации y , что ∀i ∈ N ui ( y ) ≥ ui ( x )

∃i ∈ N ui ( y ) ≥ ui ( x ) . Таким образом, ситуация оптимальна по Парето, если не существует другой ситуации, в которой каждый игрок получает не меньший выигрыш, а хотя бы

8

один – строго больший. Очевидно, в «Дилемме заключенного» множество Парето – оптимальных ситуаций PO = {( A, M ), (M , A), (M , M )}. Упражнение 2.4 Найти РО в игре «Семейный спор».

Заметим, что при изолированном поведении игроки в «Дилемме заключенного» не смогут попасть в более выгодную для обоих ситуацию (M , M ) ∈ PO : каждый побоится выбрать стратегию M , так как партнер может выбрать A . Дело в том, что оптимальность по Парето – это уже кооперативный принцип оптимальности, требующий обмена информацией между игроками. Если функция выигрыша игроков задана аналитически, то для нахождения доминирующих стратегий необходимо найти точки максимума функции выигрыша. Упражнение 2.5 Найти равновесие в доминирующих стратегиях для сле-

дующих игр: а) ui ( x1 , ... , xn ) = cxi e − ( x1 + ... + xn ) , i ∈ N , c > 0, xi ≥ 0, xi – выпуск товара i -й фирмой; α1

α2

⎛p ⎞ ⎛p ⎞ б) ui ( p1 , p2 ) = ( pi − ci ) d i , d1 = ⎜⎜ 2 ⎟⎟ , d 2 = ⎜⎜ 1 ⎟⎟ , ci > 0, α i > 1, i = 1, 2, ⎝ p1 ⎠ ⎝ p2 ⎠ где p1 , p2 – цены на товары фирм-конкурентов; в) ui ( x1 , x2 ) = ai xi2 − bi xi , ai bi > 0, xi ≥ 0, xi – выпуск товара i -й фирмой. Упражнение 2.6 Найти равновесие в доминирующих стратегиях и Парето-

оптимальные ситуации в игре «Услуга за услугу»: Б Б Н

Н

1

0 1

1

1 0

0

0

Еще один подход к построению принципа оптимальности при изолированном поведении – осторожность (расчет на худшее). 9

Определение 2.5 Стратегия xi называется осторожной стратегией игрока i ,

если inf u i (xi , xiˆ ) = sup inf u i ( yi , xiˆ ) . xiˆ ∈ X iˆ

yi ∈ X i xiˆ ∈ X iˆ

Величина α i = sup inf u i ( yi , xiˆ ) называется гарантированным выигрышем i -го yi ∈ X i xiˆ ∈ X iˆ

игрока. Таким образом, выбор осторожной стратегии гарантирует игроку i выигрыш α i (если остальные игроки не будут играть против него, то он может получить и больше). Обозначим через P i множество осторожных стратегий игрока i . Лемма 2.3 Пусть X i компактно, ui непрерывна. Тогда Pi непусто, компакт-

но и пересекается с множеством Д i . Доказательство: [3, с. 26-27]. Упражнение 2.7 Найти множества Pi в играх «Дилемма заключенного» и

«Семейный спор». Определение 2.6. Игра в нормальной форме несущественна, если нет исхо-

да x , для которого ∀i ∈ N ui ( x ) ≥ α i ∃i ∈ N u i ( x ) > α i Упражнение 2.8 Выяснить, являются ли несущественными игры «Дилемма

заключенного», «Семейный спор», «Услуга за услугу».

10

3 СЛОЖНОЕ ПОВЕДЕНИЕ В отличие от изолированного поведения, здесь предполагается, что каждый игрок знает не только свою, но и все остальные функции выигрыша. Тогда каждый игрок ожидает, что все остальные игроки исключат свои доминируемые стратегии. Пример 3.1 «Выборы с решающим голосом».

Рассмотрим игру, в которой N = {1, 2, 3}, X 1 = X 2 = X 3 = {a, b, c} , где a, b, c – некоторые альтернативы (например, кандидаты на должность). Первый игрок имеет решающий голос, т.е. выборы кандидата проходят по правилу ⎧ x2 , x2 = x3 . x , иначе ⎩ 1

π ( x1 , x2 , x3 ) = ⎨

Пусть функция выигрыша имеет следующую структуру (так называемый парадокс Кондорсе): u1 (c )
u 2 (b )
u3 (a )
Упражнение 3.1 Доказать, что стратегия a является доминирующей для

первого игрока. Упражнение 3.2 Доказать, что Д 2 = {a, c}.

Указание. Для доказательства достаточно показать следующее: а) для второго игрока с f b ; б) ∃ ( x1 , x3 ) ∈ X 1 × X 3 , ( y1 , y3 ) ∈ X 1 × X 3 :

u2 ( x1 , a, x3 ) > u2 ( x1 , c, x3 ), u2 ( y1 , a, y3 ) < u2 ( y1 , c, y3 ) .

11

Упражнение 3.3 Доказать, что Д 3 = {b, c}.

В силу доказанных утверждений, если игроки исключат свои доминируемые стратегии, то вместо исходных множеств X 1 , X 2 , X 3 останутся усеченные множества Y1 = { a } , Y2 = { a, c } , Y3 = { b, c } . Упражнение 3.4 Доказать, что теперь:

а) для второго игрока с f a ; б) для третьего игрока с f b .

Таким образом, получаем новые усеченные множества Z1 = { a }, Z 2 = { c }, Z 3 = { c }, обусловливающие однозначный выбор альтернативы по правилу

π (a, c, c ) = c . Возникает неожиданная ситуация: после исключения доминируемых стратегий будет избрана альтернатива c , наименее выгодная первому игроку с правом решающего голоса! Это право оказывает первому игроку «медвежью услугу», поскольку позволяет остальным игрокам предвидеть его выбор и распорядиться своими более скромными возможностями наиболее выгодным для себя образом. Обобщим результаты проведенного анализа. Определение 3.1 Для игры в нормальной форме G = N , {X i }i∈N , {ui }i∈N

последовательное исключение доминируемых стратегий означает построение последовательностей X i0 ⊃ X i1 ⊃ ... ⊃ X it ⊃ X it +1 ⊃ ... для всех i ∈ N ,

(

)

где X it +1 = Д i X tj , j ∈ N . Говорят, что игра G разрешима по доминированию, если существует целое

t такое, что

∀xi , yi ∈ X it

∀xiˆ ∈ X iˆt

ui ( xi , xiˆ ) = ui ( yi , xiˆ ) .

В этом случае X 1t × X 2t × ...× X nt называется множеством сложных равновесий в игре G .

12

Выбор ситуации, принадлежащей множеству сложных равновесий, можно принять в качестве решения игры (принципа оптимальности) при сложном поведении. Сложное равновесие обобщает равновесие в доминирующих стратегиях в следующем смысле. Лемма 3.1 Если в игре G множество D равновесий в доминирующих стра-

тегиях не пусто, то игра G разрешима по доминированию и D есть множество сложных равновесий. Доказательство сразу следует из леммы 1.2. Если у игрока i есть доминирующая стратегия, то Di является i -й компонентой множества сложных равновесий, если последнее существует. Пример 3.2 Игра «Пиратский дележ».

Пираты делят 100 слитков золота следующим образом. Сначала самый старший пират предлагает произвольный дележ по своему выбору. Если хотя бы половина пиратов (включая его самого) согласна с этим предложением, то оно считается принятым и игра заканчивается. В противном случае (если большинство против) старший пират исключается (вполне возможно, физически) из дальнейшего обсуждения и следующий по старшинству пират предлагает свой способ дележа среди оставшихся (n − 1) пиратов. Если и это предположение отвергается большинством голосов, то процедура повторится уже для (n − 2 ) пиратов, и так далее. Опишем сложное поведение пиратов. Если n = 2 , то старший пират забирает все 100 слитков, поскольку младший пират не составляет большинства. При

n = 3 старший пират может предложить дележ, дающий 99 слитков ему и 1 слиток младшему пирату. Младший пират вынужден соглашаться с этим «братским» предложением, поскольку иначе он попадает в рассмотренную ситуацию при

n = 2 и не получает ничего. Средний пират со своим единственным голосом в обсуждении не участвует.

13

Если n = 4 (4, 3, 2,1) , то старший пират (4 ) рассуждает следующим образом: «Если мое предложение будет отвергнуто, то три оставшихся пирата поделят добычу, как в предыдущей ситуации: (99, 0,1) . Поэтому я должен предложить такой дележ, который хотя бы одному из них был выгоднее этого, а мне давал наибольшую возможную долю». Единственным решением этой задачи является дележ

(99, 0,1, 0), в которой старший пират (4) отдает всего один слиток второму пирату. Далее в таблице 3.1 приведены решения для произвольного числа пиратов, найденные по индукции. Таблица 3.1 Решение игры «Пиратский дележ» Число пиратов n 1

100

2

0

100

3

1

0

99

4

0

1

0

99

5

1

0

1

0

98

6

0

1

0

1

0

98

...

...

...

...

...

...

2 p +1

1

0

...

0

2p + 2

0

1

...

1

1

2

3

4

...

2p

2 p +1

2p + 2

...

...

...

...

...

1

0

1

0

100 − p

0

1

0

1

0

5

6

100 − p

Для игры в нормальной форме не известны достаточные условия разрешимости по доминированию. Для получения этих условий необходимо использовать так называемую развернутую форму игры. Пример 3.3 Игра «Выборы с правом вето».

Множество N = {1, 2, 3} игроков выбирает одного кандидата из множества

A = {a, b, c, d } . Правило голосования следующее: начиная с первого игрока, каждый игрок последовательно вычеркивает одного из кандидатов. Единственный оставшийся кандидат считается избранным. 14

Функции выигрыша игроков удовлетворяют условию

u1 (d ) < u1 (c ) < u1 (b ) < u1 (a ),

u 2 (c ) < u 2 (d ) < u 2 (a ) < u2 (b ),

(5)

u3 (c ) < u3 (a ) < u3 (b )
Удобно представить игру с помощью графа (рисунок 1). Вето на

a

Вето на

Вето на

b

d

Вето на

3

3

Вето на d

c

2

Вето на c

Вето на

Вето на

2

2

. . .

3

d

с

2

d

3

1

b

3

. . .

3

3

3

3

3

c

Вето на

3

3 Вето

a

на

d

b

b

c

...

...

...

...

...

...

...

a

...

b

Рисунок 1 – Дерево игры в развернутой форме «выборы с правом вето» Отметим, что в силу гипотезы полной информированности каждый игрок может построить изображенное на рисунке 1 дерево игры. Теперь обратим внимание на вершины дерева, соответствующие ходу третьего игрока. В каждой вершине у него две возможности: вычеркнуть одного из двух оставшихся кандидатов, определяя тем самым единственного победителя. Поскольку предпочтение третьего игрока однозначно задано (рисунок 1), то его выбор также можно однозначно предсказать, сократив тем самым число уровней дерева (рисунок 2). Вето на

a

Вето на

Вето на

b

2

Вето на

d

d

Вето на

c

b

1

b

Вето на

Вето на

с

2

d d

d

d

2 a

d

d

2 b

b

Вето на

a

c

b

Рисунок 2 – Сокращенное дерево игры «выборы с правом вето» (шаг 1) Теперь очевидно, что можно однозначно предсказать результат рационального выбора игрока 2, поскольку любому его вето соответствует уже не ход третьего

15

игрока, а один из кандидатов. Поэтому ход второго игрока можно заменить результатом его выбора (рисунок 3). Вето на

a

Вето на

b

b

1

Вето на

Вето на

с

a

d

b

b

Рисунок 3 – Сокращенное дерево игры «выборы с правом вето» (шаг 2) Теперь можно предсказать выбор первого игрока, находящегося в наиболее выгодной позиции: рисунок 3 однозначно определяет итоговый результат любого его действия. Очевидно, в силу рисунка 1 первый игрок наложит вето на кандидата b , обеспечивая избрание наиболее выгодного для себя кандидата a . Обобщим результаты рассмотренного примера. Определение 3.2 Конечное дерево есть пара Г = (M , σ ) , где M – конечное

множество вершин, а отображение σ сопоставляет каждой вершине ее ближайшего предшественника так, что: •

существует единственная начальная вершина m0 : σ(m0 ) = m0 ;

•

существует l ∈ Z :∀m ∈ M σ l (m ) = mo ,

наименьшее такое l называется длиной дерева Г . Вершина m такая, что σ −1 (m ) = Ø, называется финальной вершиной Г ; множество финальных вершин обозначим Т (М ) . Для нефинальных вершин m множество σ −1 (m ) состоит из преемников m (следующих за m вершин). Определение 3.3 Игрой в развернутой форме со множеством игроков N

называется следующая совокупность: •

конечное дерево Г = (M , σ ) ;

•

разбиение (M i )i∈N множества M \ Т (M ) ;

•

для каждого игрока i ∈ N функция выигрыша ui :Т (M ) → R .

16

Разбиение (M i )i∈N определяет, какой игрок ходит в каждой конкретной нефинальной вершине. Если m0 ∈ M i , то игра начинается с того, что игрок i должен выбрать вершину m1 из множества σ −1 (m0 ). Если m1 ∈ Т (М ) , то игра заканчивается и выигрыши игроков суть u i (m1 ), i ∈ N , иначе игрок j ∈ N , для которого

m1 ∈ M j выбирает вершину m 2 ∈ σ −1 (m1 ) , и т. д. Определение 3.4 Пусть G = M , σ; M i , ui ; i ∈ N – игра в развернутой форме такая, что для ∀m, m′ ∈ Т (M )

(∃ i ∈ N :ui (m ) = ui (m′)) ⇒ (∀j ∈ N

u j (m ) = u j (m′))

(6)

Пусть L(М ) – множество вершин, для которых все последующие вершины являются финальными:

m ∈ L(M ) ⇔ σ −1 (m ) = Т (M ). Тогда игре G соответствует редуцированная игра G * = M * , σ* ; M i* ; i ∈ N , в которой: •

множество вершин определяется равенством M * = M \ Т 0 (М ) ,

где Т 0 (М ) = {m ∈ Т (M ): σ(m ) ∈ L(M )}; •

отображение σ* есть сужение σ на M * ;

•

финальные вершины дерева M * , σ* таковы:

(

)

( )

Т М * = L(M ) U {Т (М ) \ Т 0 (М )};

{

( )}

•

M i* = M i I M * \ Т М * ;

•

функция выигрыша ui* имеет вид: если m ∈ Т (М ) \ Т 0 (М ) , то ui* (m ) = ui (m ) ; если m ∈ L(М ) и m ∈ M j , то ui* (m ) = ui (m j ) ,

где u j (m j ) = sup

m′∈σ −1 ( m )

u j (m′) . 17

Алгоритм Куна состоит из последовательных редукций игры G (примером служит игра «выборы с правом вето»). После этих l редукций дерево игры M *l , σ*l имеет длину 0, т.е. M *l = {m0 }, σ*l – тождественное отображение. Обозначим через β i = ui*l (m0 ) – значение выигрыша игрока i в G *l Теорема Куна

Пусть G = M , σ; M i , ui ; i ∈ N – игра в развернутой форме, для которой выполнено условие (формула (6)). Тогда игра G , рассматриваемая как игра в нормальной форме, разрешима по доминированию, а выигрыши (β i )i∈N , соответствующие сложному равновесию, задаются алгоритмом Куна. Доказательство: [3, c. 47-48].

Упражнение 3.5 Получить с помощью алгоритма Куна сложное равновесие для игры «выборы с правом вето» для следующих структур предпочтений игроков: а) u1 (a ) < u1 (b ) < u1 (c ) < u2 (d ),

u 2 (b ) < u2 (c ) < u 2 (a ) < u 2 (d ), u3 (c ) < u3 (b ) < u3 (a )
u2 (d ) < u2 (a ) < u2 (c ) < u2 (b ), u3 (a ) < u3 (b ) < u3 (d )
18

4 РАВНОВЕСИЕ ПО ШТАКЕЛЬБЕРГУ Рассмотрим иерархическую игру двух лиц в нормальной форме

G = X 1 , X 2 , u1 , u 2 , где

(7)

индексом 1 обозначен ведущий игрок (Ведущий), а индексом 2 – подчиненный (Ведомый), в соответствии с рисунком 4. 1

u1 ( x1 , x2 )

2

x1 ∈ X 1 u2 ( x1 , x2 ) x2 ∈ X 2

Рисунок 4 – Иерархическая игра двух лиц Иерархия игроков означает право первого хода Ведущего. В силу постулата экономической рациональности иерархия гарантирует Ведущему выбор Ведомым своей стратегии из множества «оптимальной реакции».

⎫ ⎧ R2 ( x1 ) = ⎨ x2 ∈ X 2 : u2 ( x1 , x2 ) = sup u 2 ( x1 , y2 )⎬ y 2 ∈X 2 ⎭ ⎩

(8)

Это обстоятельство весьма существенно: поскольку ∀x1 ∈ X 1 R2 ( x1 ) ⊆ X 2 , а во многих случаях множество R2 ( x1 ) состоит из единственной точки, то иерархия позволяет Ведущему предвидеть рациональный выбор Ведомого и использовать это в своих интересах. Обозначим

ВR2 = {( x1 , x2 ) ∈ X 1 × R2 ( x1 )}

(9)

– график оптимальных реакций Ведомого на выбор Ведущим стратегии x1 . Наиболее распространенной концепцией оптимальности решения иерархической игры двух лиц (рисунок 4) является 1-равновесие по Штакельбергу

(x1 , x2 ) ∈ BR2 :u1 (x1 , x2 ) =

sup

( y1 , y2 )∈BR2

u1 ( y1 , y2 )

(аналогично определяется 2-равновесие по Штакельбергу). 19

(10)

Заметим, что величину S1 выигрыша Ведущего в равновесии по Штакельбергу можно определить как

S1 = sup

sup u1 ( y1 , y2 ) ,

(11)

y1∈X 1 y2 ∈R2 ( x1 )

что соответствует предположению о благожелательности Ведомого по отношению к Ведущему. Иначе говоря, если множество R2 ( x1 ) содержит более одного элемента, то предполагается выбор Ведомым наиболее благоприятной для Ведущего стратегии из этого множества (для самого Ведомого все стратегии из

R2 ( x1 ) эквивалентны, x1 ∈ X 1 ). Таким образом, концепция равновесия по Штакельбергу основана на «оптимистической» оценке Ведущим мотивов поведения Ведомого – противоположный «пессимистический» подход лежит в основе распространенного в отечественной литературе принципа гарантированного результата Ю.Б. Гермейера [1]. Максимальный гарантированный результат Ведущего в иерархической игре по формуле (7) есть

γ 1 = sup

inf

y1∈ X 1 y 2 ∈R2 ( x1 )

u1 ( y1 , y 2 ) ,

(12)

Пример 4.1 Рассмотрим игру «Услуга за услугу» из упражнения 2.6 как иерархическую. Тогда S1 = S 2 = 1 , γ 1 = γ 2 = 0 .

Упражнение 4.1 Сравнить величины γ 1 и S1 с величиной α1 гарантированного выигрыша в игре двух лиц (определение 2.5) и дать интерпретацию полученному результату.

Упражнение 4.2 Найти 1-равновесие по Штакельбергу в следующих играх: а)

B1 А1 А2

5

B2

б)

B1

5 3

4

А1

4 6

5

А2

2

5

B2 2

3 2

3 3

4

Отличаются ли в этих играх величины S1 и γ 1 ? 20

5

5 РАВНОВЕСИЕ ПО НЭШУ Предположим, что игрок i , рассматривая возможность выбора стратегии yi вместо xi , не учитывает реакции остальных игроков на это изменение, т.е. считает, что выбор xiˆ останется неизменным. Это предположение вполне естественно при большом числе игроков (отдельная фирма i в экономике, отдельный избиратель i в политике и т.п.).

Определение 5.1 Ситуация x есть равновесие по Нэшу в игре

G = N , {X i }i∈N , {ui }i∈N , если ∀i ∈ N ∀yi ∈ X i ui ( x ) ≥ ( yi , xiˆ )

(13)

Упражнение 5.1 Найти равновесие по Нэшу в играх «Дилемма заключенного», «Семейный спор», «Услуга за услугу».

Определение 5.2 Ситуация x игры G = N , {xi }i∈N , {u}i∈N называется индивидуально рациональной, если

∀i ∈ N

u i ( x ) ≥ α i = sup inf ui ( yi , y iˆ ) . yi ∈ X i yiˆ ∈ X iˆ

(14)

Обозначим через IR множество индивидуально рациональных ситуаций в игре G .

Лемма 5.1 Все равновесия по Нэшу индивидуально рациональны. Доказательство:

x ∈ NE ⇒ u i ( x ) ≥ u i ( yi , xiˆ ) ∀y i ∈ X i ⇒ ⇒ u i ( x ) ≥ sup ui ( yi , xiˆ ) ≥ sup inf u i ( yi , yiˆ ) = α i ⇒ x ∈ IR yi ∈ X i

yi∈X i yiˆ∈X iˆ

Если равновесные по Нэшу ситуации также оптимальны по Парето, то в игре возникает борьба за лидерство, что затрудняет выбор решения.

Пример 5.1 Игра «Дуэль».

У У Н

Н

1

3 1

0

0 2

3

2 21

Легко показать, что в этой игре NE = {(H , У ), (У , H )}, причем обе эти ситуации также оптимальны по Парето. Поэтому каждый игрок стремится реализовать «наступательную» стратегию H , но если он видит такую же решимость со стороны противника, то вынужден «уступить» (выбрать стратегию У ) во избежание попадания в ситуацию (H , H ) . Очевидно, борьба за лидерство возникает также в игре «Семейный спор».

Определение 5.3 В игре G имеет место борьба за лидерство, если не существует такой ситуации x , для которой

ui ( x ) ≥ S i , i = 1, 2 ,

(15)

где Si – выигрыш игрока i в равновесии по Штакельбергу (формула (11)).

Лемма 5.2 Пусть пара G имеет по крайней мере две оптимальных по Парето и равновесных по Нэшу ситуации x1 , x 2 с различными векторами выигрышей:

(u (x ), u (x )) ≠ (u (x ), u (x )), 1

1

2

1

1

2

2

2

(16)

Тогда в игре G имеет место борьба за лидерство. Доказательство: Заметим, что NE = BR1 I BR2 . Тогда по определению величины Si имеем

x ∈ NE ⇒ u i ( x ) ≤ Si , i = 1, 2 . Если в игре G нет борьбы за лидерство, то найдется ситуация x , для которой справедлива формула (15), что означает

( ) u (x ) ≤ S

ui x1 ≤ Si ≤ ui ( x ), i

2

i

≤ ui ( x ), i = 1, 2 .

Поскольку x1 и x 2 оптимальны по Парето, то все четыре неравенства должны обратиться в равенства, что противоречит предположению формулы (16).

22

Теорема 5.1 Пусть для всех i ∈ N множества X 1 конечны. Если игра G = N , {X i }i∈N , {ui }i∈N разрешима по доминированию, то любое сложное равно-

весие является равновесием по Нэшу. Доказательство: [3, c. 75]. Обратное утверждение неверно: равновесие по Нэшу может оказаться доминируемой стратегией.

Пример 5.2

L Т М B

C

1

R

0 1

0

0 1

1 0

1

1 0

0 0

0

1 1

1

0

В этой игре (Т , L ) – единственная ситуация, равновесная по Нэшу. Однако для первого игрока стратегия Т доминируется стратегией B , а для второго игрока стратегия L доминируется стратегией R . После исключения доминируемых стратегий остается игра с нулевой суммой, в которой нет седловой пары.

Упражнение 5.2 Игра двух лиц G = X 1, X 2 , u1 , u 2 называется почти несущественной, если ∀x, y ∈ IR ui ( x ) =u i ( y ), i = 1,2 . Доказать, что в такой игре пара

(x1 , x2 ) ∈ P1 × P2

является равновесием по Нэшу, оптимумом по Парето и равнове-

сием по Штакельбергу для i = 1, 2 .

Теорема 5.2 Нэша. Пусть для любого i ∈ N множество стратегий X i выпукло и компактно, а функция выигрыша ui непрерывна и вогнута по xi на X i для всех xiˆ ∈ X iˆ . Тогда множество NE равновесий по Нэшу игры G = N , {X i }i∈N , {ui }i∈N непусто и компактно. Доказательство: [3, c. 78-79]. 23

Для вычисления множества NE необходимо решить систему уравнений

( )

(

)

u i x * = max ui xi , xi*ˆ . xi ∈ X i

(17)

Если xi – внутренняя точка множества X i и функция ui дифференцируема по xi , то условия (формула (17)) эквивалентны условиям

( )

∂ui x* = 0, i ∈ N . ∂xi

(18)

Упражнение 5.3 Найти равновесие по Нэшу в следующих играх. Будут ли они оптимальны по Парето? а)

B1 А1 А2

3

B2

б)

B1

1 1

1

А1

2 1

2

А2

1

5

B2 8

2 8

2 2

5

5

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

Пример 5.3 Устойчивость в дуополии Курно с назначением выпусков. Два игрока поставляют на рынок некоторые количества x1 и x2 одного и того же товара, цена на который определяется как p( x1 , x2 ) = 1 − x1 − x2 . Рассмотрим два различных предположения о функции затрат: а) постоянные затраты на выпуск единицы продукции при увеличении масштабов производства: затраты на производство y единиц равны

y для обоих иг2

роков; б) убывающие затраты на выпуск единицы продукции при увеличении масштабов производства: затраты на производство y единиц равны

обоих игроков. 24

y 3y2 для − 2 4

Максимальные производственные возможности обоих игроков равны

1 2

(поэтому цена и затраты неотрицательны). В случае а) получаем следующую игx ⎡ 1⎤ ру: X 1 = X 2= ⎢0, ⎥ , ui ( x1 , x2 ) = xi (1 − x1 − x2 ) − i , i = 1, 2 . 2 ⎣ 2⎦

Как отмечалось в доказательстве леммы 5.2, NE = BR1 I BR 2 . Для нахождения множества R2 ( x1 ) нужно найти множество точек максимума функции

u 2 ( x1 , x2 ) по x2 при фиксированном x1 , т.е. решить уравнение откуда x2 =

∂u2 ( x1 , x2 ) = 0, ∂x2

1 x1 − – это и есть множество R2 ( x1 ) . 4 2

1 x ⎫ ⎧ Аналогично R1 ( x2 ) = ⎨ x1 ∈ X 1 : x1 = − 2 ⎬ . Поэтому множество NE = BR1 I BR 2 4 2⎭ ⎩ есть множество решений системы уравнений 1 x2 ⎧ x = − 1 ⎪⎪ 4 2 , ⎨ ⎪ x2 = 1 − x1 ⎪⎩ 4 2

⎧⎛ 1 1 ⎞⎫ откуда находим единственную ситуацию равновесия по Нэшу NE = ⎨⎜ , ⎟⎬ . ⎩⎝ 6 6 ⎠⎭

(

)

Процедура нащупывания по Курно начинается из произвольной ситуации x10 , x20 , причем каждый игрок последовательно использует наилучший ответ на стратегию партнера:

(x , x ) → (x , x )∈ BR → (x , x )∈ BR 0 1

0 2

1 1

0 2

1

1 1

1 2

2

(

)

(

)

→ ... → x1t , x2t −1 ∈ BR1 → x1t , x2t ∈ BR2 → ... (19)

На рисунке 5а) изображены две последовательности вида (формула (19)). Легко убедиться, что для любой начальной ситуации последовательность (форму-

⎛1 1⎞ ла (19)) сходится к ситуации ⎜ , ⎟ , которую естественно назвать устойчивым ⎝6 6⎠ равновесием по Нэшу. 25

X2

X2

1

1

2

1 4

2

BR1

BR1

⎛1,1⎞ ⎜6 6⎟ ⎝ ⎠

1 4

BR2

BR2

0

0 1

1

4

2

X

1

а)

1

1

4

2

X

1

б)

Рисунок 5 – Процедура нащупывания по Курно: а) устойчивое равновесие по Нешу; б) локально устойчивое и неустойчивое равновесие по Нэшу. Теперь рассмотрим случай б) убывающих затрат на выпуск единицы продукции. Получаем игру в нормальной форме 1 3 ⎡ 1⎤ X 1 = X 2 = ⎢0, ⎥, ui ( x1 , x2 ) = x i (1 − x1 − x2 ) − xi + xi2 , i = 1, 2 . 2 4 ⎣ 2⎦

Упражнение 5.4 Показать, что в этой игре 1 ⎧1 x ≤ ≤ , 0 , i ⎪⎪ 2 4 R j ( xi ) = ⎨ ⎪1 − 2 xi , 1 ≤ xi ≤ 1 , ⎪⎩ 4 2

i, j = 1, 2 .

⎧⎛ 1 1 ⎞ ⎛ 1 ⎞ ⎛ 1 ⎞⎫ Тогда получаем NE = BR1 I BR2 = ⎨⎜ , ⎟, ⎜ , 0 ⎟, ⎜ 0, ⎟⎬ . Из рисунка 5б видно, что ⎩⎝ 3 3 ⎠ ⎝ 2 ⎠ ⎝ 2 ⎠⎭

(

)

⎛1 1⎞ для любой ситуации x10 , x20 ≠ ⎜ , ⎟ последовательность (формула (19)) всегда ⎝ 3 3⎠ 26

⎛1 ⎞ ⎛ 1⎞ ⎛1 1⎞ сходится к ⎜ , 0 ⎟ или ⎜ 0, ⎟ . В этом случае естественно говорить, что ⎜ , ⎟ – ⎝2 ⎠ ⎝ 2⎠ ⎝ 3 3⎠ ⎛ 1⎞ ⎛1 ⎞ неустойчивое равновесие по Нэшу, а ⎜ 0, ⎟ и ⎜ , 0 ⎟ – локально устойчивые. ⎝ 2⎠ ⎝2 ⎠ Определение 5.4 Пусть в игре в нормальной форме G = N , {X i }i∈N , {ui }i∈N для всех i ∈ N и всех xiˆ ∈ X iˆ существует единственная функция ri (xiˆ ) такая, что

(ri (xiˆ ), x iˆ ) ∈ BRi .

(20)

С любой ситуацией x 0 ∈ X связана процедура одновременного нащупывания по Курно, т.е. последовательность

( )

xit =r i xit −1 , i ∈ N , t = 1, 2, ...

(21)

Равновесие по Нэшу x* устойчиво в игре G , если для любой начальной ситуации

x 0 ∈ X последовательность (формула (21)) сходится к x* . Равновесие по Нэшу локально устойчиво в G , если для каждого i ∈ N существует окрестность Vi точки xi* такая, что на V = V1 × ...× Vn выполнено (формула (20)) и ситуация x* устойчива в усеченной игре N , {Vi }i∈N , {ui }i∈N .

Упражнение 5.5 Для заданного порядка игроков N = {1, 2, ... , n} процедурой

{1, 2, ... , n} – последовательного нащупывания по Курно, начинающейся из

x 0 , на-

зывается последовательность x 0 , x1 , ... , x t ,

(

)

где xit = ri x1t , ... , xit−1 , xit+−11 , ... , xnt −1 , i ∈ N , t = 1, 2, ... Равновесие по Нэшу x* называется {1, ... , n} – устойчивым, если для любой начальной ситуации x 0 процедура {1, ... , n} – последовательного нащупывания по Курно, начинающаяся из x 0 , сходится к x* .

27

Рассмотрим игру трех лиц

u1 ( x ) = −( x1 − x2 ) , 2

2

X i = R, i = 1, 2, 3,

⎛ x3 ⎞ u 2 ( x ) = −⎜⎜ x2 − ⎟⎟ , 3⎠ ⎝ u3 ( x ) = −(4 x1 − 3 x2 − x 3 ) . 2

Единственным равновесием по Нэшу является (0, 0, 0) . Доказать, что оно не

{1, 2, 3}

– устойчиво, но {2,1, 3} – устойчиво. Будет ли оно устойчивым в смысле

определения 5.4?

28

6 СТАБИЛЬНЫЕ СОГЛАШЕНИЯ До сих пор явный обмен информацией между игроками отсутствовал, теперь он разрешается. После предварительных переговоров, которые могут включать взаимное выяснение функций выигрыша, торговлю и иные способы взаимодействия, игроки приходят к некоторому соглашению x . Как обеспечить стабильность этого соглашения? Наиболее простой случай – ситуация, в которой ни отдельным игрокам, ни подмножествам игроков К ⊆ N (коалициям игроков) невыгодно отступать от согласованных стратегий.

Определение

6.1

Для

данной

игры

в

нормальной

форме

G = N , {X i }i∈N , {ui }i∈N ситуация x* называется сильным равновесием,

если ∀K ⊆ N ∀xK ∈ X K не выполнено

( u (x

) ( ) ) > u (x ).

∀i ∈ K ui xK , x*N \ K ≥ ui x* , ∃i ∈ K

(

i

* K , xN \ K

i

*

(22)

)

Здесь xk = xi1 , ... , xik , K = {i1 , ... , ik } – набор стратегий участников коалиции

K. Обозначим через SE множество сильных равновесий в G . Оно может оказаться пустым.

Упражнение 6.1 Доказать, что SE ⊆ N I PO .

Указание. Рассмотреть случаи K = { i } и K = N .

Упражнение 6.2 n игроков должны поделить доллар. Игроки сдают свои заявки арбитру, который удовлетворяет их, если они совместимы; в противном случае ни один игрок ничего не получает:

29

X i = [0,1] ; n ⎧ , x x j ≤ 1, ∑ ⎪ i ui ( x ) = ⎨ j =1 ⎪0, иначе, i ∈ N . ⎩ n ⎧ ⎫ Доказать, что SE = ⎨ x ∈ X : ∑ xi = 1⎬ . ⎩ i =1 ⎭

Упражнение 6.3 Два владельца магазинов хотят разместить свои торговые точки на одной улице (отрезок [0,1] ). Они предлагают дополняющие товары, поэтому им выгодно расположить магазины поближе друг к другу. В то же время, первый игрок желает разместить магазины как можно ближе к точке 0 , второй игрок – как можно дальше от точки 0 . Поэтому игру можно записать в виде X 1 = X 2 = [0,1] , u1 ( x1 , x2 ) = α1 x1 − x1 − x2 , u 2 ( x1 , x2 ) = α 2 x1 − x1 − x2 , α1 < 0 < α 2 , α i ≤ 1, i = 1, 2 .

Доказать, что SE = {( x1 , x2 ): x1 = x2 }. Таким образом, если кооперативное соглашение удовлетворяет определению сильного равновесия, то оно обеспечивает свою стабильность «автоматически». Конечно, это очень сильное требование, и выполняется оно редко. В общем случае для обеспечения стабильности игрокам приходится использовать взаимные угрозы как реакцию на возможное отклонение от соглашения. Интересно отметить, что в теории игр угрозы рассматриваются как механизм кооперации.

Определение 6.2 Пусть G = N , {X i }i∈N , {ui }i∈N – игра в нормальной форме. Сценарием предостережения называется набор x; ξ iˆ , i ∈ N , где x ∈ X – произвольная игровая ситуация,

ξ iˆ – угроза игроку i (i ∈ N ) , т. е. отображение ξ iˆ : X i → X iˆ такое, что ξ iˆ ( xi ) = xiˆ

∀yi ∈ X i \ {xi } ui ( yi , ξ iˆ ( yi ) ) ≤ ui ( x ) 30

(23)

Таким образом, если игрок i выбирает согласованную стратегию xi , то и все остальные игроки придерживаются согласованных стратегий xiˆ , в противном случае применение угрозы ξ iˆ делает для игрока i отклонение yi ∈ X i \ {xi } невыгодным.

Пример 6.1 Игра «Торг». П В Н

О

2

0 1

1

0 0

2

0

Первый игрок (продавец) может назначить на товар высокую цену (стратегия В) или низкую цену (стратегия Н). Второй игрок (покупатель) может совершить покупку (стратегия П) или отказаться от нее (стратегия О). Исход (B, H ) является равновесием в доминирующих стратегиях (соответственно, тем более равновесием по Нэшу) и оптимален по Парето. При запрете на обмен информацией этот исход окажется бесспорным итогом игры. При разрешении обмена информацией у покупателя возникает убедительная угроза: ξ 2 (B ) = О, ξ 2 (Н ) = П , позволяющая стабилизировать более выгодную для покупателя ситуацию (Н , П ) . Продавцу придется согласиться на выбор стратегии Н под угрозой отказа от покупки. Однако следует отметить, что реализация угрозы ξ 2 (B ) = О невыгодна обоим игрокам, поэтому она на самом деле носит характер блефа. Подлинно действенная угроза не должна вызывать сомнений в своей реализации.

Определение 6.3 Дележом в игре G = N , {X i }i∈N , {ui }i∈N называется оптимальная по Парето индивидуально рациональная ситуация. Обозначим через I множество дележей в игре G .

Лемма 6.1 Пусть для любого i ∈ N множество X i компактно, а функция ui непрерывна. Тогда множество I непусто. 31

Доказательство: Обозначим через IR непустое компактное подмножество индивидуально рациональных ситуаций игры G . Выберем элемент x ∈ IR , максимизирующий

∑ ui

на IR . Пусть ситуация y доминирует x по Парето. Тогда y ∈ IR и

i∈N

∑ ui (x ) < ∑ ui ( y ) . Таким образом,

i∈N

x ∈ PO , что доказывает лемму.

i∈N

Множество дележей I является максимальной областью для переговоров о достижении кооперативного соглашения в игре G . Действительно, если ситуация x не принадлежит I , то либо x ∉ IR , и тогда обязательно найдется хотя бы один

недовольный игрок, получающий меньше своего гарантированного выигрыша α i , либо x ∉ PO , и тогда выигрыш хотя бы одного игрока в ситуации x может быть строго улучшен без ущерба для остальных игроков. Поэтому дележи из I и только они могут служить основой для построения сценария предостережений.

Лемма 6.2 Пусть в игре двух лиц x i – дележ, для которого выполнено условие

( )

ui x i = sup {ui ( x ): u j ( x ) ≥ α j };

ξ i – агрессивная угроза игрока i , т.е

( )

⎧ξ i xij = xij , ⎪ ⎨∀y ∈ X \ x i j j ⎪⎩ j

{ } u (y , ξ ( y )) = inf u (y , y ); j

j

i

i

yi ∈X i

j

j

i

ξ j – предупреждение игрока j игроку i , т е. функция вида

( )

ξ j xij = x ij ,

{ }

∀yi ∈ X i \ xij u j ( yi , ξ j ( yi ) ) = sup u j ( yi , y j )

(

y j ∈X j

)

Тогда x i , ξ i , ξ j – сценарий предостережений. Доказательство: [3, c. 158-159].

32

.

(24)

Предупреждение (формула (24)) является действенной угрозой, поскольку ее применение выгодно предупреждающему игроку, т.е. он не нуждается в блефе.

Определение 6.4 α – ядром в игре G = N , {X i }i∈N , {ui }i∈N называется подмножество Cα ситуаций x α таких, что ∀K ⊆ N ∀xK ∈ X K ∃x N \ K ∈ X N \ K одновременно невозможно

( ) ) > u (x ).

∀i ∈ K ui ( xK , x N \ K ) ≥ ui x α , ∃i ∈ K u i ( x K , x N \ K

i

α

Таким образом, для любой потенциальной стратегии отклонения xK коалиции K от согласованной стратегии xKα найдется стратегия x N \ K дополнительной коалиции N \ K (которую можно трактовать как угрозу ξ N \ K : X K → X N \ K ), делающая коалиционное отклонение xK невыгодно для K .

Упражнение 6.4 Доказать, что Cα ⊆ I . Указание. Рассмотреть коалиции K = N и K = { i } , i ∈ N .

Упражнение 6.5 Дилемма трех заключенных. У каждого из трех игроков есть агрессивная стратегия ( A) и миролюбивая стратегия (M ) . Ниже перечислены возможные варианты выигрышей игроков:

(M , M , M ) → (2, 2, 2) ( A, M , M ) → (3,1,1) ( A, A, M ) → (2, 2, 0) ( A, A, A) → (1,1,1) . Доказать следующие утверждения: 1) равновесие в доминирующих стратегиях доминируемо по Парето; 2) не существует сильного равновесия; 3) имеется ровно четыре дележа; 4) α – ядро совпадает со множеством дележей.

33

Упражнение 6.6 Каждый из трех игроков может выбрать любого игрока, в т. ч. самого себя. Примеры выигрышей приведены ниже, остальные восстанавливаются в силу симметрии:

(1, 2, 3) → (0, 0, 0) (1, 2,1) → (0, 0, − 1) (1, 3,1) → (0, 0, 0) (1,1,1) → (3,1,1) (1, 3, 2) → (0, 2, 2) (2, 3,1) → (2, 2, 2) (2, 3, 2) → (− 1, 3, 3) . Доказать следующие утверждения: 1) в игре нет сильного равновесия; 2) каждый из пяти дележей игры относится к одному из типов (1,1,1) или

(2, 3,1) ; 3) α – ядро состоит из двух исходов (2, 3,1) .

Определение 6.5 β – ядром в игре G = N , {X i }i∈N , {ui }i∈N

называется под-

множество Cβ ситуаций xβ таких, что ∀K ⊆ N ∃x N \ K ∈ X N \ K ∀xK ∈ X K . одновременно невозможно

( ) ) > u (x ).

∀i ∈ K ui ( xK , x N \ K ) ≥ ui x β , ∃i ∈ K u i ( x K , x N \ K

i

β

Сравнивая определения 6.4 и 6.5, можно увидеть, что требование β стабильности является более сильным: в этом случае у дополнительной коалиции N \ K имеется «универсальная» угроза x N \ K , делающая невыгодным любое потенциальное отклонение xK коалиции K . Таким образом, для реализации угрозы коалиции N \ K даже не обязательно знать, какое отклонение пыталась приме34

нить коалиция K , в отличие от случая α -стабильности, где по каждому конкретному отклонению xK подбирается «индивидуальная» угроза x N \ K . С учетом определений 6.1 и 6.3 получаем следующую последовательность вложений для любой игры в нормальной форме: SE ⊆ Cβ ⊆ Cα ⊆ I . Ограничимся теперь рассмотрением игр двух лиц G = X 1 , X 2 , u1 , u 2 с конечным множеством стратегий.

Лемма 6.3 Справедливы следующие утверждения: а) Cα = I ; ⎧⎪ x ∈ PO б) x ∈ Cβ ⇔ ⎨u ( x ) ≥ β = inf sup u ( y , y ), i = 1, 2. i i i j y j ∈ X j y ∈X ⎪⎩ i i i

Упражнение 6.7 Доказать лемму 6.3, используя определения 6.4, 6.5. Определение 6.6 γ -ядром игры G называется подмножество Cγ дележей

(

)

x γ , для которых существует сценарий предостережений xγ , ξ i , ξ j , где угрозы ξ i , ξ j суть предупреждения:

{ } γ

∀x j ∈ X j \ x j

( )

⎧u j (ξ i (x j ), x j ) ≤ u j xγ ⎪ ⎨u (ξ (x ), x ) = sup u (x , x ). ⎪⎩ i i j j xi ∈X i i i j

Лемма 6.4 Пусть функции ui взаимно однозначны, i = 1, 2 . Тогда Cγ состоит из таких оптимальных по Парето исходов x , для которых ui ( x ) ≥ Si , i = 1, 2 . Замечание. Предположение о взаимной однозначности можно опустить, если Si заменить на γ i (см. формулу (11), формулу (12)). Доказательство: [3, с. 177-178]. С учетом лемм 6.3 и 6.4 и определения 6.3 можно дать критерии принадлежности α − , β − и γ − ядру в игре двух лиц следующим удобным образом:

35

x α ∈ Cα ⇔

⎧ x α ∈ PO, ⎪ ⎨u x α ≥ α = sup inf u (x , x ), i, j = 1, 2; i i i j ⎪⎩ i xi ∈X i x j ∈X j

x β ∈ Cβ ⇔

⎧ x β ∈ PO, ⎪ ⎨u x β ≥ β = inf sup u (x , x ), i, j = 1, 2; i i i j ⎪⎩ i x j ∈X j x ∈ X i i

( ) ( )

⎧ xγ ∈ PO, ⎪ xγ ∈ Cγ ⇔ ⎨ u xγ ≥ γ i = sup inf ui (xi , x j ), i, j = 1, 2; ⎪⎩ i xi ∈X i x j ∈R j ( xi )

( )

или

⎧ γ ⎪ x ∈ PO, ⎪ γ ⎨ui x ≥ Si = sup sup ui (xi , x j ), xi ∈X i x j ∈R j ( xi ) ⎪ ⎪u взаимно однозначны, i, j = 1, 2. ⎩ i

( )

xγ ∈ Cγ ⇔

Упражнение 6.8 Два игрока выбирают натуральное число из множества

{1, 2,K,10}. Пусть выбраны

x1 , x2 такие, что x1 + x2 = 10 , тогда выигрыш игрока i

равен xi , i = 1, 2 . В оставшихся случаях вектор выигрышей есть (4, 0) , если x1 + x2 четно, и (0, 4 ) , если x1 + x2 нечетно. Найти Cα , Cβ , Cγ .

Упражнение 6.9 Две фирмы поставляют на рынок некоторый товар в объеме xi соответственно, i = 1, 2 . Цена на товар определяется формулой p − x1 − x2 . В предположении постоянных затрат на единицу выпуска продукции функции выигрыша можно определить формулой ui ( x1 , x2 ) = ( p − x1 − x2 )xi − cxi , i = 1, 2 , ⎡ p⎤ множества допустимых стратегий имеют вид X 1 = X 2 = ⎢0; ⎥ . Найти Cγ для этой ⎣ 2⎦ игры.

Упражнение 6.10 Найти Cγ в игре X1 = X 2 = R u i ( x ) = − x − a i , i = 1, 2 , где a i ∈ R 2 – заданные вектора. 36

Теорема 6.1 Классификация игр двух лиц β -ядро и γ -ядро не могут быть пустыми одновременно. Если β -ядро и

γ -ядро не пусты, то они пересекаются. Следствие. Игры двух лиц распадаются на три класса: I. Cβ = Ø, Cγ ≠ Ø : борьба за право второго хода. II. Cβ ≠ Ø, Cγ = Ø : борьба за лидерство. III. Cβ I Cγ ≠ Ø : непустая область пересечения допускает стабилизацию с помощью взаимных угроз. Доказательство: Пусть xi – равновесие по Штакельбергу при лидере i , i = 1, 2 . Обозначим через Di множество исходов, удовлетворяющих следующим неравенствам:

γ i ≤ ui ( x ), β j ≤ u j ( x ) .

( )

Поскольку xij ∈ R j xii , то xi ∈ Di ≠ Ø. Пусть Cγ = Cβ = Ø. Выберем оптимальный по Парето исход x ∈ D1 (например, максимизируя u1 + u2 на D1 ). Тогда справедливо Cγ = Ø ⇒ u2 ( x ) < γ 2 , Cβ = Ø ⇒ u1 ( x ) < β1 . Поскольку x 2 ∈ D2 , то x 2 доминирует x по Парето – противоречие. Пусть теперь

Cβ ≠ Ø,

Cγ ≠ Ø. Докажем, что

Cβ I Cγ ≠ Ø. Положим

γ = (γ 1, γ 2 ) . Если γ ≤ β , то Cβ ⊆ Cγ , и все доказано. Аналогично при γ ≥ β Cγ ≤ Cβ . Осталось рассмотреть случай типа β1 > γ 1 , γ 2 < β 2 . Тогда любой оптимальный по Парето дележ из D1 , например x1 , принадлежит Cβ I Cγ . Таким образом, борьба за лидерство (право первого хода) и борьба за право второго хода не могут возникнуть одновременно.

37

ЛИТЕРАТУРА 1 Гермейер Ю.Б. Игры с непротивоположными интересами. – М.: Наука, 1976. – 328 с. 2 Льюс Р.Д., Райфа Х. Игры и решения. – М.: ИЛ, 1961. – 642 с. 3 Мулен Э. Теория игр с примерами из математической экономики. – М.: Мир, 1985. – 200 с. 4 Нейман Дж., Моргенштерн О. Теория игр и экономическое поведение. – М.: Наука, 1970. – 708 с. 5 Петросян Л.А., Зенкевич Н.А., Семина Е.А. Теория игр. – М.: Высшая школа, 1998. – 304 с.

38