W
YKŁADY Z
T
EORII
G
IER I
D
ECYZJI
Str. 2
Podstawowe koncepcje rozwiązania gry
Koncepcja strategii dominujących
D
EFINICJA
.
Dla gracza P
k
strategia
i
a
jest nie gorsza od strategii
j
a
jeŜeli dla
dowolnego wyboru strategii s
i
, i=1,…,N
i≠k
graczy pozostałych zachodzi
M
k
(s
1
, …, a
i
,…, s
N
) ≥ M
k
(s
1
, …, a
j
,…, s
N
)
D
EFINICJA
.
Dla gracza P
k
strategia a
i
jest lepsza od strategii a
j
jeŜeli jest nie gorsza i
ponadto istnieje pewien wybór strategii s
i
, i=1,…,N,
i≠k
graczy pozostałych
dla którego zachodzi
M
k
(s
1
, …, a
i
,…, s
N
) > M
k
(s
1
, …, a
j
,…, s
N
)
JeŜeli strategia a
i
jest lepsza od strategii a
j
to mówimy, Ŝe strategia a
i
dominuje
strategię a
j
oraz , Ŝe strategia a
j
jest dominowana przez strategię
a
i
.
D
EFINICJA
.
Strategię, która jest zdominowana przez inną strategię nazywamy strategią
niedopuszczalną
. W przeciwnym wypadku strategia nazywana jest
dopuszczalną
albo niezdominowaną.
Oczywiście gracz moŜe, a nawet powinien ograniczyć się do strategii
dopuszczalnych. Czasami okazuje się, Ŝe konsekwentne stosowanie
kryterium dominacji jednoznacznie wskazuje sposób wyboru strategii przez
dla graczy. Tak jest w następującym przykładzie.
P
RZYKŁAD
.
Dana jest gra
A
NDRZEJ
Z.
G
RZYBOWSKI
Str. 3
(
)
(
)
(
)
(
) (
) (
)
(
)
(
)
(
) (
)
(
)
−
5
,
17
10
,
1
10
,
5
19
,
9
7
,
4
11
,
0
18
,
8
15
,
3
5
,
14
9
,
3
6
,
8
)
5
,
12
(
)
17
,
14
(
)
12
,
3
(
)
7
,
5
(
)
6
,
12
(
JeŜeli gracze są racjonalni (czyli teŜ wiedzą, Ŝe takŜe drugi gracz
postępuje racjonalnie) i konsekwentnie stosują kryterium dominacji, to
kolejno otrzymujemy następujące postaci tej gry. PoniewaŜ gracz I ma
niedopuszczalna strategię nr 1 więc wystarczy rozwaŜać grę:
(
)
(
) (
)
(
)
−
)
5
,
7
(
)
10
,
1
(
)
10
,
5
(
)
19
,
9
(
)
7
,
4
(
)
11
,
0
(
)
18
,
8
(
15
,
3
5
,
14
9
,
3
6
,
8
)
5
,
12
(
PoniewaŜ obaj zdają sobie sprawę z tej sytuacji więc w zasadzie mamy
„nową” grę. W tej „nowej” grze gracz II ma niedopuszczalną strategię nr 4
zatem wystarczy ograniczyć się do kolejnej gry
−
)
10
,
1
(
)
10
,
5
(
)
19
,
9
(
)
11
,
0
(
)
18
,
8
(
)
15
,
3
(
)
9
,
3
(
)
6
,
8
(
)
5
,
12
(
Konsekwentnie rozumując w ten sposób ostatecznie otrzymujemy, grę
[
]
)
9
,
3
(
Ostatecznie okazało się, Ŝe gracz I powinien wybrać strategię nr 2 a
gracz II strategię nr 3 ( w grze wyjściowej oczywiście).
NaleŜy jednak zauwaŜyć, Ŝe takie sytuacje w których moŜemy
wskazać optymalne postępowanie graczy jedynie poprzez stosowanie
koncepcji strategii niezdominowanych są bardzo rzadkie
W
YKŁADY Z
T
EORII
G
IER I
D
ECYZJI
Str. 4
Koncepcja strategii bezpieczeństwa
D
EFINICJA
Strategię
k
k
S
s ∈
*
nazywamy strategią bezpieczeństwa gracza P
k
w grze
>
<
N
N
M
M
M
S
S
S
K
K
,
,
;
,
,
,
2
1
2
1
jeśli spełniony jest warunek:
)
,...,
,...,
(
min
max
)
,...,
,...,
(
min
1
,
*
1
,
1
1
N
k
k
k
i
S
s
S
s
N
k
k
k
i
S
s
s
s
s
M
s
s
s
M
i
k
k
i
≠
∈
∈
≠
∈
=
(2.gmm)
Z powodu warunku ją definiującego, strategie bezpieczeństwa nazywa się teŜ
często strategią maksyminową.
D
EFINICJA
Jeśli
k
k
S
s ∈
*
jest strategią bezpieczeństwa gracza P
k
to wartość
)
,...,
,...,
(
min
*
1
,
1
N
k
k
k
i
S
s
k
s
s
s
M
v
i
≠
∈
=
nazywamy poziomem bezpieczeństwa tego
gracza.
Z definicji strategii bezpieczeństwa wynika, Ŝe jest to strategia, która
daje graczowi największa wypłatę gwarantowaną. Inaczej: bez względu na to
co zrobią pozostali gracze on dostanie co najmniej
k
v
i Ŝadna inna strategia
nie zagwarantuje mu więcej.
W przypadku gier macierzowych strategię bezpieczeństwa graczy
określa zatem warunki
- dla gracza P
1
:
j
min
=
1
0
j
i
M
i
max
j
min
1
1
v
M
ij
=
- dla gracza P
2
i
min
=
2
0
ij
M
j
max
i
min
2
2
v
M
ij
=
Zilustrujmy te pojęcia następującym przykładem. RozwaŜmy grę G1:
A
NDRZEJ
Z.
G
RZYBOWSKI
Str. 5
−
−
−
−
−
−
))
3
,
3
(
)
4
,
14
(
)
2
,
18
(
)
5
,
10
(
)
5
,
2
(
)
5
,
15
(
)
4
,
8
(
)
3
,
11
(
)
23
,
18
(
)
1
,
11
(
)
1
,
2
(
)
1
,
1
(
Dla gracza I warto
ś
ci najgorsze jakie mo
Ŝ
e uzyska
ć
stosuj
ą
c
poszczególne swoje strategie to -18 dla a
1
, 2 dla a
2
i -10 dla a
3
. Zatem
strategi
ą
bezpiecze
ń
stwa jest dla niego strategia a2 a poziomem
bezpiecze
ń
stwa
2
1
=
v
. Analogicznie rozumuj
ą
c w przypadku gracza II
otrzymujemy,
Ŝ
e w jego przypadku wyst
ę
puj
ą
dwie strategie bezpiecze
ń
stwa
b
1
, oraz b
3
. Obie zapewniaj
ą
ten sam poziom bezpiecze
ń
stwa
1
2
=
v
Zatem
widzimy,
Ŝ
e mo
Ŝ
e by
ć
kilka strategii bezpiecze
ń
stwa i gracz mo
Ŝ
e mie
ć
kłopot z wyborem jednej z nich. Mo
Ŝ
e wtedy zastosowa
ć
inne koncepcje
rozwi
ą
zania.
Koncepcja punktu równowagi
D
EFINICJA
.
Punktem równowagi
w grze
>
<
k
N
M
M
M
S
S
S
K
K
,
,
;
,
,
,
2
1
2
1
nazywamy
układ strategii
)
,
,
,
(
2
1
N
s
s
s
K
, s
i
∈
S
i
, dla którego zachodzi warunek: dla
dowolnego k i dowolnej strategii q
∈
S
k
,
)
,
,
,...,
(
)
,
,
,...,
(
1
1
N
k
N
k
k
s
q
s
M
s
s
s
M
K
K
≥
Z powy
Ŝ
szej definicji wynika,
Ŝ
e
Ŝ
adnemu z graczy nie opłaca si
ę
zmieni
ć
swojej strategii z punktu równowagi na inn
ą
o ile pozostali nie zmieni
ą
swoich
, gdy
Ŝ
w wyniku takiej zamiany nie mog
ą
nic zyska
ć
, mog
ą
co
najwy
Ŝ
ej straci
ć
.
W przypadku gry macierzowej
>
<
2
1
,
,
,
M
M
B
A
warunek z definicji
zapiszemy w postaci nast
ę
puj
ą
cej: para strategii (a
i0
,b
j0
) jest punktem
równowagi z definicji wtedy, gdy dla dowolnych i=1,…,m, j=1,…,n,
W
YKŁADY Z
T
EORII
G
IER I
D
ECYZJI
Str. 6
zachodzi
)
,
(
)
,
(
0
0
1
0
1
j
i
j
i
b
a
M
b
a
M
≤
∧
)
,
(
)
,
(
0
0
2
0
2
j
i
j
i
b
a
M
b
a
M
≤
O takiej parze strategii mówimy cz
ę
sto,
Ŝ
e s
ą
w równowadze.
Rozwa
Ŝ
my ponownie gr
ę
G1
−
−
−
−
−
−
))
3
,
3
(
)
4
,
14
(
)
2
,
18
(
)
5
,
10
(
)
5
,
2
(
)
5
,
15
(
)
4
,
8
(
)
3
,
11
(
)
23
,
18
(
)
1
,
11
(
)
1
,
2
(
)
1
,
1
(
W powy
Ŝ
szej grze par
ą
strategii w równowadze jest para (a
2
,b
3
) . Jest
oczywiste,
Ŝ
e
Ŝ
adnemu z graczy nie opłaca si
ę
zamieni
ć
strategii
wyst
ę
puj
ą
cej w tej parze na jak
ą
kolwiek inn
ą
, je
ś
li drugi nie zmieni swojej
strategii równowagi. Mówi
ą
c jeszcze inaczej, je
ś
li jeden z graczy b
ę
dzie si
ę
upierał przy swojej strategii równowagi to ma zagwarantowan
ą
przynajmniej
taka wypłat
ę
jaka w punkcie równowagi jest dla niego okre
ś
lona. Je
ś
li drugi
z graczy zmieni swoj
ą
strategi
ę
, to pierwszy z nich i tak dostanie to co ma
zagwarantowane, za
ś
drugi na zamianie mo
Ŝ
e tylko straci
ć
. Zatem koncepcja
przyj
ę
cia tej pary jako rozwi
ą
zania problemu wyboru strategii przez graczy
wydaje si
ę
by
ć
oczywista. Zauwa
Ŝ
my ponadto,
Ŝ
e obie te strategie s
ą
strategiami bezpiecze
ń
stwa graczy. Czy zatem zawsze jest tak,
Ŝ
e pary
strategii w równowadze tworzone s
ą
przez strategie bezpiecze
ń
stwa graczy?
Gdyby tak było to byłyby to mocny argument za ich wyborem. Jednak nie
zawsze tak jest. Problem mo
Ŝ
e pojawi
ć
si
ę
wtedy gdy punktów równowagi
jest wi
ę
cej, tak jak w kolejnej grze danej macierz
ą
−
−
−
−
−
)
9
,
3
(
)
4
,
14
(
)
2
,
8
(
)
5
,
10
(
)
5
,
2
(
)
3
,
5
(
)
7
,
8
(
)
5
,
11
(
)
23
,
18
(
)
2
,
20
(
)
1
,
2
(
)
2
,
1
(
A
NDRZEJ
Z.
G
RZYBOWSKI
Str. 7
W tej grze wyst
ę
puj
ą
dwie pary strategii równowagi: (a
2
,b
2
) oraz
(a
3
,b
4
) . Zauwa
Ŝ
my,
Ŝ
e gracze b
ę
d
ą
tu mieli kłopot z wyborem strategii,
nawet je
ś
li b
ę
d
ą
si
ę
mogli porozumie
ć
. A to dlatego,
Ŝ
e punkt (a
2
,b
2
) jest
lepszy dla gracza I, z kolei punkt (a
3
,b
4
) jest lepszy dla gracza II. Ponadto
Ŝ
aden z punktów równowagi nie jest tworzony przez strategie
bezpiecze
ń
stwa graczy – w przypadku tej gry obie koncepcje prowadz
ą
do
innych rozwi
ą
za
ń
!
Okazuje si
ę
jednak,
Ŝ
e jest wa
Ŝ
na klasa gier, w której taki problem nie
wyst
ę
puje, a ka
Ŝ
dy punkt równowagi jest bardzo rozs
ą
dn
ą
nie budz
ą
c
ą
Ŝ
adnych tego typu w
ą
tpliwo
ś
ci propozycj
ą
wyboru strategii przez graczy. Co
wi
ę
cej jest to propozycja zgodna tak
Ŝ
e z koncepcj
ą
strategii bezpiecze
ń
stwa.
Omówimy t
ę
klas
ę
gier w kolejnym rozdziale.
2.3 Gry macierzowe o sumie zerowej
D
EFINICJA
.
Gr
ę
>
<
N
N
M
M
M
S
S
S
K
K
,
,
;
,
,
,
2
1
2
1
w której
0
2
1
=
+
+
+
N
M
M
M
K
nazywamy gr
ą
o sumie zerowej.
Szczególnie interesuj
ą
ce s
ą
dwuosobowe gry <A, B, M
1
, M
2
>
o sumie
zero. S
ą
one modelami problemów
ś
ci
ś
le antagonistycznych, tzn. takich, w
których gracz I spo
ś
ród mo
Ŝ
liwych wyników gry preferuje wynik A nad B
wtedy i tylko wtedy, gdy gracz II preferuje B nad A.
Dwuosobow
ą
gr
ę
o sumie zerowej ze wzgl
ę
du na zale
Ŝ
no
ść
M
1
=- M
2
mo
Ŝ
emy okre
ś
li
ć
podaj
ą
c jedynie jedn
ą
z macierzy wypłat. Umówiono si
ę
,
Ŝ
e
podajemy macierz wypłat dla gracza I, gracz II dostaje wi
ę
c wypłat
ę
wyra
Ŝ
on
ą
liczb
ą
przeciwn
ą
. Zatem zapis <A, B, M> oznacza,
Ŝ
e
W
YKŁADY Z
T
EORII
G
IER I
D
ECYZJI
Str. 8
2
1
M
M
M
−
=
=
. Oczywi
ś
cie wszelkie poj
ę
cia i koncepcje omówione
wcze
ś
niej zostaj
ą
zachowane, ale wobec nowej umowy zapisujemy je w
zmienionej (dopasowanej do niej) postaci. Poni
Ŝ
ej podajemy definicje
znanych ju
Ŝ
poj
ęć
w wersji dla gier <A, B, M>.
D
EFINICJA
Para strategii
)
,
(
0
0
j
i
b
a
jest punktem równowagi gry <A, B, M> je
ś
li
0
0
0
j
i
j
i
M
M
≤
j
i
M
0
≤
(1.r)
D
EFINICJA
Element macierzy
0
0
j
i
M
spełniaj
ą
cy powy
Ŝ
szy warunek nazywamy punktem
siodłowym
gry.
Zatem inaczej powiemy,
Ŝ
e para
)
,
(
0
0
j
i
b
a
jest w równowadze wtedy i tylko
wtedy, gdy
0
0
j
i
M
jest punktem siodłowym gry. Zauwa
Ŝ
my równie
Ŝ
oczywisty fakt,
Ŝ
e
0
0
j
i
M
jest punktem siodłowym gry wtedy i tylko wtedy,
gdy
i
max
=
=
0
0
0
j
i
j
i
M
M
j
min
j
i
M
0
(2.r)
D
EFINICJA
Strategi
ą
bezpiecze
ń
stwa gracza I nazywamy strategi
ę
o numerze
0
i
dla
której spełniony jest warunek
j
min
=
j
i
M
0
i
max
j
min
ij
M
Strategi
ą
bezpiecze
ń
stwa gracza II nazywamy strategi
ę
o numerze
0
j
dla
której spełniony jest warunek
A
NDRZEJ
Z.
G
RZYBOWSKI
Str. 9
i
max
=
0
ij
M
j
min
i
max
ij
M
D
EFINICJA
Poziom bezpiecze
ń
stwa gracza I nazywamy warto
ś
ci
ą
doln
ą
gry a poziom
bezpiecze
ń
stwa gracza II nazywamy warto
ś
ci
ą
górn
ą
gry. Oznaczmy je
odpowiednio v
oraz
v
.
Zatem zachodzą wzory
i
max
j
min
v
M
ij
=
oraz
j
min
j
max
v
M
ij
=
P
RZYKŁAD
1
−
−
−
−
=
3
1
4
5
2
3
7
3
6
4
6
5
3
2
2
3
2
3
1
2
M
P
RZYKŁAD
2
−
−
−
=
1
4
3
2
2
2
3
2
1
M
T
WIERDZENIE
Dla dowolnej gry macierzowej <A, B, M> zachodzi
v
v
≤
W
YKŁADY Z
T
EORII
G
IER I
D
ECYZJI
Str. 10
D
OWÓD
Dla dowolnej pary i,j , i
∈
{1,…,m} , j
∈
{1,…,n}, zachodzi
≤
ij
M
i
max
ij
M
.
Zatem znak tej nierówno
ś
ci zostanie zachowany je
ś
li znajdziemy minima ze
wzgl
ę
du na j
∈
{1,…,n} po obu jej stronach:
j
min
≤
ij
M
j
min
i
max
v
M
ij
=
Z tego z kolej wynika, ze maksimum lewej strony ze wzgl
ę
du na i
∈
{1,…,m}
spełnia zale
Ŝ
no
ść
i
max
j
min
ij
M
v
≤
Czyli ostatecznie wykazali
ś
my,
Ŝ
e
v
v
≤
.
D
EFINICJA
Je
Ŝ
eli
v
v
=
, to mówimy,
Ŝ
e gra ma warto
ść
v, gdzie v =
v
v
=
T
WIERDZENIE
Je
Ŝ
eli
)
,
(
0
0
j
i
b
a
oraz
)
,
(
1
1
j
i
b
a
tworz
ą
pary strategii w równowadze, to parami
strategii w równaniu s
ą
takie:
)
,
(
1
0
j
i
b
a
i
)
,
(
0
1
j
i
b
a
oraz
=
0
0
j
i
M
=
1
0
j
i
M
=
1
1
j
i
M
0
1
j
i
M
D
OWÓD
.
Z definicji punktu równowagi , wzór (1.r), otrzymujemy
≤
0
0
j
i
M
≤
1
0
j
i
M
≤
1
1
j
i
M
0
1
j
i
M
0
0
j
i
M
≤
Zatem otrzymali
ś
my ci
ą
g równo
ś
ci
=
0
0
j
i
M
=
1
0
j
i
M
=
1
1
j
i
M
0
1
j
i
M
A
NDRZEJ
Z.
G
RZYBOWSKI
Str. 11
Teraz aby pokaza
ć
,
Ŝ
e np. para strategii
1
0
,
j
i
b
a
jest punktem równowagi
wykorzystamy pierwsze dwie z powy
Ŝ
szych równo
ś
ci i ponownie wzór (1.r),
który zastosujemy do punktów równowagi
0
0
j
i
M
oraz
1
1
j
i
M
. Otrzymamy
1
0
1
1
1
j
i
j
i
j
i
M
M
M
=
≤
=
0
0
j
i
M
j
i
M
0
≤
czyli rzeczywi
ś
cie
≤
1
j
i
M
≤
1
0
j
i
M
j
i
M
0
co ko
ń
czy dowód twierdzenia.
T
WIERDZENIE
Je
Ŝ
eli gra ma punkt siodłowy, to para strategii w równowadze jest utworzona
przez strategie bezpiecze
ń
stwa graczy i gra ma warto
ść
.
D
OWÓD
Niech
0
0
j
i
M
b
ę
dzie punktem siodłowym.
v
=
j
min
i
max
≤
ij
M
i
max
≤
≤
0
0
0
j
i
ij
M
M
j
min
≤
j
i
M
0
i
max
j
min
ij
M
= v
Jak wiemy , zawsze zachodzi
v
v
≤
, zatem ostatecznie
v
v
v
=
=
T
WIERDZENIE
Je
Ŝ
eli gra ma warto
ść
, to para strategii bezpiecze
ń
stwa tworzy par
ę
strategii w równowadze.
D
OWÓD
Niech strategiami bezpiecze
ń
stwa b
ę
d
ą
odpowiednio
0
0
,
j
i
b
a
. Zatem
wykorzystuj
ą
c oczywiste nierówno
ś
ci i definicje tych strategii otrzymamy:
W
YKŁADY Z
T
EORII
G
IER I
D
ECYZJI
Str. 12
v
=
i
max
j
min
ij
M
=
j
min
j
i
M
0
§
0
0
j
i
M
§
i
max
0
ij
M
=
j
min
i
max
ij
M
=
v
Z zało
Ŝ
enia
v
v
v
=
=
, zatem w rozwa
Ŝ
anym przypadku powy
Ŝ
ej
wyst
ę
puj
ą
ce nierówno
ś
ci s
ą
równo
ś
ciami i ostatecznie otrzymujemy
j
min
j
i
M
0
=
0
0
j
i
M
=
i
max
0
ij
M
co na podstawie wzoru (2,r) dowodzi prawdziwo
ś
ci tezy twierdzenia.