Словник / Зворотна індукція
На столі 50 центів. Двоє по черзі вирішують: забрати купку, і тоді собі 80%, а суперникові 20%, або передати хід, і купка подвоїться. Після шести передач гра закінчується: перший отримує 25,60 $, другий 6,40 $. Бездоганна логіка каже, що перший має забрати 40 центів одразу. Живі люди так майже не роблять і йдуть додому з більшими грошима. Хто тут помиляється?
Шар «На пальцях» приховано на всіх задачах.
Ці правила й суми взято з лабораторного експерименту 1992 року. Ходи 1, 3 і 5 належать гравцеві А, ходи 2, 4 і 6 гравцеві Б. Обидва хочуть отримати якомога більше для себе, обидва бачать усю гру наперед і знають, що суперник теж рахує. Як, на вашу думку, має зіграти А на першому ході?
Гру вигадав економіст Роберт Розенталь 1981 року, а 1992 року Річард Маккелві й Томас Палфрі зіграли її зі студентами на справжні гроші. Логіка обіцяла, що всі ігри закінчаться на першому ході. Так закінчилося близько 5%. Потім дослідники взялися за шахістів, які заробляють на розрахунку варіантів наперед, і отримали два протилежні результати.
Частка ігор (або гравців), які забрали гроші на першому ж ході. Дослідження грали схожі, але не однакові версії гри.
Найцікавіше в останньому дослідженні. Ті самі шахісти грали ще й «гонку до 100»: по черзі додають числа, хто скаже рівно 100, той виграв. Там зворотна індукція дає просту виграшну стратегію, і частина гравців розв'язала гру бездоганно. Але жоден із цих бездоганних логіків не забрав гроші на першому ході стоніжки. Рахувати з кінця вони вміли. Вони просто не вірили, що суперник рахуватиме так само.
Гонка до 21. Рахунок починається з нуля. Ви з ботом по черзі додаєте 1, 2 або 3, хто скаже рівно 21, той виграв. Тут немає довіри й жалю: один виграє, другий програє. Бот рахує з кінця. Як гадаєте, чи важливо, хто ходить першим?
Це спосіб розв'язати гру з кінця. Спершу дивимося на останній хід: там вибір очевидний, бо далі нічого немає. Знаючи це, вирішуємо передостанній хід, потім попередній, і так до першого. Ланцюжок дає єдину відповідь, і вона бездоганна, якщо гра має кінець, усі бачать усе, і кожен певен, що інші теж дорахують до кінця.
Остання умова і є слабкою ланкою. У гонці до 21 вона не потрібна: кожна позиція виграшна або програшна, хоч що думає суперник. У стоніжці від неї залежить усе: досить засумніватися в логіці суперника на одному з шести ходів, і ланцюжок розсипається.
Шар «Строго» приховано на всіх задачах.
Так знаходять те, що тепер називають рівновагою, досконалою за підіграми. Цю вимогу 1965 року запропонував Райнгард Зельтен: стратегії мають бути найкращими не лише у грі, що справді відбудеться, а й у кожній її частині. Через це порожні погрози не діють: якщо в потрібний момент виконувати погрозу невигідно, її ніхто не виконає, і всі це знають.
Уявіть натовп суперників Б. Більшість — бездоганні логіки: вони забирають гроші за першої ж нагоди, на другому ході. Але дехто просто довірливий і завжди передає. Ви — гравець А, і не знаєте, хто вам трапився. Порівняємо дві стратегії: забрати 40 центів одразу або передавати до кінця. Скільки довірливих має бути в натовпі, щоб друга стратегія приносила більше?
Лінії — точне середнє, точки — ваші 1000 ігор. Іграшкова модель: логік завжди забирає на другому ході, довірливий ніколи не забирає.
Відповідь мізерна: досить, щоб довірливим був один суперник зі 127. Бо втрачаєте ви копійки, 20 центів, а виграти можете 25 доларів. Звідси й сила сумніву: щоб зламати ланцюжок, не треба думати, що суперник дурний. Досить не бути цілком певним, що він бездоганний.
Шар «Глибше» приховано на всіх задачах.
ціль T, додавати від 1 до k: ключові числа — ті, що дають ту саму остачу від ділення на k + 1, що й T
Хто сказав ключове число, той виграв: хоч що додасть суперник, від 1 до k, ви доповните його хід до k + 1 і знову станете на ключове число, аж до самої цілі. Для гонки до 21 з кроками 1–3 це 1, 5, 9, 13, 17, 21: перший гравець каже 1 і виграє. Для гонки до 100 з кроками 1–10 це 1, 12, 23, …, 89, 100. У досліді Левітта, Ліста й Садоффа лише 12,6% пар шахістів знайшли правильний перший хід, число 1, а майже дві третини ігор «розв'язалися» лише на числі 78 чи пізніше.
q · 25,60 + (1 − q) · 0,20 > 0,40 ⇔ q > 0,20 / 25,40 = 1/127 ≈ 0,79%
Якщо забрати одразу, ви маєте 0,40 $ напевно. Якщо передавати, то з імовірністю q трапиться довірливий, і ви дійдете до кінця з 25,60 $, а з імовірністю 1 − q логік забере на другому ході й залишить вам 0,20 $. Межа точна для цієї іграшкової моделі. Маккелві й Палфрі будували тоншу: кожен гравець не знає, чи суперник альтруїст, і тоді навіть логіки на ранніх ходах часом передають. Щоб модель збіглася з їхніми даними, вистачало приблизно 5% альтруїстів.
1995 року Роберт Ауманн довів: якщо в грі з повною інформацією раціональність гравців є спільним знанням (кожен раціональний, кожен знає, що кожен раціональний, кожен знає, що кожен знає, і так без кінця), то гра закінчиться саме так, як велить зворотна індукція. Тож логіка стоніжки бездоганна. Питання лише в тому, чи бувають такі гравці.
А всередині самого міркування сидить пастка, яку 1989 року розібрали філософи Філіп Петтіт і Роберт Сагден. Щоб вирішити, чи брати на першому ході, А має уявити, що зробить Б на другому. Але Б потрапить на другий хід, лише якщо А передав, тобто зробив те, чого бездоганний логік ніколи не робить. Чому ж тоді Б має вірити, що далі А поводитиметься як бездоганний логік? Зворотна індукція спирається на віру в раціональність саме там, де ця віра вже спростована.
Варіант, який дає гравцеві більше за будь-який інший його варіант, хоч би що обрали інші.
Знижка вигідна кав'ярні, хоч би що зробила сусідня, але коли знижують обидві, кожна заробляє втричі менше, ніж якби обидві тримали ціну.
Набір стратегій, у якому нікому не вигідно змінити свою, поки інші не змінюють своїх.
У дилемі в'язня обидва зраджують, хоча мовчати вигідніше обом: рівновага не означає найкращий результат.
Усі знають факт, усі знають, що всі знають, і так без кінця.
Два генерали можуть обмінятися тисячею підтверджень і все одно не мати спільного знання, тож жоден не наважиться атакувати першим.