У теорії ігор дилема в'язня (ДВ) — гра з ненульовою сумою, в якій гравці прагнуть одержати вигоду, співпрацюючи один з одним або зраджуючи. Як у всій теорії ігор, передбачається, що гравець («в'язень») максимізує свій власний виграш, не піклуючись про вигоду інших.

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

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

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

Класична дилема в'язня

Класична дилема ув'язненого така: Двоє підозрюваних, А і Б, арештовані. У поліції немає достатніх доказів для звинувачення, і ізолювавши їх один від одного, вони пропонують їм одну і ту ж операцію: якщо один свідчить проти іншого, а той зберігає мовчання, то перший звільняється, а другий одержує 10 років в'язниці. Якщо обидва мовчать, у поліції мало доказів, і вони засуджуються до 6 місяців. Якщо обидва свідчать проти один одного, вони одержують по 2 роки. Кожен ув'язнений вибирає, мовчати або свідчити проти іншого. Проте жоден з них не знає точно, що зробить інший. Що відбудеться?

Гру можна представити у вигляді такої таблиці:

В'язень Б зберігає мовчання В'язень Б надає свідчення В'язень А зберігає мовчання Обидва одержують півроку. А одержує 10 роківБ звільняється В'язень А надає свідчення А звільняєтьсяБ одержує 10 років в'язниці Обидва одержують 2 роки в'язниці

Дилема з'являється, якщо припустити, що обидва піклуються тільки про мінімізацію власного терміну ув'язнення.

Уявимо міркування кожного з ув'язнених. Якщо партнер мовчить, то найкраще його зрадити і вийти на свободу (інакше — півроку в'язниці). Якщо партнер свідчить, то найкраще теж свідчити проти нього, щоб одержати 2 роки (інакше — 10 років). Стратегія «свідчити» строго домінує над стратегією «мовчати». Аналогічно, інший ув'язнений приходить до того ж висновку.

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

Узагальнена форма

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

У грі — два гравці і банкір. Кожен гравець тримає 2 карти: на одній написано «співпрацювати», на іншій — «зрадити» (це стандартна термінологія гри). Кожен гравець кладе одну карту перед банкіром написом вниз (тобто ніхто не знає чужого рішення, хоча знання чужого рішення не впливає на аналіз домінування). Банкір відкриває карти і видає виграш.

Якщо обидва вибрали «співпрацювати», обидва одержують C. Якщо один вибрав «зрадити», іншій «співпрацювати» — перший одержує D, другий с. Якщо обидва вибрали «зрадити» — обидва одержують d.

Значення змінних C, D, с, d можуть бути будь-якого знаку (у прикладі вище все менше або рівні 0). Обов'язково повинна дотримуватися нерівність D > C > d > c, щоб гра була ДВ.

+ Канонічна матриця виграшів ДВСпівпрацюватиЗрадитиСпівпрацюватиC, Cc, DЗрадитиD, cd, d

Якщо гра повторюється, тобто грається більше 1 разу поспіль, загальний виграш від співпраці повинен бути більшим сумарного виграшу за ситуації, коли один зраджує, а інший — ні (пояснення — нижче):

2C > D + c

Ці правила були встановлені Дугласом Гофштадтером і утворюють канонічний опис типової дилеми в'язня.

Схожа, але інша гра

ГофштадтерГофштадтер Дуглас, Метаматичні питання: у пошуку суті свідомості і шаблону (Metamagical Themas: questing for the essence of mind and pattern). 1985. Bantam Dell Pub Group. ISBN 0-465-04566-9 , глава 29. припустив, що люди простіше розуміють завдання, як завдання ДВ, якщо вона представлена у вигляді окремої гри або процесу торгівлі. Один з прикладів — «обмін закритими сумками»: Дві людини зустрічаються і обмінюються закритими сумками, розуміючи, що одна з них містить гроші, інша — товар. Кожен гравець може поважати операцію і покласти в сумку те, про що домовилися, або обдурити партнера, давши порожню сумку.

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

У варіації, популярній у програмістів і хакерів кожен агент цієї гри пам'ятає попередні результати (або має доступ до громадської думки, «колективної пам'яті»), і безліч обмінів повторюються тривалий час.

Як зазначено вище, без пам'яті ця гра має мало сенсу, вона мало що пояснює в поведінці систем і груп людей, окрім опису взаємодій, які не відбуватимуться. Складнощів вводиться більше, ніж можна чекати. Програміст (особливо який спеціалізується на функціональному програмуванні) відразу зрозуміє значущість часу і стану (пам'яті). Але і без написання програм можна припустити, як поведуться агенти. Наскільки велика пам'ять кожного агента? Яка стратегія кожного з них? Як агенти з різними стратегіями розподілені і що визначає, хто з ким взаємодіє і в якому порядку?

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

Виконана деяка робота з моделюванню цього. Різні програмісти і математики стверджують, що стратегія «око за око» (див. нижче) — якнайкраща загальна стратегія, проте не було зроблено серйозних академічних зусиль, щоб класифікувати різні типи і розподіли агентів, що навчаються, з різними стратегіями.

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

Приклади з реального життя

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

У політології, наприклад, сценарій ДВ часто використовується для ілюстрації проблеми двох країн, залучених в перегони озброєнь. Обидві заявлятимуть, що у них є дві можливості: або збільшити витрати на військові потреби, або скорочувати озброєння. Жодна із сторін не може бути впевнена, що інша дотримуватиме домовленість, отже обидві прагнутимуть до військової експансії. Це можна вважати теоретичним поясненням політики залякування.

В автоспорті яскравий приклад дилеми ув'язненого — Формула-1, де останні 20 років відбуваються перегони бюджетів команд, через яку кількість машин учасників скоротилася з 36 в 1990 до 20 в 2003.

Випадок дилеми в'язня може бути знайдений в бізнесі. Дві конкуруючі фірми повинні визначитися, скільки коштів витрачати на рекламу. Ефективність реклами і прибуток кожної фірми зменшується із зростанням витрат на рекламу у конкурента. Обидві фірми ухвалюють рішення збільшити витрати на рекламу, при цьому їх частки ринку і, можливо, обсяги продажів залишаються незмінними, а прибуток скорочується. Межа перегонів рекламних бюджетів — прибуток, втім, вони можуть намагатися якийсь час працювати і в збиток. Фірми можуть піти на угоду про скорочення витрат на рекламу, але завжди є стимул його порушити.

У олігополістичних ринках цінова політика — це повторення ДВ. Звичайно олігополісти співрацюють один з одним і не доводять ситуацію до цінової війни.

Вільям Паундстоун в книзі про дилему в'язня описує ситуацію в Новій Зеландії, де поштові скриньки залишають відкритими. Газету можна узяти, не заплативши за неї, але мало хто так робить, тому що більшість усвідомлює шкоду, яка була б якби всі крали газети. Оскільки ДВ в чистому вигляді одночасна для всіх гравців (ніхто не може вплинути на рішення інших), ця поширена лінія міркувань називається «магічне мислення»Будучи поясненням відсутності дрібної крадіжки, магічне мислення пояснює добровільне голосування на виборах (коли не голосує вважається зайцем. Як альтернатива, ця поведінка може пояснюватися сподіванням майбутніх дій (і не вимагати зв'язку з «магічним мисленням»). Моделювання майбутніх дій вимагає додавання вимірювання часу, що робиться повторюваній ДВ (див. відповідний підрозділ цієї статті)..

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

Багато дилем в реальному житті включають безліч гравців. Хоч і метафорично, «трагедію общин» Ардена можна розглядати як узагальнення ДВ для безлічі гравців. Кожен житель общини вибирає — чи пасти худобу на загальному пасовищі і одержати вигоду, виснажуючи його ресурси, або обмежити свій дохід. Колективний результат від загального (або частого) максимального використання пасовища — низький дохід (що веде до руйнування общини). Проте така гра не є формальною, оскільки може бути розбита на послідовність класичних ігор з 2 учасниками.

Дилема в'язня, що повторюється

У книзі «» (1984) Роберт Аксельрод досліджував розширення сценарію ДВ, яке він назвав дилема в'язня, що повторюється (ПДВ). У ній учасники роблять вибір знову раз у раз і пам'ятають попередні результати. Акселрод запросив академічних колег зі всього світу, щоб розробити комп'ютерні стратегії, щоб змагатися в чемпіонаті з ПДВ. Програми, що увійшли до нього розрізнялися за алгоритмічною складністю, початковою ворожістю, здатністю до прощення і так далі.

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

Найкращою детерміністською стратегією виявилася «Око за око» (), яку розробив і виставив на чемпіонат Анатолій Рапопорт. Вона була найпростішою зі всіх програм, що брали участь, складалася всього з 4 рядків коду на мові Бейсік. Стратегія проста: співпрацювати на першій ітерації гри, після цього гравець робить те ж саме, що робив опонент на попередньому кроці. Трохи краще працює стратегія «Око за око з прощенням». Коли опонент зраджує, на наступному кроці гравець іноді у будь-якому випадку співпрацює з невеликою ймовірністю (1 — 5 %). Це дозволяє випадковим чином вийти з циклу взаємної зради. Вона найкраще працює, коли у гру вводиться нерозуміння — коли рішення одного гравця повідомляється іншому з помилкою.

Аналізуючи стратегії, що набрали найкращі результати, Акселрод назвав декілька умов, необхідних, щоб стратегія отримала високий результат.

Добра