GRY
(część 1)
GRY
(część 1)
Gry dwuosobowe o sumie zero
3
Gry dwuosobowe o sumie zero
Zastosowanie:
Modelowanie sytuacji konfliktowych, w których występują
dwie antagonistyczne strony.
Najbardziej znane modele:
- wybór strategii marketingowych przez konkurujące ze sobą
firmy
- wybór strategii postępowania przedwyborczego przez
konkurujących ze sobą polityków
- analiza strategicznych konfliktów międzynarodowych
- problem wspólnego pastwiska (problem of commons)
- problem gazeciarza
4
Gry dwuosobowe o sumie zero
Założenia:
- każdy z graczy dysponuje pewną ilością strategii
- każdy z graczy zna możliwe strategie przeciwnika
- gracze podejmują decyzje równocześnie i niezależnie
*
- żaden z graczy nie wie, którą strategię wybierze przeciwnik
- gracze postępują ostrożnie i zakładają, że przeciwnik
postępuje racjonalnie
5
Gry dwuosobowe o sumie zero
Rozwiązanie gry:
- określenie optymalnych strategii dla każdego z graczy
6
Gry dwuosobowe o sumie zero
ad. założenie *:
gracze podejmują decyzję równocześnie i niezależnie
skutki jednoczesnego zastosowania przez graczy swoich
strategii opisuje tzw. macierz wypłat
Interpretacja macierzy wypłat:
macierz korzyści Gracza 1. i macierz strat Gracza 2.
Gracz 1. – maksymalizuje wygraną
Gracz 2. – minimalizuje przegraną
7
Gry dwuosobowe o sumie zero
Przykład 6.
Sztaby wyborcze dwóch polityków, kandydujących do senatu
spodziewają się, że decydujący wpływ na wynik kampanii
mogą mieć jej dwa ostatnie dni. Obaj politycy zdają sobie
sprawę, że kluczową rolę w wyborach mogą odegrać głosy
mieszkańców dwóch dużych miast: X i Y.
Każdy z polityków może wybrać jedną z trzech strategii
postępowania:
- spędzić dwa dni w mieście X
- spędzić dwa dni w mieście Y
- spędzić jeden dzień w mieście X i jeden w mieście Y
Sztab wyborczy Polityka 1. przygotował prognozy przyrostu
głosów na Polityka 1. kosztem Polityka 2. w zależności od
wybranych przez nich strategii.
8
Gry dwuosobowe o sumie zero
20
XY
XY
10
YY
XY
50
XX
XY
20
XY
YY
-10
YY
YY
20
XX
YY
40
XY
XX
-30
YY
XX
-50
XX
XX
Przyrost głosów na Polityka 1., kosztem Polityka 2.
( w tys. głosów)
Polityk 2.
Polityk 1.
Tabela 6.1.
9
Gry dwuosobowe o sumie zero
Na podstawie tablicy prognoz, zbudować macierz wypłat.
Polityk 1. – Gracz 1.
Polityk 2. – Gracz 2.
XX – strategia 1.
YY – strategia 2.
XY – strategia 3.
10
Gry dwuosobowe o sumie zero
20
10
50
XY
20
-10
20
YY
40
-30
-50
XX
Polityk 1.
XY
YY
XX
strategie
Polityk 2.
Tabela 6.2.
11
Gry dwuosobowe o sumie zero
20
10
50
3
20
-10
20
2
40
-30
-50
1
Gracz 1.
3
2
1
strategie
Gracz 2.
Tabela 6.3.
12
Gry dwuosobowe o sumie zero
Przykład 7.
Dwa koncerny samochodowe konkurują ze sobą na rynku
pewnego kraju. Koncern A rozważa uruchomienie w lokalnej
fabryce jednego z czterech modeli samochodów. Koncern B
natomiast jednego z pięciu modeli samochodów.
W macierzy wypłat przedstawiono zyski koncernu A (straty
koncernu B) przy produkcji poszczególnych samochodów, w
zależności od decyzji podjętych przez koncerny.
Należy podjąć decyzję o rodzaju produkcji, będąc
dyrektorem koncernu A.
Koncern A – Gracz 1.
Koncern B – Gracz 2.
13
Gry dwuosobowe o sumie zero
60
20
90
70
70
4
30
80
0
150
80
3
110
80
100
80
70
2
Gracz 1.
120
30
10
70
200
1
5
4
3
2
1
strategie
Gracz 2.
Tabela 7.1.
14
Gry dwuosobowe o sumie zero
I. ETAP: REDUKCJA MACIERZY WYPŁAT
Poszukiwanie strategii zdominowanych
a
ij
– element macierzy wypłat
i = 1...m
m
– ilość strategii Gracza 1. (ilość wierszy)
j = 1...n
n
– ilość strategii Gracza 2. (ilość kolumn)
15
Gry dwuosobowe o sumie zero
Poszukiwanie strategii zdominowanych dla Gracza 1.
Porównujemy parami strategie Gracza 1.
Jeżeli dla danej pary strategii spełniony jest warunek:
1...
zj
dj
a
a
j
n
≤
=
to strategia
z
jest zdominowana przez strategię
d
.
(strategia
d
to strategia dominująca strategię
z
)
16
Gry dwuosobowe o sumie zero
Strategie 1 i 2:
110
80
100
80
70
2
120
30
10
70
200
1
Warunek dominacji nie jest spełniony
Strategie 1 i 3:
30
80
0
150
80
3
120
30
10
70
200
1
Warunek dominacji nie jest spełniony
Tabela 7.2.a.
Tabela 7.2.b.
17
Gry dwuosobowe o sumie zero
Strategie 1 i 4:
60
20
90
70
70
4
120
30
10
70
200
1
Warunek dominacji nie jest spełniony
Strategie 2 i 3:
30
80
0
150
80
3
110
80
100
80
70
2
Warunek dominacji nie jest spełniony
Tabela 7.2.c.
Tabela 7.2.d.
18
Gry dwuosobowe o sumie zero
Strategie 2 i 4:
60
20
90
70
70
4
110
80
100
80
70
2
Warunek dominacji jest spełniony
Strategia 4. – zdominowana Strategia 2. - dominująca
Z macierzy wypłat usuwamy strategię 4. Gracza 1.
Porównane zostały wszystkie możliwe pary strategii Gracza 1.
Kończymy poszukiwania strategii zdominowanych dla Gracza 1.
Tabela 7.2.e.
19
Gry dwuosobowe o sumie zero
30
80
0
150
80
3
110
80
100
80
70
2
Gracz 1.
120
30
10
70
200
1
5
4
3
2
1
strategie
Gracz 2.
Tabela 7.3.
20
Gry dwuosobowe o sumie zero
Poszukiwanie strategii zdominowanych dla Gracza 2.
Porównujemy parami strategie Gracza 2.
Jeżeli dla danej pary strategii spełniony jest warunek:
1...
iz
id
a
a
i
m
≤
=
to strategia
d
jest zdominowana przez strategię
z
.
(strategia
z
to strategia dominująca strategię
d
)
21
Gry dwuosobowe o sumie zero
Strategie 1 i 2:
70
200
80
70
150
80
2
1
Warunek dominacji
nie jest spełniony
Tabela 7.4.a.
Strategie 1 i 3:
10
200
100
70
0
80
3
1
Warunek dominacji
nie jest spełniony
Tabela 7.4.b.
22
Gry dwuosobowe o sumie zero
Strategie 1 i 4:
30
200
80
70
80
80
4
1
Warunek dominacji
nie jest spełniony
Tabela 7.4.c.
Strategie 1 i 5:
120
200
110
70
30
80
5
1
Warunek dominacji
nie jest spełniony
Tabela 7.4.d.
23
Gry dwuosobowe o sumie zero
Strategie 2 i 3:
10
70
100
80
0
150
3
2
Warunek dominacji
nie jest spełniony
Tabela 7.4.e.
Strategie 2 i 4:
30
70
80
80
80
150
4
2
Warunek dominacji
jest spełniony
Tabela 7.4.f.
24
Gry dwuosobowe o sumie zero
Strategia 2. – zdominowana
Strategia 4. - dominująca
Z macierzy wypłat usuwamy strategię 2. Gracza 2.
25
Gry dwuosobowe o sumie zero
Strategie 3 i 4:
30
10
80
100
80
0
4
3
Warunek dominacji
nie jest spełniony
Tabela 7.4.g.
Strategie 3 i 5:
120
10
110
100
30
0
5
3
Warunek dominacji
jest spełniony
Tabela 7.4.h.
26
Gry dwuosobowe o sumie zero
Strategia 5. – zdominowana
Strategia 3. - dominująca
Z macierzy wypłat usuwamy strategię 5. Gracza 2.
27
Gry dwuosobowe o sumie zero
Porównane zostały wszystkie możliwe pary strategii Gracza 2.
Kończymy poszukiwania strategii zdominowanych dla Gracza 2.
28
Gry dwuosobowe o sumie zero
80
0
80
3
80
100
70
2
Gracz 1.
30
10
200
1
4
3
1
strategie
Gracz 2.
Tabela 7.5.
29
Gry dwuosobowe o sumie zero
Zmieniła się ilość strategii dla Gracza 2.
Ponownie poszukujemy strategii zdominowanych dla Gracza 1.
30
Gry dwuosobowe o sumie zero
Strategie 1 i 2:
80
100
70
2
30
10
200
1
Warunek dominacji nie jest spełniony
Strategie 1 i 3:
80
0
80
3
10
70
200
1
Warunek dominacji nie jest spełniony
Tabela 7.6.a.
Tabela 7.6.b.
31
Gry dwuosobowe o sumie zero
Strategie 2 i 3:
80
0
80
3
80
100
70
2
Warunek dominacji nie jest spełniony
Tabela 7.6.c.
32
Gry dwuosobowe o sumie zero
Porównane zostały wszystkie możliwe pary strategii Gracza 1.
Kończymy poszukiwania strategii zdominowanych dla Gracza 1.
Nie zmieniła się ilość strategii dla Gracza 1.
Nie poszukujemy strategii zdominowanych dla Gracza 2.
33
Gry dwuosobowe o sumie zero
Uwaga!!!
W przypadku wyeliminowania strategii Gracza 1., należy
ponownie sprawdzić strategie dla Gracza 2. itd....
34
Gry dwuosobowe o sumie zero
II. ETAP: POSZUKIWANIE PUNKTU SIODŁOWEGO
- dla każdego wiersza znajdujemy wartość minimalną
- dla każdej kolumny znajdujemy wartość maksymalną
35
Gry dwuosobowe o sumie zero
80
100
200
0
70
10
80
0
80
3
80
100
70
2
Gracz 1.
30
10
200
1
4
3
1
strategie
Gracz 2.
Tabela 7.7.
max
ij
i
a
min
ij
j
a
36
Gry dwuosobowe o sumie zero
- dla wyznaczonych minimalnych wartości z wierszy
określamy wartość maksymalną:
max(min ) max(10,70,0) 70
ij
j
i
a
=
=
- dla wyznaczonych maksymalnych wartości z kolumn
określamy wartość minimalną:
min(max ) min(200,100,80) 80
ij
j
i
a
=
=
37
Gry dwuosobowe o sumie zero
Punkt siodłowy istnieje, gdy spełniony jest warunek:
max(min ) min(max )
ij
ij
j
j
i
i
a
a
=
38
Gry dwuosobowe o sumie zero
W tym przykładzie warunek istnienia punktu siodłowego nie
jest spełniony
Stwierdzamy brak rozwiązania w zbiorze strategii czystych
Szukamy rozwiązania w zbiorze strategii mieszanych
39
Gry dwuosobowe o sumie zero
III. ETAP: DEFINICJA ZADAŃ PROGRAMOWANIA LINIOWEGO
Macierz wypłat:
200 10
30
70 110 80
80
0
80
ª
º
«
»
= «
»
«
»
¬
¼
A
T
200
70 80
10
110
0
30
80
80
ª
º
«
»
= «
»
«
»
¬
¼
A
40
Gry dwuosobowe o sumie zero
Gracz 1. będzie stosował:
Strategię 1. z częstością (prawdopodobieństwem)
p
1
Strategię 2. z częstością (prawdopodobieństwem)
p
2
Strategię 3. z częstością (prawdopodobieństwem)
p
3
(dla wyeliminowanej strategii 4.
p
4
= 0
)
v
– wartość gry
41
Gry dwuosobowe o sumie zero
Na podstawie transponowanej macierzy wypłat:
- wygrana Gracza 1. w przypadku, gdy Gracz 2. będzie
stosował strategię 1:
1
2
3
200
70
80
p
p
p
v
+
+
=
- wygrana Gracza 1. w przypadku, gdy Gracz 2. będzie
stosował strategię 3:
1
2
3
10
110
0
p
p
p
v
+
+
=
- wygrana Gracza 1. w przypadku, gdy Gracz 2. będzie
stosował strategię 4:
1
2
3
30
80
80
p
p
p
v
+
+
=
42
Gry dwuosobowe o sumie zero
Ponadto suma częstości (prawdopodobieństwa) stosowania
wszystkich strategii musi być równa 1:
1
2
3
1
p
p
p
+
+
=
Strategia optymalna, przy dowolnym postępowaniu Gracza 2.
powinna zapewnić Graczowi 1. wygraną nie mniejszą niż
wartość gry
v
.
43
Gry dwuosobowe o sumie zero
Czyli ograniczenia przyjmują postać:
1
2
3
200
70
80
p
p
p
v
+
+
≥
1
2
3
10
110
0
p
p
p
v
+
+
≥
1
2
3
30
80
80
p
p
p
v
+
+
≥
oraz:
1
2
3
1
p
p
p
+
+
=
44
Gry dwuosobowe o sumie zero
Gracz 1. dąży do maksymalizacji swojej wygranej.
Funkcja celu:
MAX
v
→
45
Gry dwuosobowe o sumie zero
v
– jest wartością nieznaną
Rozwiązanie zadania programowania liniowego jest niemożliwe
Aby się uniezależnić od wartości
v
:
- układ ograniczeń dzielimy obustronnie przez
v
- podstawiamy:
i
i
p
x
v
=
46
Gry dwuosobowe o sumie zero
1
2
3
200
70
80
1
x
x
x
+
+
≥
1
2
3
10
110
0
1
x
x
x
+
+
≥
1
2
3
30
80
80
1
x
x
x
+
+
≥
47
Gry dwuosobowe o sumie zero
1
2
3
1
x
x
x
v
+ + =
Korzystając z :
Otrzymujemy funkcję celu:
MAX
v
→
1
2
3
1
MIN
x
x
x
v
+ + = →
48
Gry dwuosobowe o sumie zero
Model matematyczny:
1
2
3
1
MIN
x
x
x
v
+ + = →
1
2
3
200
70
80
1
x
x
x
+
+
≥
1
2
3
10
110
0
1
x
x
x
+
+
≥
1
2
3
30
80
80
1
x
x
x
+
+
≥
1
2
3
, ,
0
x x x
≥
49
Gry dwuosobowe o sumie zero
Gracz 2. będzie stosował:
Strategię 1. z częstością (prawdopodobieństwem)
q
1
Strategię 3. z częstością (prawdopodobieństwem)
q
3
Strategię 4. z częstością (prawdopodobieństwem)
q
4
50
Gry dwuosobowe o sumie zero
Na podstawie macierzy wypłat:
- przegrana Gracza 2. w przypadku, gdy Gracz 1. będzie
stosował strategię 1:
1
3
4
20
10
30
q
q
q
v
+
+
=
- przegrana Gracza 2. w przypadku, gdy Gracz 1. będzie
stosował strategię 2:
1
3
4
70
110
80
q
q
q
v
+
+
=
- przegrana Gracza 2. w przypadku, gdy Gracz 1. będzie
stosował strategię 3:
1
3
4
80
0
80
q
q
q
v
+
+
=
51
Gry dwuosobowe o sumie zero
Ponadto suma częstości (prawdopodobieństwa) stosowania
wszystkich strategii musi być równa 1:
1
3
4
1
q
q
q
+ +
=
Strategia optymalna, przy dowolnym postępowaniu Gracza 1.
powinna zapewnić Graczowi 2. przegraną nie większą niż
wartość gry
v
.
52
Gry dwuosobowe o sumie zero
Czyli ograniczenia przyjmują postać:
1
3
4
20
10
30
q
q
q
v
+
+
≤
1
3
4
70
110
80
q
q
q
v
+
+
≤
1
3
4
80
0
80
q
q
q
v
+
+
≤
oraz:
1
3
4
1
q
q
q
+ +
=
53
Gry dwuosobowe o sumie zero
Gracz 2. dąży do minimalizacji swojej przegranej.
Funkcja celu:
M IN
v
→
54
Gry dwuosobowe o sumie zero
Aby się uniezależnić od wartości
v
:
- układ ograniczeń dzielimy obustronnie przez
v
- podstawiamy:
j
j
q
y
v
=
55
Gry dwuosobowe o sumie zero
1
3
4
20
10
30
1
y
y
y
+
+
≤
1
3
4
70
110
80
1
y
y
y
+
+
≤
1
3
4
80
0
80
1
y
y
y
+
+
≤
56
Gry dwuosobowe o sumie zero
1
3
4
1
y
y
y
v
+ +
=
Korzystając z :
Otrzymujemy funkcję celu:
MIN
v
→
1
3
4
1
MAX
y
y
y
v
+ +
= →
57
Gry dwuosobowe o sumie zero
Model matematyczny:
1
3
4
1
M AX
y
y
y
v
+ +
= →
1
3
4
20
10
30
1
y
y
y
+
+
≤
1
3
4
70
110
80
1
y
y
y
+
+
≤
1
3
4
80
0
80
1
y
y
y
+
+
≤
1
3
4
, ,
0
y y y
≥
58
Gry dwuosobowe o sumie zero
IV. ETAP: ROZWIĄZANIE
Rozwiązanie zadania programowania liniowego dla Gracza 1.:
3
3
3
1
2
3
0.584 10
9.941 10
2.339 10
x
x
x
−
−
−
=
⋅
=
⋅
=
⋅
Rozwiązanie zadania programowania liniowego dla Gracza 2.:
3
3
3
1
3
4
3.654 10
0.365 10
8.844 10
y
y
y
−
−
−
=
⋅
=
⋅
=
⋅
59
Gry dwuosobowe o sumie zero
Obliczenie wartości gry
v
.
Gracz 1.:
1
2
3
1
FC : x
x
x
v
+ + =
1
2
3
1
1
77.73
0.012864
v
x
x
x
=
=
=
+ +
Gracz 2.:
1
3
4
1
FC : y
y
y
v
+ +
=
1
3
4
1
1
77.73
0.012864
v
y
y
y
=
=
=
+ +
60
Gry dwuosobowe o sumie zero
Obliczenie częstości stosowania strategii.
Gracz 1.:
1
1
0.045455
p
x v
= ⋅ =
2
2
0.772727
p
x v
= ⋅ =
3
3
0.181818
p
x v
= ⋅ =
Gracz 2.:
1
1
0.284091
q
y v
= ⋅ =
3
3
0.028409
q
y v
= ⋅ =
4
4
0.6875
q
y v
= ⋅ =
61
Gry dwuosobowe o sumie zero
0.6875
0.028409
0.284091
0.181818
0.772727
0.045455
80
0
80
3
80
100
70
2
Gracz 1.
30
10
200
1
4
3
1
strategie
Gracz 2.
Tabela 7.8.
j
q
i
p
62
Gry dwuosobowe o sumie zero
Wartość gry
v = 77.73
Wartość gry zawsze mieści się w przedziale:
(
)
max(min ),min(max )
ij
ij
j
j
i
i
a
a
Tutaj:
(
)
70,80
v
∈
63
Gry dwuosobowe o sumie zero
Przykład 8.
Po redukcji macierzy wypłat otrzymano następującą tablicę:
540
600
750
3
400
420
650
2
Gracz 1.
250
350
520
1
4
3
1
strategie
Gracz 2.
Tabela 8.1.
64
Gry dwuosobowe o sumie zero
540
600
750
540
400
250
540
600
750
3
400
420
650
2
Gracz 1.
250
350
520
1
4
3
1
strategie
Gracz 2.
Tabela 8.2.
max
ij
i
a
min
ij
j
a
65
Gry dwuosobowe o sumie zero
max(min ) 540
ij
j
i
a
=
min(max ) 540
ij
j
i
a
=
Punkt siodłowy istnieje
Stwierdzamy, że istnieje rozwiązanie gry w zbiorze strategii czystych
66
Gry dwuosobowe o sumie zero
Wartość gry:
v = 540
Gracz 1. powinien stosować strategię 3.
Gracz 2. powinien stosować strategię 4.
67
Gry dwuosobowe o sumie zero
Przykład 9.
Dana jest macierz wypłat:
0
-1
3
2
Gracz 1.
2
8
-2
1
3
2
1
strategie
Gracz 2.
Tabela 9.1.
68
Gry dwuosobowe o sumie zero
2
8
3
-1
-2
0
-1
3
2
Gracz 1.
2
8
-2
1
3
2
1
strategie
Gracz 2.
Tabela 9.2.
max
ij
i
a
min
ij
j
a
69
Gry dwuosobowe o sumie zero
max(min )
1
ij
j
i
a
= −
min(max ) 2
ij
j
i
a
=
Wartość gry:
( 1,2)
v
∈ −
W przypadku, gdy mnie wiadomo, czy
v
jest liczbą dodatnią czy
ujemną należy przekształcić macierz wypłat.
70
Gry dwuosobowe o sumie zero
Znajdujemy w macierzy wypłat element najmniejszy:
11
2
a
= −
Do każdego elementu macierzy wypłat dodajemy wartość
bezwzględną tego elementu, czyli 2.
71
Gry dwuosobowe o sumie zero
2
1
5
2
Gracz 1.
4
10
0
1
3
2
1
strategie
Gracz 2.
Tabela 9.3.
72
Gry dwuosobowe o sumie zero
4
10
5
1
0
2
1
5
2
Gracz 1.
4
10
0
1
3
2
1
strategie
Gracz 2.
Tabela 9.4.
max
ij
i
a
min
ij
j
a
73
Gry dwuosobowe o sumie zero
Po rozwiązaniu gry, o wartość bezwzględną z elementu
najmniejszego należy zmniejszyć
v
, aby otrzymać rzeczywistą
wartość gry.