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