1 Biomatematyka Dr Wioleta Drobik-CzwarnoTeoria GIER Biomatematyka Dr Wioleta Drobik-Czwarno

2 Model matematyczny sytuacji konfliktowejCzym jest gra? 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 Model matematyczny sytuacji konfliktowej

3 Klasyfikacja gier Szopa M Teoria gier w negocjacjach i podejmowaniu decyzji

4 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

5 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ć

6 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 ruchów jakie gracz może wykonać w trakcie gry 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 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

7 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}

8 Wybieranie strony monetyZbió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

9 Typy gier w zależności od przebiegu rozgrywkiGracze 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ą

10 Matematyczne modele gierDrzewa: 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

11 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

12 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: Strategią dominującą jest B, ponieważ nigdy nie przyniesie gorszego wyniku niż A Strategia S1 S2 S3 S4 A 1 2 3 4 B 5

13 Podział ze względu na sumę wypłatGra 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

14 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 U białe

15 Dylemat wspólnych zasobówJako 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

16 Dylemat wspólnych zasobówMacierz wypłat dla przykładowego gospodarza: Zakładamy, że każdy gospodarz jest identyczny 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? Ilość cudzych krów na pastwisku 1 2 3 4 5 6 7 8 Ilość własnych krów na pastwisku 11 10 9 20 18 16 14 12

17 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.

18 Dylemat więźnia Macierz wypłat: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) Więzień B Przyznaje się Zaprzecza zarzutom Wiezień A 5, 5 0 (A), 20(B) 20 (A), 0 (B) 1, 1

19 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)) * (1- P(II)) * wypłata dla gracza I = 0,5 * 05 * * 0.5 * * 0.5 * * 0.5 * 1 = 6,5

20 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 ( ) Amerykański matematyk i ekonomista Prowadził badania nad teorią gier Był noblistą w dziedzinie ekonomii Został sportretowany w filmie „Piękny umysł”

21 Strategia równowagi Stan równowagi wg NashaTaki 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ą

22 Teoria gier a ewolucja

23 Ewolucyjna teoria gierPoszczegó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

24 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

25 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?

26 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

27 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!

28 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 przyrost stosującego zawsze strategie G p 1-p SJ SG

29 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

30 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

31 Stan równowagi

32 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

33 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

34 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ę

35 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

36 Inne strategie w grze gołąb-jastrząbPozer (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

37 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/Virology-How-does-a-virus-replicate

38 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

39 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

40 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:

41 Wirus DI i VSV Źródło: Turner, 2003, za Chao et al., Q. Rev. Biol. 75:261–275, 2000

42 Wirus DI i VSV Przykładowa macierz wypłat:Wypłata dla gracza (pomocnika), który przyjmuje strategie kooperacji podczas gdy drugi gracz oszukuje (DI) 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 graczy jeżeli wszyscy oszukują (w populacji są jedynie wirusy DI)

43 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

44 Teoria gier i bakteriofagiBaketriofagi 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 na replikacje) Viral Zone 2010, Swiss Institute of Bioinformatics

45 Teoria gier i bakteriofagiZmutowany 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

46 Literatura Wrzosek D. 2011. Matematyka dla biologów. Wydawnictwo UW.Kostecki R. Wprowadzenie do teorii gier. Materiały dostępne na stronie: Nogal P. Dylemat więźnia jako przykład wykorzystania teorii gier. Sigmund K., Nowak M.A Evolutionary game theory. Current Biology, Vol 9 No 14. Turner P.E A Virus Booster for Game Theory. Volume 69, Number 6, ASM News Roztański T html Wybrane schematy i rysunki: theory

47 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