Dylemat więźnia

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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óra może zaistnieć w strategiach wielokrotnego dylematu więźnia[1].

Dylemat więźnia został wymyślony przez dwóch pracowników RAND Corporation: Melvin Dreshera i Merrill Flood 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[edytuj | edytuj kod]

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: 10 lat
Więzień B: wolny
Więzień A zeznaje Więzień A: wolny
Więzień B: 10 lat
Obaj skazani na 5 lat
Przykładowa macierz wypłat:
Współpracuj Zdradzaj
Współpracuj -1/2, -1/2 0, -10
Zdradzaj -10, 0 -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

T określa pokusę zdrady, R – nagrodę za współpracę, P – karę za zdradę, a S – wypłatę zdradzonego. Aby gra spełniała warunki dylematu, muszą być spełnione następujące nierówności:

T > P > R > 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]

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[edytuj | edytuj kod]

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.

W 1984 roku 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ść.

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[edytuj | edytuj kod]

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.[3]
  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).[4]

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[edytuj | edytuj kod]

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[5] 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.[6]

Wpływ doświadczenia[edytuj | edytuj kod]

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ść[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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 się starał 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 przemyśle reklamowym, 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 prace innym firmom, które mogą z niego korzystać przy tworzeniu własnych produktów. 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.

W systemie podatkowym, każdy kto płaci należne podatki przyczynia się do finansowania zadań i potrzeb publicznych. Zdrajcy, którzy starają się unikać płacenia podatków, czerpiąc z tego doraźne korzyści finansowe, najczęściej korzystają na równi z innymi z infrastruktury, edukacji, systemu opieki zdrowotnej etc., finansowanych z podatków, które płacą inni.

Zobacz też[edytuj | edytuj kod]

Przypisy

  1. Ziemowit Jacek Pietraś: Decydowanie polityczne. Warszawa-Kraków: Wydawnictwo Naukowe PWN, 2000, s. 229-248. ISBN 83-01-12679-5.
  2. Richard Dawkins, Samolubny gen, Oxford University Press, 1989, ISBN 0-19-286092-5
  3. “Bayesian Nash equilibrium; a statistical test of the hypothesis”
  4. The 2004 Prisoner's Dilemma Tournament Results.
  5. Le, S. and R. Boyd (2007) "Evolutionary Dynamics of the Continuous Iterated Prisoner's Dilemma" Journal of Theoretical Biology, Volume 245, 258–267.
  6. Hammerstein, 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.

Linki zewnętrzne (ang.)[edytuj | edytuj kod]