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