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.