Social Icons

niedziela, 17 listopada 2013

Dylemat więźnia

Dylemat więźnia to jeden z najważniejszych problemów poruszanych w teorii gier. 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ą (strategia która jest zawsze nie gorsza od jakiejś innej strategii, niezależnie od wyboru strategii przez przeciwnika i zdarzeń losowych): 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 (profil strategii teorii gier, w którym strategia każdego z graczy jest optymalna, przyjmując wybór jego oponentów za ustalony) jest sytuacja, gdy obaj gracze zdradzają. W efekcie obaj zyskają mniej, niż gdyby obaj współpracowali.

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. 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 z zdradzania, współpraca obu graczy może utworzyć stan równowagi. Taka gra może mieć też wiele innych stanów 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ą strategią w tym turnieju okazała się strategia wet za wet (strategia coś za coś), którą zgłosił Anatol Rapoport. 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 nie zdradzanie 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 nie staranie się uzyskać lepszego wyniku 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ć.

Przykłady dylematu więźnia w świecie rzeczywistym

  1. 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.
  2. 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.
  3. 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ą.
  4. 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.
  5. 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.
  6. 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.

Brak komentarzy:

Prześlij komentarz