farharod

Pierwszy artykuł poświęcę zagadnieniu związanym z teorią gier, znanym jako “dylemat więźnia”.
Teoria gier? Dylemat więźnia? – za pewne zdziwił Was tytuł, jak mnie samego gdy zaczynałem przygodę z teorią gier.
I wcale nie chodzi tutaj o gry komputerowe (choć multiplayer jest przykładem), a matematyczną teorię podejmowania decyzji w przypadku jakiegoś konfliktu interesu.

Najpierw kilka słów o samej teorii gier.
Jak już wcześniej wspomniałem, pozwala nam ona wybrać optymalne rozwiązanie w przypadku jakiegoś konfliktu.
Wzięła się ona z badań nad grami hazardowymi, ale dziś wykracza dalece po za ten temat.
Dziś swymi zagadnieniami sięga przez ekonomię, biologię aż po sztuczną inteligencję.
Poprzez połączenie z biologią, powstała memetyka oraz ewolucyjna teoria gier, ale o niej innym razem.
Zapewne część z Was słyszała o matematyku: John Nash. To jemu w 1994 komitet Nagrody Nobla przyznał nagrodę za rozwój teorii gier i jej zastosowanie w ekonomii.

A więc czym jest gra? Jest to po prostu sytuacja konfliktowa, a graczami są osoby biorące w nim udział.
Każdy z graczy obiera wybraną przez siebie strategię, po czym w zależności od obranej strategii przez rywala, otrzymuje swoją wypłatę.
Wypłatą może być oczywiście pieniądz, lub coś materialnego.

Możemy wyróżnić pewien podział gier,ja podam ich mniej niż można omówić, ale zapewne wrócę do nich w innym artykule:

-gry o sumie stałej to gry, w której zysk jednego gracza oznacza stratę drugiego.
-gry o sumie zmiennej
-gry sprawiedliwe (wartość oczekiwana wypłaty każdego z graczy jest taka sama) i niesprawiedliwe (gdy wartość oczekiwana wypłaty graczy jest różna)
-gry dwuosobowe i wieloosobowe (multiplayer)
-gry w postaci normalnej (typ gry w której gracze jednocześnie i niezależne od siebie decydują o swoich strategiach nie znając decyzji przeciwników) oraz gry w których gracz posiada wiedzę o strategiach przeciwników.
-gry gdzie gracz zna wysokości wypłat innych graczy oraz gry bez takiej wiedzy
-gry o skończony i nieskończonym czasie rozgrywki.

(podział za pl.wikipedia.org)

Po tym krótkim wprowadzeniu czas na powrót do sedna tematu czyli do: dylematu więźnia.

Czym jest owy dylemat?
Jest to problem oparty na dwuosobowej grze o niezerowej sumie(jak wcześniej wspominałem, jest to gra w której zysk jednego gracza oznacza stratę drugiego) wymyślony przez pracowników RAND Corporation: Melvina Dreshera i Merrill Flood w 1950 roku, ale Albert W. Tucker sformalizował jego zasady.

A teraz treść problemu (za pl.wikipedia.org):
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ć?

Gra ta jest tzw grą o strategii silnie dominującej. Oznacza to, że strategia ta jest zawsze nie gorsza od jakiejś innej strategii, niezależnie od wyboru strategii przez przeciwnika i zdarzeń losowych.

Na “chłopski rozum” w dylemacie więźnia oznacza to, że niezależnie od tego co robi przeciwnik, lepiej zdradzać niż współpracować.

Poniżej tabelka, pokazująca konsekwencje obranej strategii:

	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

Możemy rozszerzyć dylemat więźnia, do iterowanego dylematu, w którym gracze grają wielokrotnie obierając strategie w każdej kolejnej rundzie, opierając się o rundy poprzednie.
Problem możemy także rozszerzyć do gry N-osobowej, ale o tym w innym artykule.

---

Filed under: Teoria gier - @ 8 października 2014 14:28

Tagi: dylemat więźnia, gra, Nash, strategia, teoria gier