Transcript
D. Miszczyńska, M.Miszczyński KBO UŁ
1
GRY KONFLIKTOWE GRY 2-OSOBOWE O SUMIE WYPŁAT ZERO Gra w sensie niżej przedstawionym to zasady którymi kierują się decydenci. Zakładamy, że rezultatem gry jest wypłata, którą zgodnie z regułami gry przegrany płaci wygranemu. Przy czym rozważamy tylko gry w których bierze udział dwóch graczy i przegrana jednego jest wygraną drugiego. Ponadto dysponujemy tzw macierzą wypłat, która pozwala nam na określenie gry. I. DEFINICJE i TWIERDZENIA
Konfliktowe gry dwuosobowe opisuje macierz wypłat
[(
A mxn = aij ,bij gdzie:
aij bij
)]
- wygrana gracza I - wygrana gracza II
Jeżeli suma wypłat jest równa zero, tj. aij + bij = 0 to grę nazywamy dwuosobową grą macierzową o sumie wypłat zero. Macierz wypłat takiej gry jest więc następująca
[(
A mxn = aij ,− aij
)]
W tej sytuacji macierz wypłat może opisywać tylko wygrane jednego z graczy. Przyjęto iż będzie to gracz I; zatem wygrane gracza II będą automatycznie liczbami przeciwnymi do wygranych gracza I.
D. Miszczyńska, M.Miszczyński KBO UŁ
2
Def. Macierz wypłat gry dwuosobowej o sumie wypłat zero ma postać
[ ]
A mxn = aij
Elementy macierzy A są wygranymi gracza I i jednocześnie przegranymi gracza II. Def. Strategia mieszana Wektor wierszowy opisujący częstość stosowania poszczególnych strategii przez gracza I.
X1xm = [ x1
x2
... xm ] m
gdzie:
xi ≥ 0 dla i=1,2,...,m
oraz
∑x
i
=1
i =1
Wektor kolumnowy opisujący częstość stosowania poszczególnych strategii przez gracza II
Ynx1
y1 y = 2 ... gdzie: yn
n
y j ≥ 0 dla j=1,2,...,n oraz
∑y
j
=1
j =1
Def. Strategia czysta Jeżeli X lub Y są wersorami to nazywamy je strategiami czystymi.
D. Miszczyńska, M.Miszczyński KBO UŁ
3
Def. Funkcją wypłaty nazywamy oczekiwaną wygraną gracza I (nadzieję matematycznę wygranej gracza I) m
n
E ( X , Y) = XAY = ∑ ∑ xi aij y j i =1 j =1
Def. Rozwiązaniem gry nazywamy wektory
[
X1∗×m = x1∗ oraz
liczbę rzeczywistą
( ) E (i ,Y ) ≤ v
x2∗ L xm∗
v
]
Yn∗×1 i
y1∗ ∗ y2 = M ∗ y n
takie, że spełnione są warunki
E X∗ , j ≥ v dla strategii czystych gracza II
j=1,2,...,n
∗
dla strategii czystych gracza I
i=1,2,...,m
Strategie X∗ oraz Y∗ nazywamy strategiami optymalnymi, a liczbę v wartością gry. Wartość gry v jest oczekiwaną wygraną (nadzieją matematyczną wygranej) gracza I jeżeli obaj gracze stosują swoje optymalne strategie mieszane X∗ oraz Y∗ , tj.
(
)
E X∗ , Y∗ = v Tw.
(H.Kuhn'a o punkcie siodłowym w teorii gier)
Oczekiwana wygrana (nadzieja matematyczna) gracza I stosującego dowolną strategię mieszaną X podczas gdy gracz II stosuje optymalną strategię Y∗ nie przekracza wartości gry. I odwrotnie, oczekiwana wygrana gracza I stosującego optymalną strategię X∗ podczas gdy gracz
D. Miszczyńska, M.Miszczyński KBO UŁ
4
II stosuje dowolną strategię mieszaną gry
(
)
Y
(
jest nie mniejsza niż wartość
)
(
E X , Y∗ ≤ E X∗ , Y∗ ≤ E X∗ , Y
Tw.
)
(twierdzenie minimaksowe von Neumana i Morgensterna twierdzenie zasadnicze gier macierzowych) Dla każdej gry macierzowej istnieją i są sobie równe wielkości
max min E ( X , Y) oraz min max E ( X , Y) , które odpowiadają wartości X Y Y X gry v , tj.
max min E ( X , Y) = min max E ( X , Y) = v X
Y
Y
X
Każda gra 2-osobowa o sumie wypłat zero ma zawsze rozwiązanie.
Tw.
(twierdzenie o liczbie stosowanych strategii) ∗
∗
Niech m (n ) oznacza liczbę strategii jaką używać będzie postępujący optymalnie gracz I (gracz II). Każdy z graczy postępując optymalnie używać będzie nie więcej strategii niż wynosi mniejsza z liczb m (liczba strategii gracza I) lub n (liczba strategii gracza II), tj.
m∗ ≤ min{m,n} Def. Dolna wartość gry Liczba rzeczywista
v
oraz
n∗ ≤ min{m, n}
(minimalna wygrana gracza I) taka, że
v = max{ai • } i
gdzie
{ }
ai • = min aij j
D. Miszczyńska, M.Miszczyński KBO UŁ
5
Dla dolnej wartości gry zachodzi
{ }
v = max min aij ≤ v i
Def. Górna wartość gry
v
Liczba rzeczywista
j
(maksymalna przegrana gracza II)
taka, że
{ }
v = min a• j j
{ }
a• j = max aij
gdzie
i
Dla górnej wartości gry zachodzi
{ }
v = min max aij ≥ v j
i
Sposób określania dolnej ( v ) i górnej ( v ) wartości gry nosi nazwę zasady minimaksu, tj. zasady odzwierciedlającej ostrożne postępowanie obu graczy.
2 3 5 A = aij = 4 1 0 4 [3] 5
[ ]
v=3
[ 2] 0
v=2
2≤v≤3
Def. Gra z punktem siodłowym jest to gra, w której dolna ( v ) i górna ( v ) wartości gry są sobie równe, tj.
v=v Def. Punkt siodłowy jest to ten z elementów macierzy wypłat
[ ]
A = aij , który wyznacza dolną ( v ) i górną ( v ) wartość gry w grze z punktem siodłowym.
D. Miszczyńska, M.Miszczyński KBO UŁ
Tw.
6
(twierdzenie o rozwiązaniu gry z punktem siodłowym)
Rozwiązaniem gry z punktem siodłowym jest para strategii czystych (wersorów) X∗ i Y∗ oraz wartość gry v = v = v
3 A= 4 4
[ 2] 1
5 0
[ 2]
5
[ 2] 0
X∗ = [1 0]
v=2
0 Y∗ = 1 0
v=v=v=2
v=2
Def. Gra symetryczna. Grę nazywamy grą symetryczną jeżeli macierz wypłat tej gry jest macierzą skośno-symetryczną, tj.
[
A m = aij = − a ji
Tw.
]
(twierdzenie o rozwiązaniu gry symetrycznej)
W grze symetrycznej optymalne strategie obu graczy są identyczne, a wartość gry wynosi zero, tj.
X∗ = Y∗ 0 5 −3 A = aij = −5 0 2 3 −2 0 3 5 2
[ ]
v =2
−3 −5 −2
v = −2
oraz
v=0
2 / 10 X∗ = [2 / 10 3 / 10 5 / 10] Y∗ = 3 / 10 5 / 10 v =0
D. Miszczyńska, M.Miszczyński KBO UŁ
Tw.
7
(twierdzenie o dodaniu stałej do macierzy wypłat)
Dla dwóch gier macierzowych A i B o macierzach wypłat
[
]
[ ]
A mxn = aij
B mxn = bij = aij + c gdzie c∈R \ {0} i wartościach gry odpowiednio v A oraz v B zachodzą następujące związki:
oraz
1. optymalne strategie mieszane sa identyczne, tj.
X∗A = X∗B
oraz
YA∗ = YB∗
2. wartości gry różnią się o stałą c , tj.
vB = v A + c 3 A= 4 4
[2] 5 1 0 [ 2]
[ 2] 0
vA = 2
X∗A = [1 0]
0 YA∗ = 1 0
vA = v A = v A = 2
5
vA = 2
7 B = A + [ 4] = 8 8
[6] 9 5 4 [6]
[6] 4
vB = 6
X∗B = [1 0]
0 YB∗ = 1 0
9
vB = v B = v B = 6
vB = 6
vB = v A + 4 = 2 + 4 = 6
D. Miszczyńska, M.Miszczyński KBO UŁ
8
II. ROZWIĄZYWANIE GIER MACIERZOWYCH
II.1. Redukcja macierzy wypłat Redukcja macierzy polega na zastąpieniu wyjściowej macierzy
A mxn ekwiwalentną macierzą A kxr gdzie zachodzi przynajmniej jeden z przypadków k 5 / 2 .
[
]
∗ Warunek taki spełnia strategia 3 ponieważ E X , 3 = 15 / 4 > 5 / 2 .
∗ Zatem w optymalnej strategii mieszanej gracza II y3 = 0 .
∗ Aby określić pozostałe składowe wektora Y należy rozwiązać pomocniczy układ równań
y1∗ + y2∗ + y3∗ = 1 2 y1∗ + 3 y2∗ + 5 y3∗ = 5 / 2
z def . E 1, Y∗ =
[ ] E [2 , Y ] = ∗
4 y1∗ + 1y2∗ +
0 y3∗ = 5 / 2
∗ Ponieważ y3 = 0 , to powyższy układ równań można zastąpić
[ ] E [2 , Y ] = E 1, Y∗ = ∗
y1∗ +
y2∗ =
1
2 y1∗ + 3 y2∗ = 5 / 2 4 y1∗ + 1y2∗ = 5 / 2
D. Miszczyńska, M.Miszczyński KBO UŁ
13
Wykorzystując dwa dowolnie wybrane równania powyższego układu otrzymamy
y1∗ = 1 / 2 oraz y2∗ = 1 / 2
Rozwiązanie omawianej gry o macierzy wypłat A 2 x 3 jest następujące X ∗ = [ 3 / 4 1 / 4]
1 / 2 Y∗ = 1 / 2 0
i
oraz
v = 5/ 2
Dla gier o macierzy wypłat A mx2 postępować będziemy podobnie. Rysunek dotyczył będzie gracza II, o którym należy pamiętać, że jest zainteresowany w minimalizacji warości gry v. Optymalne częstości w wektorze Y wyznaczymy tutaj analizując górną
obwiednię { E1 , E2 ,..., Em } , poszukując na niej minimalnej wartości gry (minimalnej przegranej gracza II). Dla gry o macierzy wypłat A 3 x 2 postępowanie wygląda następująco.
A 3x 2
1 = −1 5 5
2 [1] 4 −1 v =1 0 0 [ 4] 1≤ v ≤ 4
v=4 Wektory strategii mieszanych obu graczy mają tutaj postać
X = [ x1
x2
x3 ]
i
y1 Y= y2
D. Miszczyńska, M.Miszczyński KBO UŁ
14
Z założenia y1 + y2 = 1 . Przyjmując y1 = y mamy y2 = 1 − y . Stąd
y Y= 1 − y Wyznaczamy oczekiwane wygrane gracza II, jeżeli gracz I stosuje swoje
strategie czyste, tj. E [i,Y] . Oznaczać je będziemy krótko Ei .
y E1 = E [1,Y] = [1 2] = −y + 2 1 − y y E2 = E [ 2 ,Y] = [ −1 4] = −5 y + 4 1 − y y E 3 = E [ 3,Y] = [5 0] = 5y 1 − y
E2 = E3
⇒
− 5y + 4 = 5y ⇒ y = 2 / 5
D. Miszczyńska, M.Miszczyński KBO UŁ
15
Optymalna strategia mieszana dla gracza II ma więc postać
2 / 5 Y∗ = 3 / 5 Wartość wygranej przy
y=2/5 jest równa wartości gry v=2
2 / 5 E2 = E 2, = −5 × 2 / 5 + 4 = 2 3/ 5 2 / 5 E3 = E 3, = 5 × 2 / 5 = 2 3/ 5 Gracz I nie powinien stosować żadnej swojej strategii, przy której przegrana optymalnie postępującego gracza II byłaby mniejsza od wartości gry v=2 (wygrana gracza I byłaby mniejsza od wartości gry !!!).
[
]
∗ Musi wyeliminować wszystkie strategie, dla których E i,Y < 2 .
[
]
∗ Warunek taki spełnia strategia 1 ponieważ E 1, Y = 8 / 5 < 2 . ∗ Zatem w optymalnej strategii mieszanej gracza I x1 = 0 .
∗ Aby określić pozostałe składowe wektora X należy rozwiązać pomocniczy układ równań
z def . x1∗ + E X∗ ,1 = 1x1∗ −
[ ] E [ X ,2] = ∗
x2∗ + x3∗ = 1 1x2∗ + 5x3∗ = 2
2 x1∗ + 4 x2∗ + 0 x3∗ = 2
D. Miszczyńska, M.Miszczyński KBO UŁ
16
∗ Ponieważ x1 = 0 , to powyższy układ równań można zastąpić
x2∗ +
[ ] E [ X ,2] =
x3∗ =
1
E X∗ ,1 = −1x2∗ + 5x3∗ = 2 ∗
4 x2∗ + 0 x3∗ = 2
Wykorzystując dwa dowolnie wybrane równania powyższego układu otrzymamy
x2∗ = 1 / 2 oraz x3∗ = 1 / 2 Rozwiązanie omawianej gry jest następujące
X = [ 0 1 / 2 1 / 2] ∗
i
2 / 5 Y∗ = 3 / 5
oraz
v=2
D. Miszczyńska, M.Miszczyński KBO UŁ
II.4.
17
Iteracyjne rozwiązywanie gier macierzowych
Jedną z metod przybliżonego rozwiązywania gier jest metoda symulacyjna oparta na analizie skumulowanych wygranych. Omówimy ją na przykładzie.
A 2 x3
2 3 5 = 4 1 0
v=2
v=3
2≤v≤3
Proces iteracyjny prowadzimy w tablicy do momentu, gdy wykonamy minimalną liczbę iteracji (np. 8). Po ich wykonaniu możemy zakończyć proces symulacji gry, gdy: −
otrzymamy błąd oszacowania wartości gry (ε) nie większy od założonego poziomu (np. ε = 0.1)
−
osiągniemy maksymalną liczbę iteracji (np. 100) lub
W kolumnie (k) odnotowuje się numer bieżącej iteracji, a w kolumnie (ε) błąd oszacowania wartości gry. W kolumnach (gracz II) odnotowuje się skumulowane wypłaty gracza II, a w kolumnach (gracz I) skumulowane wygrane gracza I. 1. Symulację rozpoczynamy od dodania do kolumn (gracz II) pierwszego wiersza macierzy wypłat. W kolumnach (gracz II) wybieramy najmniejszą skumulowaną wypłatę; jest to wypłata 2 odpowiadająca strategii 1 gracza II. Do kolumn (gracz I) dodajemy zatem kolumnę 1 macierzy wypłat A. W kolumnach (gracz I) wybieramy największą skumulowaną wygraną; jest to wygrana 4 odpowiadająca strategii 2 gracza I. Taki wybór powoduje, że w kolejnej (k=2) iteracji do kolumn (gracz II) dodajemy wiersz 2 macierzy wypłat A. 2. W kolumnach (gracz II) wybieramy najmniejszą skumulowaną wypłatę; jest to wypłata 4 odpowiadająca strategii 2 gracza II. Do kolumn (gracz I) dodajemy zatem kolumnę 2 macierzy wypłat A. W kolumnach (gracz I) wybieramy największą skumulowaną wygraną; jest to wygrana 5 odpowiadająca strategii 1 gracza I (wybór był tutaj niejednoznaczny; wybrano strategię o niższym numerze). W wyniku tego w kolejnej (k=3) iteracji do kolumn (gracz II) dodajemy wiersz 1 macierzy wypłat A.
D. Miszczyńska, M.Miszczyński KBO UŁ
18
W ten sposób przebiegają kolejne iteracje. Po 8 iteracjach wolno nam zakończyć proces obliczeniowy jeżeli błąd oszacowania wartości gry nie przekracza 10% (ε=0.1) . Taka sytuacja ma miejsce dopiero po 10 iteracjach. Rozwiązanie gry uzyskujemy zliczając w kolumnach (gracz I) i (gracz II) krotność użycia każdej strategii. Dzieląc te krotności przez liczbę wykonanych iteracji otrzymamy oszacowania składowych wektorów X∗ i Y∗ . Przybliżone rozwiązanie gry uzyskane w wyniku symulacji jest następujące
X ∗ = [ 7 / 10 3 / 10]
i
A2x3 gracz II
1 / 2 Y ∗ = 1 / 2 0
oraz
v = 49 / 20
2 3 5 = 4 1 0 gracz I
v
iteracja strategia 1 strategia 2 strategia 3
v
ε
v
strategia 1 strategia 2
k
a •1
a •2
a •3
a• j / k
a 1•
a 2•
ai• / k
v−v
(v + v) / 2
0
0
0
0
−
0
0
−
−
−
1
2
3
5
2
2
4
4
2
3
2
6
4
5
2
5
5
5/2
1/2
9/4
3
8
7
10
7/3
8
6
8/3
1/3
5/2
4
10
10
15
5/2
10
10
5/2
0
5/2
5
12
13
20
12/5
12
14
14/5
2/5
13/5
6
16
14
20
7/3
15
15
5/2
1/6
11/4
7
18
17
25
17/7
18
16
18/7
1/7
5/2
8
20
20
30
5/2
20
20
5/2
0
5/2
9
22
23
35
22/9
22
24
24/9
2/9
23/9
10
26
24
35
12/5
25
25
5/2
1/10
49/20
krotność użycia
5
5
0
7
3
wartość gry
częstość
5/10
5/10
0
7/10
3/10
49/20