wzbo wyklad nr 6


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


Wyszukiwarka