Індукція назад, індукція з кінця або обернена індукція — це процес міркування обернений у часі, від кінця задачі або ситуації, щоб визначити послідовність найсприятливіших дій. Він рухається розглядаючи останню точку, в якій треба ухвалювати рішення і тоді з'ясовує яка дія буде найоптимальнішою в цю мить. Послуговуючись цими даними, ви можете визначити, що робити під час ухвалення другого з кінця рішення. Цей процес триває назад в часі допоки не буде визначено найліпші дії для всіх можливих становищ (наприклад, для кожної можливої ) у кожну точку в часі. Індукцію назад вперше в 1875 році ужив Артур Кейлі, який відкрив метод намагаючись розв'язати горезвісну задачу про перебірливу наречену.
У математичній оптимізації оптимізації в методі динамічного програмування індукція назад це один з головних підходів для розв'язання рівняння Беллмана.Jerome Adda and Russell Cooper, «Dynamic Economics: Quantitative Methods and Applications», Section 3.2.1, page 28. MIT Press, 2003.Mario Miranda and Paul Fackler, «Applied Computational Economics and Finance», Підрозділ 7.3.1, сторінка 164. МІТ Прес, 2002. У теорії ігор, індукція назад це метод використовуваний для обчислення у послідовних іграх.Drew Fudenberg and Jean Tirole, «Game Theory», Підрозіл 3.5, сторінка 92. МІТ Прес, 1991. Єдина різниця це те, що оптимізація залучає лише одного ухвалювача рішень, який обирає, що робити кожної миті, тоді як теорія ігор аналізує як взаємодіють рішення кількох гравців. Тобто передбачаючи, що останній гравець робитиме в кожній ситуації, ми можемо визначити, що робитиме другий з кінця гравець і так далі. У пов'язаних галузях автоматизованого планування та диспетчеризації й автоматизованого доведення теорем, метод називається пошуком назад або зворотним виводом. У шахах він відомий як ретроспективний аналіз.
Індукцію назад використовували для розв'язання ігор так довго як довго існувала теорія ігор. Джон фон Нейман і Оскар Морґенштерн запропонували розв'язувати ігри з нульовою сумою і двома гравцями за допомогою індукції назад у їхній книжці Теорія ігор і економічної поведінки (1944), ця книжка вводила теорію ігор як напрямок для дослідження.Mathematics of Chess , webpage by John MacQuarrie.Джон фон Нейман і Оскар Морґенштерн, «Theory of Games and Economic Behavior», Підрозділ 15.3.1. Princeton University Press. Третє видання, 1953. (Перше видання, 1944.)
Індукція назад в ухвалені рішень: задача оптимальної зупинки Розгляньмо безробітну людину, яка зможе працювати ще десять років t = 1,2,…,10. Припустімо, що кожен рік, протягом якого вона залишається безробітною, їй можуть запропонувати «хорошу» роботу з оплатою 100 доларів або «погану» роботу з оплатою 44 долари з рівною ймовірністю (50/50). Щойно вона погодиться на роботу, вона залишатиметься на цій роботі протягом решти десяти років. (Для простоти припустимо, що вона дбає лише про свої грошові доходи, і що вона оцінює доходи в різний час однаково, тобто ставка дисконту дорівнює одиниці.)
Чи повинна ця людина погоджуватися на погану роботу? Щоб відповісти на це запитання, ми можемо міркувати в зворотному напрямку від часу t = 10.
У момент часу 10 цінність прийняття хорошої роботи становить 100 доларів США; цінність погодження на погану роботу становить 44 долари; цінність відмови від доступної роботи рівне нулю. Тому, якщо вона все ще залишається безробітною впродовж останнього періоду, вона повинна прийняти будь-яку роботу, яку їй пропонують на той час. У момент часу 9 цінність прийняття хорошої роботи становить 200 доларів (бо ця робота триватиме два роки); цінність погодження на погану роботу рівна 2*44$ = 88$. Цінність відхилення пропозиції про роботу зараз становить 0 доларів США плюс вартість очікування наступної пропозиції про роботу, яка становитиме або 44 долари США з імовірністю 50 %, або 100 доларів США з імовірністю 50 %, для середнього («очікуваного») значення 0,5*(100$+44$)=72$. Тому, незалежно від того, хороша чи погана вакансія, доступна в момент часу 9, краще прийняти цю пропозицію, ніж чекати кращої. У момент часу 8 цінність прийняття хорошої роботи становить 300 доларів (вона триватиме три роки); цінність погодження на погану роботу становить 3*$44 = $132. Цінність відхилення пропозиції роботи зараз становить 0 доларів США плюс вартість очікування пропозиції роботи в момент 9. Оскільки ми вже дійшли висновку, що пропозиції в момент 9 повинні бути прийняті, очікувана вартість очікування пропозиції роботи в момент 9 дорівнює 0,5*(200$+88$) = 144$. Тому в момент 8 цінніше чекати наступної пропозиції, ніж погоджуватися на погану роботу. Продовжуючи роботу у зворотному напрямку, можна переконатися, що погані пропозиції слід приймати, лише якщо людина все ще безробітна в 9 або 10 моментів; їх слід відхиляти в будь-який час до t = 8. Інтуїція полягає в тому, що якщо хтось очікує працювати на роботі протягом тривалого часу, це робить більш цінним бути вибагливим щодо того, яку роботу прийняти.
Задача динамічної оптимізації такого типу називається задачею оптимальної зупинки, бо питання полягає в тому, коли припинити очікування кращої пропозиції. — це галузь мікроекономіки, яка застосовує задачі такого типу до таких контекстів, як покупки, пошук роботи та шлюб.
Індукція назад в теорії ігор У теорії ігор обернена індукція є концепцією рішення. Це уточнення концепції раціональності, яка чутлива до окремих в екстенсивному представленні гри. Ідея оберненої індукції використовує послідовну раціональність шляхом визначення оптимальної дії для кожної інформації в даному дереві гри.
У «Стратегії: Вступ до теорії ігор» Джоела Уотсона процедура зворотної індукції визначається як: «Процес аналізу гри від кінця до початку. На кожному вузлі прийняття рішень вилучаються з розгляду будь-які дії, які є домінуючими, враховуючи термінальні вузли, які можуть бути досягнуті через гру дій, визначених на наступних вузлах».
Одним із недоліків процедури зворотної індукції є те, що її можна застосовувати лише до обмежених класів ігор. Процедура чітко визначена для будь-якої гри з досконалою інформацією без прив'язки до користі. Вона також чітко визначена й значуща для ігор ідеальної інформації зі зв'язками. Однак це призводить до понад одного профілю стратегії. Процедуру можна застосувати до деяких ігор з нетривіальними інформаційними множинами, але в цілому вона ненадійна. Процедура найкраще підходить для розв'язування ігор з ідеальною інформацією. Тому, якщо всі гравці не усвідомлюють дії інших гравців і виграші на кожному вузлі від прийняття рішень, тоді обернену індукцію не так легко застосувати. (Ватсон с. 188)
Процедуру зворотної індукції можна продемонструвати на простому прикладі.
Багатоетапна гра
Розгляньмо , в якій беруть участь 2 гравці. Гравці планують піти в кіно. Зараз є 2 фільми, які дуже популярні, Джокер і Термінатор. Гравець 1 хоче дивитися Термінатора, а Гравець 2 хоче дивитися Джокера. Гравець 1 першим купить квиток і повідомить Гравцю 2 про свій вибір. Тоді Гравець 2 купить свій квиток. Після того як вони обидва спостерігатимуть за вибором, вони вирішать, піти їм у кіно чи залишитися вдома. Як і на першому етапі, гравець 1 обирає першим. Потім гравець 2 робить свій вибір після спостереження за вибором гравця 1.
У цьому прикладі ми припускаємо, що виграш додається на різних етапах. Гра є грою з повною інформацією.
Матриця нормальної форми:
Стадія 1 Джокер Термінатор Джокер 3, 5 0, 0 Термінатор 1, 1 5, 3
Стадія 2 Піти в кіно Залишитись вдома Піти в кіно 6, 6 4, -2 Залишитись вдома -2, 4 -2, -2 гри Джокер/Термінатор: Кроки для розв'язання цієї багатоетапної гри з великою формою, як показано праворуч:
Зворотна індукція починає розв'язувати гру з останніх вузлів. Гравець 2 спостерігатиме за 8 з останніх вузлів, щоб вибрати «Піти на фільм» або «Залишитися вдома». Гравець 2 загалом зробить 4 порівняння. Він обере варіант з більшим виграшем. Наприклад, якщо розглядати першу підгру, виграш 11 більший, ніж 7. Тому Гравець 2 обирає «Піти на фільм». Метод продовжується для кожної підгри. Коли Гравець 2 завершить свій вибір, Гравець 1 зробить свій вибір на основі вибраних підігор. Процес подібний до кроку 2. Гравець 1 порівнює свої виграші, щоб зробити свій вибір. Підігри, не обрані Гравцем 2 на попередньому кроці, більше не розглядаються обома гравцями, оскільки вони не є оптимальними Наприклад, вибір «Піти в кіно» пропонує виграш 9 (9,11), а вибір «Залишитися вдома» пропонує виграш 1 (1, 9). Гравець 1 обере «Піти на фільм». Процес повторюється для кожного гравця, доки не буде досягнуто початковий вузол. Наприклад, Гравець 2 обере «Джокера», оскільки виграш 11 (9, 11) більший, ніж «Термінатор» з виграшем 6 (6, 6). Наприклад, гравець 1 у початковому вузлі обере «Термінатор», оскільки він пропонує вищу винагороду 11. Термінатор: (11, 9) > Джокер: (9, 11) Щоб визначити , нам потрібно визначити маршрут, який обирає оптимальну підгру для кожної інформаційної множини. У цьому прикладі Гравець 1 обирає «Термінатор», а Гравець 2 також обирає «Термінатор». Потім обидва обирають «Піти на фільм». Ця досконала за підіграми рівновага призводить до виграшу (11,9)
Гра в ультиматум Індукція назад — це «процес аналізу гри від кінця до початку». Як і при розв'язуванні інших рівноваг Неша, передбачається раціональність гравців і повне знання. Концепція оберненої індукції відповідає цьому припущенню, бо загальновідомо, що кожен гравець діятиме раціонально з кожним вузлом ухвалення рішень, коли він обирає варіант — навіть якщо його раціональність означатиме, що такий вузол не буде досягнутий». Отже, за умови взаємного припущення раціональності, індукція назад дозволяє кожному гравцеві точно передбачити, що буде робити його суперник на кожному етапі гри.
Щоб розв'язати за допомогою оберненою індукції, гру слід записати в розгорнутій формі, а потім розділити на підігри. Починаючи з підгри найдальшої від початкового вузла або початкової точки, очікувані виграші, зазначені для цієї підгри, зважуються, і раціональний гравець вибере для себе варіант із вищою віддачею. Вибирається та позначається вектор найбільшого виграшу. Знайдіть ідеальну рівновагу в підгрі, постійно працюючи назад від підгри до підгри, поки не досягнете початкової точки. У міру того, як цей процес просувається, ваша початкова гра в екстенсивній формі ставатиме все коротшою. Цей позначений шлях векторів є ідеальною рівновагою підгри.
Індукція назад, застосована до гри в ультиматум Подумайте про гру між двома гравцями, де гравець 1 пропонує розділити один долар з гравцем 2. Це відома асиметрична гра, у яку грають послідовно і називають . Перший гравець діє першим, розділяючи долар так, як вважає за потрібне. Тепер другий гравець може прийняти частину, яку йому роздав перший гравець, або відмовитися від розподілу. Якщо гравець 2 приймає розподіл, то гравець 1 і гравець 2 отримують виграш відповідно до цього розподілу. Якщо другий гравець вирішить відхилити пропозицію гравця 1, обидва гравці нічого не отримають. Іншими словами, гравець 2 має право вето на запропонований розподіл гравця 1, але застосування вето усуває будь-яку винагороду для обох гравців. Таким чином, профіль стратегії для цієї гри можна записати у вигляді пар (x, f(x)) для всіх x від 0 до 1, де f(x)) є двозначною функцією, яка виражає, приймається x чи ні.
Розгляньмо вибір і відповідь гравця 2 на будь-яку довільну пропозицію гравця 1, припускаючи, що пропозиція перевищує 0 доларів. Використовуючи обернену індукцію, безсумнівно, ми очікуємо, що гравець 2 прийме будь-яку виграш, що перевищує або дорівнює 0 доларів. Відповідно, гравець 1 повинен запропонувати дати гравцеві 2 якомога менше, щоб отримати найбільшу частину розподілу. Якщо гравець 1 дає гравцеві 2 найменшу грошову одиницю, а решту залишає собі, це унікальна ідеальна рівновага в підгрі. Гра «Ультиматум» має кілька інших рівноваг Неша, які не є ідеальними підіграми і тому не потребують індукції назад.