Захопившись ідеями домінування стратегій

Талант — це людина у якої виникла велика ідея. Людина в якої виникло дві великі ідеї — геній. В цьому сенсі фон Нейман геній — він придумав Теорію ігор і комп'ютер.

Джейкоб Броновскі

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

Щоб краще пояснити процес давайте розглянемо приклад — гру Камінь-Ножиці-Папір, яку знають всі діти (можливо під різними назвами). Якщо грають двоє учасників, то у кожного є три можливі дії — вибрати К(амінь), Н(ожиці) або П(апір). Відомо, що ножиці ріжуть папір, але тупляться об камінь, а папір обгортає (перемагає) камінь. Також відомо, що однакові дії означають нічию. Позначимо перемогу 1, нічию 0 і програш -1, тоді формалізація однокрокової гри в вигляді матриці така:

Як розуміти цю матрицю відносно гри? Перший гравець обирає рядки, другий — стовпці. Вони роблять вибір одночасно та незалежно. В результаті їх вибори реалізується певна пара стратегій. Клітинка, яка їй відповідає і є результатом гри — перше число в ній це виграш першого гравця, друге — виграш другого. Наявність декількох (навіть двох!) гравців суттєво ускладнює — не зовсім зрозуміло тепер, що таке розв'язання гри. Коли гравець один можна казати про оптимальний розв'язок — ми шукаємо рішення, яке дає максимальне значення виграшу. А якщо мої виграші залежать від дій іншого, як можна зрозуміти що у нього в голові? Про це і поговоримо в цій публікації.

Ідея домінуючих і домінованих стратегій

Прагнення досягти кращого результату в теорії ігор називається раціональністю. Кожний раціональний гравець має враховувати правила гри, інтереси і можливості інших учасників – тобто мислити стратегічно. Теорія ігор дозволяє проаналізувати та краще зрозуміти такі ситуації, причини конфліктів, навчитись ухвалювати рішення у складних умовах, налагоджувати взаємовигідну кооперацію та багато іншого. Якщо ми хочемо отримати кращий результат, то, можливо, спробуємо виділити ситуації і ігри де це можна зробити просто? Розглянемо, наприклад, таку гру:

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

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

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

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

Розглянемо ускладнений варіант попередньої гри. Вона вже не така очевидна, домінуючої стратегії немає в жодного з гравців (переконайтесь в цьому). Як бачимо в матриці додались клітинки з великими виграшами — 10, 7 та навіть 11.

Щоб розв'язати цю гру потрібні додаткові міркування. Розглянемо стратегію С другого гравця. Він може отримати -2, 7 або 2. Але стратегія П дає йому 2, 10 і 5 відповідно, що є кращими виграшами. Стратегія С також гірша за стратегію Л. Л дає можливість отримати -1, 11, 2 що у двох випадках більше ніж С і в одному виграші однакові. Таким чином, стратегія С є домінованою, вона гірша ніж П і Л. Зауважимо, що ні Л ні П не є домінуючими — десь краще одна, а десь — друга. Але оскільки С така погана, то раціональний гравець не буде грати її взагалі. Дійсно, краще вже вибрати Л або П. Штука в тому (і це досить сильне припущення), що перший гравець знає те, що перший гравець — раціональний. Тому він буде аналізувати ситуацію, яка склалась з урахуванням цього. Тоді виникає нова матриця, в який другий гравець не грає стратегію С.

Тепер перший гравець розуміє, що його стратегія С також домінована. С дає йому можливість отримати 1 в будь-якому разі. Але вибравши стратегію В він отримує 5 та 2. До речі, тут ситуація дещо інша — Н не є завжди краща за С. Але навіть наявності однієї стратегії, яка завжди краща за С достатньо, щоб раціональний гравець викреслив її з свого арсеналу. Отже, отримуємо матрицю

Яку ми щойно розв'язували. Тобто, рівновага нової матриці і старої — одна й та сама (В, П), а виграші 2 і 2. Процес, який ми щойно описали називається ітеративне видалення домінованих стратегій (ІВДС).

Цей результат може здатися дивним, адже пара стратегій (С, С) давала гравцям можливість отримати 10 та 7. Це ж набагато більше!

Але давайте поміркуємо логічно. Щоб трішки наблизити до реальності уявіть, що ви граєте в цю гру на якомусь сайті, невідомо з ким, один раз і на реальні гроші. Для гарантії множте виграш на будь-яку суму в доларах. Уявіть, що ви перший гравець і хочете вибрати С, щоб отримати 10, розраховуючи, що інший гравець теж вибере С і отримає 7. Ви дійсно повірите, що він вибере С в цьому випадку? Якщо він буде вважати, що ви виберете С, то він вибере Л, отримає 11 і лишить вам 1. Це цілком реально.Але тоді вам краще вибирати В, щоб отримати 5 замість 1. І якщо він не повний дурень, то, очевидно, він вибере П, бо це найкраще, що він може зробити у відповідь на вибір В. Таким чином, (В, П) — це дуже логічний вибір обох.

Застосуємо тепер цей метод до розв'язання задач. Як ми побачимо — це досить потужний інструмент.

Задача про транспорт

П'ятеро гравців (A, B, C, D, E) їздять на роботу кожен день. Вони можуть їхати машиною або автобусом. Якщо вони їдуть машиною, то кожен платить різну ціну (1, 3, 5, 7, 9 відповідно). Якщо вони їдуть автобусом, то вартість квитка залежить від того яка кількість гравців використовує автобус. Якщо використовує один, то квиток коштує 10, двоє — 8, троє — 6, четверо — 4 і якщо всі використовують, то 2. Як ви думаєте, хто з учасників буде використовувати машину, а хто добиратись автобусом?

подумайте перед тим як читати далі

Розв'язок

Будувати матрицю не вийде, бо вона буде дуже велика, тому почнемо з пошуку домінованих стратегій. В кожного гравця є дві стратегії (М(ашина) та А(втобус)). Розглянемо стратегії першого гравця. Він може отримати 1 для всіх ситуацій, якщо вибере М та різні виграші (в залежності від стратегій інших), якщо вибере А. Але в випадку А може заплатити: 2, 4, 6, 8, 10. Цілком зрозуміло, що його стратегія М є строго домінуючою. Отже, стратегію А можна видалити з розгляду.

Тепер розглянемо другого гравця. Він може отримати 3, якщо вибере М. Якщо він обере А, то тепер (після того як перший видалив стратегію А) він може заплатити 4, 6, 8, 10. Отже, стратегія А є строго домінуючою для В. Аналогічно можна продовжити міркування для C, D та Е. Результат — всі їдуть машинами.

Ви можете сказати, що це дивно — адже А може дещо змінити свої виграші, погодитись, що заплатити 2 краще ніж заплатити 1 і всі щасливо їдуть в автобусі? З точки зору бажаного результату — можливо, але чи ви самі погодитесь поїхати в автобусі замість машини, особливо коли він незручний, старий і переповнений? Мабуть правильніше не очікувати від людей альтруїстичних дій, а працювати над тим, щоб бажана ситуація була рівновагою для всіх учасників.

Процес ітеративного видалення домінованих стратегій може бути і не таким очевидним.

Коли вигідно мати можливість спалювати гроші

Є одна класична гра. Скажімо, є шоу, де двоє гравців мають вибрати (одночасно і незалежно) А або В і вони ділять 500 доларів. Якщо вони обоє вибирають А, то виграші розподіляються (першому і другому) 400, 100. Якщо обоє вибирають В, то виграші розподіляються 100, 400. Якщо ж вибори не співпадають то отримують 0 0. В цій грі немає чіткого рішення — є три рівноваги Неша (одна в змішаних і дві в чистих стратегіях). І будь-яка має право на існування.

Тепер припустимо, що перед рішенням у першого гравця виникає можливість спалити 200 доларів (може палити або не палити) і другий це бачить.

Як ви думаєте чи може це змінити хід гри і яким чином?

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

Не заглиблюючись в деталі набори стратегій (А, В) та (В, А) є рівновагами Неша. Дійсно, при відхиленні від них кожен учасник програє.

Тепер припустимо, що перший гравець спалює 200 доларів. Тепер матриця буде наступна

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

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

Повертаючись до гри зі спалюванням грошей. В першого гравця є три точки гри, де він може вибирати дії. Перша — там де він може спалити 200 доларів. Дії тут {С(палити), Н(е спалювати)}. Потім дві гри в яких він має вибрати А або В. Але це різні ігри. Хоча ці дві ситуації неможливі одночасно, для визначення стратегії необхідно визначити свою дію в кожній з них.

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

Отже, побудуємо матрицю (подумайте, чому стратегій саме стільки)

Тепер застосуємо процес ІВДС.

1 крок. Стратегії С, ВА і С, ВВ першого гравця є строго доміновані стратегією Н, АА.

2 крок. Стратегія ВА другого гравця слабо домінована стратегією АА.

Стратегія ВВ другого гравця слабо домінована стратегією АВ.

3 крок. Стратегія Н, АВ і стратегія Н, ВВ першого гравця доміновані стратегіями С, АА і С, АВ відповідно.

4 крок. Стратегія АА другого гравця слабо домінуюча.

Останній крок — перший гравець вибирає Н, АА або Н, ВА

Обидві стратегії дають йому 400.

Резюме. Без можливості спалювати гроші гравці мають декілька точок рівноваги. Всі рівноваги рівноправні і вибрати одну з них неможливо. У першого гравця виникає можливість спалити 200 доларів. Він їх не спалює і вибирає А — інший теж вибирає А і це — рівновага.

Це рішення цілком логічне, але звісно не дуже практично — сподіватися, що всі гравці здатні на такий аналіз наївно.

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

Тому цілком обґрунтованим способом переконання могло б стати наступний ланцюжок тез (від першого гравця):

1. Якщо я спалюю 200 доларів, то вибирати мені В абсолютно не вигідно. Я просто втрачу гроші в будь-якому випадку крім А. Тому, якщо я спалюю гроші — я точно вибираю А.
2. Раз я вибираю А в першому випадку, то твої стратегії ВВ і ВА — гірші за інші. Вони будуть давати завжди менший або рівний виграш. Тому немає сенсу їх вибирати.
3. Знаючи це я не буду вибирати В в грі, де я не спалюю гроші — це дає мені 100, в той час як вибір спалювати, А дає 200.
4. Знаючи, що я не буду вибирати В в другій грі — тобі теж краще вибирати АА, бо отримати 100 гарантовано краще ніж отримати іноді 100, іноді 0.
5. Отже рівновага — Н, АА та АА дає нам обом 400 і 100 відповідно.