У теорији игара, затвореникова дилема () је мисаони експеримент који укључује два рационална агента, од којих сваки може или да сарађује ради обостране користи или да изда свог партнера ради личне користи. Дилема произилази из чињенице да, иако је издаја рационална за сваког агента, сарадња доноси већу исплату за обоје. Ову загонетку су осмислили Мерил Флуд и Мелвин Дрешер 1950. године током свог рада у корпорацији РАНД. Они су позвали економисту Армена Алчијана и математичара Џона Вилијамса да одиграју стотину рунди ове игре, при чему су приметили да су Алчијан и Вилијамс често бирали да сарађују. Када је упитан о резултатима, Џон Неш је приметио да се рационално понашање у итерираној (поновљеној) верзији игре може разликовати од оног у верзији са само једном рундом. Овај увид је наговестио кључни резултат у теорији игара познат као фолк теорема: сарадња се може појавити у поновљеним интеракцијама, чак и у ситуацијама када није рационална у једнократној интеракцији.
Алберт В. Такер је касније ову игру назвао „затворениковом дилемом” тако што је награде формулисао у виду затворских казни. Затвореникова дилема моделира многе ситуације из стварног света које укључују стратешко понашање. У свакодневном говору, назив „затвореникова дилема” примењује се на било коју ситуацију у којој два ентитета могу остварити значајне бенефите сарадњом или претрпети штету ако то не учине, али им је тешко или скупо да координишу своје изборе.
Премиса мини|upright=1.25|Пример матрице исплата у затворениковој дилеми Ова „типична савремена верзија” игре описана је у књизи Вилијама Паундстоуна из 1993. године Затвореникова дилема:
Два члана криминалне банде су ухапшена и затворена. Сваки затвореник се налази у самици без могућности да разговара или размењује поруке са оним другим. Полиција признаје да нема довољно доказа да их осуди за главно кривично дело. Планирају да обојицу осуде на годину дана затвора за лакши прекршај. Истовремено, полиција сваком затворенику нуди фаустовску погодбу. Ако сведочи против свог партнера, биће ослобођен, док ће партнер добити три године затвора за главно кривично дело. Али, постоји цака... Ако оба затвореника сведоче један против другог, обојица ће бити осуђена на две године затвора. Затвореницима је дато мало времена да размисле о томе, али ни у ком случају не могу сазнати шта је други одлучио пре него што неповратно донесу своју одлуку. Сваком је речено да се и другом затворенику нуди потпуно иста погодба. Сваки затвореник брине само о сопственој добробити — да сведе сопствену затворску казну на минимум.: "A typical contemporary version of the story goes like this: Two members of a criminal gang are arrested and imprisoned. Each prisoner is in solitary confinement with no means of speaking to or exchanging messages with the other. The police admit they don't have enough evidence to convict the pair on the principal charge. They plan to sentence both to a year in prison on a lesser charge. Simultaneously, the police offer each prisoner a Faustian bargain. If he testifies against his partner, he will go free while the partner will get three years in prison on the main charge. Oh, yes, there is a catch ... If both prisoners testify against each other, both will be sentenced to two years in jail. The prisoners are given a little time to think this over, but in no case may either learn what the other has decided until he has irrevocably made his decision. Each is informed that the other prisoner is being offered the very same deal. Each prisoner is concerned only with his own welfare—with minimizing his own prison sentence."
Ово доводи до три различита могућа исхода за затворенике А и Б: Ако и А и Б остану неми, сваки ће одслужити по једну годину у затвору. Ако један сведочи против другог, а други то не учини, онај који сведочи биће ослобођен, док ће други одслужити три године у затвору. Ако А и Б сведоче један против другог, сваки ће одслужити по две године.
Стратегија за затвореникову дилему Два затвореника су одвојена у засебне собе и не могу међусобно да комуницирају. Претпоставља се да оба затвореника разумеју природу игре, немају лојалност један према другом и неће имати прилику за одмазду или награду ван саме игре. Нормална игра је приказана испод:
Затвореник Б ћути(сарађује) Затвореник Б сведочи(издаје) Затвореник А ћути(сарађује) Сваки служи 1 годину Затвореник А: 3 годинеЗатвореник Б: слободан Затвореник А сведочи(издаје) Затвореник А: слободанЗатвореник Б: 3 године Сваки служи 2 године
Без обзира на то шта други одлучи, сваки затвореник добија већу награду ако изда оног другог („издаје”). Резоновање укључује анализу најбољих одговора оба играча: Б ће или сарађивати или издати. Ако Б сарађује, А би требало да изда, јер је ослобађање боље него служење 1 године. Ако Б изда, А би такође требало да изда, јер је служење 2 године боље од служења 3 године. Према томе, у сваком случају, А би требало да изда јер је издаја најбољи одговор за А без обзира на стратегију коју примени Б. Паралелно резоновање ће показати да би и Б требало да изда.
Издаја увек резултира бољом исплатом од сарадње, тако да је то строго доминантна стратегија за оба играча. Узајамна издаја је једини снажан Нешов еквилибријум у игри. Пошто је колективно идеалан резултат узајамне сарадње ирационалан са становишта личних интереса, овај Нешов еквилибријум није Парето ефикасан.
Генерализовани облик
Структура традиционалне затвореникове дилеме може се генерализовати из њеног првобитног затворског окружења. Претпоставимо да су два играча представљена бојама црвена и плава и да сваки играч бира да ли ће „сарађивати” или „издати”.
Ако оба играча сарађују, обојица добијају награду (енгл. reward) за сарадњу. Ако оба играча издају, обојица добијају казнену исплату (енгл. punishment). Ако Плави изда док Црвени сарађује, тада Плави добија исплату услед искушења (енгл. temptation), док Црвени добија исплату за „наивчину”, (енгл. sucker's payoff). Слично томе, ако Плави сарађује док Црвени издаје, онда Плави добија исплату за наивчину , док Црвени добија исплату услед искушења .
Ово се може изразити кроз нормалну форму:
+ Канонска матрица исплата у затворениковој дилеми
и да би игра била затвореникова дилема у строгом смислу, за исплате мора да важи следећи услов:
Однос исплата имплицира да је узајамна сарадња супериорнија у односу на узајамну издају, док односи исплата и имплицирају да је издаја доминантна стратегија за оба агента.
Итерирана затвореникова дилема Ако два играча играју затвореникову дилему више пута узастопно, памте претходне потезе свог противника и имају могућност да сходно томе промене своју стратегију, игра се назива итерираном (поновљеном) затворениковој дилемом.
Поред горенаведеног општег облика, итеративна верзија такође захтева да , како би се спречило да наизменична сарадња и издаја донесу већу награду од узајамне сарадње.
Итерирана затвореникова дилема је фундаментална за неке теорије људске сарадње и поверења. Под претпоставком да игра ефикасно моделира трансакције између двоје људи које захтевају поверење, кооперативно понашање у популацијама може се моделовати помоћу верзије игре са више играча. Године 1975, Бернард Грофман и Џонатан Пул проценили су да је број научних чланака посвећених овој теми већи од 2.000. Итерирана затвореникова дилема назива се и „игра мира и рата”. Проучаване су различите варијанте итериране игре, укључујући верзију у којој играчи имају опцију изласка након сваке рунде.Arend, R.J. & Seale, D.A. (2005). Modeling alliance activity: an iterated prisoners' dilemma with exit option. Strategic Management Journal, 26(11), 1057-1074. Варијанте са ендогеним друштвеним мрежама омогућавају играчима да формирају или раскидају везе, уз динамичан избор партнера и поновно повезивање које потенцијално промовише сарадњу и удруживање. Црте личности такође предвиђају сарадњу у друштвеним дилемама, а модел који комбинује Великих пет црта личности са ендогеним избором партнера открио је да веће ослањање на историју интеракција повећава просечне исплате и смањује неједнакост.
Општа стратегија Ако се итерирана затвореникова дилема игра коначан број пута и оба играча то знају, онда је доминантна стратегија и Нешов еквилибријум да се изда у свим рундама. Доказ је индуктивне природе (Математичка индукција): играч би могао да изда већ у последњем потезу, пошто противник неће имати прилику да се касније освети. Због тога ће обојица издати у последњем потезу. Такође, играч би могао да изда и у претпоследњем потезу, јер ће противник свакако издати у последњем без обзира на све, и тако даље. Исто важи ако је дужина игре непозната, али има познату горњу границу.
Да би се појавила сарадња између рационалних играча, број рунди мора бити непознат или бесконачан. У том случају, „увек издај” можда више неће бити доминантна стратегија. Као што је показао Роберт Ауман у раду из 1959. године, рационални играчи који више пута интерагују у играма које трају неограничено дуго могу одржати сарадњу. Специфично, играч може бити мање вољан да сарађује ако његов партнер више пута није сарађивао, што изазива разочарање. Насупрот томе, како време одмиче, вероватноћа сарадње тежи да расте, због успостављања „прећутног споразума” међу играчима учесницима. У експерименталним ситуацијама, сарадња се може догодити чак и када оба учесника знају колико ће се итерација одиграти.
Према експерименталној студији из 2019. године у часопису American Economic Review која је тестирала које су стратегије стварни испитаници користили у ситуацијама итериране затвореникове дилеме са савршеним праћењем, већина изабраних стратегија била је увек издај, мило за драго (енгл. tit for tat) и немилосрдни окидач. Коју ће стратегију субјекти изабрати зависило је од параметара игре.
Акселродов турнир и услови за успешну стратегију Интересовање за итерирану затвореникову дилему подстакао је Роберт Акселрод у својој књизи из 1984. године Еволуција сарадње (енгл. The Evolution of Cooperation), у којој извештава о турниру који је организовао за N-корачну затвореникову дилему (са фиксним N), где учесници морају више пута бирати своју стратегију и памтити претходне сусрете. Акселрод је позвао академске колеге из целог света да осмисле рачунарске стратегије за такмичење на турниру у итерираној затворениковој дилеми. Пријављени програми варирали су у погледу алгоритмичке сложености, почетног непријатељства, капацитета за опраштање итд.
Акселрод је открио да када се ови сусрети понављају током дугог временског периода са много играча, сваки са различитим стратегијама, похлепне стратегије обично пролазе веома лоше на дуге стазе, док су алтруистичније стратегије пролазиле боље, судећи чисто по сопственом интересу. Ово је искористио да покаже могући механизам за еволуцију алтруистичког понашања из механизама који су у почетку искључиво себични, путем природне селекције.
Победничка детерминистичка стратегија била је „мило за драго” (tit for tat), коју је развио и пријавио на турнир Анатол Рапопорт. То је био најједноставнији од свих пријављених програма, садржавао је само четири линије BASIC кода, и победио је на такмичењу. Стратегија је једноставно сарађивати у првој итерацији игре; након тога, играч ради исто оно што је његов противник урадио у претходном потезу. У зависности од ситуације, нешто боља стратегија може бити „мило за драго са опраштањем”: када противник изда, у следећем потезу играч понекад ипак сарађује, са малом вероватноћом (око 1–5%, у зависности од противника). Ово омогућава повремени опоравак од заглављивања у циклусу издаја.
Након анализе стратегија са највишим резултатом, Акселрод је навео неколико услова неопходних да би стратегија успела: