Dylemat więźnia – problem w teorii gier. Jest oparty na dwuosobowej grze o niezerowej sumie, w której każdy z graczy może zyskać, zdradzając przeciwnika, ale obaj stracą, jeśli obaj będą zdradzać. Dylemat ten jest więc niekooperacyjną (o częściowym konflikcie) grą o sumie niezerowej, ponieważ strategia konfliktu przeważa nad strategią pokojową: najwięcej można zyskać zdradzając, a najwięcej stracić idąc na współpracę. W odróżnieniu jednak od dylematu kurczaków w tej grze istnieje większe pole do współpracy, które może zaistnieć w strategiach wielokrotnego dylematu więźnia.

Dylemat więźnia został wymyślony przez dwóch pracowników RAND Corporation: Melvina Dreshera i Merrilla Flooda w 1950 roku. sformalizował jego zasady i jako pierwszy użył nazwy dylemat więźnia (Poundstone, 1992). W klasycznej formie jest przedstawiany następująco:

Dwóch podejrzanych zostało zatrzymanych przez policję. Policja, nie mając wystarczających dowodów do postawienia zarzutów, rozdziela więźniów i przedstawia każdemu z nich tę samą ofertę: jeśli będzie zeznawać przeciwko drugiemu, a drugi będzie milczeć, to zeznający wyjdzie na wolność, a milczący dostanie dziesięcioletni wyrok. Jeśli obaj będą milczeć, obaj odsiedzą 6 miesięcy za inne przewinienia. Jeśli obaj będą zeznawać, obaj dostaną pięcioletnie wyroki. Każdy z nich musi podjąć decyzję niezależnie i żaden nie dowie się, czy drugi milczy czy zeznaje, aż do momentu wydania wyroku. Jak powinni postąpić?

Jeśli założymy, że każdy z więźniów woli krótszy wyrok niż dłuższy i że żadnemu nie zależy na niskim wyroku drugiego, możemy opisać ten dylemat w terminach teorii gier. Więźniowie grają wtedy w grę, w której dopuszczalne strategie to: współpracuj (milcz) i zdradzaj (zeznawaj). Celem każdego gracza jest maksymalizacja swoich zysków, czyli uzyskanie jak najkrótszego wyroku.

W tej grze zdradzaj jest strategią ściśle dominującą: niezależnie od tego, co robi przeciwnik, zawsze bardziej opłaca się zdradzać niż współpracować. Jeśli współwięzień milczy, zdradzanie skróci wyrok z sześciu miesięcy do zera. Jeśli współwięzień zeznaje, zdradzanie skróci wyrok z dziesięciu lat do pięciu. Każdy gracz racjonalny będzie zatem zdradzał i jedyną równowagą Nasha jest sytuacja, gdy obaj gracze zdradzają. W efekcie obaj zyskają mniej, niż gdyby obaj współpracowali.

Iterowany dylemat więźnia (patrz niżej) polega na rozgrywaniu tej samej gry wielokrotnie. Wtedy każdy gracz ma możliwość ukarania drugiego gracza za zdradzanie w poprzedniej rundzie. W tej sytuacji, jeśli straty wynikające z ukarania będą większe niż zyski ze zdradzania, współpraca obu graczy może utworzyć stan równowagi. Taka gra może mieć też wiele innych stanów równowagi.

Strategie w klasycznym dylemacie więźnia Poniższa tabela przedstawia możliwe wyniki gry:

Więzień B milczy Więzień B zeznaje Więzień A milczy Obaj skazani na 6 miesięcy Więzień A: skazany na 10 latWięzień B: wolny Więzień A zeznaje Więzień A: wolnyWięzień B: skazany na 10 lat Obaj skazani na 5 lat

+ Przykładowa macierz wypłat Współpracuj Zdradzaj Współpracuj-1/2, -1/2-10, 0 Zdradzaj0, -10-5, -5

W ogólnej postaci dylemat przedstawia się jako macierz:

Współpracuj Zdradzaj WspółpracujR, RS, T ZdradzajT, SP, P

gdzie: T – określa pokusę zdrady (wypłatę za zdradę, gdy drugi współpracuje), R – nagrodę za obopólną współpracę, P – karę za obopólną zdradę, S – wypłatę zdradzonego.

Aby gra spełniała warunki dylematu, muszą być spełnione następujące nierówności:

T > R > P > S

Te warunki zapewniają, że zdradzanie jest w każdej sytuacji bardziej opłacalne niż współpraca, i jednocześnie że obaj tracą, gdy obaj zdradzają. W przypadku iterowanego dylematu więźnia powinien zachodzić dodatkowy warunekRichard Dawkins, Samolubny gen, Oxford University Press, 1989, .:

2 R > T + S

Jeśli nie jest on spełniony, współpraca graczy nie daje im większych zysków niż naprzemienne zdradzanie się.

Szczególny, prosty przypadek uzyskuje się, gdy zysk ze zdrady jest niezależny od decyzji przeciwnika i gdy koszt bycia zdradzonym jest niezależny od naszej decyzji, czyli:

T+S = P+R.

Iterowany dylemat więźnia W iterowanym dylemacie więźnia ci sami gracze grają wielokrotnie ze sobą, wybierając strategie w kolejnych rundach na podstawie wcześniejszych rund. Robert Aumann pokazał w 1959 roku, że w nieskończonym ciągu takich rozgrywek współpraca może być stanem równowagi.

W przypadku, gdy wiadomo, ile dokładnie będzie rozgrywek, optymalna jest strategia Zawsze Zdradzaj. Wynika to z następującego rozumowania: w ostatniej rundzie można równie dobrze zdradzić, ponieważ przeciwnik nie będzie miał już okazji ukarać za to zagranie. Dlatego obaj gracze w ostatniej rundzie zdradzają. Zatem w przedostatniej rundzie również opłaca się zdradzić, ponieważ w ostatniej rundzie przeciwnik i tak zdradzi itd. Zatem aby pojawiła się współpraca, liczba rund musi być losowa albo przynajmniej nieznana graczom.

zaprosił akademików z całego świata do uczestnictwa w turnieju dla programów komputerowych, grających w iterowany dylemat więźnia. Przysyłane programy różniły się pod względem złożoności, startowego zachowania, reakcji na działanie przeciwnika itp. Wyniki pokazały, że przy wielokrotnych rozgrywkach, egoistyczne strategie dawały średnio bardzo małe wygrane w porównaniu z bardziej altruistycznymi. Axelrod pokazał w ten sposób możliwość ewolucyjnego wykształcenia się zachowań altruistycznych z nastawionych na własny zysk, wyłącznie za pomocą selekcji naturalnej.

Najlepszą deterministyczną strategią w tym turnieju okazała się strategia wet za wet (strategia coś za coś), którą zgłosił . Była ona jednocześnie najprostszą zgłoszoną – jej cały program w języku BASIC zajmował cztery linie. Strategia polegała na współpracy w pierwszej rundzie, a w każdej kolejnej robieniu tego, co przeciwnik robił w poprzedniej.

W niektórych sytuacjach lepsza była lekko zmodyfikowana strategia wet za wet z wybaczaniem. W strategii tej, jeśli przeciwnik zdradzał, z małym prawdopodobieństwem (1–5%) gracz wybaczał i w kolejnej rundzie dalej współpracował. Pozwalało to na przerwanie ciągu wzajemnych zdrad, w którym dwie strategie wet za wet mogły utykać w nieskończoność. W szczególności taka modyfikacja zabezpieczała przed nieskończonym ciągiem zdrad wynikającym z pojedynczego błędu komunikacji (decyzja o współpracy, podjęta przez gracza A, przez przypadek zostaje odebrana przez gracza B jako decyzja o zdradzie, na co gracz B odpowiada zdradą).

Analizując najlepsze strategie, Axelrod przedstawił kilka cech, którymi się one wyróżniały: Przyjaznośćoznaczająca niezdradzanie, dopóki przeciwnik tego nie zrobił. Mściwośćoznaczająca reagowanie na zdradę przeciwnika. Bez tej cechy strategia nie mogła dawać dobrych rezultatów. Przykładowo strategia Zawsze Współpracuj dawała bardzo kiepskie wyniki, gdyż wielu przeciwników bezlitośnie wykorzystywało takiego gracza. Skłonność do wybaczania oznaczająca wracanie do współpracy po okresie zemsty za zdradę. To pozwalało uzyskać znacznie lepsze wyniki niż ciągłe wzajemne mszczenie się. Brak zazdrości oznaczająca niestaranie się o lepszy wynik niż przeciwnik.

Axelrod wywnioskował na podstawie tego eksperymentu, że dbanie wyłącznie o własne zyski można często najlepiej realizować będąc przyjaznym i wybaczającym.

W jednorazowym dylemacie więźnia zdradzanie jest zawsze najlepszym rozwiązaniem, niezależnie od tego, co robi przeciwnik. W iterowanym optymalna strategia zależy od tego, jak grają przeciwnicy i jak reagują na współpracę i zdradę. Przykładowo, gdyby wszyscy gracze grali strategią Zawsze Zdradzaj, to jeden gracz grający strategią Wet Za Wet uzyskałby nieco gorszy wynik niż reszta. Gdyby wszyscy gracze grali strategią Zawsze Współpracuj, znacznie lepszy wynik uzyskałby jeden gracz grający strategią Zawsze Zdradzaj.

W pewnych sytuacjach optymalna okazuje się strategia zwana Pavlov. Polega ona na współpracy w pierwszej rundzie i zawsze, jeśli w poprzedniej rundzie gracze zagrali tak samo. Jeśli w poprzedniej rundzie gracze zagrali różnie, strategia każe zdradzić.

Znajdowanie optymalnych strategii W ogólności optymalne strategie znajduje się na dwa sposoby: Analitycznie: Jeśli statystyczne występowanie wszystkich strategii w grze jest znane (np. 50% wet za wet i 50% Zawsze Współpracuj), optymalną strategię można wyliczyć na tej podstawie. Metodą Monte Carlo: Symulując wiele rozgrywek i usuwając strategie, które dają najgorsze wyniki, zastępując je tymi, które dają najlepsze. Aby uniezależnić końcowy wynik od początkowego rozkładu, można dodać losowe mutacje do powielanych strategii, uzyskując algorytm genetyczny do znajdowania strategii optymalnej. Eksperymenty pokazują, że ta metoda zwykle prowadzi do opracowania strategii wet za wet (Chess 1988), ale nie ma dowodu, że zawsze tak musi być.

Mimo że wet za wet jest uważana za najlepszą strategię, w zawodach urządzonych w dwudziestolecie zawodów Axelroda wygrała zupełnie inna strategia. Zaproponowała ją drużyna z Uniwersytetu w Southampton. Opierała się ona na współpracy pomiędzy programami przysłanymi przez tę drużynę, tak aby uzyskać maksymalny wynik jednego z tych programów. Uniwersytet przysłał 60 programów, które były napisane tak, aby rozpoznać się wzajemnie na podstawie pierwszych 5-10 posunięć. Po rozpoznaniu jeden program zawsze współpracował, a drugi zawsze zdradzał, tak aby dać maksymalny zysk zdradzającemu. Grając przeciwko przeciwnikowi nie z Southampton, program poświęcający się zawsze zdradzał, tak aby zminimalizować zysk przeciwnika, a program wygrywający stosował wet za wet. W rezultacie drużyna zajęła pierwsze trzy miejsca (i wiele ostatnich).

Powyższa strategia wykorzystała fakt, że w tym turnieju można było zgłaszać wiele programów, a wynik był mierzony dla najlepszego z nich. Dlatego poświęcanie własnych graczy pozwoliło uzyskać lepszy rezultat. Gdy każda drużyna może zgłosić tylko jednego gracza, wet za wet pozostaje optymalną możliwością. Przykład ten pokazuje dodatkowo możliwości, jakie daje uzgadnianie strategii przed przystąpieniem do gry. Podobne sytuacje opisał wcześniej Richard Dawkins w książce Samolubny gen.

Dylemat więźnia stanowi podstawę niektórych teorii ludzkiej współpracy i zaufania. Zakładając, że może on modelować interakcje w społeczeństwie, powstawanie zaufania można przedstawiać jako wynik iterowanego dylematu więźnia pomiędzy wieloma graczami.

Dylemat więźnia w wersji ciągłej Większość prac dotyczących iterowanego dylematu więźnia skupia się na przypadku dyskretnym, w którym gracze mogą albo współpracować, albo zdradzać. Można jednak rozważać też przypadek ciągły, w którym strategia gracza może przyjmować wartości pośrednie. Le i BoydLe, S. and R. Boyd (2007) „Evolutionary Dynamics of the Continuous Iterated Prisoner’s Dilemma” Journal of Theoretical Biology, Volume 245, 258–267. pokazali, że w takim przypadku współpraca pojawia się znacznie rzadziej. Wynika to z prostego argumentu: w takiej wersji, jeśli początkowo gracze zdradzają, gracze lekko współpracujący zyskują bardzo niewiele grając ze sobą. W dyskretnej wersji gracze współpracujący ze sobą uzyskują znaczną przewagę nad graczami zdradzającymi się nawzajem. Wynik ten ma znaczenie w modelowaniu zachowań zwierząt stadnych. Ponieważ zwykle mają one znacznie więcej możliwości interakcji niż tylko dwie skrajne, może to wyjaśniać, czemu zachowanie wet za wet jest spotykane bardzo rzadko, mimo że teoretycznie jest optymalneHammerstein, P. (2003). Why is reciprocity so rare in social animals? A protestant appeal. In: P. Hammerstein, Editor, Genetic and Cultural Evolution of Cooperation, MIT Press. pp. 83–94..

Wpływ doświadczenia