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:













=

4

2

1

3

M

Ł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

Str. 2

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:

}

0

,

,

,

1

,

1

:

)

,

,

(

{

*

1

≥

=

∀

=

=

=

∑

=

i

m

i

i

m

a

m

i

A

α

α

α

α

K

K

α

Analogicznie oznaczamy i określamy zbiór strategii gracza II:

1

:

)

,

,

(

{

*

1

=

=

=

∑

=

n

j

i

n

i

B

β

β

β

K

β

n

i

j

,

,

K

=

∀

}

0

≥

j

β

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:

j

m

i

n

j

i

j

i

j

m

i

n

j

i

j

i

M

b

a

M

M

β

α

β

α

∑∑

∑∑

=

=

=

=

=

=

1

1

1

1

)

,

(

)

,

(

β

α

A

NDRZEJ

Z.

G

RZYBOWSKI

Str. 3

a gracz II otrzymuje

)

,

(

β

α

M

−

. Zauwa

ż

my,

ż

e prawdziwe s

ą

równie

ż

wzory

∑

∑

=

=

=

=

n

j

j

i

m

i

j

M

i

M

M

1

1

)

,

(

)

,

(

)

,

(

β

α

α

β

β

α

Oczywi

ś

cie A

⊆A* oraz B⊆B*, gdy

ż

strategie czyste mo

ż

emy

uto

ż

sami

ć

z rozkładami skoncentrowanymi w jednym punkcie:

)

0

,

,

0

,

1

,

0

,

,

0

(

K

K

≡

i

a

)

0

,

,

0

,

1

,

0

,

,

0

(

K

K

≡

j

b

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(

α

α

α

α,j) oznacza,

ż

e gracz I gra strategi

ę

dowoln

ą

(mieszan

ą

lub

nie) natomiast gracz drugi gra swoj

ą

j-t

ą

strategi

ę

czyst

ą

, zatem

∑

=

=

m

i

i

j

i

M

j

M

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

ą

α

α

α

α*

jest strategi

ą

bezpiecze

ń

stwa gracza pierwszego, gdy spełnia warunek:

W

YKŁADY Z

T

EORII

G

IER I

D

ECYZJI

Str. 4

w

M

M

=

=

)

(

inf

sup

)

*

(

inf

β

α,

β

,

α

β

α

β

oraz

β

β

β

β* jest strategi

ą

bezpiecze

ń

stwa gracza drugiego, gdy:

w

M

M

=

=

)

(

sup

inf

*)

(

sup

β

α,

β

α,

α

β

α

W powy

ż

szych okre

ś

leniach i dalej w tej cz

ęś

ci wykładu kres górny

brany jest po

α

α

α

α∈A*, a kres dolny po β

β

β

β∈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*:

)

(

max

)

(

sup

β

,

β

α,

α

i

M

M

i

=

A

NDRZEJ

Z.

G

RZYBOWSKI

Str. 5

oraz dla ka

ż

dej strategii

α

α

α

α∈A*:

)

(

min

)

(

inf

j

M

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

ść

)

(

max

)

(

sup

β

,

β

α,

α

i

M

M

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

)

(

max

)

(

β

,

β

,

i

M

l

M

i

=

Wobec faktu niezale

ż

no

ś

ci wyborów strategii, rozkładów brzegowe wektora

(

α,β

α,β

α,β

α,β) s

ą

niezale

ż

ne. Poniewa

ż

warto

ść

M dla strategii mieszanych jest

warto

ś

ci

ą

oczekiwan

ą

u

ż

yteczno

ś

ci uzyskiwanych przy strategiach czystych,

to dla dowolnego

α

α

α

α∈A* i ka

ż

dego ustalonego

β

β

β

β∈B* otrzymujemy:

)

,

(

max

)

,

(

)

,

(

)

,

(

)

,

(

)

,

(

1

1

1

β

β

β

β

β

β

α

i

M

l

M

l

M

l

M

i

M

M

i

m

i

i

m

i

i

i

m

i

=

=

=

≤

=

∑

∑

∑

=

=

=

α

α

α

Zatem

)

(

max

)

(

sup

β

,

β

α,

α

i

M

M

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

W

YKŁADY Z

T

EORII

G

IER I

D

ECYZJI

Str. 6

i wnioski.

T

WIERDZENIE

Dla dowolnej gry macierzowej <A*,B*,M>

)

(

min

sup

j

M

w

j

α,

α

=

oraz

)

(

max

inf

β

,

β

i

M

w

i

=

W

NIOSEK

1

Strategia

α

α

α

α

∗

∈A* jest strategi

ą

bezpiecze

ń

stwa gracza I wtedy i tylko wtedy,

gdy

)

*

(

min

j

M

w

j

,

α

=

Strategia

β

β

β

β

∗

∈B* jest strategia bezpiecze

ń

stwa gracza II wtedy i tylko wtedy,

gdy

*)

(

max

β

,i

M

w

i

=

W

NIOSEK

2

Pomi

ę

dzy warto

ś

ciami górnymi i dolnymi gier <A,B,M> oraz

<A*,B*,M> zachodz

ą

nast

ę

puj

ą

ce zwi

ą

zki:

v

w

w

v

≤

≤

≤

D

OWÓD

Uzasadnimy tylko drugi wniosek, gdy

ż

poprzednie stwierdzenia s

ą

oczywiste wobec wykazanych wcze

ś

niej faktów.

Nierówno

ść

w

v

≤

jest łatwa do stwierdzenia wobec obserwacji,

ż

e

obie te wielko

ś

ci s

ą

kresami górnymi tej samej funkcji

)

(

min

)

(

j

M

f

j

,⋅

=

⋅

,

przy czym pierwsza z nich jest kresem na zbiorze A druga za

ś

na zbiorze A*

A

NDRZEJ

Z.

G

RZYBOWSKI

Str. 7

i spełniona jest relacja A

⊆A*. Analogicznie mo

ż

na wykaza

ć

prawdziwo

ść

nierówno

ś

ci

v

w

≤

.

Niech teraz

α

α

α

α∈A* i β

β

β

β∈B* b

ę

d

ą

ustalonymi strategiami graczy.

Wtedy

)

(

max

)

(

β

,

β

α,

i

M

M

i

≤

w

i

M

M

i

=

≤

)

(

max

inf

)

(

inf

β

,

β

α,

β

β

w

j

M

j

≤

)

(

min

α,

w

j

M

w

j

≤

=

)

(

min

sup

α,

α

Zatem i trzecia z nierówno

ś

ci jest prawdziwa, co ko

ń

czy dowód

poprawno

ś

ci Wniosku 2.

Zauwa

ż

my,

ż

e ostatni wniosek mówi wprost,

ż

e wprowadzenie

strategii mieszanych mo

ż

e zwi

ę

kszy

ć

poziomy bezpiecze

ń

stwa graczy (nigdy

ich nie zmniejszaj

ą

c). To powa

ż

nie uzasadnia uwzgl

ę

dnienie przez graczy tej

mo

ż

liwo

ś

ci.

T

WIERDZENIE

Je

ż

eli gra <A*,B*,M> ma warto

ść

oraz

α

α

α

α∗∈A* i β

β

β

β

∗

∈B* s

ą

strategiami bezpiecze

ń

stwa graczy w tej grze, to s

ą

one w równowadze

D

OWÓD

Nierówno

ś

ci

*)

(

sup

*)

*

(

)

*

(

inf

β

α,

β

,

α

β

,

α

α

β

M

M

M

≤

≤

s

ą

oczywiste. Je

ż

eli

α

α

α

α∗∈A* i β

β

β

β

∗

∈B* s

ą

strategiami bezpiecze

ń

stwa, to na

W

YKŁADY Z

T

EORII

G

IER I

D

ECYZJI

Str. 8

podstawie Lematu oraz Wniosku 1 mamy zatem

w

i

M

M

j

M

w

i

j

=

≤

≤

=

*)

(

max

*)

*

(

)

*

(

min

β

,

β

,

α

,

α

Z zało

ż

enia istnieje warto

ść

gry,

,

w

w

w

=

=

wi

ę

c powy

ż

sze nierówno

ś

ci s

ą

równo

ś

ciami i otrzymujemy

)

*

(

inf

)

*

(

min

*)

*

(

*)

(

max

*)

(

sup

β

,

α

,

α

β

,

α

β

,

β

α,

β

α

M

j

M

M

i

M

M

j

i

=

=

=

=

czyli dla dowolnych

α

α

α

α∈A* i β

β

β

β∈B*

)

*

(

*)

*

(

*)

(

β

,

α

β

,

α

β

α,

M

M

M

≤

≤

To ko

ń

czy dowód.

W

NIOSEK

3

Je

ż

eli w grze <A*,B*,M> strategie

α

α

α

α∗ i α

α

α

α^ s

ą

strategiami

bezpiecze

ń

stwa gracza I, a strategie

β

β

β

β

∗

i

β

β

β

β^ s

ą

strategiami bezpiecze

ń

stwa

gracza II, to

M(

α

α

α

α∗,β

β

β

β

∗

)=M(

α

α

α

α∗,β

β

β

β^)=M(α

α

α

α^,β

β

β

β^)=M(α

α

α

α^,β

β

β

β

∗

)

i wszystkie wskazane pary strategii s

ą

w równowadze

Powy

ż

szy wniosek jest oczywist

ą

konsekwencj

ą

poprzedniego

twierdzenia i jego dowód pomijamy. Czytelnik zechce go przeprowadzi

ć

jako

ć

wiczenie.

T

WIERDZENIE

Je

ż

eli gra <A*,B*,M> ma warto

ść

oraz

α

α

α

α∗∈A* i β

β

β

β

∗

∈B* s

ą

w równowadze to s

ą

one te

ż

strategiami bezpiecze

ń

stwa graczy w tej grze.

A

NDRZEJ

Z.

G

RZYBOWSKI

Str. 9

D

OWÓD

Je

ś

li

α

α

α

α∗∈A* i β

β

β

β

∗

∈B* s

ą

w równowadze to

)

(

inf

sup

)

*

(

inf

*)

*

(

*)

(

sup

)

(

sup

inf

β

α,

β

,

α

β

,

α

β

α,

β

α,

β

α

β

α

α

β

M

M

M

M

M

≤

=

=

≤

Poniewa

ż

z zało

ż

enia

,

w

w

=

wi

ę

c powy

ż

sze nierówno

ś

ci s

ą

rozwa

ż

anym przypadku równo

ś

ciami i otrzymujemy w szczególno

ś

ci

)

(

inf

sup

)

*

(

inf

β

α,

β

,

α

β

α

β

M

M

=

)

(

sup

inf

*)

(

sup

β

α,

β

α,

α

β

α

M

M

=

To ko

ń

czy dowód.

Dwa ostatnie twierdzenia i wniosek 3 s

ą

niezwykle wa

ż

ne dla

omawianej teorii. Mówi

ą

one,

ż

e koncepcje rozwi

ą

zania oparte na poj

ę

ciu

strategii bezpiecze

ń

stwa nie s

ą

w sprzeczno

ś

ci z koncepcj

ą

opart

ą

na punkcie

równowagi - gracz nie b

ę

dzie wi

ę

c miał dylematu, któr

ą

z tych koncepcji

wybra

ć

. Co wi

ę

cej, nawet wyst

ą

pienie wi

ę

kszej liczby ró

ż

nych strategii

bezpiecze

ń

stwa gracza nie prowadzi do dylematu, gdy

ż

wszystkie one

gwarantuj

ą

dokładnie ta sam

ą

wypłat

ę

.

T

WIERDZENIE

Je

ż

eli macierz M ma punkt siodłowy

0

0

j

i

M

, to strategie czyste i

0

,j

0

s

ą

strategiami bezpiecze

ń

stwa w grze <A*,B*,M>

D

OWÓD

Z wniosku 2 i z Twierdzenia C3 otrzymujemy

0

0

j

i

M

v

w

w

v

=

=

=

=

W

YKŁADY Z

T

EORII

G

IER I

D

ECYZJI

Str. 10

Teraz, aby wykaza

ć

,

ż

e i

0

jest strategi

ą

bezpiecze

ń

stwa gracza I wystarczy

zauwa

ż

y

ć

,

ż

e

w

M

j

i

M

j

i

j

=

=

0

0

)

(

min

0

,

gdzie pierwsza z równo

ś

ci jest konsekwencj

ą

tego,

ż

e

0

0

j

i

M

jest punktem

siodłowym.

Analogicznie dowodzimy,

ż

e j

0

jest strategi

ą

bezpiecze

ń

stwa gracza

II.

Ostatnie twierdzenie pokazuje,

ż

e koncepcje gry w strategiach

czystych i w strategiach mieszanych nie s

ą

koncepcjami pozostaj

ą

cymi w

konflikcie. Jakiekolwiek rozwi

ą

zanie uzyskane w grze w strategiach czystych

jest te

ż

rozwi

ą

zaniem w grze w strategiach mieszanych. Zatem rozszerzanie

gry <A,B,M> do gry <A*,B*,M> ma na celu jedynie znalezienie rozwi

ą

zania

w przypadku, gdy ta pierwsza go nie posiada.

Aby zamkn

ąć

nasze rozwa

ż

ania na temat gier o sumie zero pozostało

nam jedynie udowodni

ć

,

ż

e gry <A*,B*,M> maj

ą

zawsze rozwi

ą

zanie, czyli

ż

e zawsze istniej

ą

strategie bezpiecze

ń

stwa graczy i gra zawsze ma warto

ść

.

Jest to tre

ś

ci

ą

kolejnego paragrafu.

2.4 Twierdzenie minimaksowe Johna von Neumanna