Даруємо!!!

Домінуючі і домінованi стратегії в теорії ігор


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

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

Поняття домінування використовується при вирішенні або спрощення деяких типів некооперативних ігор.

Термінологія

При виборі своєї стратегії з безлічі допустимих гравець порівнює переваги результатів від їх застосування. Може виникати три типи результатів:

  • Стратегія В домінує стратегію A, якщо при будь-якій поведінці інших гравців використання стратегії В призводить до не гіршого результату, ніж використання А. Розрізняють строге домінування, коли В дає більший виграш, ніж А, в будь-яких умовах, і слабке домінування, якщо при деяких діях інших гравців В забезпечує більший виграш, ніж А, а при інших – однаковий з нею.
  • Стратегія В домінується стратегією A, якщо при будь-якій поведінці інших гравців стратегія В призводить до не кращого результату, ніж стратегія А. Аналогічно попередньому випадку, стратегія може домінувати строго і слабо.
  • Стратегії А і В називаються нетранзитивністю, якщо В не домінує А і А не домінує В. Це оначает, що в залежності від вибору стратегій іншими гравцями, великі виграші гравцеві може забезпечувати як вибір стратегії А, так і В.

Це поняття узагальнюється на порівняння більш ніж двох стратегій:

  • Стратегія B називається строгодомінуючою,якщо вона строго домінує будь-яку іншу допустиму стратегію гравця.
  • Стратегія B називається слабодомінуючою, якщо вона домінує будь-яку іншу допустиму стратегію гравця, при цьому деякі з них домінує слабо.
  • Стратегія B називається строгодомінованою, якщо існує інша стратегія, яка строго її домінує.
  • Стратегія B називається слабодомінованою, якщо існує інша стратегія, яка слабо її домінує.

Домінування і рівноваги Неша


CD
C1, 10, 0
D0, 00, 0
Слабке домінування

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

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

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

Послідовне виключення домінованих стратегій

Послідовне виключення домінованих стратегій – часто використовувана технологія рішення або спрощення некооперативних ігор. Вона заснована на припущенні про те, що в процесі гри сторони не будуть використовувати доміновані стратегії, в зв’язку з чим їх можна не розглядати при подальшому вирішенні. Однак, виключення цих стратегій з розгляду призводить до звуження безлічі можливих ситуацій, в результаті чого можуть виникнути нові доміновані стратегії, які у вихідній грі не домінували.

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

Приклад

Приклад рішення гри методом послідовного виключення строго домінованих стратегій.

Нехай в грі беруть участь гравці A і B. Для гравця A доступні стратегії a1 і a2, для гравця B – стратегії b1,b2,b3. Гравці вибирають стратегії одночасно і незалежно один від одного. У таблиці наведено платежі, які отримують гравці, зігравши свою стратегію, в залежності від обраної стратегії іншого гравця. Перша цифра в осередку – платіж першого гравця, цифра після крапки з комою – платіж, отриманий другим гравцем.

Вихідна таблиця. Наприклад, з таблиці видно, що якщо гравець A зіграє стратегію a2,а гравець B зіграє стратегію b3,то гравець A отримає 4 очка, а гравець B – 1 очко.


b1b2b3
a16; 53, 63, 9
a27, 73, 04; 1

Можна помітити, що незалежно від вибору гравця A, для другого гравця стратегія b2 поступається за своїми характеристиками стратегії b3 (6 <9 і 0 <1).

Тому стовпець зі стратегією b2 можна не враховувати в подальшому розгляді, викреслюємо його. З точки зору гравця A, серед решти стратегій, a1 явно поступається a2 (6 <7 і 3 <4)


b1b3
a16; 53, 9
a27, 74, 1

Викреслюємо рядок зі стратегією a1.У таблиці платежів залишається всього два осередки, і для другого гравця стратегія b1 явно краще стратегії b3 (1 <7).


b1b3
a27, 74, 1

Таким чином, винятком строго домінованих стратегій ми вирішили гру: раціональні гравці зіграють стратегії b1 і a2,кожен гравець отримає платіж рівний 7.