Dylemat więźnia jest najbardziej znanym przykładem gry o sumie niezerowej. Historyjka jest następująca. Dwóch znanych policji przestępców złapano w kradzionym aucie. Podejrzewa się ich o popełnienie dużo poważniejszego przestępstwa (zbrodni), na co jednak nie ma żadnych dowodów. Przestępcy są przesłuchiwani w osobnych celach bez możliwości komunikowania się ze sobą. Przesłuchujący ich komisarz wpada na pewien pomysł - proponuje im nagrodę za wsypanie wspólnika i dostarczenie dowodów na jego udział w zbrodni. Możliwe są trzy sytuacje:
oboje milczą - wówczas oboje otrzymują niewielki wyrok za kradzież auta
jeden się przyznaje i wsypuje wspólnika - zdrajca wychodzi na wolność, jego kompan (tzw. frajer) otrzymuje wyrok za kradzież i za popełnienie zbrodni
oboje się przyznają i wsypują wspólnika - oboje otrzymują karę za kradzież i popełnienie zbrodni, nieco złagodzoną ze względu na współpracę z wymiarem sprawiedliwości
W toerii gier zapisalibyśmy tę sytuację w postaci macierzy wypłat. Strategia W oznacza współpracę (między graczami), czyli milczenie. Strategia Z oznacza zdradę, czyli wsypanie wspólnika. Oto nasza macierz:
Znaczenie poszczególnych wartości jest dość oczywiste:
x1 - kara za kradzież auta
x2 - kara za kradzież i zbrodnię (tzw. wypłata frajera)
x3 - karaz za kradzież auta złagodzona za wsypanie wspólnika (tzw. zachęta do zdrady)
x4 - kara za kradzież i zbrodnię złagodzona ze względu na współpracę z wymiarem sprawiedliwości
Aby taką grę uznać za dylemat więźnia muszą być spełnione pewne zależności między wysokościami poszczególnych wypłat w macierzy:
2 * x1 > x2 + x3
x2 < x4 < x1 < x3
Tłumacząc to "z matematycznego na nasze" :) można powiedzieć, że:
suma uniewinnień musi być większa od sumy pełnego wymiaru kary i zachęty do zdrady
kara, którą ponosi frajer, musi być odpowiednio wysoka
Wysokość poszczególnych wypłat jest nieistotna. Ważne, by spełniałe były powyższe warunki. Przykładowa macierz dylematu więźnia może wyglądać tak (łatwo sprawdzisz, że spełnia ona podane wyżej warunki):
Wypłaty w niej są umownę - można je traktować np. jako liczbę lat, jaką przestępca spędzi w więzieniu, w ciągu najbliższych 5 lat.
Patrząc na macierz wypłat trudno ukryć zdziwienie prostotą tej gry. A przecież tkwi tu poważny haczyk... Nieprzypadkowo dylemat więźnia stał się podstawą wielu badań prowadzonych w naukach społecznych.
Z łatwością można zauważyć, że dla obu graczy strategia zdrady (Z) jest dominująca. Prowadzi to do równowagi ZZ - a przecież na pierwszy rzut oka widać, że oboje lepiej wyszliby zgodnie współpracując ze sobą ! W ten sposób doszliśmy do sedna sprawy - do konfliktu pomiędzy troską o własny zyska, a troską o "dobro grupy".
W przypadku rozgrywki jednorazowej praktycznie wszystko jest jasne - grający na współpracę jest frajerem. Jedynym rozsądnym wyjściem jest zdrada-. Jest to sytuacja dosyć absurdalna, zważywszy na fakt, że powoduje ona przegraną obu graczy, w sytuacji, w której w prosty sposób mogliby zarobić (grając solidarnie współpraca).
Po pierwsze zwróćmy uwagę na fakt, że w przypadku gdy gracze znają ilość rozgrywanych gier, rozgrywka wielokrotna przestaje się różnić od jednokrotnej ! Zacznijmy nasze rozważania od końca, od ostatniej, n-tej kolejki. Skoro gracz wie, że jest to ostatnia gra, to pragnąc zmaksymalizować swoje zyski nie ma wyjścia. Musi grać zdradą ma bowiem świadomość, że grając współpracę wyjdzie na frajera - jego przeciwnik z pewnością zdradzi. Skoro wiadomo co się stanie w ostatniej kolejce (oboje zdradzą) analogiczne rozumowanie można przeprowadzić dla kolejki przedostatniej. Znów okaże się, że jedynym rozsądnym wyjściem dla obu graczy jest zdrada. I tak dalej - aż do początku rozgrywki.
Jak widać rozgrywka wielokrotna ma sens jedynie wówczas, kiedy gracze nie wiedzą kiedy nastąpi jej koniec
Odpowiedź na pytanie o najkorzystniejszą strategię w grze w iterowany dylemat więźnia jest trudne. Zdradzić czy grać na współpracę ? A jeżeli nadziejemy się na zdradę drugiego gracza, to jak zachowac się w kolejnym spotkaniu ? Odpłacić mu, czy też puścić płazem ?
Omawiając ten problem nie sposób pominąć znane doświadczenie Roberta Axelroda, który przeprowadził następującą próbę. Otóż poprosił on osoby interesujące się teorią gier o napisanie programów komputerowych, z których każdy realizował pewną (czasami bardzo złożoną) strategię gry w dylemat więźnia. Następnie zorganizował turniej(1) w którym programy te grały przeciwko sobie. Turniej wygrał program realizujący prostą stratęgię, nazwaną WET ZA WET:
każdą rozgrywkę zaczynaj od współpracy
w następnych kolejkach wybieraj tę, którą drugi gracz zagrał w poprzedniej kolejce
Po dokładnym omówieniu wyników, Axelrod zorganizował drugą rundę turnieju. Biorący w niej udział zawodnicy nadesłali kolejne programy czerpiąc z doświadczeń rundy poprzedniej i... WET ZA WET znów okazał się najlepszy ! Axelrod przeprowadził dokładną analizę nadesłanych programów i doszedł do wniosku, że wśród plasujących się w czołówce, większość wyróżniała się następującymi cechami:
przyjazna - nie zdradza jako pierwsza
odwetowa - za zdradę karze zdradą
przebaczająca - po ukaraniu zdrady wyciąga rękę na zgodę
przejrzysta - jej decyzje powinny być spójne i łatwe do przewidzenia
Warto się też przyjrzeć innym uczestnikom turnieju:
PROSTODUSZNY TESTER - w zasadzie zachowuje się jak WET ZA WET ale od czasu do czasu niespodziewanie zdradza
TESTER SKRUSZONY - zachowuje się podobnie do PROSTODUSZNEGO TESTERA, z tym że po własnej zdradzi godzi się na jedną niekontrowaną zdradę ze strony przeciwnika
PAMIĘTLIWY - raz zdradzony zawsze zdradza
WET ZA DWA WETY - wybacza jedną zdradę, odpłaca się dopiero za drugą
Zauważmy, że nie wszystkie z wymienionych strategii spełniają wymienione powyżej warunki. Niektóre z nich są wredne, tj. zdradzają niesprowokowane. Inne z kolei nie przebaczają (w związku z czym istnieje spora szansa, że rozgrywka z ich udziałem sprowadzi się do ciągłych obustronnych zmian).
Wyniki konkursów Axelroda są bardzo interesujące. W drugiej rozgrywce 14 spośród pierwszych 15 miejsc zajęły strategie uprzejme. Odwrotna proporcja panowała w ostatniej piętnastce - tu znalazła się tylko jedna strategia.
Czy możemy więc postawić tezę o wyższość strategii uprzejmych nad wrednymi ? Czy możemy obwołać WET ZA WET absolutnym tryumfatorem ? Nie, nie możemy. Warto zauważyć, że w pewnej konfiguracji strategii biorących udział w turnieju WET ZA WET nie wygrałby. Byłoby tak w przypadku, gdyby oprócz niego wszystkie pozostałe strategii były wredne.
Warto przyjrzeć się uczestnikom turnieju Axelroda odwołując się do pojęcia strategii ewolucyjnie stabilnej. Jeżeli nie czytałeś jeszcze tekstu poświęconego zastosowaniu teorii gier w biologii, to zrób to teraz, a potem wróć tutaj.
Jeżeli czytasz to zdanie, to zakładam, że przeczytałeś już tekst omawiający grę w jastrzębie i gołębie i orientujesz się w zagadnieniu strategii ewolucyjnie stabilnej. Przypomnę tylko za Dawkinsem, e strategię ewolucyjnie stabliną ...
... definiuje się jako taką strategię, której od momentu gdy zostanie przyjęta przez większość członków populacji, nie jest w stanie wyprzeć żadna inna strategia alternatywna. | ||
| --Richard Dawkins | ||
Axelrod wykonał kolejne doświadczenie, w którym wzięły udział 63 strategie zgłoszone do drugiej rundy turnieju. W trzecim turnieju zasady były nieco inne, a badaniu podlegała właśnie ewolucyjna stabilność poszczególnych strategii. Oddajmy głos Dawkinsowi:
Axelrod wprowadził te 63 strategie do komputera, stwarzając tym samym "pokolenie nr 1" w ewolucyjnym następstwie pokoleń. W pokoleniu nr 1 na "aurę" składały się wszystkie 63 strategie w równych proporcjach. pokolenie to zakończyło się wypłaceniem każdej strategii jej wygranej, lecz nie w pieniądzach czy punktach, ale w potomstwie, tożsamym z ich (bezpłciowymi) rodzicami. Z każdą mijającą generacją pewne strategie stawały się coraz rzadsza, aż w końcu zanikały. Inne zaś stawały się liczniejsze. Toteż wraz ze zmieniającymi się proporcjami zmieniała się i "aura", w jakiej przebiegały kolejne rundy gry.
Dokładne omówienie wyników konkursu i interesujące rozważania na temat ewolucyjnego powodzenia poszczególnych rodzajów strategii znajdziesz w "Samolubnym genie" Dawkinsa. Tutaj powiemy tylko, że turniej ten wygrały strategie cechujące się uprzejmością (tj. te, które nie zdradzają jako pierwsze) - po wielkiej liczbie powtórzeń gry tylko one zostały na placu boju, a że wszystkie są uprzejme, więc ich rozgrywki polegały na ciągłej współpracy [6]. Jednak żadna z nich nie zasługuje na miano ewolucyjnie stabilnej, bo zdominowana przez nią populacja jest podatna na inwazje innych uprzejmych strategii.
Konkurs typu "ewolucyjnego" doczekał się różnych wariantów. Najciekawszy wydaje się ten, w którym dopuszcza się możliwość "pomyłki". Zauważmy, że zdarza się nam zrobić od czasu do czasu coś niezgodnego z naszymi zamierzeniami - czy to przez nieuwagę czy też z powodu chwilowego kaprysu. Podobne zachowania wprowadzono w ramy eksperymentu przyjmując, że każdy osobnik stosuje swoją strategię z pewnym prawdopodobieństwem. Przykładowo - osobnik A w 99% procentach przypadków stosuje strategię wet-za-wet, ale wyjątkowo - w 1% przypadków - zdarza mu się grać strategią zawsze zdradzaj.
Wspominany już wcześniej Axelrod wpadł też na pomysł rozegrania nieco innego turnieju. Podstawą pomysłu była obserwacja, że starcia typu "każdy z każdym" nie oddają najlepiej procesów zachodzących w rzeczywistości (np. w kontaktach międzyludzkich). W większości przypadków kontaktujemy się tylko z tymi, którzy przebywają w naszym pobliżu. Z tego prostego spostrzeżenia narodził się przestrzenny dylemat więźnia (SPD).
Idea jest następująca. Rozłóżmy naszych graczy na przestrzennej siatce [7] , tak aby każdy z nich miał dokładnie 4 sąsiadów. Następnie każdy gracz rozgrywa z każdym ze swoich sąsiadów jedną rundę gry w dylemat więźnia korzystając z właściwej mu strategii. Po 4 takich grach (jedna z każdym sąsiadem) gracz podlicza swoją wypłatę. Następnie spogląda na wypłaty swoich sąsiadów. Jeżeli znajdzie wśród nich osobnika, który wygrał więcej od niego, w kolejnej rundzie zastosuje taką strategią, jaką ów osobnik stosował w rundzie ostatniej. Proste, nie ?
W wyniku wielokrotnych rozgrywek przeżyją tylko strategie najlepsze - a więc takie, które przynoszą swoim graczom wypłaty większe od innych.
Istnieją pewne charakterystyczne stany, do których może dojść cały układ. Zazwyczaj następuje grupowanie się strategii w skupiska.
Eksperyment Axelroda (w którym użył on tych samych 63 strategii, które zgłoszono do oryginalnego turnieju) niezależnie od początkowego (losowego) rozrzucenia "graczy" na płaszczyźnie zawsze kończył się takim samym wynikiem - wszyscy gracze grali na współpracę, skutkiem czego dalsza ewolucja układu była niemożliwa.
Oczywiście sama rozgrywka za każdym razem przebiegała inaczej, w zależności od ilości i rozmieszczenia strategii złośliwych. Niemniej jednak końcówka należała do łagodnych. Ze względu na to, że w pewnym momencie strategie grające w pierwszym ruchu "współpracuj" stają się od siebie nierozróżnialne, trudno tu mówić o "najlepszej" strategii.
Zauważmy, że istnieją znaczące różnice pomiędzy przestrzennym a ewolucyjnym wariantem eksperymentu. W wariancie przestrzennym mianowicie, ze względu na rozprzestrzenienia się strategii wśród sąsiadów, strategia będzie często grała przeciw samej sobie.
[6] Przypominam, że mówimy o wielokrotnej rozgrywce dylematu więźnia, w której gracze mogą zdradzać albo współpracować
[7] "przestrzenna siatka" nieuchronnie przenosi nas myślą na terytorium, którego badaniem zajmują się specjaliści od automatów komórkowych. Polecam dobrą stronę autorstwa dr K. Malarza poświęconą tymże automatom.