Теорія ігор і дизайн механізмів: найгірша гра сторіччя у бадмінтон та поділ торту

Основну задачу теорії ігор можна (дещо грубо і неформально) визначити наступним чином:

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

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

Одна з надзвичайно захопливих частин теорії ігор має трохи дивну назву Дизайн механізмів. Дизайн механізмів - це обернена задача до щойно описаної, яка полягає у створенні правил гри, які б гарантували певну поведінку раціональних гравців. Тобто, головний фокус дизайну механізмів зосереджений на формуванні інституцій, правил або стимулів (в залежності від контексту задачі), які мають спонукати гравців до певної бажаної поведінки. Відповідно, погані механізми спонукають учасників робити дивні на перший погляд речі. Один такий приклад, який яскраво ілюструє ідею описав у своїй книзі “20 лекцій з алгоритмічної теорії ігор” Тім Роугартен (запис його лекцій на ютубі ).

Отже, Олімпіада 2012 року, Лондон. Жіночій бадмінтон - не дуже скандальний вид спорту, що може піти не так? Тим не менш скандал стався і закінчився дискваліфікацією чотирьох команд і в усьому винна Данія… але про все по порядку.

Правила розіграшу були досить стандартні - є чотири групи, переможці кожної групи виходять на другі місця у відомому наперед порядку. Тобто, перша команда групи А виходить на другу команду групи C, а перша команда групи В - на другу команду групи D. ( повна розстановка). Далі відбуваються чвертьфінали, півфінали і, нарешті, фінал.

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

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

І тут не треба бути генієм, щоб зрозуміти ідею - програш дає кращі шанси на медалі. І ця думка прийшла всім в голову одночасно, тому далі спортсмени суперкласу почали розв’язувати складну проблему - як непомітно програти в бадмінтон команді, яка теж хоче програти. І це виявилось дуже непросто, ви можете “насолодитись” цим видовищем (там до речі в коментарях в основному читачі книги Роугартена, тобто студенти курсу теорії ігор):

посилання на ютуб
Китайці виявились вправнішими у забиванні воланчика під сітку. Цей результат запустив наступну хвилю. Через годину інша група визначала аналогічну розстановку між командами Індонезія-1 і Корея-2. Абсолютно з тих самих причин Корея-2 хотіла бути другою, щоб не потрапити на “переможців” корейців, а індонезійці не хотіли потрапити на китаянок з першого місця. Ні освистування глядачами, ні попередження суддів не допомогли. Врешті решт всі чотири команди були дискваліфіковані.

І найважливіше питання тут: чи винуваті гравці, які намагалися отримати краще парування, чи проблема в правилах, які заохочували їх до такої поведінки? Можливо, якби всі останні матчі проводилися одночасно (як це давно робиться у футболі), то такої ситуації б не виникло? Бажання організаторів, які з якихось міркувань поставили їх послідовно, та несподіваний виграш данців призвели до катастрофічного ланцюжка подій.

Отже, ви отримали уявлення, як правила стимулюють учасників до певної поганої поведінки. Розглянемо більш позитивний приклад.

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

Звичайно, може так статись, що тістечко фізично важко поділити на дві половинки (наприклад асиметрія, вишеньки або прикраси з крему) і тоді потрібно домовлятись, але поки що зупинимось на простому випадку.

Інтуїтивно зрозуміло, що схема поділу “один ріже, інший вибирає” є справедливою. Але справедливість можна розуміти по різному! В даному випадку справедливість визначається як “беззаздрісність”, тобто схема має гарантувати, що кожен учасник не повинен заздрити іншому. Не заздрити тут означає мати впевненість, що його шматок не більше за мій. Дійсно, якщо я ріжу тістечко і (ми вважаємо, що є повна “керованість”) можу вибирати як поділити, то я маю усвідомити, що найкраща стратегія іншого гравця - забрати більший шматок. Тому якщо я хочу отримати найбільше, то моя найкраща стратегія - ділити 50:50.

Але двоє учасників - то дуже простий випадок. Виявляється. алгоритм можна узагальнити на N гравців. І він буде беззаздрісним.

Задачу можна сформулювати наприклад так: троє ( але все вірно і для N) піратів зібрались біля купи скарбів і хочуть швидко поділити її, але у них по-перше немає часу, по-друге вони б хотіли, щоб процедура гарантувала беззаздрісність (бо коли тобі заздрить пірат - це іноді (тобто завжди) закінчується перерізаною горлянкою).

І така процедура існує. Вона полягає в наступному:

1. Перший пірат відділяє від купи частину, варту, на його думку ⅓ усього. Він передає хід другому пірату.
2. Другий пірат має або погодитись з першим або сказати: Тут більше третини і повернути те, що на його думку зайве на купу. Після цього хід переходить до третього пірата.
3. Третій пірат має або погодитись з першим і другим, що тут ⅓ , або повернути частину на купу.
4. Алгоритм повторюється до того часу коли всі погоджуються, при цьому частину отримує той, хто торкався її останнім.

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

Загалом, це лише одна з можливих схем поділу (можу присвятити цьому наступну публікацію, якщо цікаво).

Зауважу, ще, що іноді правил недостатньо, подивіться наступну рекламу (англійською)

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

Ще одним цікавим застосуванням Дизайну механізмів є правила (протоколи) переговорів. Цілком аналогічні протоколи можна створювати. наприклад, для опису транзакцій на он-лайнових біржах або аукціонах. Скажімо для вирішення проблеми гарантування чесності при купівлі товару за об’явою.

Один з найперших випадків створення незвичайних правил здійснення переговорів (торгівлі) в історії людства зафіксований у Геродота (ІV, 196) і пов'язаний він з спілкуванням карфагенян і африканських племен:

"Карфагеняни розповідають іще, що є країна в Лівії і в ній

живуть люди там за Геракловими стовпами, куди прибувши вони схо­дять на берег і вивантажують свої товари і розкладають їх на березі, а потім підіймаються на свої кораблі і дають сигнал димом, а тубільці, побачивши його, йдуть до моря і як обмін за товари кладуть золото і відходять від товарів. А карфагеняни тоді сходять із своїх кораблів і обстежують золото, і коли їм здається, що золота стільки, скільки коштують товари, забирають його і відходять, проте, якщо їм здається, що його недостатньо, вони знову підіймаються на кораблі і спокійно чекають, а тубільці приходять і додають ще золота, поки не задоволь­нять карфагенян. Проте ні ті, ні інші не хочуть зробити щось несправед­ливе. Адже ні ті не беруть золота, поки його не буває стільки, скільки коштують товари, і ці не беруть товарів, поки карфагеняни не візьмуть золото." (Турійця Геродота історії» К.: Наукова думка, 1993.)

Зауважте, як цікаво - по-перше, правилами гарантується, що результатом (якщо він досягається) задоволені обидві сторони. По-друге, всі знають, що якщо одна зі сторін обмане іншу, то більше (на значному проміжку часу) торгівлі не буде. Це дозволяє гарантувати чесність.