Індукція назад
Що таке зворотна індукція?
Індукція назад в теорії ігор – це ітераційний процес міркувань назад у часі, від кінця проблеми чи ситуації, для вирішення кінцевої екстенсивної форми та послідовних ігор та висновку про послідовність оптимальних дій.
Пояснення зворотної індукції
Індукція назад використовується для вирішення ігор, оскільки Джон фон Нейман і Оскар Моргенштерн встановили теорію ігор як навчальний предмет, коли вони опублікували свою книгу ” Теорія ігор та економічна поведінка” в 1944 році.
На кожному етапі гри індукція назад визначає оптимальну стратегію гравця, який робить останній хід у грі. Потім визначається оптимальна дія наступного до останнього гравця, що рухається, приймаючи дії останнього гравця, як зазначено. Цей процес триває назад, доки не буде визначено найкращі дії для кожного моменту часу. Фактично, одним є визначення рівноваги Неша для кожної підігри оригінальної гри.
Однак результати, виведені з індукції назад, часто не можуть передбачити реальну гру людини. Експериментальні дослідження показали, що «раціональна» поведінка (як передбачає теорія ігор) рідко проявляється в реальному житті. Ірраціональні гравці насправді можуть отримати виграші більші, ніж передбачали зворотні індукції, як це показано в грі сороконіжка.
У грі з сороконіжкою два гравці по черзі отримують шанс взяти більшу частку зростаючого банку грошей або передати банк іншому гравцеві. Виграш організований таким чином, що якщо банк передає опоненту, а опонент бере банк у наступному раунді, отримує трохи менше, ніж якщо би взяв банк у цьому раунді. Гра закінчується, як тільки гравець бере запас, при цьому гравець отримує більшу частину, а інший гравець отримує меншу частину.
Приклад зворотної індукції
Як приклад, припустимо, що гравець А йде першим і повинен вирішити, чи повинен він «взяти» чи «передати» схованку, яка наразі становить 2 долари. Якщо він бере, тоді А і В отримують по 1 долару, але якщо А проходить, рішення взяти або здати зараз повинен приймати Гравець В. Якщо Б бере, вона отримує 3 долари (тобто попередній запас 2 $ + 1 долар) а А отримує 0 дол. Але якщо B проходить, A тепер вирішує, брати чи здавати тощо. Якщо обидва гравці завжди вирішили пройти, кожен з них отримує виграш у розмірі 100 доларів в кінці гри.
Сенс гри полягає в тому, що як А, так і В співпрацюють і продовжують проходити до кінця гри, вони отримують максимальну виплату в розмірі 100 доларів за кожну. Але якщо вони не довіряють іншому гравцеві і сподіваються, що вони «приймуть» за першої нагоди, рівновага Неша прогнозує, що гравці приймуть мінімально можливу вимогу (1 долар у цьому випадку).
Рівновага Неша в цій грі, коли жоден гравець не має стимулу відступити від обраної ним стратегії, обміркувавши вибір суперника, свідчить про те, що перший гравець взяв банк у перший же раунд гри. Однак насправді це робить порівняно мало гравців. В результаті вони отримують вищий виграш, ніж виграш, передбачений аналізом рівноваги.
Розв’язування послідовних ігор за допомогою зворотної індукції
Нижче – проста послідовна гра двох гравців. Етикетки з програвачем Player 1 та Player 2 – це набори інформації для гравців одного або двох відповідно. Цифри в дужках внизу дерева – це виграш у кожній відповідній точці. Гра також є послідовною, тому гравець 1 приймає перше рішення (ліворуч або праворуч), а гравець 2 приймає рішення після гравця 1 (вгору або вниз).
Індукція назад, як і вся теорія ігор, використовує припущення про раціональність та максимізацію, що означає, що Гравець 2 максимізує свій виграш у будь-якій ситуації. У будь-якому наборі інформації ми маємо два варіанти, усього чотири. Усунувши вибір, який гравець 2 не обере, ми можемо звузити наше дерево. Таким чином, ми позначимо лінії синім кольором, які максимізують виграш гравця за заданим набором інформації.
Після цього зменшення Гравець 1 може максимізувати свої виграші тепер, коли вибір Гравець 2 став відомим. Результатом є рівновага, знайдена шляхом зворотної індукції гравця 1, вибравши «право», і гравця 2, вибравши «вгору». Нижче наведено рішення гри з рівноважним шляхом.
Наприклад, можна легко налаштувати гру, подібну до наведеної вище, використовуючи компанії в якості гравців. Ця гра може включати сценарії випуску продуктів. Якщо компанія 1 хотіла випустити продукт, що може зробити компанія 2 у відповідь? Чи випустить компанія 2 подібний конкуруючий продукт? За прогнозування продажів нового продукту в різних сценаріях, ми можемо створити гру, щоб передбачити, як події можуть розгортатися. Нижче наведено приклад того, як можна моделювати таку гру.