Навігація
Головна
 
Головна arrow Природознавство arrow ТЕОРІЯ ІГОР
Переглянути оригінал

ДОСКОНАЛЕ ПОДИГРОВОЕ РІВНОВАГУ НЕША

Визначення 3.3. Нехай задана гра в розгорнутій формі. Назвемо поди- Грою таку гру, яка:

  • а) починається в одноточечного вирішальному вузлі п (але не в початковому вузлі);
  • б) включає в себе всі вирішальні і кінцеві вузли, які йдуть за п на дереві гри (але не включає в себе вузли, які не йдуть за п );
  • в) не перетинає жодного інформаційного безлічі, що включає в себе вузли п годі було за п (тобто якщо п слід за / ?, то і всі інші вузли, що належать одному з п інформаційного безлічі, повинні слідувати за п і, отже , повинні бути включені в подигру).

Відповідно до зауваженням в дужках до п. А) визначення вся гра не вважається подигрой. Втім, вважати чи не вважати всю гру поди- Грою - це справа смаку.

Приклад 3.7. Розглянемо динамічну гру (рис. 3.12).

Мал. 3.12

У цій грі тільки одна подигра, яка починається після ходів т і х. Вузол А не породжує подигру, оскільки багатоточкове інформаційне безліч містить вузол В , які не наступний на дереві гри за вузлом А. Отже, частина дерева, що починається з вузла А, не є поди- Грою, - не виконано вимогу в) у визначенні подигри.

У грі, представленої на рис. 3.10, як і в інших статичних іграх, немає подигр.

У грі, представленої на рис. 3.11, дві подигри, що починаються після ходу першого гравця.

Одним з мотивів прийняття у визначенні пункту в) є те, що ми хочемо мати можливість аналізувати подигру саму по собі, як окремо взяту гру.

Іншою причиною, по якій в визначення подигри введено положення в), є той факт, що положення а) гарантує знання передісторії гри до вузла п лише того гравця, який в вузлі п робить хід. Це не стосується інших гравців - вони можуть і не знати всю передісторію розвитку гри до моменту п. Положення в) гарантує, що всі гравці мають повну інформацію про всю передісторію гри до моменту досягнення вузла п.

Під цим мається на увазі наступне. У кожному вузлі, наступного за п у скажімо п гравець, який здійснює хід в п знає, що гра досягла вузла п. Таким чином, хоча п може і не належати одноточечного інформаційного безлічі, всі вузли з цього інформаційного безлічі повинні слідувати за п , т. е. гравець в вузлі п знає, що гра досягла п , слідуючи за п.

Якщо образно розглядати дерево гри, то подигра, що починається в вузлі п, володіє тим властивістю, що ми можемо в цьому вузлі «ножицями відрізати» цілком всю гілку, і вона не буде «чіплятися» за пунктирні інформаційні безлічі - винесемо її і розглянемо як окремо взяту гру. У грі на рис. 3.12 вузол, наступний після ходу п першого гравця, не володіє такою властивістю, оскільки ця гілка буде зчеплена многоточечним інформаційним безліччю з вузлом сусідньої гілки.

Дамо тепер визначення досконалого подигрового рівноваги Неша.

Визначення 3.4. Рівновага Неша називається досконалим подигро- вим ( subgame-perfect ), якщо воно становить рівновагу Неша в кожній поди- греко. Позначається: SPNE.

Можна довести, що будь-яка кінцева динамічна гра з повною інформацією (тобто будь-яка динамічна гра, в якій кожен з кінцевого числа гравців має кінцеве число можливих стратегій і всі функції виграшу відомі кожному гравцеві) має хоча б одне досконале подигровое рівновагу Неша, можливо , в змішаних стратегіях.

Для побудови досконалого подигрового рівноваги Неша, по-перше, слід визначити всі найменші можливі подигри, що містять кінцеві вузли на дереві початкової гри (найменшою подигрой назвемо подигру, що не містить в собі ніякої іншої подигри). Далі замінимо кожну таку подигру платежами, відповідними їх рівноваги Неша. Тепер початкові вузли цих подигр будемо трактувати як кінцеві вузли нової версії початкової гри. Продовжуючи цю процедуру, методом зворотної індукції ми отримаємо досконале подигровое рівновагу Неша, оскільки стратегії гравців складають рівновагу Неша в кожній подигре.

Слід розрізняти між собою поняття досконалого подигрового рівноваги Неша і назад-індукційного результату. Рівновага Неша має на увазі сукупність стратегій всіх гравців (повний план дій кожного з гравців), в той час як назад-індукційний результат має на увазі лише очікуваний результат, тобто послідовність ходів гравців, яка повинна мати місце в грі з принципу очікуваного раціональної поведінки гравців (але не поведінка гравців у всіх можливих ситуаціях).

Пояснимо це на прикладі, розглянутому в параграфі 3.1.

Назад-індукційним результатом в даній грі є , /? 2 ( «[)). Для другого гравця R 2 (a) - найкраща відповідь на стратегію а [> але не його стратегія, оскільки стратегія другого гравця повинна вказувати його дії під всіх можливих ситуаціях, а не тільки в ситуації, коли перший гравець пішов а .

Рівновагою Неша в даній грі є (d [, R 2 (a x )), де R 2 (a {) - найкраща відповідь другого гравця на всілякі дії першого гравця ci з А. Неважко показати, що це буде саме досконалим ігровим рівновагою Неша . Для цього достатньо показати, що, по-перше, це буде рівновагою Неша і, по-друге, стратегії гравців становитимуть рівновагу Неша в будь-який подигре. Оскільки подигрой в даному випадку є вибір другим гравцем дії після того, як перший гравець здійснив довільний хід а, то його найкраща відповідь R> {U ) за визначенням і буде рівновагою Неша в даній подигре.

Головна ідея введення вчиненого подигрового рівноваги - виключити з рівноваги Неша все неспроможні загрози і обіцянки. Пояснимо це на прикладі гри, представленої на рис. 3.13.

Мал. 3.13

В нормальній формі дана гра призводить до матриці

Вирішуючи цю гру назад-індукційним методом, ми отримаємо обратноіндукціонний результат ( b ; п ), позначений на малюнку жирною лінією. Зауважимо також, що існує додатковий жирний ділянку: при виборі ходу а першим гравцем другої грає d.

У нормальній (матричної) формі подання гри ми спостерігаємо два рівноваги Неша в чистих стратегіях (вони відзначені жирним шрифтом): (a; de) і (b; dn ). Зараз ми можемо порівняти ці рівноваги з результатами методу зворотного індукції. Рівновага (b; dn) відповідає всім жирним лініях в грі в розгорнутій формі. Раніше ми називали (6; п ) назад-індукційним результатом. Дотримуючись цієї термінології, можна було б назвати {b dn) назад-індукційним рівновагою Неша в грі. Але ми будемо використовувати більш загальну термінологію і називати ( b ; dn) досконалим подигровим рівновагою Неша. Різниця між назад-індукційним результатом і рівновагою в тому, що результат визначає лише одну жирну лінію від початкового вузла до кінцевого, в той час як рівновага визначає все жирні лінії. Таким чином, рівновага визначає повну стратегію другого гравця.

Але що можна сказати про інше рівновазі Неша (a; de )? В цьому профілі стратегій укладена загроза другого гравця робити хід е навіть в тому випадку, якщо перший гравець зіграє Ь. Якби ця загроза спрацювала (гравець 1 повірив би в неї), то він не став би грати Ь, так як йому загрожував би виграш О, в той час як при грі а він отримав би виграш 1. Однак ця у [троянда неспроможна, оскільки він знає, що при виборі їм Ь другий гравець буде вирішувати своє завдання максимізації виграшу і вибере п. Міркуючи більш формально, рівновагу Неша (a; de) не є досконалим подигровим рівновагою Неша, оскільки стратегії гравців нс містять рівновагу Неша у всіх подиграх. А саме, розглянемо подигри, що починаються з другого ходу (гравця 2). Стратегія de другого гравця в цій ситуації полягає у виборі d після ходу а першого гравця і у виборі е після ходу b першого гравця. Але вибір другим гравцем е не є оптимальною відповіддю в подигре, що починається після вибору першим гравцем ходу Ь.

Розглянемо ще кілька прикладів на визначення досконалого поди- Гров рівноваги Неша.

Приклад 3.8. На рис. 3.14 задана гра двох гравців. Уявити гру в нормальній формі (побудувати матричну гру). Знайти всі рівноваги Неша. Знайти всі вчинені подигровие рівноваги Неша.

Мал. 3.14

Рішення

У першого гравця два інформаційних безлічі: початковий вузол і двухточечное інформаційне безліч. Відповідно стратегії першого гравця будемо позначати двома буквами, перша з яких позначає його хід у початковому вузлі, а друга - хід в багатоточковому інформаційному безлічі. Безліч чистих стратегій першого гравця: {ad ае; bd; be}. Аналогічно у другого гравця два інформаційних безлічі, обидва одноточкові. Безліч чистих стратегій другого гравця: {cf; cg ', nf, ng}.

Уявімо гру в нормальній (матричної) формі:

Жирним шрифтом виділені точки, відповідні равновесиям Неша:

У даній грі є дві подигри. Одна з них починається після ходу b першого гравця, і в ній, очевидно, рішення другого гравця - вибір g (оскільки 3> 2). Его означає, що все рівноваги Неша, в яких зустрічається буква /, не є досконалими подигровимі равновесиями. З нашого списку ми можемо викреслити перше з них.

Друга подигра починається після ходу а першого гравця і має вигляд, зображений на рис. 3.15.

Мал. 3.15

Нормалізуємо цю подигру. У першого і другого гравця по дві стратегії:

У цій нодигре отримали два рівноваги Неша: {(d; c), (с; і)}.

Розглянемо решта п'ять рівноваг Неша.

Стратегія ( ае; ng ) наказує в даній подигре вибір стратегій е і п, тобто можна сказати, що проекція на цю подигру становить профіль (е; п), який є рівновагою Неша. Значить, ( ae; ng ) становить рівновагу Неша в кожній з двох подигр. Профіль (ае; ng) - досконале поди- Гров рівновагу Неша.

Стратегія ( bd; cg ) наказує в даній подигре вибір стратегій d і с, тобто можна сказати, що проекція на цю подигру становить профіль (d; с), який є рівновагою Неша. Значить, (bd; eg) становить рівновагу Неша в кожній з двох подигр. Профіль ( bd; cg) - досконале подигровое рівновагу Неша.

Стратегія ( bd; ng) наказує в даній подигре вибір стратегій d і п, тобто можна сказати, що проекція на цю подигру становить профіль (d; п), який не є рівновагою Неша. Значить, ( bd; ng) не складає рівновагу Неша в одній з двох подигр. Профіль (bd; ng) є рівновагою Неша, але не є досконалим подигровим рівновагою Неша.

Стратегія ( be ; eg) наказує в даній іодигре вибір стратегій е і с, тобто можна сказати, що проекція на цю подигру становить профіль (е; с), який не є рівновагою Неша. Значить, (be; eg) не складає рівновагу Неша в одній з двох подигр. Профіль (be; eg) є рівновагою Неша, але не є досконалим подигровим рівновагою Неша.

Стратегія (be; ng) наказує в даній подигре вибір стратегій їй п, тобто можна сказати, що проекція на цю подигру становить профіль (е; п), який є рівновагою Неша. Значить, (be; ng) становить рівновагу Неша в кожній з двох подигр. Профіль (be; ng) - досконале ноди- Гров рівновагу Неша.

В результаті отримаємо три рівноваги Неша, вчинені в подиграх:

Приклад 3.9. На рис. 3.16; Уявити гру в нормальній формі (побудувати матричну гру). Знайти всі рівноваги Неша. Знайти всі вчинені подигровие рівноваги Неша.

Мал. 3.16

Рішення

У першого гравця три інформаційних безлічі. Перше - одноточечное - початковий вузол, друге - багатоточкове, наступне після ходу а першого гравця і наступних ходів з або d другого гравця, і третє також багатоточкове, наступне після ходу b першого гравця і наступних ходів х або у другого гравця. Відповідно, стратегія першого гравця буде складатися з трьох букв (за кількістю інформаційних множин), кожна з яких показує хід першого гравця у відповідних інформаційних множинах.

Стратегії першого гравця: amf; amg; anf; ang; bmf; bmg; bnf; bng.

У другого гравця два інформаційних безлічі, обидва одноточкові. Відповідно його стратегії будуть формуватися з двох букв, перша з яких показує хід другого гравця після ходу першого гравця а, а друга - хід другого гравця після ходу першого Ь.

Стратегії другого гравця: сх; су; dx; dy.

У даній послідовної грі існує шість рівноваг Неша (виділені жирним шрифтом в таблиці) в чистих стратегіях:

(anf ; dx), ( ang ; dx), ( bmf ; су), ( bmf; dy), {bnf ; cy), ( bnf ; dy).

Далі розглянемо дві подигри. Перша з них починається після ходу а першого гравця (рис. 3.17).

Мал. 3.17

Нормалізуємо гру і знайдемо рівноваги Неша:

Рівновага Неша - ( n; d ). Тільки три з згаданих вище шести рівноваг Неша для всієї гри в проекції на цю подигру складають рівновагу Неша:

Розглянемо тепер другу подигру (рис. 3.18).

Мал. 3.18

Нормалізуємо її:

У цій подигре тільки одне рівновагу Неша: (/; у).

З решти трьох рівноваг тільки останнє ( bnf dy) в проекції на дану подигру становить також рівновагу Неша.

Таким чином, у розглянутій грі існує єдине рівновагу Неша, вчинене в подиграх: {bnf] dy).

Приклад 3.10. Знайти всі рівноваги Неша в чистих стратегіях і всі скоєні подигровие рівноваги в наступній послідовної грі (рис. 3.19).

Мал. 3.19

Рішення

Нормалізуємо гру. У кожного гравця по чотири чисті стратегії:

Жирним шрифтом виділені максимальні елементи першої матриці по стовпцях і максимальні елементи другуматриці по рядках.

Рівновага Неша:

У даній грі три подигри.

1. У подигре, що починається після ходу а першого гравця, очевидно, що стратегія з другого гравця буде домінувати стратегію d (3> 2).

Отже, рівноваги (birr, df), (bn; de) не є досконалими подьіровимі равновесиями.

  • 2. У подигре, що починається після ходу / другого гравця, очевидно, що стратегія т першого гравця буде домінувати стратегію п (2> 1). Отже, рівноваги (an; ce), (an; cf), (bn; ce), (bn; de) не є досконалими подигровимі равновесиями.
  • 3. Розглянемо подигру, що починається після ходу b першого гравця. Нормалізуємо її:

У цій подигре два рівноваги Неша: ( «; е ), ( т ; /)}. З решти рівноваг Неша в загальній грі (am; се), (am; з /) тільки останнім в проекції на дану подигру становить рівновагу. Перше рівновагу в проекції на подигру дає профіль (т, е ), який не є рівновагою Неша в цій подигре. Друге рівновагу в проекції на подигру дає профіль (т; /), який є рівновагою Неша в подигре.

Отже, в даній грі тільки одне досконале подигровое рівновагу Неша: (am; с /).

Розглянемо приклад нескінченної гри двох гравців (безліч стратегій нескінченно).

Приклад 3.11. Спочатку перший гравець вибирає деяке число х е R. Потім другий гравець, знаючи х, вибирає число у е R. Платежі гравців відомі обом гравцям і дорівнюють відповідно U ^ (x, у) = х 2 -2ху; U 2 (х, У) = 2 + 4хг / + х 3 + Південь /. Знайти: а) назад-індукційні результати в цій грі і б) вчинені подигровие рівноваги Неша.

Рішення

Оскільки останнім робить свій вибір другий гравець, то при відомому йому значенні х він максимізує свій виграш:

Але цю задач}? може вирішити і перший гравець, поставивши себе на місце другого, і тому він може використовувати цей результат при виборі значення ХГ.

Перший гравець максимізує свій виграш: х = -1.

Назад-індукційний результат в задачі: (х * = -1; у * = 3).

Але (х * = -1; у * = 3) не є рівновагою Неша. Дійсно, якщо перший гравець вибирає х = -1, то другого найвигідніше вибирати у = 3. Але якщо у = 3, то перший гравець, знаючи це, вибрав би х з умови максимізації функції U x (x, у) = х 2 -2х-3> шах, що призвело б до відповіді х = - 3 Ф - 1.

Якщо ж розглянути профіль стратегій (х = -1; у- 2х + 5), то неважко переконатися, що такий профіль буде складати вчинене подигровое рівновагу Неша. Для цього треба показати, що:

  • 1) профіль буде рівновагою Неша;
  • 2) профіль буде рівновагою Неша в проекції на всі подигри.

Перша частина очевидна. Вона повністю повторює міркування пошуку

назад-індукційного результату. Але все подигри починаються після ходу х першого гравця. І в будь-який іодигре незалежно від значення х, другому гравцеві вигідніше всього вибирати у = 2х + 5.

Відповідь : а) (х * = -1; у * = 3); б) (х = -1; у = 2х + 5).

Приклад 3.12. Саша і Маша прийшли в ресторан. У Саші 6 золотих, у Маші - 8 золотих. Кожен вирішує витратити всі гроші, розподіляючи їх на їжу або на музику. Музика є загальним благом - її чують все. Їжа - приватним. Корисності рівні:

де т г е { - витрати на музику і їжу відповідно (схоже, що Маша не в захваті від музичних уподобань Саші). Спочатку свої витрати на музику і їжу визначає Саша. Потім Маша, знаючи розподіл Саші, робить свій вибір за видатками. Кожен з них знає функції корисності обох. Припустимо, що гроші нескінченно подільні. Знайти: а) вчинене подигровое рівновагу Неша; б) які витрати кожного з гравців на музику і на їжу в знайденому рівновазі.

Рішення

Завдання вирішуємо методом зворотної індукції.

Але оскільки т з е [0; 6], то залишається тільки перший випадок:

Цей розрахунок може виконати і Саша, поставивши себе на її місце і знаючи її переваги. Тому він може на першому кроці використовувати отриманий результат:

Відповідь : a) SPNE :

6) витрати гравців на музику і на їжу:

Приклад 3.13 (модель Штакельберга). Дві фірми виробляють однаковий продукт. Спочатку перша фірма (лідер) оголошує про свій намір виробляти товар в кількості q x . Далі друга фірма (послідовник), знаючи Ц, оголошує про своє кількості товару q 2 . Відома зворотна функція попиту на продукцію фірм: P = 2Q-Q, де Q = q + q 2 ~ сумарний випуск продукції двох фірм. Граничні витрати фірм дорівнюють відповідно 1 і 2 і відомі обом фірмам. Знайти вчинене подигровое рівновагу Неша. Які обсяги продукції будуть вибирати фірми в знайденому рівновазі?

Рішення

Очевидно, що всі q)

Але це завдання може вирішити і перша фірма, якій відома функція виграшу U 2 , і отриману реакцію q 2 = f Oh ) перша фірма може використовувати при оптимізації вибору q.

Неважко бачити, що максимум досягається в точці q { = 10.

Рівновага Неша, вчинене в подиграх:

У знайденому рівновазі фірми вибиратимуть q = 10; q 2 = 4.

Приклад 3.14. Три фірми виробляють однаковий продукт. Спочатку перша фірма вибирає свій обсяг випуску q. Потім друга і третя фірми, знаючи <7 Ь одночасно вибирають свої обсяги випуску с / 2 і q 3 . Граничні витрати випуску дорівнюють відповідно 1, 2 і 4. Зворотній функція попиту має вигляд P = 10-Q, де Q = г /, + q 2 + Tj - сумарний випуск продукції трьох фірм. Кожна фірма максимізує свій прибуток. Знайдіть рівновагу Неша, вчинене в іодиграх. Які обсяги продукції будуть вибирати фірми в знайденому рівновазі?

Рішення

Очевидно, що всі д ( е [0; 10]. Використовуємо метод зворотного індукції. Оскільки на останньому (другому) етапі рішення приймаються другої і третьої фірмою одночасно, то вирішуємо за них завдання оптимізації (при відомому їм значенні q x )

Перша із завдань призведе до наступного результату:

Друга - до наступного:

Цю ж задачу може вирішити і перша фірма. Вона може передбачити реакцію другої і третьої фірм на другому етапі. Тому перша фірма може використовувати цей результат на першому етапі:

або

Розглянемо різні випадки.

Випадок 1: (1а), (2а). нехай

тоді

Ці формули визначають найкращу відповідь другого і третього гравців при <4.

Випадок 2: (1а), (26). нехай

тоді

Ці формули визначають найкращу відповідь другого і третього гравців при q x е [4; 8].

Випадок 3: (16), (2а). нехай

Ця система не має рішень, які відповідають умові q , е [0; 10], i = 1,2,3.

Випадок 4: (16), (26). нехай

тоді

Ці формули визначають найкращу відповідь другого і третього гравців при q x е [8; 10].

Узагальнимо отримані результати:

Розглянемо тепер виграш першого гравця.

при

При <7, е [4; 8] отримаємо

При <7, е [8; 10] отримаємо

Таким чином,

Графік функції U x [q x ) зображено на рис. 3.20.

Мал. 3.20

Очевидно, що максимальне значення функції досягається при q = 5. Це і буде оптимальна стратегія першої фірми.

Рівновага Неша, вчинене в подиграх:

При цьому назад-індукційний результат дорівнює

Зауваження 1. Профіль стратегій не є рівновагою Неша. Дійсно, якщо , то перша фірма, знаючи це, максимізує свій прибуток: що дає

Зауваження 2. Формули (3) можна отримати і з графічного представлення залежностей між q x і q 2 відповідно до формулами (la) - (26). При малих значеннях q x графічне представлення залежностей має вигляд, представленнийна рис. 3.21. Неважко порахувати точку перетину

графіків:

Мал. 321

При збільшенні значень q x конфігурація графіків змінюється і приймає вигляд, представлений на рис. 3.22. Це станеться, коли виконається умова

Мал. 322

Перетин графіків відбувається в точці. Ця ж точка

перетину буде і при q { е [6; 8).

При q x е [8; 10] графіки перетинаються в початку координат (рис. 3.23).

Мал. 3.23

 
Переглянути оригінал
< Попередня   ЗМІСТ   Наступна >
 
Дисципліни
Агропромисловість
Аудит та Бухоблік
Банківська справа
БЖД
Географія
Документознавство
Екологія
Економіка
Етика та Естетика
Журналістика
Інвестування
Інформатика
Історія
Культурологія
Література
Логіка
Логістика
Маркетинг
Медицина
Нерухомість
Менеджмент
Педагогіка
Політологія
Політекономія
Право
Природознавство
Психологія
Релігієзнавство
Риторика
Соціологія
Статистика
Техніка
Страхова справа
Товарознавство
Туризм
Філософія
Фінанси
Пошук