Dylemat więźnia

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. Albert W. Tucker 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 lat Więzień B: wolny
Więzień A zeznaje	Więzień A: wolny Wię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
Zdradzaj	0, -10	-5, -5

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

	Współpracuj	Zdradzaj
Współpracuj	R, R	S, T
Zdradzaj	T, S	P, 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 warunek:

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.

Robert Axelrod 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ł Anatol Rapoport. 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:

1. 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.
2. 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 Boyd 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 optymalne.

Wpływ doświadczenia

Jeśli gracze mogą uczyć się oceniać prawdopodobne zachowanie przeciwnika, mogą dostosowywać do tego swoje własne zachowanie. Statystyka pokazuje, że początkujący gracze z większym prawdopodobieństwem uzyskują nietypowo wysokie lub nietypowo niskie wyniki. Jeśli grają potem na podstawie tych doświadczeń (częściej współpracując lub zdradzając z ich powodu), wpływa to również na ich przyszłe wyniki. W ten sposób wczesne doświadczenia mają większy wpływ na sumaryczny wynik graczy niż takie same późniejsze doświadczenia. Ten efekt dobrze modeluje istnienie kształtujących doświadczeń u młodych ludzi.

Prawdopodobieństwo zdradzania w grupie można zredukować przez zbudowanie pomiędzy graczami zaufania bazującego na współpracy we wcześniejszych grach. Poświęcanie się niektórych graczy może po początkowym okresie strat przekonać większą część grupy do współpracy, co w efekcie przynosi zyski wszystkim grającym. Efekt ten jest szczególnie silny w małych grupach. Takie procesy są przedmiotem intensywnych badań dotyczących altruizmu odwzajemnionego, doboru grupowego i doboru krewniaczego.

Racjonalność i nadracjonalność

Douglas Hofstadter w książce Metamagical Themas zaproponował wprowadzenie konkurencyjnego pojęcia do racjonalności, która każe graczom zdradzać i uzyskiwać niższy wynik. W jego definicji prawdziwie racjonalny gracz (nadracjonalny) powinien przewidywać również przypuszczalne zachowanie swojego przeciwnika i zakładać, że przeciwnik postąpi tak samo. W takiej sytuacji bardziej opłacalne jest współpracowanie.

Przykłady w świecie rzeczywistym

Istnieje wiele sytuacji, w których interakcje w społeczeństwie, jak i w przyrodzie charakteryzują się podobnymi wypłatami jak w dylemacie więźnia. Z tego powodu dylemat ten jest badany w wielu naukach społecznych takich jak ekonomia, polityka czy socjologia, jak również w naukach biologicznych takich jak etologia i biologia ewolucyjna. Wiele procesów w przyrodzie można również modelować w postaci niekończącej się gry w iterowany dylemat więźnia.

W politologii przykładowym scenariuszem są dwa państwa uwikłane w wyścig zbrojeń. Każde z nich ma dwie możliwości: albo zwiększyć wydatki na zbrojenia, albo podpisać porozumienie o ich zmniejszeniu. Żadna ze stron nie może być pewna, czy druga dotrzyma warunków porozumienia. W rezultacie racjonalną decyzją każdego państwa jest rozwój militarny.

W sporcie podobny dylemat dotyczy wszystkich szkodliwych dla zdrowia zabiegów poprawiających szanse zwycięstwa. Przykładami może być doping bądź gwałtowne tracenie wagi tak, aby trafić do niższej kategorii wagowej. Zawodnik, który tego nie robi (współpracuje), może stracić szanse na zwycięstwo. W momencie, gdy wszyscy tak robią, sensowność zawodów staje się problematyczna.

Innym przykładem związanym ze sportem jest sytuacja w zawodach kolarskich. Częstą sytuacją jest, gdy dwóch zawodników wyprzedza peleton, zmieniając się na męczącej przedniej pozycji. Jeśli żaden z zawodników nie będzie starał się jechać jako pierwszy, peleton szybko ich dogoni. Jeśli tylko jeden z nich będzie to robił, istnieje duża szansa, że zawodnik, który jechał za nim i dzięki temu mniej się męczył, wyprzedzi go tuż przed metą.

W reklamie sytuacja podobna do dylematu więźnia odnosi się do towarów, które ludzie kupują niezależnie od tego, czy są reklamowane. Przykładowo, gdy dwie firmy sprzedają papierosy na tym samym rynku, zysk każdej z nich zależy głównie od tego, ile sprzeda druga firma. Jeśli obie przeznaczą więcej pieniędzy na reklamy, ich efekty się zniosą. Jednak, jeśli tylko jedna firma będzie reklamować swoje produkty, zyska znacznie więcej niż druga. Obu firmom zależy wtedy na tym, żeby wszyscy ograniczyli swoje wydatki na reklamę. W rzeczywistości w USA producenci papierosów aktywnie wspierali uchwalenie prawa zabraniającego ich reklamowania.

W informatyce udostępnianie programów na publicznej licencji GNU (jak np. Linux) jest odpowiednikiem współpracy w dylemacie więźnia. Każda firma, która udostępnia takie oprogramowanie, ułatwia pracę innym firmom, które mogą z niego korzystać tworząc własne produkty. Każde ulepszenie takiego oprogramowania musi zostać również udostępnione na publicznej licencji, co wymusza współpracę pomiędzy rywalizującymi firmami.

W ochronie środowiska dbanie o czystość wód, powietrza, utylizacja odpadów etc. są działaniami odpowiadającymi współpracy, które wymagają wysiłku. Znacznie łatwiej jest nie podejmować tej współpracy, a korzystać z wysiłku innych na rzecz czystego środowiska – to postawa zdrajcy. Kiedy jednak wszyscy będą zdradzać i zaśmiecać środowisko, życie w nim stanie się uciążliwe.

Zobacz też

• automat komórkowy
• dylemat podróżnika
• gra w cykora
• gra o sumie stałej
• nadracjonalność
• optimum Pareta
• równowaga Nasha
• strategia stabilna ewolucyjnie
• wet za wet
• wojna na wyczerpanie (gra)
• Piotr Kropotkin

Linki zewnętrzne (ang.)

• StevenS. Kuhn StevenS., Prisoner's Dilemma, [w:] Stanford Encyclopedia of Philosophy, CSLI, Stanford University, 29 sierpnia 2014, ISSN 1095-5054 [dostęp 2017-12-30]  (ang.). (Dylemat więźnia)
• Effects of Tryptophan Depletion on the Performance of an Iterated Prisoner's Dilemma Game in Healthy Adults
• Is there a "dilemma" in Prisoner's Dilemma
• "Games Prisoners Play"
• Gra w iterowany dylemat więźnia.
• Inna wersja gry w iterowany dylemat więźnia
• Iterated prisoner's dilemma game
• The Bowerbird's Dilemma
• Examples of Prisoners' dilemma
• The Edge cites Robert Axelrod's book and discusses the success of U2 following the principles of IPD.