Теорія ігор — це математичне вивчення стратегічного прийняття рішень серед раціональних агентів. Від дилеми в'язня до еволюційної біології рівноваги Неша розкривають, чому індивідуально раціональні вибори можуть призводити до колективно катастрофічних результатів — і як співпраця може попри це виникнути.
Гра в математичному сенсі — це модель будь-якої ситуації, де кілька агентів приймають рішення, і результат кожного агента залежить не лише від власного вибору, а й від виборів інших. Три складові визначають кожну гру: множину гравців, множину доступних стратегій для кожного гравця та функцію виплат, що відображає кожну комбінацію вибору стратегій у значення результату для кожного гравця.
Для двогравцевих ігор структуру виплат зручно представити як матрицю виплат: рядки відповідають стратегіям Гравця 1, стовпці — стратегіям Гравця 2, а кожна клітинка містить упорядковану пару (виплата Гравця 1, виплата Гравця 2), що є результатом цієї комбінації. Читання матриці дозволяє визначити, які стратегії привабливі для кожного гравця з огляду на їхні переконання про те, що зробить інший.
Домінантна стратегія — це та, що дає вищу виплату для гравця незалежно від того, що робить будь-який інший гравець. Коли домінантна стратегія існує, раціональний гравець завжди її обере — жодних прогнозів щодо опонентів не потрібно. Не всі ігри мають домінантні стратегії, але коли вони є, аналіз значно спрощується.
Найвідоміша гра в усій теорії ігор — дилема в'язня. Двох підозрюваних допитують окремо. Кожен може або Співпрацювати (мовчати, позначено C), або Зрадити (видати іншого, позначено D). Виплати в роках тюремного терміну, яких вдалося уникнути:
Якщо обидва мовчать, кожен отримує один рік (кооперативний результат, виплата -1 кожному). Якщо один зраджує, а інший мовчить, зрадник виходить на волю (виплата 0), а вірний партнер отримує три роки (-3). Якщо обидва зраджують, обидва отримують два роки (-2 кожному). Тепер розгляньмо міркування Гравця 1: якщо Гравець 2 співпрацює, Гравець 1 отримує -1 при співпраці, але 0 при зраді — зрада краща. Якщо Гравець 2 зраджує, Гравець 1 отримує -3 при співпраці, але -2 при зраді — зрада все одно краща. Зрада є домінантною стратегією для обох гравців. Проте результат (D, D) з виплатами (-2, -2) гірший для всіх, ніж взаємна співпраця (-1, -1). Це основна напруга в усіх соціальних дилемах: індивідуальна раціональність призводить до колективної неефективності.
Центральним розв'язковим поняттям некооперативної теорії ігор є рівновага Неша, названа на честь математика Джона Неша, який довів її існування 1950 року. Формально профіль стратегій (s1*, s2*, ..., sn*) є рівновагою Неша, якщо жоден окремий гравець не може підвищити власну виплату, односторонньо перейшовши на іншу стратегію, тримаючи стратегії всіх інших гравців фіксованими. Стратегія кожного гравця є найкращою відповіддю на стратегії всіх інших гравців.
Теорема існування Неша гарантує, що кожна скінченна гра — з скінченною кількістю гравців і скінченними множинами стратегій — має принаймні одну рівновагу Неша, можливо в мішаних стратегіях, де гравці рандомізують свої чисті стратегії. Цей результат, доведений за допомогою теореми про нерухому точку Какутані, є одним з основоположних досягнень математики 20 століття.
У дилемі в'язня (Зрада, Зрада) — єдина рівновага Неша. Якщо Гравець 1 зраджує, найкраща відповідь Гравця 2 — теж зрадити (оскільки -2 > -3). Симетрично для Гравця 2. Жоден гравець не може покращити свою виплату, перейшовши в односторонньому порядку — рівновага стабільна, хоча вона й гірша за Парето за (Співпраця, Співпраця).
Рівноваги Неша в мішаних стратегіях виникають, коли жодна чиста стратегія не є завжди найкращою. У «Камінь-ножиці-папір» будь-яку чисту стратегію можна побити, тож єдина рівновага Неша — це рандомізація кожного гравця рівномірно: кожна дія розігрується з ймовірністю 1/3. Логіка в тому, що гравець буде мішати лише тоді, коли йому байдуже між чистими варіантами — а ця байдужість точно підтримується ймовірностями мішання опонента.
Коли існує кілька рівноваг, теорія ігор стикається з проблемою вибору рівноваги. У «Полюванні на оленя» двоє мисливців можуть обрати полювання на оленя разом (висока винагорода, вимагає координації) або на кролика поодинці (гарантовано, але нижча винагорода). І (Олень, Олень), і (Кролик, Кролик) — рівноваги Неша. Перша домінує за виплатою; друга домінує за ризиком. Яку рівновагу досягнуть гравці, залежить від переконань, спілкування та фокальних точок — питань, які теорія ігор сама по собі не може повністю вирішити.
Одноразова дилема в'язня захоплює гравців у зраду. Але що відбувається, коли ті самі гравці зустрічаються повторно? Ітерована дилема в'язня усе змінює: репутація, взаємність і тінь майбутнього стають стратегічно значущими. Гравець, що зраджує сьогодні, ризикує помстою завтра, роблячи співпрацю потенційно стійкою як раціональну довгострокову стратегію.
Політолог Роберт Аксельрод провів у 1980 році знамениту серію комп'ютерних турнірів, запросивши теоретиків ігор подати стратегії для ітерованої дилеми в'язня. Найпростіша подана стратегія — «Око за око» — виграла обидва турніри. «Око за око» співпрацює на першому ході, а потім дзеркально повторює те, що опонент зробив минулого раунду. Вона доброзичлива (ніколи не зраджує першою), карає (негайно карає за зраду), вибачає (повертається до співпраці, щойно це робить опонент) і зрозуміла (легко вивчається опонентами). Ці чотири властивості пояснюють її стійкість проти широкого кола конкуруючих стратегій.
Еволюційна теорія ігор, започаткована Джоном Мейнардом Смітом і Джорджем Прайсом, запитує не яка стратегія індивідуально раціональна, а які стратегії можуть вижити в популяції, що зазнає природного добору. Стратегія є еволюційно стабільною стратегією (ESS), якщо популяцію гравців, що її використовують, не може захопити мала група мутантів, що використовують будь-яку альтернативну стратегію. Формально стратегія I є ESS, якщо для будь-якої мутантної стратегії J:
Модель «Яструби і Голуби» чудово це ілюструє. Яструби завжди загострюють конфлікти за ресурси і б'ються, доки одна зі сторін не отримає травму. Голуби завжди демонструють, але тікають, якщо опонент загострює конфлікт. У популяції суцільних Голубів мутант-Яструб має дуже добрі справи (він виграє кожен конфлікт без травм). У популяції суцільних Яструбів мутант-Голуб має кращі справи за середнє (він уникає дорогих бійок). Жодна чиста стратегія не є ESS; замість цього виникає стабільна рівновага з мішаною частотою, за якої обидва типи співіснують. Частота ESS для Яструбів — p* = V/C, коли V < C, де V — цінність ресурсу, а C — вартість програшу бійки.
Важливо, що співпраця може також еволюціонувати в просторових умовах навіть без добору спорідненості чи повторюваної взаємодії. Коли агенти грають на ґратці й взаємодіють лише із сусідами, кооператори можуть формувати кластери, що захищають одне одного від експлуатації. Геометрія локальної взаємодії дозволяє співпраці зберігатися там, де вона була б витіснена в добре перемішаній популяції.
Теорія ігор стала незамінною практично в кожній соціальній і природничій науці. Її математичний каркас перетворює якісні інтуїції про стратегічну поведінку на точні, перевірювані прогнози.
У промисловій організації моделі Бертрана та Курно використовують рівновагу Неша для прогнозування цін та обсягів на олігополістичних ринках. Дизайн аукціонів значною мірою спирається на теорію ігор: аукціон Вікрі (другої ціни) має примітну властивість — заявляти свою справжню цінність є домінантною стратегією, роблячи чесність індивідуально раціональною. Нобелівська галузь дизайну механізмів (Майєрсон, Маскін, Гурвіч, 2007) ставить обернене запитання: за бажаного соціального результату, які правила гри змусять зацікавлених у собі агентів його виробити?
Системи голосування демонструють стратегічні маніпуляції: парадокс Кондорсе показує, що більшісна перевага може циклічно замикатися (A перемагає B, B перемагає C, C перемагає A) без стабільного переможця. Ядерне стримування під час Холодної війни аналізується як рівновага Неша: взаємне гарантоване знищення (MAD) стабільне саме тому, що жодна сторона не може виграти, завдавши удару першою — похмурий теоретико-ігровий аргумент на користь стабільності через катастрофічну загрозу. Формування коаліцій у парламентах використовує кооперативну теорію ігор і значення Шеплі для розподілу влади між партіями.
Тваринні конфлікти, чесна сигналізація (принцип гандикапу Захаві — дорогі сигнали надійні, бо їх не можна дешево підробити) та коеволюція паразитів і господарів усі моделюються як еволюційні ігри. Статевий добір, альтруїзм серед родичів (правило Гамільтона: rb > c) та еволюція злоби мають теоретико-ігрові пояснення, вкорінені у виплатах пристосованості.
Парадокс Браеса — один із найбільш контрінтуїтивних результатів алгоритмічної теорії ігор: додавання нової дороги до мережі може сповільнити всіх водіїв, коли кожен маршрутизує егоїстично. Причина в тому, що нова дорога зсуває потоки трафіку в рівновазі Неша так, що загальний затор зростає. Інтернет-пошук і показова реклама використовують механізми Вікрі-Кларка-Гровса (VCG) для стимулювання чесних ставок у реальному часі мільярди разів на день.
Перегляньте інтерактивні симуляції алгоритмів і теорії ігор — побачте, як агенти співпрацюють, конкурують та еволюціонують стратегії в реальному часі.
Теорія ігор поділяється на некооперативну теорію ігор (аналіз стратегічної взаємодії між зацікавленими в собі гравцями без обов'язкових угод — основа більшості економіки) та кооперативну теорію ігор (вивчення формування коаліцій і справедливого розподілу, коли обов'язкові угоди можливі). Інші розділи включають еволюційну теорію ігор (застосування теорії ігор до біологічної еволюції), дизайн механізмів (обернена теорія ігор — розробка правил для досягнення бажаних результатів) та повторювані ігри (аналіз довгострокової стратегічної взаємодії).
Гра з нульовою сумою — це гра, де загальна виплата всім гравцям стала — виграш одного гравця точно дорівнює програшу іншого. Шахи, покер і конкурентні ринки товарів з фіксованою пропозицією приблизно є грами з нульовою сумою. Теорема мінімакса (фон Нейман, 1928) гарантує, що кожна двогравцева гра з нульовою сумою має оптимальний розв'язок у мішаних стратегіях. Більшість реальних економічних і соціальних ситуацій мають ненульову суму — співпраця може створювати цінність для всіх сторін.
Зворотна індукція — метод розв'язання послідовних ігор (розгорнутої форми). Починаючи з останнього вузла рішення, визначається оптимальна дія. Потім рух назад до попереднього вузла, припускаючи, що майбутня гра буде оптимальною. Продовжується до кореня. Ця процедура знаходить досконалу підігрову рівновагу Неша — набір стратегій, які є рівновагами Неша в кожній підгрі, усуваючи недостовірні погрози. Вона розв'язує шахи в принципі (хоча непрактично через розмір дерева гри).
Народна теорема стверджує, що в нескінченно повторюваних іграх будь-який індивідуально раціональний результат (де кожен гравець отримує принаймні свою мінімаксну виплату) можна підтримати як рівновагу Неша, якщо гравці достатньо терплячі (коефіцієнт дисконтування близький до 1). Це пояснює, як довгострокові стосунки підтримують співпрацю, яка була б неможливою в одноразових іграх: загроза майбутнього покарання підтримує теперішню хорошу поведінку.
Теорія аукціонів застосовує теорію ігор до аукціонів — механізмів розподілу товарів серед учасників торгів. Ключові формати аукціонів включають англійський (з підвищенням ціни), голландський (зі зниженням ціни), закритий торг першої ціни та Вікрі (закритий торг другої ціни). Теорема еквівалентності доходу показує, що вони генерують однаковий очікуваний дохід за симетричних умов. Аукціони Вікрі мають домінантні стратегії чесних заявок. Теорія аукціонів застосовується до прав на спектр, онлайн-реклами (Google AdWords) та державних закупівель.
В іграх з повною інформацією (шахи, шашки) усі гравці знають повну історію гри та все дерево гри. В іграх з неповною інформацією (покер, «Дипломатія») гравці мають приватну інформацію — власні карти — яку інші не знають. Неповна інформація вносить стратегічний блеф і сигналізацію. Теорія ігор обробляє неповну інформацію за допомогою баєсівської рівноваги Неша (гравці оптимізують за переконаннями про приватну інформацію інших).
Рівновага Неша в мішаних стратегіях передбачає рандомізацію гравцями своїх чистих стратегій відповідно до розподілів ймовірностей. Навіть ігри без рівноваги Неша в чистих стратегіях завжди мають рівновагу в мішаних стратегіях (теорема Неша). Гравці мішають, коли кожна використовувана ними чиста стратегія дає рівну очікувану виплату. У тенісі оптимальна стратегія подачі передбачає змішування подач у корпус і по лінії, щоб опоненти не могли скористатися передбачуваністю.
Значення Шеплі — це розв'язкове поняття кооперативної теорії ігор, яке справедливо розподіляє загальну цінність, створену коаліцією, серед гравців на основі їхніх граничних внесків. Кожен гравець отримує свій середній граничний внесок за всіма можливими порядками формування коаліції. Значення Шеплі задовольняє чотири аксіоми: ефективність (розподіляє всю цінність), симетрію (рівні гравці отримують рівні частки), лінійність та фіктивність (гравці, що не додають цінності, нічого не отримують). Воно використовується в розподілі витрат, аналізі виборчої влади та атрибуції ознак у машинному навчанні (значення SHAP).
Проблема принципала-агента (теорія контрактів) вивчає ситуації, коли принципал (роботодавець, акціонер) делегує роботу агенту (працівнику, менеджеру) з іншою інформацією та, можливо, іншими інтересами. Агент може ухилятися (моральний ризик) або спотворювати свій тип (несприятливий добір). Оптимальний дизайн контракту узгоджує стимули через моніторинг, оплату за результатами, опціони та механізми репутації. Ключові застосування: компенсація CEO, страхові франшизи, франчайзингові угоди.
Теорія ігор моделює ядерне стримування (взаємне гарантоване знищення як рівновага Неша), торгові переговори (повторювана дилема в'язня з репутацією), гонки озброєнь (ігри координації), формування альянсів (теорія коаліцій) та режими санкцій. Шеллінг у своїй книзі 1960 року «Стратегія конфлікту» започаткував використання теорії ігор для міжнародної безпеки. Карибську кризу широко аналізували як гру в «боягуза», де рішучість і комунікація обох сторін формували рівновагу.