Домінування (теорія ігор)

У Вікіпедії є статті про інші значення цього терміна: Домінування.

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

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

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

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

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

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

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

Формальні визначення

Кажуть, що стратегія ${\displaystyle s^{*}\in S_{i}}$ гравця ${\displaystyle i}$ слабко домінує стратегію ${\displaystyle s^{\prime }\in S_{i}}$, якщо

${\displaystyle \forall s_{-i}\in S_{-i}:u_{i}(s^{*},s_{-i})\geq u_{i}(s^{\prime },s_{-i})}$, причому хоча б одну нерівність виконано строго.

тут ${\displaystyle S_{-i}}$ є прямим добутком стратегічних множин усіх гравців, окрім ${\displaystyle i}$ -го.

Стратегія ${\displaystyle s^{*}}$ строго домінує ${\displaystyle s^{\prime }}$, якщо

${\displaystyle \forall s_{-i}\in S_{-i}:u_{i}(s^{*},s_{-i})>u_{i}(s^{\prime },s_{-i})}$.

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

	C	D
C	1 ; 1	0 ; 0
D	0 ; 0	0 ; 0
Слабке домінування

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

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

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

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

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

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

Приклад

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

Нехай у грі беруть участь гравці A і B. Для гравця A доступні стратегії a₁ і a_2, для гравця B — стратегії b_1, b_2, b_3. Гравці вибирають стратегії одночасно і незалежно один від одного. У таблиці наведено платежі, які отримують гравці, зігравши свою стратегію, залежно від вибраної стратегії іншого гравця. Перша цифра в комірці — платіж першого гравця, цифра після крапки з комою — платіж, отриманий другим гравцем.

Початкова таблиця. Наприклад, з таблиці видно, що якщо гравець A зіграє стратегію a_2, а гравець B зіграє стратегію b_3, то гравець A отримає 4 очка, а гравець B — 1 очко.

	b 1	b 2	b 3
a 1	6 ; 5	3 ; 6	3 ; 9
a 2	7 ; 7	3 ; 0	4 ; 1

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

	b 1	b 2	b 3
a 1	6 ; 5	3 ; 6	3 ; 9
a 2	7 ; 7	3 ; 0	4 ; 1

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

	b 1	b 3
a 1	6 ; 5	3 ; 9
a 2	7 ; 7	4 ; 1

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

	b 1	b 3
a 2	7 ; 7	4 ; 1

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