Teoria Gier i Decyzji - strategie ...

[ Pobierz całość w formacie PDF ]
2.4 Dwuosobowe gry macierzowe o sumie zerowej -
strategie mieszane
Okazuje się, Ŝe często gra macierzowa nie posiada punktu
siodłowego. Jaką strategię naleŜy wówczas przyjąć?
W grach bez punktu siodłowego Ŝadne czyste strategie nie są w
równowadze. Zatem z powyŜszego stwierdzenia moŜna wnioskować, Ŝe
odstępstwo graczy od swoich strategii minimaksowych moŜe być dla nich
opłacalne. Przeanalizujmy następujący przypadek.
Dana jest gra o następującej macierzy wypłat:
M
=
3
1
2
4
Łatwo jest zauwaŜyć, Ŝe nie posiada ona punktu siodłowego.
ZałóŜmy, Ŝe gracz I zastanawia się nad wykorzystaniem strategii
a
2
, swojej
strategii bezpieczeństwa, a gracz II chce wykorzystać swoją strategie
bezpieczeństwa
b
1
. JednakŜe takie proste rozegranie tej gry prowadzi nas do
sytuacji, kiedy jeden z graczy (przypuśćmy, Ŝe jest nim gracz I) przeanalizuje
rozgrywkę w następujący sposób:
JeŜeli mój przeciwnik będzie grał swoją
optymalną strategią b
1
to ja zagram a
1
i w ten sposób zwiększę swoją
wygraną.
JeŜeli jednak w tym samym momencie gracz II domyśli się
rozumowania gracza I, to zamiast zagrać swoją najbezpieczniejszą strategię
b
1
wybierze
b
2
, a w takim przypadku gracz I powinien zagrać jednak
a
2
.
Przyjmując taki sposób rozumowania wpadamy w pętlę domysłów, czyli nie
jesteśmy w stanie jednoznacznie stwierdzić co zagrać. Bo przecieŜ, gdy gra
nie ma punktu siodłowego, to strategie bezpieczeństwa nie są w
równowadze! Co w takiej sytuacji gracze powinni zrobić?
W takiej sytuacji (gdy nie ma punktu siodłowego) wydaje się, Ŝe
W
YKŁADY Z
T
EORII
G
IER I
D
ECYZJI
najlepszym rozwiązaniem dla obu graczy jest wybór swojej strategii w
drodze losowania. Jest to pomysł intuicyjny – ludzie bardzo często odwołują
się w swoich decyzjach do losu, zwłaszcza gdy nie są pewni co wybrać. Jest
teŜ ten pomysł
genialny
- łatwo bowiem dowieść, co uczynimy za chwilę, Ŝe
wybór strategii przez losowanie
zwiększa w rozwaŜanym przypadku poziom
bezpieczeństwa
graczy. Czy jednak losowanie to moŜe odbywać się dowolna
metodą, czy istnieje sposób najlepszy? Na pytania te odpowiemy w dalszym
ciągu wykładu. Najpierw jednak wprowadzimy pewne formalne definicje i
oznaczenia. JuŜ na wstępie do tego rozdziału określiliśmy strategię mieszaną
jako rozkład prawdopodobieństwa na strategiach czystych (nielosowych). W
grach macierzowych, w których zbiory strategii czystych są skończone
rozkłady prawdopodobieństwa mogą być utoŜsamiane z wektorami o
nieujemnych współrzędnych sumujących się do jedności.
RozwaŜmy zatem grę
<A, B, M>,
w której
A
i
B
są zbiorami strategii
czystych graczy I i II o mocach, odpowiednio,
m
i
n
. Zbiór
A*
strategii
mieszanych gracza I jest określony następująco:
∑
=
m
A
*
=
{
Α
=
(
A
a
,
2
,
A
m
)
:
A
i
=
1
"
i
=
1
2
,
m
,
A
i
³
0
i
1
Analogicznie oznaczamy i określamy zbiór strategii gracza II:
∑
=
n
B
*
=
{
Β
=
(
B
2
,
,
B
)
:
B
=
1
"
j
=
i
,
2
,
n
B
³
0
i
n
i
j
1
PoniewaŜ wypłaty graczy podane są w ich uŜytecznościach, a wybory
strategii niezaleŜne, więc zgodnie z własnością B funkcji uŜyteczności
otrzymujemy, Ŝe wypłaty dla gracza pierwszego określone są następująco:
∑∑
m
n
∑∑
m
n
M
(
Β
Α
,
)
=
M
(
a
i
,
b
)
A
i
B
j
=
M
i
A
i
B
j
=
1
j
=
1
=
1
=
1
Str. 2
j
j
i
i
j
 A
NDRZEJ
Z.
G
RZYBOWSKI
a gracz II otrzymuje
−
M
(
Β
Α
,
)
. ZauwaŜmy, Ŝe prawdziwe są równieŜ wzory
∑
m
∑
n
M
(
Α
,
Β
)
=
M
(
i
,
Β
)
A
Α
=
M
(
,
j
)
B
i
j
i
=
1
j
=
1
Oczywiście
A
Í
A*
oraz
B
Í
B*,
gdyŜ strategie czyste moŜemy
utoŜsamić z rozkładami skoncentrowanymi w jednym punkcie:
a
i
º
(
0
2
,
2
,
b
j
º
(
0
2
,
2
,
)
gdzie 1 jest, odpowiednio,
i-
tą i
j
-tą współrzędną w powyŜszych wektorach.
Na przykład jeśli gracz I wybiera strategię mieszaną (0,1,0…,0), to jest to
równowaŜne wyborowi strategii
a
2
i na odwrót.
UWAGA
: W przypadku gdy będziemy chcieli podkreślić, Ŝe gracz uŜywa
strategię czystą, w funkcji wypłaty będziemy wpisywali jedynie jej numer.
Na przykład
M
(A,
j
) oznacza, Ŝe gracz I gra strategię dowolną (mieszaną lub
nie) natomiast gracz drugi gra swoją
j
-tą strategię czystą, zatem
∑
=
m
M
(
Α
,
j
)
=
M
i
j
A
i
1
D
EFINICJA
Grę
<C, D, U>
nazywamy
rozszerzeniem
gry
<A, B, V>
jeśli
A
Í
C ,
B
Í
D
oraz dla kaŜdej pary strategii
a
Î
A
i
b
Î
B
zachodzi:
V
(
a
,
b
)=
U
(
a
,
b
)
Zatem gra w strategiach mieszanych jest rozszerzeniem gry w
strategiach czystych. Wobec tego, Ŝe w nowej grze
<A*,B*,M>
moce
zbiorów strategii są nieprzeliczalne pojawiają się nowe problemy. Zacznijmy
od zapisu definicji strategii bezpieczeństwa. Zgodnie z ogólną definicją A*
jest strategią bezpieczeństwa gracza pierwszego, gdy spełnia warunek:
Str. 3
i
 W
YKŁADY Z
T
EORII
G
IER I
D
ECYZJI
inf
M
(
Α
*
,
Β
)
=
sup
inf
Β
M
(
Α,
Β
)
=
w
Α
oraz B* jest strategią bezpieczeństwa gracza drugiego, gdy:
sup
M
(
Α,
Β
*)
=
inf
sup
M
(
Α,
Β
)
=
w
Β
Α
Α
W powyŜszych określeniach i dalej w tej części wykładu kres górny
brany jest po AÎ
A*
, a kres dolny po BÎ
B
*. Liczby
w
oraz
w
oznaczają
wartość dolną i górną dla gry
<A*,B*,M>
.
Wobec tego, Ŝe oba te zbiory są nieprzeliczalne, nie mamy pewności,
Ŝe owe kresy są osiągane na zbiorach strategii, zatem nie mamy pewności,
czy istnieją strategie bezpieczeństwa graczy oraz czy wartości dolna i górna
rzeczywiście są ich poziomami bezpieczeństwa, tj. czy rzeczywiście tyle
mogą sobie zagwarantować.
Celem dalszej części tego rozdziału będzie pokazanie, Ŝe tak jest. Co
więcej pokaŜemy, Ŝe strategia bezpieczeństwa obu graczy nie tylko istnieją,
ale równieŜ, Ŝe gra w strategiach mieszanych ma zawsze wartość tj.
w
=
w
.
Dowód obu tych twierdzeń będzie jednak odwoływał się do wyników z teorii
programowania liniowego i dlatego przeniesiemy go do kolejnego paragrafu.
Tutaj udowodnimy jeszcze kilka faktów pomocniczych oraz pozostałe
wyniki, które razem złoŜą się na centralne teorii gier o sumie zerowej, zwane
twierdzeniem minimaksowym von Neumanna.
Zaczniemy od udowodnienia lematu, który ma duŜe znaczenie dla
omawianej teorii
L
EMAT
Dla kaŜdej strategii BÎ
B
*:
sup
M
(
Α,
Β
)
=
max
M
(
i
,
Β
)
Α
i
Str. 4
Β
 A
NDRZEJ
Z.
G
RZYBOWSKI
oraz dla kaŜdej strategii AÎ
A
*:
inf
Β
M
(
Α,
Β
)
=
min
j
M
(
Α,
j
)
D
OWÓD
Udowodnimy pierwszą z powyŜszych równości. Dowód drugiej jest
analogiczny.
ZauwaŜmy, Ŝe wobec faktu
A
Í
A*
nierówność
sup
M
(
Α,
Β
)
³
max
M
(
i
,
Β
)
Α
i
jest oczywista. PoniewaŜ liczba strategii gracza I jest skończona zatem
maksimum znajdujące się po prawej stronie powyŜszej nierówności osiągane
jest dla pewnej z nich. Niech to będzie strategia o numerze
l
, czyli
M
(
l
,
Β
)
=
max
i
M
(
i
,
Β
)
Wobec faktu niezaleŜności wyborów strategii, rozkładów brzegowe wektora
A,B) są niezaleŜne. PoniewaŜ wartość
M
dla strategii mieszanych jest
wartością oczekiwaną uŜyteczności uzyskiwanych przy strategiach czystych,
to dla dowolnego AÎ
A
* i kaŜdego ustalonego BÎ
B
* otrzymujemy:
∑
m
∑
m
∑
m
M
(
Α
,
Β
)
=
M
(
i
,
Β
)
A
£
M
(
l
,
Β
)
A
=
M
(
l
,
Β
)
A
=
M
(
l
,
Β
)
=
max
M
(
i
,
Β
)
i
i
i
i
=
1
=
1
i
=
1
Zatem
sup
M
(
Α,
Β
)
£
max
M
(
i
,
Β
)
Α
i
PoniewaŜ nierówność w drugą stronę juŜ wykazaliśmy, więc to kończy
dowód lematu.
Z udowodnionego lematu bezpośrednio wynikają następujące twierdzenie
Str. 5
A,B
(A,B
i
i
[ Pobierz całość w formacie PDF ]