Теорія ігор навколо нас
Теорія ігор - це наука, яка розташована на перетині математики, економіки, досліджень поведінки людей, комп’ютерних наук та навіть біології. Що ж об’єднує всі ці різнорідні галузі? Спільним в них є наявність осіб-агентів (людей, компаній, програм), які ухвалюють рішення і намагаються отримати кращий для себе результат. Принциповим моментом, який, власне, формує гру є взаємозв’язаність учасників, коли дії одних гравців впливають на виграші інших. Ці взаємодії відбуваються навколо нас щодня і ми, свідомо чи несвідомо, беремо в них участь.
Прагнення досягти кращого результату в теорії ігор називається раціональністю. Кожний раціональний гравець має враховувати правила гри, інтереси і можливості інших учасників – тобто мислити стратегічно. Звичайно, як і в будь-якої наукової теорії, тут є обмеження і припущення, вважається, що гравці діють раціонально і не роблять помилок. В реальному житті це не завжди так. Теорія ігор не обіцяє вирішити всі проблеми тут і зараз, але її застосування роблять наше життя кращим.

Задумаємось на хвилинку, що було б, якби ми не враховували інтереси інших в стратегічних ситуаціях?
Одна така історія відома з колоніальної історії. Якось в Індії розплодились кобри і британська адміністрація у відповідності до свого досвіду з Британії (щодо вовків) призначила винагороду за кожну голову кобри. Через деякий час вони зрозуміли, що кількість сплаченої винагороди все зростає. Тубільці просто почали вирощувати кобр! Тоді розлючені британці оголосили про припинення будь-яких виплат. Що зробили індуси - просто повідпускали кобр на волю, бо це відповідало їх переконанням. Британці не врахували, що в стратегічній ситуації, яку вони створили у місцевих жителів можуть бути свої інтереси.
Описана вище історія, швидше за все, є анекдотом, тобто пізнішою придумкою, але вона описує реальну проблему. Пізніше аналогічні ситуації виникали не один раз і добре відомі. Цілком реальною, наприклад, є історія про ханойських пацюків, кількість яких намагались зменшити французи під час колоніального правління. Французи призначили фіксовану винагороду за один хвіст. І спробуйте вгадати, що сталося? Через певний час по Ханою почали бігати безхвості пацюки! Оскільки місцеві ловили, відрізали хвоста і відправляли тварин назад у каналізацію “на розплід”.
Цілком схожа ситуація сталась відносно недавно в Америці, де призначили винагороду за вбивство диких свиней,  що шкодили зеленим насадженням. Очікувалось зменшення або винищення популяції, натомість кількість свиней зросла. Люди почали підгодовувати коштовний товар.
Врешті і в Україні можна навести багато прикладів ефекту кобри. Наприклад, історія про “24 години” [докладно описано тут 1]. Вже давно відома схема ввезення товарів через кордон “човниками” для того, щоб не сплачувати повну вартість.  Велика партія дробиться на дрібні частини вартістю до 500 євро, і люди-фізособи завозять її безкоштовно. Всі знали про цю “діру” і, нарешті, в 2017 році Верховна Рада вирішила її закрити. Яким чином? Була прийнята норма про 24 години, які мають пройти між виїздом з України та поверненням з речами. Але до чого це призвело? За оцінками, зросла вартість товару для кінцевого споживача, ці гроші тепер витрачаються для “безпроблемного” перетину кордону.  А звичайні люди, які хочуть купити в сусідній країні щось дорожче 50 євро змушені лишатись на ніч.  Доходи окремих митників зросли і навряд це той результат, який очікували законодавці.
Отже, теорія ігор це не тільки і не стільки про ігри. Теорія ігор намагається використати математику для того, щоб розв’язати заплутану взаємодію інтересів гравців і знайти рішення, яке є раціональним в певному сенсі. Спробую проілюструвати головну ідею на прикладі ситуації, яка, мабуть, відома всім (можливо вже дещо втратила актуальність, але все ж включимо  фантазію). Як поділити тістечко (уявімо, що воно одне) між двома дітками? Як би акуратно не ділили батьки, діти все одно посваряться за право вибрати першим більший шматочок. Розв’язком є делегувати право ділити одному, а право вибирати першим іншому (можна навіть розіграти це випадково).  Тоді жадібність (або прагматичність) є гарантією справедливого поділу. Одна дитина не може сказати, що тістечко поділене не порівну, оскільки вона сама його ділила. Друга дитина теж не може жалітись, оскільки вона вибрала той шматок, який захотіла.
Проблема поділу тістечка - це приклад конфлікту інтересів. Кожна сторона хоче шматок якнайбільше, і в цьому вони співпадають. Розв’язок конфлікту залежить від рішень учасників - як поділити, яку частину вибрати. Важливим є те, що кожен намагається зрозуміти  як буде діяти інший. Саме “розв’язок наперед” дає першому гравцю розуміння, як буде діяти інший. Якщо він розріже тістечко на нерівні частини, то залишиться з меншою. Тому його виграшна стратегія - це поділити тістечко навпіл так рівно, як це можливо, це гарантує йому не менш як половину. Це і є розв’язком гри, який не залежить від щедрості або виховання, а є наслідком врахування власних інтересів, тобто егоїзму. Теорія ігор аналізує ситуації саме таким чином, тому її моделі корисні в багатьох областях людської діяльності.

Один з найяскравіших математиків 20 сторіччя, людина яка зробила внесок практично в кожну галузь математики, була співавтором ядерної бомби, розробила перший в світі комп’ютер та придумала теорію ігор. Джон фон Нейман (1903 – 1957)

Сучасна теорія ігор оформилась завдяки роботі Джона фон Неймана (і Оскара Моргенштерна). І, коли вони придумували цей термін, вони мали на увазі салонні ігри (покер, нарди, шахи) та стратегічні ситуації які при цьому виникають. Виявилось, що ці моделі придатні для розуміння багатьох проблем реального світу, зокрема досліджень фінансових ринків, процесів переговорів і торгівлі та інших областей економіки. Сам Нейман помер досить рано. Визнання і слава зустрілась з теорією ігор вже в дев'яностих роках минулого сторіччя, коли стали виникати зрозумілі людям застосування. На сьогодні теорію ігор використовують для розуміння поведінки людей в різних ситуаціях, дослідження еволюційних механізмів та побудови комп’ютерних алгоритмів. В 1994 році “нобелівку з економіки”* отримали Джон Неш, Джон Харсаньї та Рейнхард Зелтен – за концепцію рівноваги (Неша) та її застосування. Далі, в 1996  Вільям Вікрі (разом з іншими) – за внесок у теорію аукціонів та ігор з асиметричною інформацією. В 2005 році Роберт Ауман і Томас Шелінг, за вклад у розуміння процесів конфлікту і кооперації через аналіз моделей теорії ігор. В 2007, Леонід Гурвіц, Ерік Маскін і Роджер Майерсон, за фундаментальний вклад у розвиток теорії оптимальних механізмів, зокрема побудови аукціонів (до речі, Прозорро теж є аукціоном спеціального типу). Нарешті в 2012 році Ллойд Шеплі та Алвін Рот отримали премію за дослідження алгоритмів стійкого розподілу і їх застосування до вивчення ринків.

Зупинимось на деяких несподіваних застосуваннях теорії ігор. В 1962 році була надрукована стаття з дещо дивною назвою: “Подача документів у коледж та стабільність шлюбу” Девіда Гейла і Ллойда Шеплі. Справа в тому, що тоді в американській пресі обговорювалась проблема вступу до університетів. Тоді це відбувалось за знайомою нам схемою: бажаючі подавали документи в різні навчальні заклади, і вступна комісія проводила відбір. Проблема полягала в тому, що у приймальної комісії немає можливості зрозуміти, наскільки пріоритетний даний заклад для претендента, а у претендента - оцінити свої шанси у конкуренції з іншими. В результаті виникає базова дилема:

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

Кандидат має вибирати між потужними універами з конкурсом і ризиком з одного боку та слабкими універами з гарантованим вступом  - з іншого. Таким чином, ситуація перетворюється на гру “вгадай, куди поступати”. Гейл і Шеплі запропонували алгоритм, який гарантує “якісне” парування. Саме цей алгоритм нещодавно був імплементований в новому законі “Про вищу освіту” .

В 2005-2007 роках Алвін Рот застосував ідею алгоритму Гейла-Шеплі для створення ринку донорства нирок. Справа в тому, що є два типи донорства нирки: звичайне (від людини, яка загинула в катастрофі, наприклад) та живе, коли людина віддає одну свою нирку і живе з одною. Проблема полагає в тому, що не всі нирки сумісні, до того ж в США заборонено отримувати за донорство органу “будь-яких коштовні вигоди”, тому можливим є лише одночасний обмін (тобто одночасна операція). Алвін Рот запропонував алгоритм, який дозволяв створювати цілі ланцюжки операцій і автоматично парував донорів з різних частин країни. В 2003 році в Сполучених Штатах було усього 19 операцій від живих американських донорів. Після запуску алгоритму кількість операцій стрімко зростала: 400 за 2012 рік, 5300 операцій за 2017 рік. Тому їх нобелівська премія 2012 року була цілком заслужена, рідко коли математичні результати дозволяють рятувати життя так наочно.

Алвін Рот, математик, який рятує життя.

Нарешті, найбільш суттєвим застосуванням у грошовому розумінні є аукціони. Аукціон те теж гра: є гравці - учасники аукціону, є правила проведення аукціону і визначений виграш - це отримана вартість мінус витрати на участь. Виявляється, що правила аукціону можуть суттєво впливати на поведінку учасників. Правильний вибір аукціону може значно підвищити виграші і саме цим займається теорія ігор - конструює аукціони і намагається передбачити їх властивості. Можливо найбільш відомим прикладом є процес продажі частот (радіо, ТВ та пізніше інтернет) в США. Спочатку це був адміністративний процес, потім, у 80хх, після численних скарг, його замінили на лотерею. Але в якийсь рік частоти вартістю півтора мільйони доларів отримала асоціація дантистів (яка просто подала заявку на участь в лотереї). Тому в 1993 році влада запросила групу спеціалістів з теорії ігор з метою створення нового аукціону. Був запропонований багатокроковий аукціон з одночасними торгами. В результаті виручка зросла на порядок. З 1994 року протягом 87 аукціонів було отримано 60 мільярдів доларів

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