На кораблі п'ятеро піратів різного рангу і скриня зі 100 золотими монетами. Найстарший пропонує, як їх поділити, і голосують усі, разом із ним. Якщо «за» хоча б половина, так і ділять. Якщо ні, автора пропозиції викидають за борт, і пропонує наступний за рангом. Пірати бездоганно логічні: насамперед хочуть вижити, потім отримати якомога більше золота, а за інших рівних умов охоче викинуть когось за борт. Що запропонує капітан?
Здається, що капітанові доведеться ділити порівну або навіть віддати майже все, аби вижити. Насправді він залишає собі 98 монет, а по одній дає піратам 3 і 5. Вони погоджуються, бо без капітана не отримали б нічого. Уся хитрість у тому, щоб міркувати з кінця: від двох піратів до п'яти.
Ця головоломка — класика підготовки до співбесід на посади кількісних аналітиків: у збірнику Сіньфена Чжоу (2008) вона відкриває розділ головоломок як «Screwy pirates». Вона перевіряє одне вміння: міркувати з кінця. Математики називають це оберненою індукцією, і на ній тримається чимала частина теорії ігор.
П'ятеро піратів мають різні ранги: від 1 (капітан) до 5 (наймолодший). Двох піратів однакового рангу немає.
Найстарший із живих пропонує, скільки монет отримає кожен. Монети не ріжуть, і кожна зі 100 має комусь дістатися.
Голосують усі, і автор пропозиції теж. Якщо «за» щонайменше половина, поділ ухвалено. Інакше автора викидають за борт, і все повторюється з наступним за рангом.
Кожен пірат насамперед хоче вижити. Потім хоче якомога більше золота. А якщо йому однаково, як голосувати, він голосує «проти»: подивитися, як когось викидають за борт, теж приємно.
Який поділ запропонує капітан, щоб вижити і залишити собі якомога більше?
«Порівну, по 20: інакше команда збунтується»
Інші думають, що капітанові пощастить, якщо він узагалі виживе. Насправді він залишає собі 98 монет: голоси піратів 3 і 5 коштують лише по монеті, бо без капітана ці двоє не отримають нічого.
П'ятеро піратів, 100 монет, правила з умови. Зафіксуйте, скільки, на вашу думку, капітан може залишити собі й не полетіти за борт.
Тут з'явиться розбір вашої відповіді.
Важко вирішити? Відкривайте підказки по одній: спочатку легка, далі сильніша.
Пірат голосує не за справедливість. Він порівнює два майбутні: з цим капітаном і без нього. Тож спершу треба знати, що буде, якщо капітана викинуть за борт.
Міркуйте з кінця: розв'яжіть гру для двох піратів, потім для трьох, чотирьох і лише тоді для п'яти. Голос пірата коштує на одну монету більше, ніж він отримав би без капітана.
Залишаться пірати 4 і 5: пірат 4 сам становить половину і забирає всі 100. Тоді пірат 3 купує голос пірата 5 за одну монету: 99, 0, 1. Тепер так само порахуйте гру для чотирьох, а потім для п'яти.
Оберіть, скільки піратів на кораблі, і роздайте монети. Решта дістається вам. Кожен пірат голосує за правилами задачі: порівнює ваш поділ із тим, що отримає, якщо вас викинуть, і каже «за», лише коли ви даєте більше. Біля кожного голосу коротке пояснення.
Міркування з кінця можна перевірити грубою силою: перебрати всі можливі поділи, проголосувати за кожен і подивитися, де капітан отримує найбільше. А потім кинути на голосування сотні тисяч випадкових поділів і порівняти з точним підрахунком.
Рядок означає гру з n піратами, стовпець ранг. Кожен рядок обчислено з попереднього: капітан купує найдешевші голоси.
П'ятеро піратів, 100 монет. Капітан бере собі c монет, а решту розкидає між іншими чотирма навмання (усі розклади однаково ймовірні). Яка частка таких поділів пройде голосування? Лінія показує точну частку з повного перебору, точки показують симуляцію.
Пірат голосує не за справедливість, а порівнює два майбутні: з цим капітаном і без нього. Щоб знати друге, треба розв'язати гру з меншою командою. Тож починаємо з кінця.
Коли пірат лишився сам, усе золото його. Коли їх двоє, голос капітана вже становить половину, тож він забирає все. Кожна наступна сходинка спирається на попередню: пірат знає, що отримає, якщо капітана викинуть.
Пірат голосує «за», лише якщо отримує більше, ніж без капітана, бо за рівних умов радо голосує «проти». Тож голос пірата коштує на одну монету більше, ніж він отримав би в грі з чотирма. Піратам 3 і 5 там дістається 0, тож їхні голоси коштують по монеті. Капітанові потрібні три голоси з п'яти: свій і ще два.
Поділ 20, 20, 20, 20, 20 не провалиться: пірати 3, 4 і 5 отримують більше, ніж без капітана, і голосують «за». Проти лише пірат 2, бо без капітана він сам стане капітаном і забере 99. Але капітан платить 60 монет за три голоси, коли йому досить двох по монеті. Справедливість тут коштує йому 78 монет.
Другий за рангом чекає, коли викинуть капітана: тоді він сам ділить скриню і забирає майже все. Щоб купити його голос, довелося б дати йому щонайменше 100, а це вся скриня. Тож його не купують ніколи: у таблиці раунду 3 у стовпці рангу 2 лише нулі.
Звідси й чергування. Хто отримує монету в грі з n піратами, той нічого не отримає в грі з n + 1, і навпаки (крім самого капітана). Тому монети завжди йдуть рангам 3, 5, 7 і далі через одного.
Гра з піратами має повну інформацію: кожен знає все, що сталося, і всі можливі продовження. Таку гру розв'язують з кінця. Спершу знаходять найкращий хід в останній ситуації, потім у передостанній, знаючи, що буде далі, і так до початку.
Vn = G − (сума ⌈n/2⌉ − 1 найменших з xi(n−1) + 1)
Тут Vn означає частку капітана в грі з n піратами, а xi(n−1) те, що пірат i отримає в грі без капітана. Райнгард Зельтен 1965 року запропонував для таких ігор вимогу, яку тепер називають досконалою рівновагою в підіграх: стратегії мають бути найкращими не лише в справжній грі, а й у кожній її частині, навіть тій, до якої не дійде. Погроза «я проголосую проти, навіть собі на шкоду» тут нічого не важить, бо в момент голосування її ніхто не виконав би.
Потрібно щонайменше половину голосів. Один голос капітан має завжди, решту треба купити.
Кожен куплений голос коштує 1 монету: його продає пірат, який без капітана отримав би 0. Таких піратів завжди вистачає.
П'ятеро піратів і 100 монет: купити треба два голоси.
Межа: за 2G + 1 і 2G + 2 піратів капітан роздає всі монети й лишається з нулем, але живий. Далі монет на голоси вже не вистачає.
Формулу легко перевірити на таблиці з раунду 3: кожні два пірати коштують капітанові ще одну монету. Зверніть увагу: з непарним n і наступним парним капітан платить однаково, бо половина від парного n дорівнює більшості від n − 1.
Задача про піратів відкриває двері в три світи. У математиці вона показує, що буває, коли золота на всіх не вистачає. У логіці вона стикається з власною слабкістю: що, як суперник не такий логічний? А на практиці той самий підрахунок голосів допомагає зрозуміти переговори й парламентські коаліції.
Математика
Капітани, які виживають після 2G піратів:
Поки піратів не більше 2G + 2, капітан купує голоси по монеті. Далі монет не вистачає, і з'являється нова валюта: страх. Пірат, якого викинуть слідом за капітаном, голосує «за» безкоштовно, аби вижити.
Капітан із 2G + 3 піратів має G монет і свій голос, а треба G + 2: його викидають. Тоді капітан із 2G + 4 отримує безкоштовний голос наступного, і цього якраз досить. Від 2G + 5 до 2G + 7 капітани гинуть, і з кожним загиблим з'являється ще один наляканий виборець, тож капітан із 2G + 8 має G куплених голосів, 3 безкоштовні і свій: рівно половину. Наступні виживають на 2G + 16, 2G + 32 і так далі. Для 100 монет і 500 піратів це капітани з 201, 202, 204, 208, 216, 232, 264, 328 і 456 піратами. Версію з 500 піратами запропонував Стів Омохундро, Ієн Стюарт розібрав її в колонці для Scientific American у травні 1999 року, а ми перевірили її власним підрахунком.
Чесне застереження: уже з 2G + 2 піратами дешевих голосів більше, ніж монет, тож кому саме дістанеться монета, не визначено однозначно. Рівноваг багато. Але хто виживає, від цього не залежить: кожен голос, крім наляканих, коштує щонайменше монету, а монет лише G.
Логіка
Ви гравець A і ходите першим. На кожному ході можна забрати 4/5 купи (суперникові 1/5) або передати хід, і тоді купа подвоюється. Якщо після шостого ходу ніхто нічого не забрав, A отримує 256, а B 64.
Міркуйте з кінця. На шостому ході B забере 128, а не передасть хід заради 64. Знаючи це, A на п'ятому ході забере 64. Знаючи це, B на четвертому забере 32. І так до першого ходу: A забирає 4 одразу. Обидва отримують мізер, хоча могли б отримати в десятки разів більше.
Цю гру описав Роберт Розенталь 1981 року. 1992 року Маккелві і Палфрі провели в лабораторії саме таку шестихідну гру, лише в доларах: від 0,40/0,10 до 25,60/6,40. На першому ході забрали менше ніж 1% гравців: люди довіряють, а довіра окупається. Ланцюжок оберненої індукції крихкий: досить сумніву, що хоча б один гравець десь далі діятиме бездоганно, і вся конструкція руйнується. У піратів ланцюжок довжиною чотири сходинки, і кожна вимагає, щоб усі знали, що всі знають, що всі логічні.
Практика
Уявний парламент на 100 місць, для більшості потрібно 51. Клацайте партії, щоб додати їх до коаліції.
Капітан не купує зайвих голосів, бо кожен зайвий партнер забирає частку здобичі. Політолог Вільям Райкер 1962 року в книжці «The Theory of Political Coalitions» сформулював той самий «принцип розміру»: раціональні гравці складають коаліції, лише трохи більші за потрібну більшість. У цьому парламенті найбільша партія з 38 місцями не входить до найменшої виграшної коаліції: Б, В і Д разом мають рівно 51.
А от живі люди поводяться не як пірати. 1982 року Вернер Ґют, Рольф Шміттбергер і Бернд Шварце запустили гру «ультиматум»: один пропонує, як поділити суму, другий приймає або відмовляється, і тоді обидва не отримують нічого. Логіка піратів підказує запропонувати мінімум, а відповідач має його прийняти. За зведенням експериментів у книжці Коліна Камерера «Behavioral Game Theory» (2003), у середньому пропонують 40–50%, а пропозиції у 20% або менше відхиляють приблизно в половині випадків. Люди готові платити, щоб покарати жадібність, і пірат, який запропонує 98 із 100 живій команді, ризикує.
Ернст Цермело написав про шахи одну з перших статей теорії ігор. Теорема його імені каже: або білі можуть форсовано виграти, або чорні, або кожна сторона може забезпечити собі нічию. Сам Цермело не формулював її так і не міркував з кінця (Швальбе і Вокер, 2001). Сьогодні її доводять саме оберненою індукцією.
Вільям Райкер у книжці «The Theory of Political Coalitions» стверджував, що учасники складають коаліції саме такого розміру, який, на їхню думку, гарантує перемогу, і не більші. Капітан піратів купує рівно стільки голосів, скільки треба.
Роберт Розенталь описав гру, де обернена індукція велить забрати одразу, хоча терплячі гравці отримали б набагато більше. Назву пояснюють довгим деревом ходів: у ранніх версіях було до 100 «ніжок».
Ґют, Шміттбергер і Шварце опублікували перший експеримент із грою «ультиматум» у «Journal of Economic Behavior and Organization». Відтоді її повторили в багатьох країнах, і майже скрізь люди відкидають надто нечесні пропозиції, хоча це коштує їм грошей. Винятком стали мачігенга з перуанської Амазонії, які приймали майже будь-яку пропозицію (Генріх, 2000).
Райнгард Зельтен запровадив досконалу рівновагу в підіграх 1965 року в статті про олігополію. 1994 року він отримав премію Банку Швеції з економічних наук пам'яті Альфреда Нобеля разом із Джоном Нешем і Джоном Харсаньї.
У травні 1999 року Ієн Стюарт присвятив піратам колонку «A Puzzle for Pirates» у Scientific American і розібрав, що стається, коли піратів більше, ніж монет. Якщо піратів 500, а монет 100, за борт полетять 44 найстарші, і виживе лише капітан решти 456. Задачу йому надіслав Стів Омохундро, а у власній версії Стюарта піратів було 10.
Поділіться своїм поясненням, запереченням чи варіантом задачі. Для коментаря потрібен акаунт GitHub.
Я поступово додаю нові задачі, інші способи їх пояснити й розбори дискусій. Залиште email, і я напишу, коли з'явиться щось нове. Без спаму, відписатися можна в один клік.
Форма підписки з'явиться тут найближчим часом.