Temat13

Report
Dominika Staszewska
Roksana Hejman
Leszek Gryczka
We wcześniejszym referacie była mowa o grach n-osobowych o
sumie niezerowej, które nie dają się sensownie analizować,
sprowadzając do postaci funkcji charakterystycznej. W tym
referacie zajmiemy się pewnym szczególnym typem gier o takiej
własności. Należy do niego między innymi następująca gra:
Gra jest symetryczna, dla każdego z trzech graczy strategia D
dominuje nad C. Jedyną równowaga jest DDD z wypłatami
(-1,-1,-1), a więc wynik zdominowany w sensie Patero przez CCC
z wypłatami (1,1,1). Mamy więc do czynienia z trzyosobowym
dylematem więźnia.
Wraz z dojściem trzeciego gracza pojawia się możliwośd
zawierania koalicji. Sprawdzimy zatem, co się stanie gdy Kolumna
i Warstwa zawrą koalicję. Otrzymamy wówczas grę:
Zauważmy, że gra Wiersza ma punkt siodłowy (przy strategiach
dominujących obu graczy) w DDD a więc jego poziom
bezpieczeństwa wynosi -1. W grze Kolumny i Warstwy punktami
siodłowymi o wartości 0 są DCD i DDC. Ze względu na
symetryczność gry. Analogicznie wyniki uzyskamy dla pozostałych
koalicji. Wyznaczymy więc funkcje charakterystyczna gry ( L
oznacza panią Warstwę)
Wynikałoby z tego, że lepiej być w koalicji dwuosobowej niż w
żadnej (gdy dopuszczamy wypłaty uboczne) oraz, że najlepiej dla
wszystkich byłoby zawrzeć trzyosobową koalicję, w której wszyscy
zgodzą się grać C. O tym iż jest to tylko iluzja wynikająca ze
zbytniego zaufania do funkcji charakterystycznej można się
przekonać jeśli się pomyśli jak w praktyce jak w praktyce mogłaby
przebiegać gra z poprzedniego slajdu.
Jeżeli gracze będą grad swoje strategie bezpieczeństwa to
wynikiem będzie DCD lub DDC z wynikiem ( , ). Kolumna i
Warstwa osiągną swój poziom bezpieczeństwa , ale Wiersz
dostanie więcej niż -1, czyli jego poziom bezpieczeństwa.
Założenie że Kolumna i Warstwa będą dążyły do minimalizacji
wypłat Wiersza jest w tym przypadku nieuzasadnione. Oznacza
to , że Wiersz (bądź inny gracz) wychodzi lepiej na graniu
samemu niż na dwu-, trzyosobowej koalicji. Dwóm pozostałym
graczom (przy zachowaniu racjonalnym) najlepiej będzie zagrać
strategią w której jeden zagra D, a drugi C.
Mamy zatem dwa wnioski:
•Wnioski wyciągane z analizy funkcji charakterystycznych nosobowych gier o sumie niezerowej mogą byd mylące
•Dążenie do współpracy w sytuacjach, które mogą byd
modelowane przez n-osobowy dylemat więźnia bywa ryzykowne
Aby przekonać się jakie dokładnie może być to ryzyko rozważny
grę pięcioosobową: każdy z graczy ma strategie C i D, zaś wypłata
gracza zależy od tego czy gra on C, czy D oraz od tego ilu z
pozostałych graczy gra C.
Ponieważ wypłata przy graniu strategii D jest zawsze wyższa niż
odpowiednia wypłata, gdy zagra się C, dla wszystkich graczy
strategia D dominuje strategię C. Kiedy wszyscy grają D, wypłaty
wszystkich graczy wynoszą -1. Jest to wynik nieoptymalny w
sensie Pareto, ponieważ gdyby wszyscy grali C, każdy
otrzymałby wypłatę .
EKSPERYMENT
Dobierzcie sobie czterech przyjaciół (lub wrogów) i zagrajcie z
nimi w grę 2.1.3. dziesięć razy, zapisujecie za każdym razem
decyzje i wypłaty wszystkich graczy. Na koniec obliczcie łączne
wypłaty wszystkich graczy i dla każdego porównajcie jej
wysokośd z liczbą przypadków , w których zagrał C.
Jeśli przeprowadzicie ten eksperyment jego wyniki
prawdopodobnie was zaniepokoją. Dlaczego? Rozważmy skutki
zagrania C zamiast D:
•Obniża to własną wypłatę o 1 (wszystkie wypłaty strategii C są o
1 mniejsze niż odpowiednie wypłaty D)
•Dla pozostałych graczy oznacza to podniesienie o 1 liczby
„innych graczy” grających C ,a w konsekwencji podniesienie
wypłat o 1.
Za każdym razem gdy wybierasz C szkodzisz sobie i pomagasz
innym.
Przykład
Przeprowadzając eksperyment na 5 graczach tylko sześciu
(nazwijmy ich kooperatorami) zagrało C pięć lub więcej razy. Trzy
z pięciu grup miało dwóch kooperatorów ( nazwijmy je grupami
częściowo kooperującymi). Gracze uzyskali następujące wypłaty:
Aby odnieśd sukces w tej grze należy byd dezerterem w grupie,
której częśd członków próbuje kooperowad. Na uczestnictwie w
grupie niekooperujących wszyscy wychodzą źle, ale w najgorszej
sytuacji są osoby nastawiające się na kooperację w grupie, w
której wykorzystają ich dezerterzy. W świecie n-osobowego
Dylematu Więźnia cnota jest karana, a oportunizm nagradzany.
N-osobowym Dylematem Więźnia nazywamy każdą grę, w
której każdy z n graczy ma dwie strategie ( nazwijmy je C i D),
takie że:
•Dla każdego gracza D jest strategią dominującą
•Jeśli wszyscy zagrają D, wszyscy uzyskają gorsze wypłaty niż w
sytuacji, gdy wszyscy zagrają C
Na zakończenie przyjrzymy się grze „zanieczyszczanie jeziora” .
Wyobraźmy sobie jezioro ,nad którym leży pięć wsi
czerpiących z niego wodę i spuszczających do niego swoje
ścieki. Mieszkańcy każdej wsi decydują czy oczyszczać ścieki
przed spuszczeniem do jeziora, czy nie. Koszty oczyszczania
ścieków to 5 tys. dolarów rocznie dla każdej wsi, a z drugiej
strony koszty uzdatniania wody pitnej dla jednej wsi to 20 tys.
dolarów razy liczna wsi ,które nie oczyszczają swoich ścieków.
Poniższa tabela przestawia roczne koszty prowadzenia
gospodarki rolnej każdej z wsi, w zależności od tego, czy wieś
oczyszcza swoje ścieki, czy nie oraz w zależności od liczby
pozostałych wsi oczyszczających ścieki:
Ponieważ koszty dla danej wsi są zawsze niższe, jeśli nie oczyszcza
ona swych ścieków, wszystkie będą zanieczyszczały jezioro i każda z
nich poniesie łącznie koszty uzdatniania wody 100 tys. dolarów, co
jest kwotą znacznie wyższą niż 5 tys. dolarów, które każda wieś
musiałaby rocznie wyłożyć na utrzymanie czystości wody w jeziorze.
Czy istnieje jakieś wyjście z tej pułapki? Wiemy, że żadnej ze wsi
nie opłaca się oczyszczać ścieków ( gdyby to robiła jej mieszkańcy
wydaliby rocznie 30 tys. dolarów więcej, żeby zapewnić
oszczędności mieszkańca pozostałych wsi).
Może jednak nie której wsie mogłyby wspólnie przeprowadzić
swoją gospodarkę wodną? Dwie wsie nie mogą osiągnąć w ten
sposób oszczędności, ale trzy już tak. Jeśli będą oczyszczały swoje
ścieki, każda z nich zaoszczędzi na uzdatnianiu wody 6 tys.
dolarów rocznie, płacąc za oczyszczanie tylko 50 tys. dolarów.
Byłoby jednak naiwnością sądzić, że łatwo będzie zawiązać taką
koalicję bo, jak już widzieliśmy wsie ,które do niej nie wejdą
również zaoszczędzą swoje 6 tys. dolarów, ale bez poniesienia 5
tys. dolarów kosztów.
Zatem każda z wsi widziałaby chętnie pozostałe
zawiązujące takie porozumienie, ale robiłaby wszystko żeby
samej się w niej nie znaleźć. Jeden z amerykańskich
ekologów Garret Hardin sugerował, że najlepszym
rozwiązaniem takich problemów mogłaby byś zgoda każdej
z wsi na ”zmuszenie” wszystkich do zawarcia koalicji.
Wychodzi na to, że zbiorowy przymus byłby dla wszystkich
przymuszanych opłacalny.
ĆWICZENIA
1.Rozważmy następującą grę kooperacji-dezercji, niebędącą
jednak pięcioosobowym Dylematem Więźnia, gdyż dezercja nie
zawsze przynosi w niej korzyści:
a)Załóżmy, że w pierwszej rundzie wszyscy gracze grają C. Czy
gracz grający C uzna za korzystne zmianę w następnej rundzie
swojej strategii na D?
b) Załóżmy, że w pierwszej grze czterech graczy gra C, zaś jeden D
(CCCCD).
Czy gracz grający C chciałby w następnej rundzie zagrać D?
Czy gracz grający D chciałby w następnej rundzie zagrać C?
c) Przeprowadź analogiczne analizy sytuacji, w których w pierwszej
rundzie zagrano CCCDD, CCDDD, CDDDD, DDDDD.
2. Sześciu farmerów użytkuje wspólne pastwisko, na którym można
wypasać sześć krów po 1000 dolarów zysku każda. Wypasanie każdej
dodatkowej (powyżej sześciu) spowoduje zmniejszenie zysków
przynoszących przez jedną krowę o 100 dolarów. Każdy farmer ma do
wyboru dwie strategie:
C: wypasać jedną krowę
D: wypasać dwie krowy
a) Uzupełnij tabelkę:
b) Jak liczna musi być koalicja farmerów, by mogła osiągnąć
korzyści z tego, że wszyscy jej członkowie zagrają C?
c) Jeśli taka koalicja powstanie , to wolałbyś do niej należeć czy
nie?
Teoria Gier a Sport.
DRAFT
w Futbolu
Amerykańskim.
Draft-dobór zawodników do drużyn futbolu
amerykańskiego.
W futbolu, koszykówce czy innych sportach w których
działają zawodowe ligi, zespoły wybierają nowych graczy
w systemie draftu, który zakłada sekwencyjny dobór
zawodników przez poszczególne drużyny. Spośród
zawodników wpisanych na listy transferowe najsłabszy w
ostatnim sezonie zespół wybiera jednego zawodnika jako
pierwszy. Po nim wybiera jednego zawodnika drugi zespół
od końca itd., a gdy wszystkie zespoły wybiorą po jednym
zawodniku procedurę tę powtarza się w tej samej
kolejności do momentu kiedy nie ma już „zawodników do
wyboru”. W założeniu tego systemu danie najsłabszej
drużynie pierwszeństwa wyboru ma sprawić że liga stanie
się bardziej wyrównana a jej rozgrywki bardziej atrakcyjne
dla kibiców.
Problem z tą pozornie doskonałą procedurą polega na tym, że
prowadzi ona do sytuacji, które są w istocie pewną wymyśloną
formą Dylematu Więźnia. Rozpatrzmy najprostszy przykład.
Załóżmy że mamy do czynienia z dwiema drużynami, Niebieskimi
i Czerwonymi, a w drafcie jest czterech zawodników, A, B, C, D.
Przyjmijmy że zespoły mają następujące preferencje co do
graczy:
Niebiescy Czerwoni
A
B
C
D
B
C
D
A
Tak więc Niebiescy najbardziej
potrzebują A, a najmniej D, zaś
Czerwoni najbardziej chcą dostać
B, a najmniej A.
Gdyby obie drużyny przyjęły podczas draftu „szczere” strategie, a
Niebiescy wybrali jako pierwsi, draft przebiegałby następująco:
Ostatecznie każda z drużyn dostanie pierwszego i trzeciego
zawodnika ze swojej listy.
Jednakże, podobnie jak wyborcy nie muszą głosować szczerze,
drużyny również nie muszą wybierać graczy –i czasem mogą
odnieść z tego korzyść. Załóżmy że w naszej sytuacji:
1) Każdy zespół zna preferencje konkurentów;
2 ) Celem każdego z zespołów jest zdobycie swoich najbardziej
preferowanych graczy (a nie np. uniemożliwienie innym
zdobycia graczy, których potrzebują).
W sporcie założenie pierwsze jest zasadne –zespoły dysponują
szczegółowymi informacjami zarówno o kwalifikacjach
poszczególnych zawodników w drafcie, jak i o potrzebach
innych drużyn. Różnie natomiast bywa z warunkiem drugim –
zdarzyło się że wybierano w drafcie jakiegoś zawodnika tylko
po to, by nie wzmocnił innej drużyny.
Jeśli jednak przyjmiemy oba założenia, Niebiescy mogliby wybrać
bardziej preferowanych przez siebie zawodników, wykorzystując
fakt że Czerwoni na pewno nie będą chcieli gracza A. Wobec tego
Niebiescy mogą spokojnie w pierwszej rundzie wybrać drugiego
w kolejności preferencji gracza B, licząc na to, że gracza A
wybiorą w rundzie drugiej. Daje to następujący przebieg draftu:
Czerwoni jeśli mają się trzymać założenia 2) nie mogą bronić się
przed taką strategią –powyższe wybory są dla obu drużyn
optymalne. W naszym przykładzie nie mamy do czynienia z
Dylematem Więźnia. Czerwoni stracili a Niebiescy zyskali, a
ostateczny wynik jest paretooptymalny. Ale gdy w drafcie wezmą
udział trzy zespoły sytuacja ulegnie zmianie. Rozważmy
następujący przykład z trzema drużynami i sześcioma graczami:
Jeśli zespoły wybierają graczy szczerze, Niebiescy i Czerwoni
dostają po dwóch najbardziej pożądanych przez siebie graczy,
również Zieloni nie wychodzą na tym najgorzej. Oczywiście ani
Niebiescy ani Czerwoni nic na nieszczerości nie mogliby zyskać,
ale co z Zielonymi?
Gdy w pierwszej rundzie Niebiescy i Czerwoni wybiorą swoich
najbardziej pożądanych graczy, Zieloni mogą zamiast C wybrać F i
wtedy mamy taki rezultat:
Niewątpliwie Zieloni zyskali na nieszczerości. Jak w tej sytuacji
mogą się bronić Czerwoni, którzy, wybierając w pierwszej rundzie
E, zostaną poszkodowani na skutek nieszczerości Zielonych?
Okazuję się, że wybranie w pierwszej rundzie F nic by im nie
pomogło, zadziałałoby wybranie B:
Wynika to stąd że teraz Zieloni muszą wybrać C w pierwszej
rundzie, bo inaczej straciliby go na rzecz Niebieskich. W tym
przypadku nieszczerość Czerwonych działa na szkodę Niebieskich
- czy ci mogą się jakoś bronić? Nie pomoże im wybranie w
pierwszej rundzie B. ale jeżeli wybiorą wtedy C, doprowadzą do
następującego przebiegu draftu:
Takie wybory są optymalne dla wszystkich drużyn. Jeżeli
porównamy wynik przy wyborach optymalnych z pierwotnym
wynikiem draftu przy wyborach szczerych, zobaczymy że
mielibyśmy do czynienia z Dylematem Więźnia. Wszystkie trzy
zespoły uzyskały w drafcie wyniki gorsze niż gdyby wszyscy
wybierali szczerze –racjonalne działania mające na celu
zabezpieczenie własnego interesu wszystkim przyniosą szkodę.
Uczestnicy skomplikowanej procedury draftu zawodników
okazują się tak samo narażeni na paradoks Dylematu Więźnia, jak
farmerzy wypasający krowy na gminnym pastwisku.
ĆWICZENIA
1. [Kohler i Chanrasekaran, 1971] podają następujący algorytm
wyznaczania optymalnych wyborów dla sytuacji, gdy w drafcie
biorą udział tylko dwie drużyny (np. Niebiescy i Czerwoni)
1)Przy optymalnej grze w ostatniej rundzie Czerwoni wybiorą
gracza zajmującego na liście preferencji Niebieskich ostatnią
pozycję. Oznaczamy tego gracza jako wybór Czerwonych w
ostatniej rundzie i (w wyobraźni) skreślimy z listy preferencji obu
drużyn.
2)W ostatniej rundzie Niebiescy wybiorą zawodnika, który jest na
ostatniej pozycji zredukowanej listy Czerwonych. Oznaczamy
tego gracza jako wybór Niebieskich w ostatniej rundzie i
skreślimy go z listy preferencji obu drużyn.
3)Powtarzajmy powyższą operację dla rund od przedostatniej do
pierwszej. Wypróbuj algorytm na poniższych przykładach; wyniki
porównaj ze skutkami szczerych wyborów.

similar documents