Transcript
A. Kasperski, M. Kulej BO - Analiza decyzji, drzewa decyzyjnie, elementy teorii gier1
1
Analiza decyzji - tablica decyzyjna, klasyfikacja problemów
W celu formalizacji i klasyfikacji problemów decyzyjnych wprowadzimy tzw tablicę decyzyjną. Niech decydent (lub grupa decydentów) ma osiągnąć pewien cel (np. zysk z uprawy swojego pola). Aby go osiągnąć podjmuje pewne działania, które nazywamy strategiami, alternatywami decyzyjnymi lub decyzjami. Zakładamy, że ilość tych działań jest m i działania te oznaczymy a1 , a2 , . . . , am . Podejmując dane działanie jego wynik zależy od zewnętrznych dla decydenta n czynników, które nazywamy stanami natury i oznaczamy przez θ1 , θ2 , . . . , θn . Pełny opis konsekwencji dla decydenta podjęcia działania ai w sytuacji, gdy wystąpi stan natury θj oznaczać będziemy przez Xij i zapisuje się w postaci następującej tablicy decyzyjnej : Alternatywy decyzyjne a1 a2 .. . am
Stany natury θ2 ... θ X12 . . . X1n X22 . . . X2n .. .. ... . . Xm1 Xm2 . . . Xmn θ1 X11 X21 .. .
Tab. 1: Ogólna postać tablicy decyzyjnej Przykład 1. Rozważmy osobę, która ma przygotować omlet z 6 jajek. Właśnie wbiła już do miski 5 jaj, które okazały się dobrymi i zastanawia się co zrobić z szóstym jajkiem, które może być albo dobre albo zepsute. Tablica 2 podaje możliwe sposoby działania i opis konsekwencji tych działań. Alternatywy decyzyjne zbić jajko do miski
Stan natury jajko zepsute nie ma omletu i 5 jajek zniszczonych zbić jajko do omlet z 6 jaj omlet z 5 jajek do innego naczynia i naczynie do umycia i naczynie do umycia wyrzucić jajko omlet z 6 jajek omlet z 5 jajek i jedno jajko zniszczone jajko dobre omlet z 6 jaj
Tab. 2: Pełny opis konsekwencji problemu decyzyjnego przygotowanie omletu W analizie decyzji stosuje się tablice decyzyjne w których zamiast pełnego opisu konsekwencji Xij używa się miary wartości konsekwencji v(Xij ) oznaczanej dalej przez vij dla i = 1, . . . , m; j = 1, . . . , n i nazywanej dalej użytecznością.
A. Kasperski, M. Kulej BO - Analiza decyzji, drzewa decyzyjnie, elementy teorii gier2 Miara ta powinna spełniać warunek, że vij > vkl , gdy dla decydenta bardziej sprzyjające są konsekwencje Xij niż konsekwencje Xkl (mówi się również, że decydent preferuje konsekwencje Xij w stosunku do konsekwencji Xkl ). Dlatego dalej będą używane tablice decyzyjne w których konsekwencje zostaną zastąpione użytecznością. Postać taką podano w tablicy 3. Alternatywy decyzyjne a1 a2 .. . am
Stany natury θ2 . . . θ v12 . . . v1n v22 . . . v2n .. .. ... . . vm1 vm2 . . . vmn θ1 v11 v21 .. .
Tab. 3: Postać ogólna tablicy decyzyjnej, w której konsekwencje zastąpiono użytecznością
1.1
Typy problemów decyzyjnych
Wyróżnia się trzy typy problemów decyzyjnych: Problemy decyzyjne w warunkach pewności. Występuje tylko jeden stan natury, którego wystąpienie jest pewne - tablica decyzyjna ma tylko jedną kolumnę. Problemy decyzyjne w warunkach ryzyka. Znane jest prawdopodobieństwo wystąpienia każdego stanu natury. Dla dyskretnych stanów natury θ1 , θ2 , . . . , θn prawdopodobieństwa ich wystąpienia oznaczamy przez P (θ1 ), P (θ2 ), . . . , P (θn ). Problemy decyzyjne w warunkach niepewności. Znane są sposoby postępowania decydenta i potrafimy zidentyfikować wszystkie możliwe stany natury ale nie wiemy nic o prawdziwym stanie natury. W zależności od typu problemu decyzyjnego stosowane są różne kryteria wyboru decyzji optymalnej (rozwiązania optymalnego).
1.2
Kryteria wyboru decyzji w warunkach pewności
W problemach w warunkach pewności decyzją optymalną jest alternatywa o najbardziej sprzyjającej dla decydenta wartości użyteczności (co sprowadza się do wyboru elementu maksymalnego lub minimalnego w tablicy decyzyjnej o jednej kolumnie).
A. Kasperski, M. Kulej BO - Analiza decyzji, drzewa decyzyjnie, elementy teorii gier3
1.3
Kryteria wyboru decyzji w problemach w warunkach ryzyka
W problemach w warunkach ryzyka racjonalne kryterium wyboru optymalnej decyzji polega na wyborze takiej alternatywy decyzyjnej ak , która maksymalizuje (lub minimalizuje, gdy użyteczność jest kosztem) wartość średnią użyteczności tj. n X
m
P (θj )vkj = max i=1
j=1
n X
P (θj )vij
j=1
Przykład 2. Sprzedawca truskawek kupuje na plantacji koszyczek truskawek za 3zł. a sprzedaje za 8zł. Sprzedany koszyk przynosi mu zatem 5zł. zysku a nie sprzedany stratę 3zł. Z doświadczenia wie, że dzienny popyt może wynosić 10, 11, 12 lub 13 koszyczków. Z 90 obserwacji, które zgromadził wie, że w 18 przypadkach dzienny popyt kształtował się na poziomie 10 , w 36 na poziomie 11, w 27 na poziomie 12 i w 9 na poziomie 13 koszyczków. Jeśli przez ai oznaczymy alternatywę zakup na plantacji 10 + (i − 1) koszyczków truskawek, przez θi - popyt dzienny na poziomie 10 + (i − 1) (i = 1, 2, 3, 4) koszyczków a użytecznością będzie dzienny zysk sprzedawcy, to tablicą decyzyjną jest tablica 4. W tej tablicy Zysk a1 a2 a3 a4 Rozkład
θ1 50 47 44 41 0.2
θ2 50 55 52 49 0.4
θ3 50 55 60 57 0.3
θ4 50 55 60 65 0.1
EV (ai ) 50 53.4 53.6 51.4
Tab. 4: Tablica decyzyjna sprzedawcy truskawek EV (ai ) oznacza wartość średnią użyteczności alternatywy ai . Decyzją optymalną jest wybór alternatywy a3 , która daje maksymalny oczekiwany zysk wynoszący EV (a3 ) = 53.6. Dla problemów decyzyjnych o dużej liczbie alternatyw i stanów natury wypisywanie całej tablicy decyzyjnej możne być uciążliwe. Można podać metodę rekurencyjną wyznaczania wartości średniej użyteczności dla kolejnych alternatyw. Opiszemy jej idę i pokażemy jej zastosowanie dla rozpatrywanego przykładu. Niech X będzie dyskretną zmienną losową rozkładu stanów natury (tj. wielkości popytu na truskawki w problemie sprzedawcy truskawek) przyjmującą wartości q, q + 1, . . . , Q o rozkładzie P (x) dla x = q, q + 1, . . . , Q i dystrybuancie F (x) = P (X ≤ x). Wartość średnia użyteczności alternatywy ai , jest wartością średnią funkcji zmiennej losowej X. Oznaczmy przez d(z), z = q, q + 1, . . . , Q wartość średnią zysku sprzedawcy, gdy zakupił na plantacji z koszyczków truskawek(tj. EV (ai ) = d(z), gdzie z = 10+i−1, i = 1, 2, 3, 4 ). Oznaczmy przez a zysk
A. Kasperski, M. Kulej BO - Analiza decyzji, drzewa decyzyjnie, elementy teorii gier4 jaki osiąga sprzedawca z jednego sprzedanego koszyczka a przez b stratę na jednym nie sprzedanym koszyczku (dla rozpatrywanego przykładu a = 5, b = 3). Załóżmy, że sprzedawca zakupił z −1 koszyczków (jego średni zysk wynosi d(z −1)). Dokupienie dodatkowo jednego koszyczka truskawek przyniesie stratę b jeśli popyt x będzie x ≤ z − 1. Prawdopodobieństwo tego zdarzenia wynosi P (X ≤ z − 1). Natomiast przyniesie zysk a jeśli popyt x będzie x > z − 1. To zdarzenie ma prawdopodobieństwo 1 − F (z − 1). Mamy zatem rekurencyjny wzór: d(z) = d(z − 1) + a[1 − F (z − 1)] − bF (z − 1) = d(z − 1) + a − (a + b)F (z − 1) (z = q + 1, q + 2, . . . , Q.) Dla z = q mamy d(q) = aq. Dla sprzedawcy truskawek mamy: EV (a1 ) = d(z = 10) = 5 ∗ 10 = 50 EV (a2 ) = d(11) = d(10) + 5 − (5 + 3)F (10) = 50 + 5 − 8
2 = 53.4 10
6 = 53.6 10 9 EV (a4 ) − d(13) = d(12) + 5 − 8F (12) = 58.6 − 8 = 51.4 10
EV (a3 ) = d(12) = d(11) + 5 − 8F (11) = 58.4 − 8
Optymalną strategię można również wyznaczyć wzorem analitycznym. Jeśli strategią optymalną jest wybór alternatywy polegającej na zakupie k ∗ koszyczków, to z własności maksimum lokalnego mamy, że d(k ∗ ) ≥ d(k ∗ − 1) ⇒ F (k ∗ − 1) ≤ d(k ∗ ) ≥ d(k ∗ + 1) ⇒
a a+b
a ≤ F (k ∗ ) a+b
Stąd mamy
a ≤ F (k ∗ ) a+b Wartość k ∗ spełniająca tę nierówność jest optymalną decyzją. Ten ostatni sposób wyznaczania alternatywy optymalnej jest najoszczędniejszy. Dla sprzedawcy truskawek mamy F (k ∗ − 1) ≤
5 a = = 0.425 i 0.4 = F (11) ≤ 0.425 ≤ F (12) = 0.9, a+b 3+5 czyli optymalną alternatywą jest zakup 12 koszyczków (k ∗ = 12). W problmach w warunkach ryzyka wprowadza się pojęcie oczekiwanej wartości pewnej informacji (EVPI). Sposób jej obliczania podamy na przykładzie problemu sprzedawcy truskawek. Załóżmy, że sprzedawca może z całą pewnością przewidzieć zajście danego stanu natury (ma pewną prognozę odnośnie stanów
A. Kasperski, M. Kulej BO - Analiza decyzji, drzewa decyzyjnie, elementy teorii gier5 natury). Wtedy powinien wybierać alterntywę a1 dla stanu θ1 , a2 dla θ2 , a3 dla θ3 i a4 dla θ4 . Ponieważ zna rozkład prawdopodobieństwa stanów natury, to wartość oczekiwana użyteczności wyniesie wtedy: 50 ∗ 0.2 + 55 ∗ 0.4 + 60 ∗ 0.3 + 65 ∗ 0.1 = 56, 5. Bez znajomości tej prognozy wartość oczekiwana zysku wynosi 53,6. Różnica 56.5-53.6=2.9 definiuje oczekiwaną wartość pewnej informacji, czyli EVPI=2.9. Wartość tę możemy interpretować jako maksymalną kwotę, którą można wydać za pewną prognozę.
1.4
Kryteria wyboru decyzji w warunkach niepewności
Dana jest tablica decyzyjna dla problemu z funkcją użyteczności vij (funkcją tą może być zysk lub koszt). Kryterium Walda - wybór alternatywy dla której najmniej sprzyjający rezultat jest dla decydenta najkorzystniejszy (maksymalizacja minimalnego zysku, gdy użyteczność vij jest zyskiem). Dla każdej alternatywy ai , i = 1, . . . , m wyznacza się dwie wielkości: najbardziej sprzyjający dla decydenta rezultat oi oraz najmniej sprzyjający rezultat si . Jeśli użyteczność vij jest zyskiem , to oi = max{vij } oraz si = min{vij } j
j
natomiast, gdy użyteczność vij jest kosztem, to oi = min{vij } oraz si = max{vij }. j
j
Decyzją optymalną jest alternatywa ak taka, że sk = max si = max min{vij } jeśli vij jest np. zyskiem i
i
j
lub sk = min si = min max{vij } jeśli vij jest np. kosztem i
i
j
Kryterium to jest najbardziej konserwatywne - decydent wybiera alternatywę, w której najgorszy (najmniej sprzyjający) rezultat będzie dla niego najkorzystniejszy spośród wszystkich alternatyw. Nie wszyscy decydenci wykazują taką postawę względem ryzyka. Niektórzy decydenci mogą preferować alternatywy dla których najbardziej sprzyjający rezultat jest najkorzystniejszy tj, wybierać alternatywę ak dla której ok = max oi = max max{vij } i
i
j
A. Kasperski, M. Kulej BO - Analiza decyzji, drzewa decyzyjnie, elementy teorii gier6 Większość decydentów wykazuje mniej skrajne postawy. Kryterium następne (Hurwicza) zakłada, że postawę decydenta wykazywaną we wszystkich problemach można scharakteryzować przez pewien współczynnik (nazywany współczynnikiem ostrożności). Kryterium Hurwicza - wybór alternatywy o najkorzystniejszej dla decydenta średniej ważonej z najmniej i najbardziej sprzyjającego rezultatu (maksymalizacja - gdy vij jest zyskiem - średniej ważonej z najmniej i najbardziej sprzyjającego rezultatu). Jeśli vij jest zyskiem, to decyzją optymalną jest alternatywa ak taka, że αsk +(1−α)ok = max{αsi +(1−α)oi } = max{α min{vij }+(1−α) max{vij }}, i
i
j
j
gdzie α jest współczynnikiem charakteryzującym decydenta. Dla α = 1 kryterium jest identyczne z kryterium Walda, czyli jest najbardziej zachowawczym, dla α = 0 mamy najbardziej optymistyczne kryterium. Wartości α z przedziału (0,1) pozwalają na modelowanie postaw pośrednich. Jeśli vij jest kosztem, to decyzją optymalną jest alterntywa ak taka, że αsk +(1−α)ok = min{αsi +(1−α)oi } = min{α max{vij }+(1−α) min{vij }}. i
i
j
j
Kryterium Savage’a - minimalizacja maksymalnego ”żalu”. Na podstawie tablicy decyzyjnej [vij ] konstruuje się nową tablicę [rij ] następująco: rij =
maxm l=1 {vij } − vij vij − minm l=1 {vij }
jeśli vij jest zyskiem, jeśli vij jest kosztem.
Element rij tej tablicy jest różnicą pomiędzy użytecznością najlepszej decyzji jaką należałoby podjąć przy wystąpieniu stanu θj a podjętą decyzją (dla vij zysku) i może być interpretowany jako ”‘żal”’ z niepodjęcia najlepszej decyzji. W tablicy rij do wyboru decyzji optymalnej stosuje się kryterium Walda (dla kosztów). Decyzją optymalną jest ak takie, że sk = min{si } = min{max{rij }}. i
i
j
Kryterium Laplace’a(1825) - maksymalizacja (lub minimalizacja, gdy użyteczność jest kosztem) wartości średniej. Optymalną decyzją jest wybór takiej alternatywy ak , że n n X X 1 1 m vkj = max{ vij }. i=1 n n j=1 j=1
A. Kasperski, M. Kulej BO - Analiza decyzji, drzewa decyzyjnie, elementy teorii gier7 Przykład 3. Ośrodek wczasowy przygotowuje zapasy żywności na nadchodzący weekend. Możliwe stany natury θ1 , θ2 , θ3 , θ4 odpowiadają odpowiednio przyjazdowi 100, 150, 200 i 250 turystów. Alternatywy decyzyjnyme a1 , a2 , a3 , a4 to przygotowanie (zakup) zapasów dla odpowiednio 100, 150, 200 i 250 turystów. Użyteczność vij będąca kosztem związanym z podjęciem alternatywy ai i wystąpieniem stanu θj podana jest w tablicy 5. Optymalną decyzją stosując kryterium Walda jest wybór vij a1 a2 a3 a4
θ1 θ2 θ3 θ4 5 10 18 25 8 7 8 23 21 18 12 21 30 22 19 15
si oi 25 5 23 7 21 12 30 15
Tab. 5: Tablica decyzyjna dla ośrodka wczasowego alternatywy a3 , dla kryterium Hurwicza, gdy współczynnik α = 0.5 alternatywą optymalną jest a4 . Dla kryterium Savage’a musimy najpierw wyznaczyć tablicę rij , którą podano w tablicy 6. Decyzją optymalną jest w tym przypadku wybór rij a1 a2 a3 a4
θ1 0 3 16 25
θ2 θ3 θ4 3 10 10 0 0 8 8 4 6 12 11 0
si 10 8 16 25
Tab. 6: Tablica wartości [rij ] dla ośrodka wczasowego alternatywy a2 .
2
Drzewa decyzyjne
Do analizy problemów decyzyjnych szczególnie w sytuacjach, gdy mamy do czynienia z decyzjami wieloetapowymi szczególnie stosuje się tzw. drzewa decyzyjne. Ich definicję i zastosowanie podamy na przykładzie. Przykład 4. T.B. Inwestor Puckett nabył firmę produkującą materiały tekstylne. Teraz zastanawia się nad przyszłością tej firmy. Rozważa trzy warianty decyzji: 1. Rozbudować fabrykę i produkować lekkie, trwałe materiały, przeznaczone na rynek wojskowy, na którym nie ma dużej zagranicznej konkurencji. 2. Utrzymać ststus quo, nadal produkując materiały tekstylne, w której to branży istnieje ostra zagraniczna konkurencja. 3. Natychmiast sprzedać fabrykę.
A. Kasperski, M. Kulej BO - Analiza decyzji, drzewa decyzyjnie, elementy teorii gier8 Stany natury Dobre warunki na Złe warunki na Decyzja rynku zagranicznym rynku zagranicznym Rozbudować 800000zł. 500000zł. Utrzymać stan obecny 1300000zł. -150000zł. Sprzedać natychmiast 320000zł. 320000zł. Tab. 7: Tablica decyzyja firmy Puckett W przypadku wyboru jednego z pierwszych dwóch wariantów decyzji fabryka zostanie sprzedana po roku. Zysk ze sprzedaży fabryki po roku zależy od warunków na rynku zagranicznym i od losów ustawy o embargu handlowym. Sytuacja decyzyjna jest przedstawiona w tabeli decyzyjnej 7. Rozważany problem możemy zapisać w postaci drzewa decyzyjnego(Rys. 2), w którym wyróżniamy węzły: decyzyjne (oznaczone kwadratem), losowe (oznaczone większymi kółkami) oraz końcowe(oznaczone małymi kólłkami). Z węzła decyzyjnego 1 wychodzą 3 krawędzie do węzłów losowych 2, 3 i 4. Krawędzie te oznaczają alternatywy decyzyjne. Z każdego węzła losowego wychodzą dwie krawędzie odpowiadające możliwym stanom natury tj . dobrym z prawdopodobieństem 0.7 i złym z prawdopodobieństwem 0,3 warunkom na rynkach zagranicznych. Węzły końcowe mają przypisane wartości zysku odpowiadającego sytuacji, gdy decydent podejmie jakąś decyzję i zajdzie określany stan natury. Liczby przy węzłach losowych są wartościami oczekiwanymi zysku przy wyborze przez decydenta odpowiedniej decyzji. Z drzewa decyzyjnego możemy odczytać, że decyzją optymalna dla pana Packetta jest wybór alternatywy ”zachować stan obecny”, która daje mu oczekiwany zysk wynoszacy 865000zł.
Rozważymy teraz sytuację, gdy w problemie decyzyjnym oprócz danych prawdopodobieństw stanów, które nazywa się prawdopodobieństwami a priori dysponujemy dodatkowymi informacjami tzw. prawdopodobieństwami a posteriori. W rozważanym poprzednio problemie załóżmy, że pan Packett wynajął firmę kosultingową do opracowania raportu o politycznej i rynkowej sytuacji w przyszłości. Raport będzie albo pozytywny (P) albo negatywny (N), wskazując na dobre (g) albo złe (p) przyszłe warunki na rynku zagranicznym. Warunkowe prawdopodobieństwa uzyskania każdej z ocen stanu rynku przy danych stanach natury są następujące: P r(P/g) = 0.7 P r(N/g) = 0.3; P r(P/p) = 0.2, P r(N/p) = 0.8. Te prawdopodobieństwa warunkowe pozwalają wyznaczyć (korzystając ze wzoru
A. Kasperski, M. Kulej BO - Analiza decyzji, drzewa decyzyjnie, elementy teorii gier9 Dobre warunki(0.7) 800000zł.
710000zł. 2
Złe warunki(0.3)
500000zł.
Rozbudować Dobre warunki(0.7) 1
1700000zł.
Status quo 3
865000zł.
-150000zł. Złe warunki(0.3)
Sprzedać Dobre warunki(0.7) 320000zł. 4
320000zł.
320000zł. Złe warunki(0.3)
Rys. 1: Drzewo decyzyjne Puckett Bayes’a) prawdopodobieństwa a posteriori. P r(g/P ) = = = P r(p/P ) = P r(g/N ) = = = P r(p/N ) =
P r(P/g)P r(g) P r(P/g)P r(g) + P r(P/p)P r(p) (0.7)(0.7) (0.7)(0.7) + (0.2)(0.3) 0.891 0.109 P r(N/g)P r(g) P r(N/g)P r(g) + P r(N/p)P r(p) (0.3)(0.7) (0.3)(0.7) + (0.8)(0.3) 0.467 0.533.
(1) (2) (3) (4) (5) (6) (7) (8)
Znajomość tych prawdopodobieństw pozwala na skonstruowanie drzewa decyzyjnego z prawdopodobieństwami a posteriori i przeprowadzenie analizy w celu
A. Kasperski, M. Kulej BO - Analiza decyzji, drzewa decyzyjnie, elementy teorii gier10 wyznaczenia strategii optymalnej. Nowe drzewo decyzyjne ma węzeł początkowy (jest to węzeł losowy) 1, z którego wychodzą dwie krawędzie odpowiadającę dwóm możliwym stanom natury (raport pozytywny lub negatywny). Następnie mamy dwa węzły decyzyjne 2 i 3 z których wychodzą po trzy krawędzie odpowiadające decyzjom, jakie decydent może podjąc. Krawędzie te prowadzą do węzłów losowych 4,5,6,7,8 i 9, z każego z nich wychodzą po dwie krawędzie (odpowiadające dwóm stanom natury) do węzłów końcowych. Drzewo decyzyjne wraz wartościami oczekiwanych wypłat(zysku) dla węzłów podaje rys. 2. 767300
0.891
Pr(g/P)=
4 Pr(p/P)=0.109
wa
do ozbu
500000
R
1141850 2
Status quo
Pr(g/P)=
0.891
1300000
Pr(p/P)=0.109
−150000
Pr(g/P)=0.891
320000
5
1141950 Pozytywny
Sprzedaz 6
Pr(P)=0.55
320000 1
800000
Pr(p/P)=0.109
320000
916117.5 Pr(N)=0.45
wa
do zbu
Negatywny
7
0.46
/N)=
640000
Pr(g
7 Pr(p/N)=0.533
Ro
0.467
527150 640100
3
Pr(g/N)= 8
Status quo
Pr(p/N)=0.533 0.467
Pr(g/N)=
Sprzedaz
800000
500000 1300000 −150000 320000
9
320000zł.
Pr(p/N)=0.533
320000
Rys. 2: Drzewo decyzyjne z prawdopodobieństwami a posteriori
Z analizy dzrzewa możemy odczytać strategię optymalną. Jeśli raport będzie pozytywny, to decydent powinien wybrać alternetywę ”‘Statu quo”’, która przyniesie mu największy oczekiwany zysk 1141950zł. Natomiast w przypadku otrzymania rapotru negatywnego powinien wybrać alternatywę ”‘Rozbudować”’, dla której oczekiwany zysk wynosi 640100zł. Takie postępowanie jest optymalne, decydent w ten sposób zapewnia sobie oczekiwany zysk wynoszący 916117.5zł. Bez dodatkowej informacji (znajomości prawdopodobieństw a posteriori ) jego oczekiwany zysk wynosi tylko 865000zł.
A. Kasperski, M. Kulej BO - Analiza decyzji, drzewa decyzyjnie, elementy teorii gier11
3
Gry dwuosobowe o sumie zerowej
W poprzednio rozpatrywanych sytuacjach decyzyjnych na efekty działań decydenta miały wpływ stany natury. Obecnie zajmiemy się sytuacjami, gdy na działania decydenta ma wpływ nie natura, którą możemy traktować jako pasywnego oponenta lecz inny racjonalnie działający decydent. W teorii gier obu decydentów nazywamy graczami. Zajmować się będziemy tylko grami dwuosobowymi o sumie zerowej. W takich grach podejmowane przez obu graczy decyzje nazywane sa strategiami. Efekt (użyteczność) podjęcia strategii i przez jednego gracza, gdy drugi gracz wybrał strategię j nazywa się wypłatą i oznaczamy przez [wij ], i = 1, . . . , m; j = 1, . . . , n. W grach o sumie zero wypłata (wygrana) dla jednego gracza jest równa przegranej drugiego. Przykład 5. Mamy dwóch graczy: gracza 1 i gracza 2. Każdy z nich dysponuje trzema strategiami 1,2 i 3. Macierz wypłat podaje tabela 8
Strategie 1 Gracz 1 2 3
Macierz wypłat Gracz 2 1 2 3 1 2 4 1 0 5 0 1 -1
Tab. 8: Macierz wypłat gry 1 Macierz wypłat tej gry jest dość specyficzna i rozwiązanie otrzymamy wykorzystując koncepcję strategii zdominowanych. Mówimy, że strategia i jest zdominowana przez strategię k jeśli strategia k jest co najmniej tak dobra jak i(a czasami lepsza), bez względu na to, co zrobi oponent (drugi gracz). Formalnie strategię i będziemy nazywać strategią zdominowaną przez strategię k, jeśli ∀j=1,...,n wij ≤ wkj oraz ∃l wil < wkl . Natomiast k nazywamy strategią dominującą, jeśli: ∀j=1,...,n wkj = max{wij }. i
Strategie, które nie są zdominowane przez inne strategie nazywamy strategiami niezdominowanymi. Racjonalnie działający decydent będzie dokonywał wyboru spośród strategii niezdominowanych. Strategia 3 jest dla gracza 1 zdominowaną przez strategię 1, gdyż bez względu na to jaką strategię wybierze gracz 2 wypłata gracza 1 jest przy wyborze strategii 3 nie niższa niż wypłata przy wyborze strategii 1. Zatem wiersz trzeci odpowiadający strategii zdominowanej możemy skreślić z macierzy wypłat. Zredukowana macierz wypłat jest podana w tablicy 9.
A. Kasperski, M. Kulej BO - Analiza decyzji, drzewa decyzyjnie, elementy teorii gier12 1 1 1 2 1
2 2 0
3 4 5
Tab. 9: Zredukowana macierz gry11 1 2 1 1 2 2 1 0 Tab. 10: Zredukowana macierz gry12 Ponieważ zakładamy racjonalność obu graczy, to gracz 2 też ma strategię zdominowaną 3. Jest ona zdominowana zarówno przez strategię 1 jak i przez strategię 2. Eliminujemy strategię 3 gracza 2 co daje macierz wypłat 10: Teraz strategia 2 dla gracza 1 jest zdominowana przez strategię 1. Eliminując zdominowaną strategię mamy macierz wypłat podaną w tablicy 11: Strategia 2 dla gracza 2 jet 1 2 1 1 2 Tab. 11: Zredukowana macierz gry13 zdominowana przez strategię 1 zatem powinna być wyeliminowana. Ostatecznie obaj gracze powinni wybierać strategie 1. Gracz 1 otrzyma wtedy wypłatę 1, ta wartość jest przegraną gracza 2. Jest to wartość gry. Jeśli wartość gry jest 0, to nazywa się grą sprawiedliwą (rozważana gra nie jest grą sprawiedliwą, gdyż jej wartość wynosi 1). Koncepcja zdominowanych strategii pozwala na redukcję wymiaru macierzy wypłat i w niektórych przypadkach pozwala wyznaczyć rozwiązanie gry. Jednak w większości przypadków potrzebujemy innego podejścia, które zaprezentjemy na dwu kolejnych przykładach. Przykład 6. Rozpatrzymy teraz grę o macierzy wypłat podanej w tablicy 12 W tej grze gracz 1 stosując strategię 1 może wygrać 6 ale może również przegrać 3(wypłata -3). Stosując strategię 3 może wygrać 5 ale może przegrać 4. Natomiast w strategii 2 jego wygrana bez względu na to co zrobi gracz 2 będzie co najmniej 0. Analizując strategie dla gracza 2 mamy, że w strategiach 1 i 3 jego maksymalna przegrana wynosi odpowiednio 5 i 6. natomiast w strategii 2 tylko zero. Obaj gracze powinni zatem wybrać strategię 2, gdyż każdemu z nich zapewnia ona w najgorszym przypadku najlepszy wynik. Jest to tzw. kryterium minimaksowe standardowo proponowane w teorii gier do wyboru strategii optymalnej. Według tego kryterium gracz 1 powinien wybrać strategię ,dla której minimalna wypłata jest największa (tj. maxi minj {wij }) a gracz 2 strategię dla której maksymalna wypłata gracza 1 jest jest najmniejsza (tj. mini maxj {wij }). W analizowanym przykładzie strategią max min jest strategia 2 gracza 1 a strategią
A. Kasperski, M. Kulej BO - Analiza decyzji, drzewa decyzyjnie, elementy teorii gier13
Strategie 1 Gracz 1 2 3 Maximum
Macierz wypłat Gracz 2 1 2 3 -3 -2 6 2 0 2 5 -2 -4 5 0 6 ↑ min
Minimum -3 0← max -4
Tab. 12: Macierz wypłat gry 2
Strategie 1 Gracz 1 2 3 Maximum
Macierz wypłat Gracz 2 1 2 3 0 -2 2 5 4 -3 2 3 -4 5 4 2 ↑ min
Minimum -2← max -3 -4
Tab. 13: Gra 3 - nie ma punktu siodłowego min max jest strategia 2 dla gracza 2.Wartość gry jest równa 0, czyli jest to gra sprawiedliwa. W tej grze ten sam element macierzy wypłat(w22 = 0) jest jednocześnie wartością max min i wartością min max, czyli mamy element, który jest najmniejszy w wierzsu i jednocześnie największy w kolumnie. Taki punkt, jesli istnieje, nazywa się punktem siodłowym. Jesli gra ma punkt siodłowy, to obaj gracza powinni do wyboru strategii optymalnej stosować odpowiednio max min i min max strategie. Jednak nie każda gra posiada punkt siodłowy - taką jest np. gra 3. W rozważanej poprzednio grze wartości maxi minj wij = −2 6= 2 = mini maxj wij nie są równe co oznacza, że gra nie posiada punktu siodłowego. W tej grze informacja o tym jaką strategię wybierze jeden z graczy pozwala drugiemu poprawić swoją pozycję. Koncepcja rozwiazania optymalnego w tego typu grach oparta jest na pojęciu strategii miesznych, które charakteryzują się tym, że żaden z graczy nie może wydedukować jaką strategię użyje oponent.
A. Kasperski, M. Kulej BO - Analiza decyzji, drzewa decyzyjnie, elementy teorii gier14
3.1
Strategie mieszane dla gry bez punktu siodłowego
Dla gier nie posiadających punktu siodłowego dla każdego z graczy wyznacza się rozkłady prawdopodobieństwa na zbiorach ich strategii. Niech: xi = prawdopodobieństwo, że gracz 1 użyje strategii i (i = 1, . . . , m), yj = prawdopodobieństwo, że gracz 2 użyje strategii j (j = 1, . . . , n), P Pn gdzie m i=1 xi = 1, j=1 yj = 1. Wartości xi , i = 1, . . . , m oraz yj , j = 1 . . . , n nazywamy strategiami mieszanymi natomiast oryginalne strategie strategiami czystymi. W trakcie gry każdy z graczy wybiera strategię czystą jednak powinien wybierać ją w pewien losowy sposób zgodny z rozkładem (x1 , x2 , . . . , xm ) dla gracza 1 i rozkładem (y1 , y2 , . . . , yn ) dla gracza 2. Np. jesli (x1 , x2 , x3 ) = ( 12 , 12 , 0) a (y1 , y2 , y3 ) = (0, 12 , 21 ), to gracz 1 nie powinien wybierać strategii czystej 3 a wybór strategii 2 lub 3 rozstrzygnąć rzucając monetą. Analogicznie gracz 2 nie powinien wybierać czystej strategii 1 a wybór pomiędzy strategiami 2 i 3 rozstrzygnąć rzucając monetą. Przy stosowaniu strategii mieszanych przez każdego z graczy oczekiwaną wygraną gracza 1 jest Oczekiwana wypłata gracza 1 =
m X n X
wij xi yj ,
i=1 j=1
gdzie wij jest wypłatą jeśli gracz 1 używa czystej strategii i a gracz 2 używa czystej strategii j. W rozpatrywanej poprzednio grze 3 jeśli gracze 1 i 2 stosują odpowiednio strategie mieszane (x1 , x2 , x3 ) = ( 12 , 21 , 0) i (y1 , y2 , y3 ) = (0, 21 , 21 ) to oczekiwana wypłata gracza 1 wynosi 14 (−2 + 2 + 4 − 3) = 41 . Minimaksowe (min max) ktyterium dla strategii mieszanych mówi, że gracz powinien wybierać strategię mieszaną, która minimalizuje jego maksymalne oczekiwane straty. Równoważnie, jeśli rozważamy wygraną gracza 1 (a nie przegraną gracza 2 co jest równoważne) to kryterium to jest maksyminowe (max min), tj. maksymalizuje się minimalną oczekiwaną wypłatę gracza 1. Przez minimalną oczekiwaną wypłatę rozumie się najmniejszą możliwą wypłatę, którę można uzyskać przy dowolnej strategii miesznej, podjętej przez oponenta. Zatem mieszna strategia dla gracza 1 jest optymalną, jeśli minimalna oczekiwana wypłata jest maksymalna. Wartość tą oznaczamy przez w. Dla gracza 2 podobnie optymalną strategią mieszaną jest strategia, która minimalizuje maksymalną oczekiwaną wartość przegranej. Wartość tę oznacza się przez w. Dla gier nie posiadających punktu siodłowego jeśli tylko rozpatruje się czyste strategie, to nie ma rozwiązania stabilnego. Zachodzi wtedy nierówność w < w i gracze mogą zmieniać strategie, aby poprawić swoją pozycję. Dla strategii mieszanych koniecznym warunkiem, aby rozwiązanie optymalne było stabilne jest równość w = w. W grach o sumie zerowej ten warunek jest zawsze spełniony. Twierdzenie 1. Para strategii miesznych dla graczy jest optymalną dając stabilne rozwiązanie przy kryterium minimaksowym, (min max), gdy w = w = w.
A. Kasperski, M. Kulej BO - Analiza decyzji, drzewa decyzyjnie, elementy teorii gier15 Stosując te strategie żaden z graczy nie może poprawić swojej pozycji zmieniając jednostronnie swoją strategię.
3.2
Zastosowanie programowania liniowego do wyznaczenia rozwiazania gry
Rozwiązanie dowolnej gry w strategiach miesznych można wyznaczyć rozwiazując pewne zagadnienie programowania liniowego. Rozważymy najpierw jak wyznaczyć optymalną strategię mieszaną gracza 1. Oczekiwana wypłata gracza 1 =
m X n X
wij xi yj ,
i=1 j=1
i strategia (x1 , x1 , . . . , xm ) jest optymalną jeśli m X n X
wij xi yj ≥ w = w
i=1 j=1
dla każdej strategii (y1 , y2 , . . . , yn ) gracza 2. Ta nierówność musi również zachodzić dla czystych strategii tj. (y1 , y2 , . . . , yn ) takich, że jedna współrzędna yj = 1 a reszta jest zerami. Zatem mamy: m X
wij xi ≥ w dla j = 1, . . . , n.
i=1
Co więcej ten zbiór nierówności implikuje wyjściową nierówność: n X j=1
m n X X yj ( wij xi ) ≥ yj w = w, i=1
i=1
P ponieważ nj=1 yj = 1. Spełnienie tych n nierówności jest równoważne spełnieniu wyjściowej nierówności dla każdej strategii y1 , y2 , . . . , yn . Wyznaczenie optymalnej strategii może być zatem sprowadzone do rozwiązania następującego zagadnienia programowania liniowego: xm+1 → max w11 x1 + w21 x2 + · · · , +wm1 xm − xm+1 ≥ 0 w12 x1 + w22 x2 + · · · , +wm2 xm − xm+1 ≥ 0 ··· ··· ··· w1n x1 + w2n x2 + · · · , +wmn xm − xm+1 ≥ 0 x1 + x2 + · · · + xm = 1 xi ≥ 0, dla i = 1, 2, . . . , m.
A. Kasperski, M. Kulej BO - Analiza decyzji, drzewa decyzyjnie, elementy teorii gier16 Zmienna xm+1 zastępuje nieznaną wartość w i w rozwiązaniu optymalnym będzie jej równa. Jednak na tę zmienną nie jest nałożony warunek nieujemności. Analogiczne rozumowanie prowadzi do następującego modelu wyznaczania optymalnej strategii gracza2: yn+1 → max w11 y1 + w12 y2 + · · · , +w1n yn − yn+1 ≤ 0 w21 y1 + w22 y2 + · · · , +w2n yn − yn+1 ≤ 0 ··· ··· ··· wm1 y1 + wm2 y2 + · · · , +wmn yn − yn+1 ≤ 0 y1 + y2 + · · · + yn = 1 yi ≥ 0, dla i = 1, 2, . . . , n. Problem wyznaczenia optymalnej strategii mieszanej dla gracza 1 jest dualnym do problemu wyznaczania strategii opotymalnej gracza 2. Z twierdzeń o dualności ∗ wiemy, że dla optymalnych rozwiązań x∗m+1 oraz yn+1 tych zagadnień mamy, że ∗ ∗ −x∗m+1 = −yn+1 czyli x∗m+1 = yn+1 . ∗ = w skąd otrzymujemy równość Z okreslenia w i w mamy, że w = x∗m+1 oraz yn+1 w = w. Pozostaje jeszcze jeden element do rozpatrzenia. W podanych modelach li∗ niowych zmienne x∗m+1 , yn+1 nie są nieujemne. Jeśli jest oczywiste, że w ≥ 0, to można stosować sympleks. Jeśli tak nie jest należy zastosować jedną z następujących modyfikacji:
• zamienić zmienną dowolną różnicą dwu zmiennych nieujemnych, • zamienić rolami graczy tak, aby wypłata gracza 1 była nieujemna, • dodać do macierzy wypłat pewną stałą (równą np. maksymalnej wartości modułów ujemnych wartości macierzy wypłat), tak aby wartość gry w była nieujemną - dodanie stałej nie może zmienić optymalnych strategii, a po rozwiązaniu gry modyfikujemy jej wartość o tę wielkość. Ostatni sposób jast najczęściej stosowany. Zastosujmy teraz programowanie liniowe do wyznaczenia optymalnych strategii mieszanych dla gry 3. Przyjmiemy, że wartość gry jest nieujemna tj. w ≥ 0 (okaże się że tak rzeczywiście jest) czyli nie będziemy stosować modyfikacji macierzy wypłat. Przykład 7. W tej grze strategia 3 dla gracza 1 jest zdominowaną zatem powinna być wyeliminowana. Macierz wypłat po usunieciu strategii 3 gracza 1 jest podana w tablicy 14 Modele liniowe dla gracza 1 i gracza 2 są następujące:
A. Kasperski, M. Kulej BO - Analiza decyzji, drzewa decyzyjnie, elementy teorii gier17 Macierz wypłat Gracz 2 Strategie 1 2 3 1 0 -2 2 Gracz 1 2 5 4 -3 Tab. 14: Gra 3 po wyeliminowaniu zdominowanej strategii 3. x3 5x2 − x3 −2x1 + 4x2 − x3 2x1 − 3x2 − x3 x1 + x2 x1 , x2
→ ≥ ≥ ≥ = ≥
max 0 0 0 1 0.
y4 −2y2 + 2y3 − y4 5y1 + 4y2 − 3y3 − y4 y1 + y2 + y3 y1 , y2 , y3
→ ≤ ≤ = ≥
min 0 0 1 0.
Rozwiązując te modele otrzymujemy dla bgracza 1 optymalne strategie mieszane 7 4 2 x∗1 = 11 , x∗2 = 11 i wartość gry w = x∗3 = 11 . Dla gracza 2 mamy y1∗ = 0, y2∗ = 5 6 2 , y3∗ = 11 oraz w = y4∗ = 11 . To rozwiązanie można otrzymać z rozwiązania 11 modelu dla gracza 1 dlatego wystarcza rozwiązać tylko jeden z tych modeli, aby otrzymać strategie optymalne dla obu graczy. Rozwiązania zostały otrzymane przy założeniu,że w ≥ 0. Jeśli nie jest spełnione to założenie, to model może nie mieć rozwiązania dopuszczalnego. Aby tego uniknąć dodajemy do macierzy wypłat stałą 3 i odpowiednio modyfikujemy ograniczaenia. Po rozwiązaniu tylko wartość gry zmnieszamy o 3.
