Дилема в'язня — Вікіпедія

Дилема в'язня
Досліджується в	суспільні науки і економіка
Підтримується Вікіпроєктом	Вікіпедія:Проєкт:Математика
Дилема в'язня у Вікісховищі

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

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

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

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

Класична дилема ув'язненого така:

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

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

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

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

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

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

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

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

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

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

2C > D + c

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

Гофштадтер^[1] припустив, що люди простіше розуміють завдання, як завдання ДВ, якщо вона представлена у вигляді окремої гри або процесу торгівлі. Один з прикладів — «обмін закритими сумками»: Дві людини зустрічаються і обмінюються закритими сумками, розуміючи, що одна з них містить гроші, інша — товар. Кожен гравець може поважати операцію і покласти в сумку те, про що домовилися, або обдурити партнера, давши порожню сумку.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Добра

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

Мстива

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

Прощаюча

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

Не заздрісна

Остання якість — не бути заздрісним, тобто не намагатися набрати більше очок, ніж опонент (що у принципі неможливо для «доброї» стратегії, тобто добра стратегія ніколи не може набрати більше очок, ніж опонент).

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

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

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

Визначити оптимальну стратегію можна двома шляхами:

• Рівновага Байеса-Неша: якщо визначено статистичний розподіл поведінки (наприклад, 33 % «око за око», 33 % завжди одурюють і 33 % завжди співпрацюють), що зустрічається, то стратегію можна обчислити математично^[3]. Цим детально займається теорія еволюційної динаміки.
• За методом Монте-Карло робилися симуляції популяцій, де індивіди з низькими результатами вимирали, а з високими відтворювалися (використовувався генетичний алгоритм пошуку оптимальної стратегії). Структура поведінки в кінцевій популяції залежить від структури на початку.

Хоча стратегія «око за око» вважалася найвдалішою простою стратегією, команда Університету Саутгемптона з Англії (під керівництвом професора Ніколаса Дженнінгса [1]) представила нову стратегію на 20-ту річницю Чемпіонату з ПДВ. Ця стратегія виявилася успішнішою, ніж «око за око». Вона ґрунтувалася на взаємодії між програмами, щоб одержати максимальний рахунок для однієї з них. Університет виставив на чемпіонат 60 програм, які розпізнавали одна одну за рядом дій на перших 5-10 ходах. Розпізнавши іншу, одна програма завжди співпрацювала, а інша зраджувала, що давало максимум очок зраднику. Якщо програма розуміла, що опонент — не саутгемптонській, вона далі весь час зраджувала його, щоб мінімізувати результат суперника. В результаті^[4] ця стратегія зайняла перші три місця в змаганні, як і декілька місць підряд нижче.

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

Якщо ПДВ грається рівно N раз (якась відома константа N), є ще один цікавий факт. Рівновага Неша — завжди зраджувати. Доводимо за індукцією: якщо обидва співпрацюють, на останньому ході вигідно зрадити, тоді у суперника не буде можливості помститися. Тому обидва зрадять один одного на останньому ході. Раз суперник зрадить на останньому ході у будь-якому випадку, будь-який гравець захоче зрадити на передостанньому ході, і так далі. Щоб співпраця залишалася вигідною, необхідно, щоб майбутнє було невизначеним для обох гравців. Одне з рішень — робити число N випадковим і підраховувати результати за середнім виграшем за хід.

Дилема ув'язненого — фундаментальна для деяких теорій про взаємодію людей і довіру. З припущення моделі ДВ, що транзакція між двома людьми вимагає довіри, довірча поведінка в популяціях може бути змодельована за допомогою багато-гравцевої версії гри, що повторюється. Це роками надихало багатьох вчених. У 1975 році Грофман і Пул оцінювали число робіт, присвячених цій темі, їх близько 2000.

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

Можна зменшити ймовірність зради в популяції за допомогою співпраці в ранніх іграх, дозволивши укріпити довіру^[5]. Отже самопожертвування може в деяких ситуаціях підсилити моральний дух групи. Якщо група маленька, на позитивну поведінку з більшою ймовірністю відповідять взаємністю, що заохотить індивідів на подальшу співпрацю. Це пов'язано з ще однією дилемою, що хороше ставлення без причини — це потурання, яке може погіршити моральні якості.

Ці процеси — головне поле інтересу взаємного альтруїзму, групового відбору, сімейного відбору і етики.

У бойових мистецтвах вивчається даоське прислів'я, яке говорить, що:

• Відповідати добром на добро — дає добро
• Відповідати злом на зло — дає добро
• Відповідати злом на добро — дає зло
• Відповідати добром на зло — дає зло

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

• Axelrod, Robert and Hamilton, William D. (1981). «The Evolution of Cooperation». Science, 211 : 1390—1396.
• Axelrod, Robert (1984). The evolution of cooperation. New York: Basic Books. ISBN 0-465-02121-2.
• Axelrod, Robert (1997). The Complexity of Cooperation. Princeton University Press. ISBN 0-691-01567-8.
• Dawkins, Richard (1989). The selfish gene. Oxford New York: Oxford University Press. ISBN 0-19-286092-5., друге видання — включає два розділи про еволюцію співпраці
• Grofman and Pool (1975). «Bayesian Models for Iterated Prisoner's Dilemma Games». General Systems 20 : 185–94.
• Hardin, Garrett (1968). «The Tragedy of the Commons» [Архівовано 1 вересня 2005 у Wayback Machine.]. Science, 162 : 1243—1248.
• Kreps, David, Robert Wilson, Paul Milgrom, and John Roberts (1982). «Rational Cooperation in the Finitely Repeated Prisoners' Dilemma.» Journal of Economic Theory 27(2) : 245–52.
• Milgrom, Paul (1984). «Axelrod's The Evolution of Cooperation.» Rand Journal of Economics 15(2) : 30–59.
• Poundstone, William (1992). Prisoner's Dilemma: John von Neumann, Game Theory, and the Puzzle of the Bomb. Doubleday. ISBN 0-385-41567-2. Розлогий популярний вступ, як відзначено в заголовку.
• Rapoport, Anatol and Chammah, Albert M. (1965). Prisoner's Dilemma. University of Michigan Press. Розрахунок множини експериментів, в яких гралася ДВ.
• Verhoeff, Tom (1998). «The Trader's Dilemma: A Continuous Version of the Prisoner's Dilemma» [Архівовано 21 травня 2005 у Wayback Machine.]. Computing Science Notes 93/02, Кафедра математики і обчислювальних систем, Технічний Університет Ейндховена, Нідерланди.
• New Tack Wins Prisoner's Dilemma [Архівовано 8 лютого 2007 у Wayback Machine.] (з Wired.com [Архівовано 14 червня 2022 у Wayback Machine.])

• Рівновага Неша
• Трагедія спільнот
• Парадокс Бреса
• Довіра

• Еволюція довіри [Архівовано 28 червня 2018 у Wayback Machine.] — симуляція повторюваної гри в дилему в'язня, на основі роботи Роберта Аксельрода
• Дилема в'язня, що повторюється в онлайні [Архівовано 29 грудня 2005 у Wayback Machine.]
• Ще одна дилема в'язня, що повторюється [Архівовано 20 березня 2012 у Wayback Machine.]
• Звіт про дослідження про дилему в'язня (англ.)
• Критика [Архівовано 11 лютого 2007 у Wayback Machine.] економістів, включаючи школу контракту, які використовували деякі теоретичні результати ДВ, щоб виправдати необхідність втручання держави, щоб «поліпшити» результат. (англ.)
• Симуляція дилеми ув'язненого в просторі [Архівовано 19 липня 2006 у Wayback Machine.]