Transcript
TEORIA GIER Biomatematyka Dr Wioleta Drobik-Czwarno
Czym jest gra? Model matematyczny sytuacji konfliktowej
Warunki: Co najmniej dwóch graczy (gracz rozumiany jest jako pojedynczy podmiot lub koalicja) Istnieją co najmniej dwie strategie czyli drogi postępowania W wyniku każdej gry każdy z graczy otrzymuje pewną wygraną, której wysokość zależy od strategii zastosowanych przez wszystkich graczy
Klasyfikacja gier
Szopa M. 2010. Teoria gier w negocjacjach i podejmowaniu decyzji
Teoria gier
Pierwszy raz pojawiła się w książce „The Theory of Games and Economic Behavior” autorstwa Johna von Neumanna (matematyk) oraz Oskara Morgensterna (ekonomista) opublikowanej w połowie lat 50-tych
Szerokie zastosowania m.in. w:
Ekonomii Naukach politycznych i społecznych Biologii ewolucyjnej Filozofii Informatyce
https://www.pokersnowie.com/blog/2013/06/25/basic-guide-game-theory
Teoria gier
Dziedzina matematyki, która powstała w połowie lat 50-tych XX wieku Jest narzędziem do rozpatrywania modeli podejmowania optymalnych decyzji, w sytuacjach z udziałem co najmniej dwóch graczy
Podejmowanie decyzji w układach z wieloma uczestnikami, zwanymi graczami lub agentami Gracze nie znają strategii swoich przeciwników Każdy z graczy ma swoje preferencje, które określają jego sposób działania Działania graczy muszą być zgodne z ustalonymi regułami Nagrodą jest wypłata, którą każdy z graczy stara się maksymalizować
Z czego składa się gra?
Zbiór wszystkich graczy D = {1,2,3,…,Pn} Zbiór reguł gry R Zbiór możliwych strategii S
Zbiór możliwych wyników W to wartości funkcji określonych na zbiorze strategii Możliwe wypłaty ui(w) dla każdego gracza Pi i dla każdego wyniku ze zbioru W
Zbiór możliwych ruchów jakie gracz może wykonać w trakcie gry
Korzyści jakie odniesie gracz, jeżeli uzyska w grze określony wynik Mogą być różne dla różnych graczy
ui(w) nazywana jest funkcją wypłaty
Przykład gry Wybieranie strony monety:
Dwóch graczy wybiera niezależnie orła lub reszkę i informuje o swoim wyborze sędziego
Zbiór graczy D = {P1, P2}
Zbiór zasad R:
Gracz może wybrać jedną z dwóch opcji: orła lub reszkę
Wybór gracza musi być niezależny od wyboru drugiego gracza
Gracz 1 wygrywa jeżeli obydwu graczy wybierze tą samą stronę monety
Gracz 2 wygrywa jeżeli dwóch graczy wybierze różne strony monety
Zbiór strategii S:
Wybór orła lub reszki czyli S1=S2={orzeł, reszka}
Wybieranie strony monety
Zbiór możliwych wyników W:
W={wygrana, przegrana}
S1 x S2 = {(orzeł, orzeł), (orzeł, reszka), (reszka, orzeł), (reszka, reszka)}
Przykładowe wypłaty: Wypłaty są równe:
u1(wygrana) = 100 u1(przegrana) = 0 u2 (wygrana) = 100 u2 (przegrana) = 0
A gdyby gracz 2 zyskiwał więcej na wygranej gracza 1 niż swojej? u1(wygrana) = 100
u1(przegrana) = 0 u2 (wygrana) = 50 u2 (przegrana) = 100
Gracze zawsze dążą do maksymalizacji swoich wyników (maksymalnej wypłaty), ale niekoniecznie do „wygranej” w grze
Typy gier w zależności od przebiegu rozgrywki
Gracze mogą wykonywać swoje ruchy:
naprzemiennie (gry pozycyjne) – reprezentowane za pomocą drzewa równocześnie (gry symultaniczne) – reprezentowany za pomocą macierzy
W zależności od tego kiedy gracze dowiadują się o swoich działaniach wyróżniamy gry:
z pełną informacją (wszystkie gry naprzemienne) z niepełną informacją
Matematyczne modele gier
Drzewa:
Służą do reprezentacji gier o naprzemiennej sekwencji ruchów Pokazują kolejność działań wykonywanych przez graczy Reprezentują gry w postaci rozwiniętej - gracze w poszczególnych ruchach są poinformowani na temat struktury gry
Macierze
Nie pokazują sekwencji ruchów, ale wypłaty otrzymywane na skutek wybrania przez graczy określonej kombinacji strategii Reprezentują gry w postaci strategicznej - gracze przy poszczególnych ruchach nie są poinformowani na temat struktury gry
Wypłata
Wygrane (wypłaty) otrzymywane na skutek wybrania przez graczy określonej kombinacji strategii W modelach przedstawiamy wartości liczbowe, które rzadko odpowiadają prawdziwym wypłatom, jakie gracze otrzymują w trakcie rozgrywki Wartości liczbowe symbolizujące wypłatę są pewnym porządkiem, symbolem tego ile gracz zyskuje a ile traci
Strategia dominująca
Strategia, której zastosowanie przyniesie graczowi, taką samą, a przynajmniej w jednym wypadku wyższą wypłatę, niż zastosowanie jednej z pozostałych strategii Macierz wypłat przykładowej gry: Strategia
S1
S2
S3
S4
A
1
2
3
4
B
1
2
3
5
Strategią dominującą jest B, ponieważ nigdy nie przyniesie gorszego wyniku niż A
Podział ze względu na sumę wypłat
Gra o sumie niezerowej:
Wielkość wygranej jednego z graczy nie jest bezwzględnie równa przegranej drugiego Każdy w graczy może coś zyskać na grze Brak czystego konfliktu, może się pojawić jedynie niezgodność interesów Gracze nie rywalizują o jedno dobro, współpraca czasami się opłaca
Gra o sumie stałej:
Wypłata jednego gracza może się zwiększyć jedynie kosztem wypłaty innych graczy Zawsze mamy do czynienia z konfliktem Podtypem są gry o sumie zerowej
Gry o sumie zerowej
Suma wartości oczekiwanej wypłat dla wszystkich uczestników dla każdego wyniku w grze wynosi 0
Strategia zwiększająca zysk jednego gracza zmniejsza wypłatę pozostałych
Opisują pewien konflikt, rywalizację lub konkurencję Gry antagonistyczne – są to gry o sumie zerowej, dla dwóch graczy, w których gracze nie współpracują Szachy jako przykład gry o sumie zerowej: Czarne wygrywają
Białe wygrywają
U czarne
1
0
U białe
0
1
Dylemat wspólnych zasobów
Jako przykład gry o sumie niezerowej Nazwa pochodzi od artykułu Garretta Hardina z 1968 roku "Tragedy of the Commons”
Przykład: Krowy na pastwisku
Jest 5 gospodarzy, każdy z nich ma dwie krowy, które może wypasać na wspólnym pastwisku Wypłata – ilość paszy zjedzona na pastwisku przez krowy gospodarza Pastwisko ma ograniczoną powierzchnie – im więcej krów tym mniejsza wydajność pastwiska
Dylemat wspólnych zasobów
Macierz wypłat dla przykładowego gospodarza:
Zakładamy, że każdy gospodarz jest identyczny Ilość cudzych krów na pastwisku
Ilość własnych krów na pastwisku
0
1
2
3
4
5
6
7
8
0
0
0
0
0
0
0
0
0
0
1
11
10
9
8
7
6
5
4
3
2
20
18
16
14
12
10
8
6
4
Każdemu z gospodarzy z osobna opłaca się najbardziej wypuścić dwie krowy na pastwisko Zakładając współpracę wszystkim gospodarzom opłaca się wypas jednej krowy na gospodarza Ile jednostek zarobi gospodarz, który się wyłamie i wypuści dwie krowy?
Dylemat więźnia Dwóch znanych policji złodziei zostało zatrzymanych na drobnej kradzieży. Podejrzani są o poważniejsze przestępstwo, jednak brak jest wystarczających dowodów na ich winę. Aresztowanych umieszczono w osobnych pomieszczeniach oraz zaproponowano wyrok w zawieszeniu za wydanie wspólnika i dostarczenie dowodów na jego udział w zbrodni.
Dylemat więźnia
Macierz wypłat: Więzień B Przyznaje się Przyznaje się Wiezień A
Zaprzecza zarzutom
Zaprzecza zarzutom
5, 5
0 (A), 20(B)
20 (A), 0 (B)
1, 1
W przypadku, gdy obaj nie przyznają się do winy otrzymują niewielki wyrok za kradzież na której zostali złapani (np. 1 rok) Jeżeli jeden aresztowany obciąży drugiego, sam dostanie wyrok w zawieszeniu, a drugi dostanie wyrok za poważniejsze przestępstwo (np. 20 lat) Jeżeli oboje się przyznają otrzymują karę za kradzież i popełnienie zbrodni, nieco złagodzoną ze względu na współpracę z wymiarem sprawiedliwości (np. 5 lat)
Najlepsza strategia?
Co powinien zrobić więzień A? Która strategia jest dla niego najbezpieczniejsza, a który rezultat (wygrana) byłby najlepszy? Ile wynosi oczekiwana odsiadka w więzieniu dla gracza A, w zależności od prawdopodobieństwa przypisywanego przez jednego gracza poszczególnym decyzjom, których może dokonać drugi gracz?
Gracz I zakłada, że prawdopodobieństwo przyznania się jego samego (P(I)) oraz gracza II (P(II)) jest równe czyli wynosi 0,5 P(I) * P(II) * wypłata dla gracza I + (1-P(I)) * P(II) * wypłata dla gracza I + P(I) * (1-P(II)) * wypłata dla gracza I + (1-P(I)) * (1P(II)) * wypłata dla gracza I = 0,5 * 05 * 5 + 0.5 * 0.5 * 20 + 0.5 * 0.5 * 0 + 0.5 * 0.5 * 1 = 6,5
Równowaga Nasha Szczególny stan w którym każdy uczestnik wybiera najlepszą z możliwych strategii. Strategia ta jest najlepszą możliwą odpowiedzią na zachowanie innych graczy.
John Forbes Nash (1928-2015) Amerykański matematyk i ekonomista Prowadził badania nad teorią gier Był noblistą w dziedzinie ekonomii Został sportretowany w filmie „Piękny umysł”
Strategia równowagi
Stan równowagi wg Nasha
Taki wybór strategii dokonany przez graczy, że dowolna zmiana strategii przez jednego gracza (przy równoczesnym braku zmiany strategii przez pozostałych graczy) nie spowoduje wzrostu wygranej tego gracza Jeżeli gra posiada tylko jedną strategię równowagową Nasha to jest to jedyne rozwiązanie tej gry Często gra ma więcej niż jedną strategie równowagową
Teoria gier a ewolucja
Ewolucyjna teoria gier
Poszczególne gatunki i/lub geny traktowane są jako gracze Reguły gry określa selekcja naturalna Przy zadanym środowisku każdy osobnik danego gatunku ma tym większą wypłatę, im większą liczbę potomków spłodzi dzięki swoim cechom Dostosowanie jakie warunkuje dana strategia może być zależne od jej częstości występowania w populacji Nie rozważamy już osobników wybierających określone strategie, ani równowagowych położeń pojedynczych gier, ale grę poszczególnych strategii grających przeciwko sobie
Gra gołąb-jastrząb
Populacja zwierząt w której dochodzi do konkurencji między samcami w okresie godowym
Typy zachowań samców nazywamy strategiami
Przyjmujemy, że strategie są dziedziczne Przyjęcia danej strategii z punktu widzenia zasady maksymalizacji dostosowania, może być: korzystne, niekorzystne lub neutralne Dla uproszczenia przyjmiemy, że dostępne są tylko dwa typy zachowań: gołąb oraz jastrząb
Gra gołąb-jastrząb Strategie:
Gołąb (G) - strategia wycofania się
Unika walki niezależnie od okoliczności Ogranicza się do demonstracji siły
Jastrząb (J) - strategia agresji
Zawsze dąży do walki W przypadku przeciwnika jastrzębia walczy do końca
Które wzorce zachowań powinny być częściej spotykane w populacji i od czego to zależy?
Gra gołąb-jastrząb
Rezultat – wygrana lub przegrana, pomijamy możliwość remisu Korzyścią jest wzrost dostosowania wzrost sukcesu reprodukcyjnego wzrost liczby potomstwa oraz zasobów środowiska Korzyść jest zmienną losową określoną na dwuelementowym zbiorze zdarzeń elementarnych ΩG,J
Korzyść (K) lub strata (korzyść ujemna) wyraża ilościowo wielkość wygranej i zależy od tego, którzy partnerzy wchodzą w konflikt
Gra gołąb-jastrząb
Macierz wypłat Osobnik, który wygrywa zyskuje α Osobnik zraniony traci γ Średnie wygrane dla gracza 1 względem gracza 2:
Macierz wypłat jest symetryczna dla obydwu graczy!
Gra gołąb-jastrząb Strategia a jej częstość
W populacji występuje frakcja p stosująca strategię jastrząb (J) oraz frakcja 1-p stosująca strategie gołębia (G)
Prawdopodobieństwo spotkania J = p Prawdopodobieństwo spotkania G = 1- p
Zmienną losową Sj oznaczamy przyrost dostosowania dla stosującego zawsze strategię J, natomiast SG SJ przyrost stosującego zawsze SG strategie G
p
1-p
Gra gołąb-jastrząb
Wartość oczekiwana zmiennej SJ Średni wzrost dostosowania dla stosującego zawsze strategie J
Wartość oczekiwana zmiennej SG Średni wzrost dostosowania dla stosującego zawsze strategie G
Gra gołąb-jastrząb
Jeżeli wielkość straty przewyższa możliwy zysk czyli α < γ, korzyści ze stosowania obydwu strategii zrównają się kiedy
Jeżeli
to D(J,p) < D( G, 1-p) czyli warto stosować G
Jeżeli
to D(J,p) > D( G, 1-p) czyli warto stosować J
Po pewnym czasie powinna ustalić się równowaga osobników stosujących strategie G i J
Stan równowagi
http://www.indiana.edu/~curtweb/S318/S318/lecturexi/lecturexi.html
Gra gołąb-jastrząb
Proporcja jastrzębi będzie tym mniejsza im więcej można stracić w walce w stosunku do zysku Inna interpretacja?
Strategia mieszana – zakładamy, że osobnik jest nosicielem genów, które z prawdopodobieństwem p powodują przyjęcie strategii J, oraz z prawdopodobieństwem 1-p przyjęcie strategii G Strategie J i G nazywamy czystymi
Strategia ewolucyjnie stabilna (ESS) „... 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
Strategia ewolucyjnie stabilna (ESS)
Pojęcie wprowadzone przez Maynarda Smitha Teoria ta rozważa grę poszczególnych strategii grających przeciwko sobie Zbiór strategii wziętych w określonych proporcjach jest strategią ewolucyjnie stabilną (ESS) jeśli:
żaden osobnik nie może zwiększyć swojego dostosowania (rozrodczego) poprzez zmianę strategii na inną żaden mutant korzystający z innej strategii nie ma szans dokonania „inwazji” na badaną populację
Strategia ewolucyjnie stabilna (ESS)
W grze gołąb-jastrząb strategia ewolucyjnie stabilna to:
Strategia czysta J – jeżeli wartość wygranej bardzo przewyższa koszt ewentualnej przegranej Strategia mieszana – Jeżeli straty w razie przegranej przewyższają maksymalny zysk, bardziej opłaca się stosować strategie mieszaną, czyli wymiennie strategie czyste G i J
Inne strategie w grze gołąb-jastrząb
Pozer (chojrak) - na początku przystępuje do ataku, ale jeżeli przeciwnik się nie przestraszy, ucieka. W starciu z jastrzębiem zachowuje się więc jak gołąb, w starciu z gołębiem jak jastrząb Odwetowiec (mściciel) - na początku walki zachowuje się jak gołąb. Jeżeli przeciwnik zaatakuje, odpłaca mu tym samym. W starciu z jastrzębiem zachowuje się jak jastrząb, w starciu z gołębiem jak gołąb http://www.toonpool.com/cartoons/Revenge%20of%20worms_94202
Teoria gier i wirusy
W trakcie replikacji w komórce gospodarza, białka wirusa znajdują się w cytoplazmie (lub jądrze komórkowym) i żaden konkretny wirus nie ma do nich wyłącznego dostępu Przypomina to dzielenie magazynu i może prowadzić do różnych strategii, kooperacji lub wyłącznie prób maksymalizacji własnej korzyści
Który wirus dostanie którą część, jeżeli do komórki dostanie się więcej niż 1? https://www.quora.com/Vi rology-How-does-a-virusreplicate
Teoria gier i wirusy
Strategie: Wirus może tworzyć (za pośrednictwem komórki) duże ilości produktu, wtedy przyjmuje strategie kooperacji Wirus może tworzyć (za pośrednictwem komórki) małe ilości produktu i korzystać z tego co wytworzą inne wirusy, wtedy dąży do maksymalizacji wyłącznie własnych korzyści Co opłaca się bardziej w kontekście skuteczności infekcji, a co dla pojedyńczego wirusa?
Model macierzy wypłat: Turner, 2003
Teoria gier i wirusy
Strategia maksymalizacji własnych korzyści została przyjęta przez wirusy DI (ang. defective-interfering particles)
Wirusy DI nie posiadają genów odpowiadających za syntezę części nowych produktów, zamiast tego korzystają z tego co wytworzyły inne wirusy
Zakłada się, że przy niskiej frekwencji wirusy DI będą lepiej dostosowane i będą zwiększały swoją frekwencję do pewnej granicy
Równowaga pomiędzy „zwykłymi” wirusami oraz wirusami DI jest bardzo często obserwowana w przyrodzie, szczególnie u wirusów roślinnych
Wirus DI i VSV
Wirus pęcherzykowatego zapalenia jamy ustnej (ang. vesicular stomatitis virus -VSV) :
należy do rodziny Rhabdoviridae jest patogenem ssaków kopytnych, w tym zwierząt hodowlanych takich jak: konie, bydło, świnie posiada genom w postaci pojedynczej nici RNA o ujemnej polarności (ssRNA(-)) złożonej z pięciu nie nakładających się na siebie genów kodujących białka wirusowe
Źródło: Tomczyk T., Orzechowska B. Zastosowanie wirusa pęcherzykowatego zapalenia jamy ustnej (VSV) jako wektora szczepionek przeciwwirusowych. Postepy Hig Med Dosw 67: 1345-1358.
Wirus DI i VSV
Źródło: Turner, 2003, za Chao et al., Q. Rev. Biol. 75:261–275, 2000
Wirus DI i VSV Przykładowa macierz wypłat: Gracze przyjmują strategie kooperacji (populacja złożona wyłącznie z pomocników)
Wypłata dla gracza, który oszukuje (DI), podczas gdy drugi z graczy (pomocnik) przyjmuje strategie kooperacji
Wypłata dla gracza (pomocnika), który przyjmuje strategie kooperacji podczas gdy drugi gracz oszukuje (DI)
Wypłata dla graczy jeżeli wszyscy oszukują (w populacji są jedynie wirusy DI)
Wirus DI i VSV
Wirusy DI po pojawieniu się w populacji zwykłych wirusów mają przewagę ewolucyjną, ponieważ ich replikacja jest bardziej wydajna i są otoczone pomocnikami, których białka mogą wykorzystywać szybko zwiększą swoją frekwencję. Wirusy DI są zależne od właściwych form wirusa (nie posiadają sekwencji kodującej białka) i nie mogą istnieć bez pomocników w miarę zwiększania się ich frekwencji ich dostosowanie będzie malało Najlepszą strategią dla wirusów DI jest populacja polimorficzna, równowaga pomiędzy cząstkami DI a pomocnikami Turner, 2003
Teoria gier i bakteriofagi
Baketriofagi
Wirusy atakujące bakterie (9 rodzin) lub archeony (2 rodziny) Materiał genetyczny: DNA lub RNA
Bakteriofag ɸ6 z rodziny Cystoviridae
Materiał genetyczny: dsRNA Wykorzystanie dylematu więźnia z teorii gier do analizy interakcji między wirusami (Chao i Turner, 1999) po raz pierwszy. Obserwuje się bardzo dużo spontanicznych mutacji (rzędu od 10-3 do 10-5 na replikacje) Viral Zone 2010, Swiss Institute of Bioinformatics
Teoria gier i bakteriofagi
Zmutowany bakteriofag ɸH2 w porównaniu z ɸ6
Dostosowanie ɸH2 jest zależne od frekwencji W obecności ɸH2 zredukowane jest łączne dostosowanie całej populacji
Bakteriofagi, które oszukują, będą się rozprzestrzeniać w populacji, ponieważ rzadko pojawiający się kooperatorzy będą mieli słabsze dostosowanie w starciu z nimi
P. Turner and L. Chao, Nature 398:441–443, 1999
Turner, 2003
Literatura
Wrzosek D. 2011. Matematyka dla biologów. Wydawnictwo UW. Kostecki R. Wprowadzenie do teorii gier. Materiały dostępne na stronie: http://www.fuw.edu.pl/~kostecki/teoria_gier.pdf Nogal P. Dylemat więźnia jako przykład wykorzystania teorii gier. http://jmf.wzr.pl/pim/2012_4_2_7.pdf Sigmund K., Nowak M.A. 2014. Evolutionary game theory. Current Biology, Vol 9 No 14. Turner P.E. 2003. A Virus Booster for Game Theory. Volume 69, Number 6, ASM News Roztański T. 2003. http://coin.wne.uw.edu.pl/tkopczewski/MIKROsite/teoria_gier_ksiazka/ch 01.html Wybrane schematy i rysunki: http://www.britannica.com/topic/gametheory
Dziękuję za uwagę „Cała ta opowieść o jastrzębiach i gołębiach jest oczywiście naiwnie prosta. Jest modelem, czymś co w rzeczywistości nie występuje w przyrodzie, ale ma nam pomóc w zrozumieniu zjawisk, które naprawdę w naturze istnieją.” Richard Dawkins
http://markmcmillion.com/hawks-and-doves-part-1/
