Теорія ігор і дизайн механізмів : найгірша гра сторіччя у бадмінтон та поділ торта
Основну задачу теорії ігор можна ( дещо грубо і неформально ) визначити наступним чином :
Нехай задані гравці , їх бажання і можливості впливу на ситуацію ( правила гри ) .
Тоді що можна було б сказати про раціональні рішення гравців , тобто такі рішення коли гравці а ) намагаються отримати найкращий результат , б ) здатні обчислити наслідки своїх рішень і розв’язувати будь-які складні задачі .
Звичайно , в реальності не завжди можна визначити бажання і правила .
Припущення раціональності є також ідеалізацією , але задача теорії ігор полягає саме в пошуку “ ідеального рішення ” .
Скажімо , концепція рівноваги є таким рішенням , тобто ситуацією , яка має виникати при стратегічній взаємодії раціональних гравців , і є чисто математичним результатом .
Іноді це рішення допомагає зрозуміти процеси , які відбуваються навколо нас , іноді ні ( і тоді виникає питання : а чому ж люди ведуть себе інакше і цим займається поведінкова теорія ігор ) .
Але говорити , що теорія ігор не працює тільки тому , що іноді люди ведуть себе нераціонально , це все одно що говорити , наче математика не працює , оскільки дехто не вміє додавати числа .
Одна з надзвичайно захопливих частин теорії ігор має трохи дивну назву — Дизайн механізмів .
Дизайн механізмів — це обернена задача до щойно описаної , яка полягає у створенні правил гри , які б гарантували певну поведінку раціональних гравців .
Тобто головний фокус дизайну механізмів зосереджений на формуванні інституцій , правил або стимулів ( залежності від контексту задачі ) , які мають спонукати гравців до певної бажаної поведінки .
Відповідно , погані механізми спонукають учасників робити дивні , на перший погляд , речі .
Один такий приклад , який яскраво ілюструє ідею , описав у своїй книзі “ 20 лекцій з алгоритмічної теорії ігор ” Тім Роугартен .
Отже , Олімпіада 2012 року , Лондон .
Жіночий бадмінтон — не дуже скандальний вид спорту , що може піти не так ?
Тим не менш , скандал стався і закінчився дискваліфікацією чотирьох команд , і в усьому винна Данія … але про все за порядком .
Правила розіграшу були досить стандартні — є чотири групи , переможці кожної групи виходять на другі місця у відомому наперед порядку .
Тобто перша команда групи
А виходить на другу команду групи C , а перша команда групи В — на другу команду групи D . ( повна розстановка ) .
Далі відбуваються чвертьфінали , півфінали і , нарешті , фінал .
Тепер про бажання команд — як у будь-якому спорті вищого рівня гравці хочуть медаль вищого можливого гатунку , крім того , ще є командний залік країни , тому бажано мати більше медалей .
І вони будуть робити все , що необхідно , щоб покращити свої шанси на виграш .
Організатори , в свою чергу , зацікавлені в тому , щоб ігри були видовищні і цікаві для глядачів .
Важлива деталь — ігри останнього раунду групового етапу були рознесені в часі .
Драма почалась , коли команда Данії несподівано обіграла фаворитів — китайських спортсменів ( далі Китай - 1 ) .
Обидві команди вийшли в наступний раунд , але Китай - 1 тепер займав друге місце .
На їхню біду , інша група , яка також мала двох фаворитів , що забезпечили собі одне з перших місць — друга команда Китаю ( Китай - 2 ) та команду Південної Кореї ( Корея - 1 ) .
Перше місце цієї групи виходило на Китай - 1 у півфіналі і китайці зіткнулись із перспективою не взяти золото і срібло .
І тут не треба бути генієм , щоб зрозуміти ідею — програш дає кращі шанси на медалі .
І це думка прийшла всім в голову одночасно , тому далі спортсмени суперкласу почали розв’язувати складну проблему — як непомітно програти в бадмінтон команді , яка теж хоче програти .
І це виявилось дуже непросто , ви можете “ насолодитись ” цим видовищем ( там , до речі , в коментарях в основному читачі книги Роугартена , тобто студенти курсу теорії ігор ) .
Китайці виявились вправнішими у забиванні воланчика під сітку .
Цей результат запустив наступну хвилю .
Через годину інша група визначала аналогічну розстановку між командами Індонезія - 1 і Корея - 2 .
Абсолютно з тих самих причин Корея - 2 хотіла бути другою , щоб не потрапити на “ переможців ” корейців , а індонезійці не хотіли потрапити на китаянок з першого місця .
Ні освистування глядачами , ні попередження суддів не допомогли .
Врешті - решт усі чотири команди були дискваліфіковані .
І найважливіше питання тут : чи винуваті гравці , які намагалися отримати краще парування , чи проблема в правилах , які заохочували їх до такої поведінки ?
Можливо , якби всі останні матчі проводилися одночасно ( як це давно робиться у футболі ) , то такої ситуації б не виникло ?
Бажання організаторів , які з якихось міркувань поставили їх послідовно , та несподіваний виграш данців призвели до катастрофічного ланцюжка подій .
Отже , ви отримали уявлення , як правила стимулюють учасників до певної поганої поведінки .
Розгляньмо більш позитивний приклад .
Якщо потрібно поділити одне тістечко на двох діток , це може закінчитись скандалом та сльозами .
Адже кожен хоче отримати більший шматочок , особливо більший , ніж у брата / сестри .
Відоме майже всім рішення полягає у тому , щоб призначити одну дитину різати , а іншу — вибирати першою .
І це є чудовим прикладом дизайну механізму .
Дійсно , правила , по-перше , гарантують , що перша дитина буде старатись поділити якомога рівніше ( в ідеалі — навпіл ) , а інша отримає можливість вибрати першою — тобто забезпечить собі як мінімум половину .
Звичайно , може так статись , що тістечко фізично важко поділити на дві половинки ( наприклад , асиметрія вишеньки або прикраси з крему ) і тоді потрібно домовлятись , але поки що зупинимось на простому випадку .
Інтуїтивно зрозуміло , що схема поділу “ один ріже , інший вибирає ” є справедливою .
Але справедливість можна розуміти по-різному !
У даному випадку справедливість визначається як “ беззаздрісність ” , тобто схема має гарантувати , що кожен учасник не повинен заздрити іншому .
" Не заздрити " тут означає мати впевненість , що його шматок не більший за мій .
Дійсно , якщо я ріжу тістечко і ( ми вважаємо , що є повна “ керованість ” ) можу вибирати як поділити , то я маю усвідомити , що найкраща стратегія іншого гравця — забрати більший шматок .
Тому якщо я хочу отримати найбільше , то моя найкраща стратегія — ділити 50 : 50 .
Але двоє учасників — то дуже простий випадок .
Виявляється .
алгоритм можна узагальнити на N гравців .
І він буде беззаздрісним .
Задачу можна сформулювати , наприклад , так : троє ( але все вірно і для N ) піратів зібрались біля купи скарбів і хочуть швидко поділити її , але у них , по-перше , немає часу , по-друге , вони б хотіли , щоб процедура гарантувала беззаздрісність ( бо коли тобі заздрить пірат — це іноді ( тобто завжди ) закінчується перерізаною горлянкою ) .
І така процедура існує .
Вона полягає в наступному :
Перший пірат відділяє від купи частину , варту , на його думку ⅓ усього .
Він передає хід другому пірату .
Другий пірат має або погодитись із першим , або сказати : тут більше третини і повернути те , що , на його думку , зайве , на купу .
Після цього хід переходить до третього пірата .
Третій пірат має або погодитись із першим і другим , що тут ⅓ , або повернути частину на купу .
Алгоритм повторюється до того часу , коли всі погоджуються , при цьому частину отримує той , хто торкався її останнім .
Цей алгоритм спонукає піратів ділити якомога точніше і гарантує , що жоден пірат не може заявити , що його ошукали , оскільки він мав можливість вибрати частину або не погодитись з її розміром .
Загалом це лише одна з можливих схем поділу ( можу присвятити цьому наступну публікацію , якщо цікаво ) .
Зауважу ще , що іноді правил недостатньо , подивіться наступну рекламу ( англійською ) .
Як ви думаєте , чому схема не спрацювала ?
Один із братів отримав явно більший шматок .
Ще одним цікавим застосуванням Дизайну механізмів є правила ( протоколи ) переговорів .
Цілком аналогічні протоколи можна створювати .
наприклад , для опису транзакцій на онлайнових біржах або аукціонах .
Скажімо , для вирішення проблеми гарантування чесності при купівлі товару за об’явою .
Один із найперших випадків створення незвичайних правил здійснення переговорів ( торгівлі ) в історії людства зафіксований у Геродота ( ІV , 196 ) і пов'язаний він зі спілкуванням карфагенян і африканських племен :
" Карфагеняни розповідають іще , що є країна в Лівії і в ній
живуть люди там за Геракловими стовпами , куди прибувши вони схо­дять на берег і вивантажують свої товари і розкладають їх на березі , а потім підіймаються на свої кораблі і дають сигнал димом , а тубільці , побачивши його , йдуть до моря і як обмін за товари кладуть золото і відходять від товарів .
А карфагеняни тоді сходять із своїх кораблів і обстежують золото , і коли їм здається , що золота стільки , скільки коштують товари , забирають його і відходять , проте , якщо їм здається , що його недостатньо , вони знову підіймаються на кораблі і спокійно чекають , а тубільці приходять і додають ще золота , поки не задоволь­нять карфагенян .
Проте ні ті , ні інші не хочуть зробити щось несправед­ливе .
Адже ні ті не беруть золота , поки його не буває стільки , скільки коштують товари , і ці не беруть товарів , поки карфагеняни не візьмуть золото " ( " Турійця Геродота історії » К . : Наукова думка , 1993 ) .
Зауважте , як цікаво — по-перше , правилами гарантується , що результатом ( якщо його досягають ) задоволені обидві сторони .
По-друге , всі знають , що якщо одна зі сторін обмане іншу , то більше ( на значному проміжку часу ) торгівлі не буде .
Це дозволяє гарантувати чесність .
