Wybrane zagadnienia badań operacyjnych dr inż. Zbigniew Tarapata Wykład nr 6: Elementy teorii gier 6. ELEMENTY TEORII GIER Podejmowanie decyzji inwestycyjnych często jest dokonywane w sytuacjach, w których nie wiadomo, jaki będzie stan otoczenia lub też, jaką decyzję podejmą inni decydenci, mający wpływ na wyniki decyzji przez nas podejmowanych. Przykładem może być konkurencja kilku przedsiębiorstw na rynku, który jest podzielony między nie - decyzje podjęte przez każdego z konkurentów mają wpływ na wyniki pozostałych udziałowców rynku. Można powiedzieć, że w świecie finansów bez przerwy stykamy się z konfliktem interesów, podobnie jak w grach. Grać możemy np. na giełdzie. Sytuacje te noszą nazwę konfliktowych (sytuacje decyzyjne, w których występują decydenci o, najczęściej, rozbieżnych celach). Stąd nauka, która zajmuje się analizą wszelkiego rodzaju sytuacji konfliktowych (nie tylko ekonomicznych) nosi nazwę teorii gier. O uczestnikach gry mówi się, że są jej graczami. Grać można: " z jednym graczem (gry dwuosobowe), " bądz z wieloma graczami (gry wieloosobowe). Gracze mogą się ze sobą porozumiewać, tworząc koalicje (gry kooperacyjne), bądz mogą się nie porozumiewać (gry niekooperacyjne). Grać można z przeciwnikiem inteligentnym (gry właściwe), bądz z przeciwnikiem, któremu nie zależy na wygranej (gry z naturą). W naszych rozważaniach zajmiemy się szczegółowo grami z naturą oraz grami dwuosobowymi o sumie zero1. 1 Gry o sumie zero są to takie gry, w których wygrana jednego gracza jest równa przegranej drugiego z nich. 1 Wybrane zagadnienia badań operacyjnych dr inż. Zbigniew Tarapata Wykład nr 6: Elementy teorii gier 6.1 GRY Z NATUR Gry z naturą są grami dwuosobowymi, przy czym natura jest rozumiana jako przeciwnik nierozumny w przeciwieństwie do innych graczy. Naturze nie zależy na wyniku gry. Istnieje kilka sposobów wyboru optymalnej strategii w grach z naturą: a) kryterium optymisty; b) kryterium pesymisty; c) kryterium Hurwicza; d) kryterium Bayes a; e) kryterium Savage a. Opisane rodzaje kryteriów zdefiniujemy na przykładzie. Przykład 7.1 Rolnik posiadający glebę klasy III ma wybrać pod uprawę jeden z trzech rodzajów zbóż. Plony tych zbóż z 1 ha, w kwintalach, w zależności od warunków klimatycznych przedstawia tabela. Który z rodzajów zbóż powinien wybrać rolnik? Stany natury Susza Normalnie Deszcze Zboże Żyto 24 28 36 Pszenica 31 30 28 Jęczmień 28 34 29 Przyjmijmy następujące oznaczenia: M liczba decyzji (w przykładzie: 3) , N liczba stanów natury (w przykładzie: 3), aij wartość zysku (w przykładzie: wysokość plonów) wynikającego z podjęcia decyzji o numerze i przy wystąpieniu sytuacji (stanu i = 1,..., M j = 1,..., N natury) o numerze j, , ; 2 Wybrane zagadnienia badań operacyjnych dr inż. Zbigniew Tarapata Wykład nr 6: Elementy teorii gier Kryterium optymisty zakłada, że wystąpi najlepszy z możliwych stanów natury (jesteśmy optymistami). Wybór decyzji polega na określeniu najlepszej wartości w każdym wierszu macierzy, a następnie wybieramy tą decyzję (zboże), z którą jest związana największa wartość z wcześniej określonych, tzn. * io wybieramy taką decyzję , dla której zachodzi: * vo(io)= max max aij (7.1) i=1,M j =1, N Dla naszego przypadku mamy: max a1 j = max{24, 28, 36}= 36 j=1,3 max a2 j = max{31, 30, 28}= 31 * j=1,3 io max=36, =1 max a3 j = max{28, 34, 29}= 34 j=1,3 Kryterium pesymisty jest kryterium ostrożnym. Zakłada ono, że zajdzie sytuacja najmniej korzystna dla podejmującego decyzję (jesteśmy pesymistami). Dlatego dla każdej strategii (każdego wiersza) macierzy wypłat należy określić najmniejszą wartość (związaną z najbardziej niekorzystną sytuacją) dla której ta minimalna wartość jest największa, tzn. i* wybieramy taką decyzję , dla której zachodzi: p vp(i*)= max min aij (7.2) p i=1,M j =1, N Dla naszego przypadku mamy: min a1 j = min{24,28,36}= 24 j=1,3 min a2 j = min{31,30,28}= 28 j=1,3 i* i* max=28, =2 lub =3 p p min a3 j = min{28,34,29}= 28 j=1,3 3 Wybrane zagadnienia badań operacyjnych dr inż. Zbigniew Tarapata Wykład nr 6: Elementy teorii gier Kryterium Hurwicza jest kryterium ważonym między kryteriami: optymisty i pesymisty. Wagą jest arbitralnie wybrana wartość * ą "[0,1] ih parametru (tzw. współczynnik optymizmu), a decyzją optymalną dla tego kryterium jest taka decyzja, dla której zachodzi: * vh(ih,ą)= maxńłą " max aij + (1-ą)" min aij ł ł żł (7.3) i=1,M j =1, N j =1,M ół ł * * ą = 1, to ih = io , Zauważmy: jeżeli * jeżeli ą = 0, to ih = i* . p Niech ą=0,4. Dla naszego przykładu mamy: 0,4 " max a1 j + 0,6" min a1 j = 0,4 "36 + 0,6 " 24 = 28,8 j=1,3 j=1,3 0,4 " max a2 j + 0,6 " min a2 j = 0,4 "31+ 0,6 " 28 = 29,2 j=1,3 j=1,3 0,4 " max a3 j + 0,6 " min a3 j = 0,4 "34 + 0,6 " 28 = 30,4 j=1,3 j=1,3 * max{28,2; 29,2; 30,4}= 30,4 ih = 3. oraz , stąd Kryterium Bayes a zakłada, że decyzją optymalną jest ta decyzja, dla której wartość oczekiwana wygranej jest największa, przy p = p1, p2,& , pN na stanach ( ) założeniu znajomości rozkładu natury. Najczęściej przyjmuje się, że każdy stan natury może wystąpić 1 pj = , j = 1, N z jednakowym prawdopodobieństwem, tzn. . N * ib Wybieramy taką decyzję , dla której zachodzi: N * vb(ib)= max pjaij " (7.4) i=1,M j =1 4 Wybrane zagadnienia badań operacyjnych dr inż. Zbigniew Tarapata Wykład nr 6: Elementy teorii gier Dla naszego przypadku mamy: 1 1 p1 = p2 = p3 = = N 3 1 1 1 dla i = 1 24 " + 28 " + 36 " = 29,04 3 3 3 1 1 1 dla i = 2 31" + 30 " + 28 " = 29,4 3 3 3 1 1 1 dla i = 3 28 " + 34 " + 29 " = 30,03 3 3 3 * max{29,04; 29,4; 30,03}= 30,03 ib = 3. oraz , a stąd Kryterium Savage a spełnia postulat minimalizacji oczekiwanej straty wynikłej z podjęcia przez nas decyzji gorszej niż najlepsza możliwa dla danego stanu natury (z punktu widzenia podejmującego decyzję). Pierwszym etapem jest znalezienie tzw. macierzy strat. Strata jest różnicą między największą wygraną możliwą dla danego stanu natury, a wygraną odpowiadającą naszej decyzji. Element Sij macierzy strat wyliczymy następująco: Sij = a* - aij (7.5) j gdzie: a* = maxaij j (7.6) i=1,M * is Mając określoną macierz strat wybieramy taką decyzję , dla której strata jest najmniejsza, tzn.: * vs(is )= min max sij (7.7) i=1,M j =1, N 5 Wybrane zagadnienia badań operacyjnych dr inż. Zbigniew Tarapata Wykład nr 6: Elementy teorii gier Utwórzmy najpierw macierz strat. Macierz pierwotna A miała postać: 24 28 36 ł łł ł31 30 28śł A = ł śł ł śł ł28 34 29ł maksymalne wygrane dla poszczególnych 31 34 36 ! stanów natury * a1 = maxai1 = 31, tzn. i=1,M * a2 = maxai2 = 34 , i=1,M * a3 = maxai3 = 36. i=1,M Macierz strat S będzie miała wobec tego postać: 31- 24 34 - 28 36 - 36 7 6 0 ł łł ł łł ł31- 31 34 - 30 36 - 28śł ł0 4 8śł S = = ł śł ł śł ł śł śł ł31- 28 34 - 34 36 - 29ł ł 0 7ł ł3 max s1 j = max{7,6,0}= 7 j=1,3 max s2 j = max{0,4,8}= 8 j=1,3 max s3 j = max{3,0,7}= 7 j=1,3 * * min{7,8,7}= 7 is = 1 lub is = 3 oraz , stąd . 6 Wybrane zagadnienia badań operacyjnych dr inż. Zbigniew Tarapata Wykład nr 6: Elementy teorii gier PRZYKAAD Podejmujemy decyzję, czy iść do kina, teatru, czy muzeum. Możemy trafić na dobry film lub spektakl, albo też słaby. Nie wiemy tylko, czy muzeum jest otwarte. Muzeum zamknięte Muzeum otwarte dobry słaby dobry słaby Film 20 4 Film 20 4 Spektakl 13 10 Spektakl 13 10 Wystawa 0 0 Wystawa 12 12 max 20 10 max 20 12 Żal odpowiadający powyższym sytuacjom przedstawiają tabelki: max Jeżeli muzeum jest zamknięte, max to idziemy do kina, w p.p. do 0 6 6 0 8 8 teatru ?!!!! 7 0 7 7 2 7 20 10 20 8 0 8 7 Wybrane zagadnienia badań operacyjnych dr inż. Zbigniew Tarapata Wykład nr 6: Elementy teorii gier 6.2 GRY DWUOSOBOWE O SUMIE ZERO Załóżmy, że w grze bierze udział dwóch graczy ostrożnych i inteligentnych: gracz A i gracz B. Każdy z nich może samodzielnie podejmować decyzje (nazywane strategiami gracza). Przyjmijmy, że gracz A ma ich M, a gracz B N. Dla każdej pary (i, j) decyzji graczy A i B znana jest pewna liczba aij oznaczająca wygraną gracza A w przypadku, gdy gracz ten podejmie decyzję o numerze i przy podjęciu przez gracza B decyzji o numerze j. Macierz MA=[aij]MN nazywać będziemy macierzą wypłat gracza A. Dla gracza B, w przypadku gier z zerową sumą wypłat, macierz wypłat jest równa MB= -MA. Oczywistym jest, że gracz A będzie się starał zmaksymalizować swoją wygraną, a gracz B zminimalizować swoją przegraną (ujemna wygrana gracza A oznacza wygraną gracza B). Interesy obu graczy są więc sprzeczne. Obaj gracze będą dążyć do osiągnięcia tzw. punktu równowagi w grze. Jest to taka sytuacja (para strategii (i*, j*) obu graczy), która zapewni graczowi A możliwie największą wygraną, graczowi B możliwie najmniejszą stratę oraz zmiana tej pary strategii przez obu graczy nie jest dla żadnego z nich opłacalna. ai* j* Element nosi nazwę wartości V gry. Punkt równowagi nazywa się często punktem siodłowym macierzy wypłat. Jest to element macierzy znajdujący się na przecięciu wiersza o takim numerze i* oraz ai j* * kolumny, o takim numerze j*, że element jest najmniejszy w swoim wierszu i jednocześnie największy w swojej kolumnie. Formalnie punkt równowagi jest wyznaczany następująco: wyznaczyć taką parę strategii (i*, j*), dla której zachodzi: max min aij = min max aij = ai j* = V * (7.8) i"{1,..,M } j"{1,...,N} j"{1,..,N} i"{1,...,M } Jeżeli w grze istnieje taka para strategii, dla której spełnione jest (7.8), to parę tą nazywamy rozwiązaniem gry w zbiorze tzw. strategii czystych. Strategię czystą można utożsamiać z taką decyzją gracza, która jest podejmowana tylko raz. 8 Wybrane zagadnienia badań operacyjnych dr inż. Zbigniew Tarapata Wykład nr 6: Elementy teorii gier Przed sprawdzeniem, czy w grze istnieje para strategii czystych w równowadze, powinniśmy usunąć z macierzy wypłat MA tak zwane MA strategie zdominowane. Uzyskamy wówczas macierz . Mówimy, że strategia i-ta gracza A (i-ty wierz macierzy MA) dominuje strategię k-tą tego gracza (k-ty wierz macierzy MA) jeżeli aij e" akj dla każdego j (7.9) oraz aij > akj dla przynajmniej jednego j (7.10) Mówimy, że strategia j-ta gracza B (j-ta kolumna macierzy MA) dominuje strategię k-tą tego gracza (k-tą kolumnę macierzy MA) jeżeli aij d" aik dla każdego i (7.11) oraz aij < aik dla przynajmniej jednego i (7.12) Poprzez usunięcie strategii zdominowanych zmniejszamy wymiar macierzy wypłat, a następnie sprawdzamy, czy istnieje punkt siodłowy. Jeśli istnieje, to para strategii (i*, j*), dla której spełnione jest (7.8) jest rozwiązaniem gry. Często zdarza się, że nie istnieje taka para strategii (i*, j*), dla której spełnione jest (7.8) (czyli nie istnieje punkt siodłowy), tzn. zachodzi ą = max min aij `" min max aij = ł (7.13) i"{1,..,M } j"{1,...,N} j"{1,..,N} i"{1,...,M } Liczba ą jest tzw. dolną wartością gry, a liczba ł - górną wartością gry. Wówczas wyznacza się tzw. sytuację równowagi w zbiorze tzw. strategii mieszanych. Strategia mieszana jest to kombinacja liniowa strategii czystych. Inaczej można powiedzieć, że strategię mieszaną każdego gracza tworzy rozkład prawdopodobieństwa na zbiorze jego strategii czystych. Strategie mieszane stosowane są na ogół w dwóch 9 Wybrane zagadnienia badań operacyjnych dr inż. Zbigniew Tarapata Wykład nr 6: Elementy teorii gier rodzajach sytuacji: w przypadku wielokrotnego (niezależnego od siebie) rozgrywania tej samej gry (wtedy prawdopodobieństwa informują o częstości stosowania poszczególnych strategii czystych) lub gdy obszar zastosowania decyzji (strategii czystych) daje się podzielić na wystarczająco wiele obszarów częściowych (przykład rolnika, który ma do obsiania pewien areał wieloma rodzajami pszenicy i zmuszony jest stosować różny materiał siewny w odpowiednich proporcjach). Dla przypadku, gdy obaj gracze mają po dwie dopuszczalne strategie, rozkład prawdopodobieństwa na strategiach czystych (czyli strategię mieszaną) wyznacza się następująco: a22 - a21 * * * x1 = (7.14) , a11 - a12 - a21 + a22 x2 =1- x1 a22 - a12 * * * y1 = (7.15) , a11 - a12 - a21 + a22 y2 =1- y1 * xi y* gdzie jest częstością stosowania i-tej strategii przez gracza A, a j jest częstością stosowania j-tej strategii przez gracza B. Oczekiwana V wygrana obu graczy jest taka sama i wynosi: 2 2 * H (x*, y*) = V = ""a " xi " y* ij j (7.16) . i=1 j=1 MA Jeżeli macierz jest wymiaru 2N lub M2, to stosujemy metodę graficzną poszukiwania strategii mieszanych. 10 Wybrane zagadnienia badań operacyjnych dr inż. Zbigniew Tarapata Wykład nr 6: Elementy teorii gier Przykład 7.2 (wykorzystanie teorii gier do ustalenia wielkości produkcji dwóch firm) Dwóch producentów wytwarza ten sam towar, który jest sprzedawany na rynku. Niech d(z) oznacza funkcję popytu (z - liczba sztuk towaru na rynku (w tys.)), c(z) - funkcja kosztów wytwarzania. W ustalonym okresie producent A może wytworzyć z1 sztuk wyrobu, zaś producent B - z2 sztuk wyrobu. Popyt maleje wraz ze wzrostem liczby sztuk towaru na rynku i jest zerowy, gdy łączna liczba sztuk towaru ze"z0. Załóżmy, że producenci z pewnych względów nie porozumiewają się przed wystawieniem towaru na rynek. Jeśli producenci wystawią na rynek z1 i z2 sztuk towaru, to pierwszy z nich otrzyma zysk w wysokości: H1(z1, z2 ) = z1 " d(z1 + z2 ) - c(z1) (7.17) a drugi H2 (z1, z2 ) = z2 " d(z1 + z2 ) - c(z2 ) (7.18) Przy założeniu, że 1 c(z) = " z (7.19) 10 1 ńł , z < z0 = 5 ł d(z) = z ł (7.20) ł0, w przeciwnym przypadku ół określić ile towaru powinien każdy z producentów produkować, aby jego udział w zysku był możliwie największy oraz wielkość wygranej każdego z nich. Założyć, że obaj producenci mogą produkować towar w następujących liczbach sztuk (w tys.): 1, 2 i są jedynymi producentami na rynku tego wyrobu. 11 Wybrane zagadnienia badań operacyjnych dr inż. Zbigniew Tarapata Wykład nr 6: Elementy teorii gier Rozwiązanie: Z treści zadania wynika, że każdy z producentów ma do wyboru 2 strategie (liczba sztuk produkowanych wyrobów). Najpierw tworzymy macierz wypłat dla gracza (producenta) nr 1 (A). Elementami aij macierzy wypłat gracza nr 1 będą wartości funkcji H1(z1, z2) H1(z1, z2)= H1(z1, z2)+ H2(z1, z2) opisującej udział w zysku, przy czym z1=i, z2=j. Dla przykładu: 1 1 1" - H1(1,2) 1" d(1+ 2) - c(1) 3 10 a12 = = = = 0.33 1 1 1 2 H1(1,2)+ H2(1,2) 1" d(1+ 2) - c(1) + 2" d(1+ 2) - c(2) 1" - + 2" - 3 10 3 10 Macierz wypłat MA dla gracza A po niezbędnych wyliczeniach wygląda następująco: 2 1 1 0.5 0.33 ł łł (7.21) MA = śł 2ł0.33 0.5 ł ł Dla gracza B macierz wypłat jest następująca: MB=1-MA, gdzie 1 1 ł łł 1 = ł1 1śł . Otrzymaliśmy zatem grę ze stałą sumą wypłat2 równą 1. ł ł Okazuje się, że taką grę można rozpatrywać podobnie jak grę z zerową sumą wypłat korzystając z pewnego twierdzenia3. Zauważmy, że gra ta nie posiada rozwiązania w zbiorze strategii czystych ponieważ w macierzy MA nie istnieje taki element, który byłby najmniejszym w swoim wierszu i jednocześnie największym w swojej kolumnie, tzn. nie da się wyznaczyć takiej pary strategii (i*, j*), dla której zachodzi (7.8). W związku z tym, będziemy poszukiwali rozwiązania w zbiorze strategii mieszanych wyznaczając rozkład 2 Gra z zerową sumą wypłat jest szczególnym przypadkiem gry ze stałą sumą wypłat. 3 Każda niekooperacyjna gra ze stałą sumą wypłat jest równoważna (w sensie strategii) pewnej grze z zerową sumą wypłat. 12 Wybrane zagadnienia badań operacyjnych dr inż. Zbigniew Tarapata Wykład nr 6: Elementy teorii gier prawdopodobieństwa na strategiach czystych obu graczy ze wzorów (7.14), (7.15). Otrzymamy: " dla gracza A: a22 - a21 0.5 - 0.33 * x1 = = = 0.5 , a11 - a12 - a21 + a22 0.5 - 0.33 - 0.33 + 0.5 * * x2 =1- x1 = 0.5 " dla gracza B: a22 - a12 0.5 - 0.33 * y1 = = = 0.5 , a11 - a12 - a21 + a22 0.5 - 0.33 - 0.33 + 0.5 * * y2 =1- y1 = 0.5 Każdy z graczy powinien zatem stosować obie swoje strategie z częstościami 0.5, co zapewni im oczekiwaną wygraną (oczekiwany udział zysku) równą: 2 2 V = " ""a " xi* y* = 0.5"0.5"0.5 + 0.33"0.5"0.5 + 0.5"0.5"0.5 + 0.33"0.5"0.5 = 0.665 ij j i=1 j=1 g 13 Wybrane zagadnienia badań operacyjnych dr inż. Zbigniew Tarapata Wykład nr 6: Elementy teorii gier 6.3 ZADANIA TEORII GIER A ZADANIA PL Załóżmy, że mamy grę dwuosobową o sumie zero, przy czym pierwszy z graczy posiada M strategii, a drugi odpowiednio N. Mamy MA =[aij] macierze wypłat: dla gracza A - , dla gracza B - MxN x = (x1,x2,& , xM ), y = (y1, y2,& , yN ) MB = -MA oraz wektory oznaczające częstości stosowania poszczególnych strategii przez graczy. Zadanie wyznaczenia optymalnych wartości wektora x, dla gracza nr 1 można sformułować następująco: max v (7.22) przy ograniczeniach: a11 " x1 + a21 " x2 +& + aM 1 " xM e" v
a1N " x1 + a2N " x2 +& + aMN " xM e" v (7.23) x1 + x2 +& + xM =1 x1, x2,& , xM e" 0 Podobnie dla gracza nr 2: min v (7.24) a11 " y1 + a12 " y2 +& + a1N " yN d" v
aM 1 " y1 + aM 2 " y2 +& + aMN " yN d" v (7.25) y1 + y2 +& + yN =1 y1, y2,& , yN e" 0 14 Wybrane zagadnienia badań operacyjnych dr inż. Zbigniew Tarapata Wykład nr 6: Elementy teorii gier Jeżeli dokonamy podstawień: xi zi = , v (7.26) yj wj = v to pierwsze z tych zadań można zapisać następująco: M 1 min zi = " (7.27) v i=1 przy ograniczeniach: M "a " zi e"1, j =1, N ij i=1 (7.28) zi e" 0 , i =1, M Drugie zadanie po dokonaniu podstawień zapiszemy jak poniżej: N max "w = 1 j (7.29) v j =1 przy ograniczeniach: N "a " wj d"1, i =1, M ij j=1 (7.30) wj e" 0 , j =1, N 15