Словник / Домінантна стратегія
Зазвичай, щоб ухвалити рішення в конкуренції, треба вгадати, що зробить суперник. Але іноді один варіант кращий за інші, хоч би що той зробив. Це і є домінантна стратегія: гадати не треба, думки конкурента можна не читати. Здавалося б, із нею не можна прогадати. Проте буває, що двоє грають свої домінантні стратегії й обидва отримують менше, ніж якби обидва від них відмовилися.
Шар «На пальцях» приховано на всіх задачах.
Щопонеділка кожна кав'ярня вирішує: тримати ціну чи зробити знижку. Домовитися власники не можуть. Тижневий прибуток, у тисячах гривень:
Обидві власниці розумні й обидві бачать, що знижка завжди краща. Що буде з прибутком кожної, якщо обидві оберуть кращий для себе варіант, порівняно з тижнем, коли обидві тримали ціну?
Прибуток кожної впаде утричі: 1 замість 3.
Обидва міркування правильні водночас. «Хоч би що зробила сусідка, мені краще знизити» — правда: 5 більше за 3, а 1 більше за 0. «Якщо обидві знизимо, обом буде гірше» — теж правда: 1 менше за 3. Знижка найкраща для кожної окремо, і та сама знижка, зроблена обома, гірша для кожної. Домінантна стратегія порівнює ваші варіанти за незмінного вибору суперника. Але суперник незмінним не лишається: він має ту саму таблицю і ту саму спокусу.
Перевірка проста: закрийте очі на свій улюблений варіант і порівнюйте по стовпцях. Візьміть перший стовпець (суперник обрав перший варіант) і подивіться, який ваш рядок дає вам більше. Потім другий стовпець. Якщо в обох виграє той самий рядок, він домінантний. Для суперника те саме, лише порівнюють рядок за рядком його числа. Спробуйте у трьох іграх.
Домінантна стратегія — розкіш, яка трапляється нечасто. У грі «Де зустрітися» найкращий вибір цілком залежить від іншого, і тоді важать домовленості й звички. А в грі з новачком цікаве інше: свою домінантну стратегію має лише лідер, але новачкові досить знати про неї. Якщо реклама вигідна лідерові завжди, лідер її дасть, і новачок відповідає на рекламу, а не на здогадки. Чужа домінантна стратегія теж підказка.
Шар «Строго» приховано на всіх задачах.
Домінантна стратегія — це варіант, який дає гравцеві більше за будь-який інший його варіант, хоч би що обрали інші гравці. Протилежність — домінована стратегія: існує інший варіант, кращий за неї за будь-якого вибору інших. Розумний гравець домінованої стратегії не обирає ніколи, а домінантну обирає завжди, якщо вона є.
Тут у кожного гравця три варіанти, і домінантної стратегії немає ні в кого. Але деякі варіанти доміновані: є інший, кращий за них за будь-якого вибору суперника. Розумний гравець їх не обере, а суперник, знаючи це, може їх викреслити й дивитися на меншу таблицю. У меншій таблиці з'являються нові доміновані варіанти. У клітинці спершу ваш виграш (рядки), потім виграш суперника (стовпці). Клітинка «5 · 5» найкраща для обох. Чи дійдуть до неї розумні гравці? Натискайте на рядок або стовпець, який, на вашу думку, можна викреслити.
Кожен крок тут спирається на попередній: суперник викреслює стовпець, лише якщо вірить, що ви не оберете вже викреслений рядок, а ви — якщо вірите, що він міркує так само. Чим довший ланцюжок, тим більше довіри до чужої розумності він вимагає і тим менш надійний прогноз, коли грають живі люди.
Шар «Глибше» приховано на всіх задачах.
ui(si*, s−i) > ui(si, s−i) для кожної іншої стратегії si ≠ si* і кожного вибору інших s−i
Тут ui — виграш гравця i, s−i — стратегії всіх інших. На відміну від рівноваги Неша, де нерівність перевіряють лише проти рівноважних стратегій інших, тут вона мусить виконуватися проти всіх. Тому домінантна стратегія — набагато сильніша умова. Якщо в кожного гравця є строго домінантна стратегія, набір цих стратегій — єдина рівновага Неша гри. Зворотне хибне: рівновазі домінантні стратегії не потрібні. У полюванні на оленя (олень удвох дає по 4, заєць завжди 3, олень наодинці 0) жоден мисливець не має домінантної стратегії, а рівноваг дві.
Ще дві властивості викреслювання строго домінованих стратегій. Воно ніколи не викреслює рівновагу Неша. І порядок не важить: хоч би в якій послідовності викреслювати, залишиться той самий набір.
Нехай у вас три варіанти, а в суперника два: ліво і право. Варіант «Верх» дає 3 проти лівого і 0 проти правого, «Середина» — 0 і 3, «Низ» — 1 і 1. «Низ» не домінований жодним іншим варіантом: проти правого він кращий за «Верх», проти лівого кращий за «Середину». Але киньте монетку між «Верхом» і «Серединою»:
½ · 3 + ½ · 0 = 1,5 > 1 · ½ · 0 + ½ · 3 = 1,5 > 1
Монетка в середньому дає 1,5 проти будь-якого вибору суперника, а «Низ» лише 1. Так само спрацьовує будь-яка суміш, де «Верх» обирають з імовірністю між 1/3 і 2/3. Тож «Низ» домінований сумішшю, і розумний гравець його не обере, хоча жоден окремий варіант його не перемагає. Тому в строгій теорії стратегію викреслюють, якщо її домінує будь-яка суміш.
Зі слабко домінованими стратегіями викреслювання поводиться дивно. Візьміть гру, де у вас три варіанти, а в суперника два, ліво і право. Пари чисел — ваш виграш і виграш суперника.
Верх: (1, 1) і (0, 0) · Середина: (1, 1) і (2, 1) · Низ: (0, 0) і (2, 1)
«Середина» слабко домінує і «Верх», і «Низ». Викресліть спершу «Верх»: тоді суперникові «право» слабко краще за «ліво», і гра закінчується виграшами (2, 1). Викресліть спершу «Низ»: тепер суперникові слабко краще «ліво», і виходить (1, 1). Та сама гра, ті самі правила, а відповідь залежить від того, з чого почати. Зі строгим домінуванням такого не буває.
Набір стратегій, у якому нікому не вигідно змінити свою, поки інші не змінюють своїх.
У дилемі в'язня обидва зраджують, хоча мовчати вигідніше обом: рівновага не означає найкращий результат.
Розв'язування гри з кінця: спершу останній хід, потім передостанній, і так до першого.
У грі-стоніжці логіка велить забрати копійки на першому ж ході, хоча, граючи довше, обидва отримали б сотні, і живі люди так майже не роблять.
Усі знають факт, усі знають, що всі знають, і так без кінця.
Два генерали можуть обмінятися тисячею підтверджень і все одно не мати спільного знання, тож жоден не наважиться атакувати першим.