Тема 2. Сильное и параметрическое равновесия Нэша.

 

Введение понятия сильного равновесия можно считать попыткой объединения концепций равновесия Нэша и равновесия Парето.

Определение 16: Для игры п лиц обозначим множество игроков через N ={1,2, 3,...,n}. Любое непустое подмножество S данного множества, включая и само N, называется коалицией.

Понятно, что для игры п лиц возможны 2ⁿ –1 коалиций. Множество всех возможных коалиций обозначим 2^N. Обозначим (x^*_-S,x_s) ситуацию, в которой игроки, не входящие в коалицию S N, используют стратегии х_i^* (I N\ S) a игроки из S исполь­зуют стратегии x_j (j ∈ S).

Определение 17: Ситуация х^* называется сильно равновесной по Нэшу, если для любых коалиций S ⊂ N и любых x_s ∈ найдется участник коалиции i ∈ S, такой, что K_i(x^*)>K_i(x_-s^*,x_s).

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

Довольно просто показать, что все сильные равновесия, если они существуют, оптимальны по Парето.

Тем не менее, при всех привлекательных чертах сильного равновесия Нэша, его использование ограничено тем, что даже в смешанных стратегиях оно существует не во всех играх.

«Параметрическое» равновесие Нэша

Для того чтобы вычислить равновесие Нэша, исследователь игры должен точно знать функции выигрыша игроков. В задачах управления часто встречается ситуация, когда на момент исследования игры функции выигрыша известны исследователю игры не полностью. Эта ситуация характерна для механизмов управления с сообщением информации.

Неточную информацию о функциях выигрыша игроков принято описывать с помощью понятия типа игрока. Рассмотрим следующую игру п лиц, в которой каждый из игроков имеет некоторый тип r_i ∈ Ω, из множества Ω _i, возможных типов данного игрока i. Будем считать, что все множества типов Ω_i, компактны, i ∈ N. Функции выигрыша игроков K_i = К_i (х_1,...х_n,r₁,...r_п) зави­сят как от действий x_t e X_t всех игроков, так и от их типов r_i ∈ Ω_i, i ∈ N.

Определение 18: Профилем типов игроков называется вектор r= (r_1,r₂,…,r_n) ∈ Ω .

Определение 19: Набор функций x^*(r) = (x^*₁(r),...,x_n ^*(r)) будем называть равновесием Нэша (в чистых стратегиях) в игре с параметрически заданными функциями выигрыша,если для каждого фиксированного профиля r типов игроков для каждого игрока i ∈ N и для всех его стратегий х_i ∈ Х_i, справедливо неравенство K_i(x^*(r),r) ≥ K_i(x_i,x_-i^*(r),r).

Пример 15. «Простая задача распределения ресурса».

Рассмотрим организационную систему, состоящую из центра и двух агентов (игроков). Центр распределяет между игроками ресурс, для чего собирает от них заявки s_i ∈ [0; 1] (i = 1, 2) и выдает каждому игроку ресурс по формуле

x_i =s_i – (11)

В этом механизме центр «недодает» игрокам ресурс относительно заявленных ими потребностей, причем, чем больше сообщенная общая потребность в ресурсе s₁ +s₂, тем существеннее становится «недодача».

Игроки имеют типы r_i ∈ [0; 1]. Функции выигрыша игроков зависят от полученного ими ресурса и типа следующим образом:

K_i = 2x_i – . (12)

Параметр r_i ∈ [0; 1] можно интерпретировать как количество ресурса, оптимальное для игрока, так как именно при х_i =r_i, достигается максимум его выигрыша. Центр не знает типы {r_i} игроков.

Стратегиями игроков в этой игре являются их заявки s_i на ресурс. Подставив (11) в (12), можно выразить функции выигрыша через стратегии, получив игру в нормальной форме. В этой игре функции выигрыша игроков зависят не только от их стратегий, но и от типов r_i.

Задача исследователя заключается в том, чтобы предсказать, насколько это возможно, равновесные заявки игроков.

Можно показать, что в зависимости от типов r₁ и r₂игроков равновесие Нэша в этой игре будет задаваться заявками (s₁^*(.),s₂^*(.))=

= (13)

Равновесные заявки зависят от типов {r₁} игроков. Если в дальнейшем исследователь получит точную информацию о типах игроков, то, подставив значения типов игроков в (13), сможет получить точное равновесие Нэша этой игры.

Однако полученный результат можно использовать и другим способом. Пусть исследователю известна та же информация, что и центру. Пусть игра разыграна один раз, и центр получил от игроков заявки (s_1,s₂). Тогда, зная (13), центр может узнать типы игроков. Так, например, если обе заявки меньше 1, центр может определить типы игроков по формуле:

r₁ = 0.75 s₁ – 0.25 s₂, r₂ = 0.75 s₂ – 0.25 s₁.

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

Пример.«Решение задачи «Экспертиза».

Приведем решение задачи примера 2.

Сообщение достоверной информации в механизмах планирования является равновесием в доминантных стратегиях для всех r ∈ Ω, если: ∀r ∈ Ω, ∀ i ∈ N, ∀ s_i ∈ Ω_i, ∀ ∈ Ω_-i, выполняется φ_i (π_i (r_i, ),r_i) ≥ φ_i (π_i (s_i, ),r_i).

Для механизма экспертизы справедливо следующее утвер­ждение: для каждого r ∈ [d,D]ⁿ равновесие Нэша s^*(r) имеет следующую структуру:

1) s_i^*=

2) если d < s_i^*<D, то x^* = r_i.

Определим для каждого k = векторы сообщений:

s(k) =

и вычислим последовательность точек W_k = π(s(k)).

В [9] доказано, что всегда найдется такой номер k ∈ {0,...,n}, что либо r_k ∈ [W_k,W_k-1],либо r_k > W_k-1.

Общий результат, характеризующий решение задачи экспертизы, гласит, что итоговое решение в равновесии имеет вид: х^* = max min (r_k, W_k-1).

Следовательно, для любой процедуры активной экспертизы найдется эквивалентный прямой механизм.

Тема 3. Антагонистические игры. Задачи и упражнения.

Упражнение 1.

Установить цену игры V и оп­тимальность смешанных стратегий Р ° = (0,4; 0,6) и Q ° = (0; 0; 0,6; 0,4) для игры с платежной матрицей 2x4

Bj Ai	B1	B2	B3	B4
A1
A2

Упражнение 2.

В условиях упражнения 1 установить оптимальность стратегий Р°= (0,4; 0,6) и Q ° = (0; 0; 0,6; 0,4).

Упражнение.3.

Для доказательства оптимальности стратегий Р° = (0,4; 0,6) и Q ° = (0; 0; 0,6; 0,4) и определения цены игры в условиях упражнения 1 применить теорему 2.

Упражнение.4.

В условиях упражнения 3 показать, что выигрыш игрока А больше цены игры, если игрок А использует свою оптимальную смешанную стратегию Р°= (0,4; 0,6), а игрок В использует свои чистые стратегии B1 и В2.Показать, что ни одна из активных стратегий обоих игроков не является оптимальной.

Упражнение.5.

Сформировать смешанную стратегию Qтаким образом, чтобы она представляла собой смесь активных стратегий В₃и В₄игрока Вв пропорциях 0,2 и 0,8 со­ответственно и проверить выполнение утверждения 2) теоремы 2.10.7 (о смесях активных стратегий) при условии, что игрок А применяет свою оптимальную стратегию Р° = (0,4; 0,6).

Вопросы для самоконтроля

1.Какая стратегия игрока А называется доминирующей (доминируемой)?

2. Какая стратегия игрока В называется доминирующей (доминируемой)?

3. В чем состоит отличие доминирующей стратегии от строго доминирующей?

4. Почему строку платежной матрицы, доминируемую некоторой выпуклой
комбинацией остальных ее строк, можно удалить?

5. Почему столбец платежной матрицы, доминируемый некоторой выпуклой
комбинацией остальных ее столбцов, можно удалить?

6. Дайте определение дублирующих стратегий игрока и объясните, почему
одну из дублирующих стратегий можно удалить?

Упражнение 1.

Удаляя доминируемые и дублирующие стратегии игроков, выполните редуци­рование матрицы игры [5x5]

 

Ai Bj	B1	B2	B3	B4	B5
A1
A2
A3
A4
A5

 

к матрице [2x2].

Упражнение 2.

Удаляя доминируемые и дублирующие стратегии игроков, выполните редуцирова­ние матрицы игры [4x4] «Антагонистическая конкуренция» (см. пример 2.4.1)

 

Ai Bj	B1	B2	B3	B4
A1
A2
A3
A4

К матрице [2x2].

Упражнение 3.

Используя предложение 1) теоремы 2.11.1, покажите, что матрицу игры [4x2]

Ai Bj	B1	B2
A1
A2
A3
A4	-1

Можно редуцировать к матрице [2x2].

Упражнение 4.

Используя предложение 3) теоремы 2.11.1, покажите, что матрицу игры [2x4]

Ai Bj	B1	B2	B3	B4
A1
A2

Можно редуцировать к матрице [2x2].

Ai Bj	B3	B4
A1
A2

Упражнение 5

Редуцируйте матрицу игры [3x3]

Ai Bj	B1	B2	B3
A1
A2
A3

К матрице [2x2].

Тема 4. Игры с природой.

Критерии Байеса и Лапласа.

Вопросы для самоконтроля

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

2. Дайте определение оптимальной по Байесу чистой стратегии относительно выигрышей.

3. Каким образом связаны показатели эффективности смешанной и чистой стратегий по Байесу относительно выигрышей?

4. Почему при принятии решения в условиях риска по критерию Байеса относительно выигрышей можно обойтись только чистыми стратегиями, не используя смешанные?

5. Дайте определение оптимальной по Байесу чистой стратегии относительно рисков.

6. Почему при принятии решения в условиях риска по критерию Байеса относительно рисков можно обойтись только чистыми стратегиями, не используя смешанные?

7. Каким отношением связаны между собой оптимальные по Байесу стратегии относительно рисков и относительно выигрышей?

8. Дайте определение оптимальной по Лапласу чистой стратегии относитель­но выигрышей.

9. Какая существует связь между критериями Байеса и Лапласа?

10. Какой показатель используется для выбора оптимальной по Лапласу чистой стратегии относительно риска?

11. Какой показатель используется для выбора оптимальной стратегии по кри­терию относительных значений вероятностей состояний природы с учетом выиг­рышей?

12. Какой показатель используется для выбора оптимальной стратегии по крите­рию относительных значений вероятностей состояний природы с учетом рисков?

Упражнение 1.

 

В условиях задачи «Поставка товаров» (см. упражнение 4.1), найти чистую стра­тегию, оптимальную по критерию Байеса относительно выигрышей, если вероятно­сти состояний природы известны и равны:q₁ = 0,2; q₂ = 0,3; q₃=0,1; q₄=0,4.

 

Упражнение2.

 

В условиях задачи «Поставка товаров», найти чистую стратегию, оптималь­ную по критерию Байеса относительно рисков, если вероятности состояний при-роды известны и равны: q₁=0,2; q₂=0,3; q₃=0,1; q₄=0,4.

Упражнение 3.

 

Рассматривая задачу «Поставка товаров» как игру с природой с неизвестными вероятностями состояний природы, найти чистую стратегию, оптимальную по критерию Лапласа относительно выигрышей.

Упражнение 4.

 

Рассматривая задачу «Поставка товаров» как игру с природой с неизвестными вероятностями состояний природы, найти чистую стратегию, оптимальную по критерию Лапласа относительно рисков.

Упражнение.5.

Рассматривая задачу «Поставка товаров» как игру с природой, вероятности состояний которой образуют строго убывающую последовательность, пропор­циональную убывающей арифметической прогрессии:

 

q₁: q₂ : q₃ : q₄ = 4:3:2:1,

 

найти чистую стратегию, оптимальную по критерию относительных значений ве­роятностей состояний природы с учетом выигрышей.

 

Упражнение.6.

 

Рассматривая задачу «Поставка товаров» как игру с природой, неизвестные вероятности состояний которой образуют строго убывающую последователь­ность, пропорциональную убывающей

 

q₁: q₂ : q₃ : q₄ = 4:3:2:1,

 

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