Podstawy teorii gier

1. Podstawowe pojęcia teorii gier

Teoria gier

to jest rozdział badań operacyjnych, który zajmuje się opracowaniem

metod podejmowania decyzji w warunkach sytuacji konfliktowych i warunkach
niepewności.

Zbiór reguł definiujących jednoznacznie kolejność działalności jednej ze stron

(jednego z graczy) w sytuacji konfliktowej nazywa się

strategią

.

„

Grą

” nazywa się zbiór omówionych wcześniej graczami reguł i warunków.

Jeśli n gracze G

1

, G

2

, ... , G

n

, przejmują udział w grze, wtedy podstawowe zadanie

teorii gier brzmi: jak powinien postępować gracz z numerem j (j=1, 2, ... , n)
dla osiągnięcia swojego celu – maksymalizacji wygranej?

Przepuśćmy dalej, że w końcu gry każdy gracz G

j

otrzymuje kwotę v

j

, którą

nazywamy wygranej w tej grze. Jeżeli

v

j

>0

, to gra jest

wygrana

graczem G

j

, jeśli

v

j

<0

, to

przegranej

graczem G

j

, a jeśli

v

j

= 0

, to gra skończyła się

remisem

.

W dużej ilości przypadków mamy

gry o sumie zero

: v

1

+ v

2

+ ... + v

n

= 0. W

takich grach suma wygranej przechodzi od jednego gracza do drugiego, bez
wykorzystania zewnętrznych źródeł.

W takich zadaniach suma wygranej jest stała, zmienia się tylko suma wygranej

każdego gracza. W przeciwnym przypadku mamy grę o sumie niezerowej.

W grze może brać udział dwóch lub więcej graczy lub koalicji.

Poniżej rozważamy:

— gry dwuosobowe o sumie zero, w tym tzw. gry z naturą,
— gry dwuosobowe o sumie dowolnej, niekooperacyjne i kooperacyjne,
— gry wieloosobowe, niekooperacyjne i kooperacyjne.

Podstawa matematycznej teorii gier jest schemat gry dwuosobowej z sumą zero. Jest to gra
ściśle konkurencyjna, nie ma w niej miejsca na negocjacje między graczami — co jeden z nich
wygrywa, co drugi przegrywa. Jeżeli w grze ściśle konkurencyjnej każdy z graczy dysponuje
jedynie skończoną liczbą strategii, to nazywa się grą macierzową. Optymalne postępowanie
obu graczy określone przez teorię gier ma charakter zasady stabilności: każdemu z graczy
niewygodnie jest zmieniaé swoja strategie, jeżeli jego przeciwnik pozostawi swoją strategię nie
zmieniona.

W grach dwuosobowych o sumie dowolnej wypłaty dla graczy określa się przy każdym
podjęciu decyzji, przy czym interesy obu graczy nie są (nie musza być) dokładnie przeciwne,
bardzo często obaj mogą nawet zyskać przez współpracą. Ponieważ zyski jednego gracza nie
muszą być równe stratom drugiego, to wypłaty każdego z nich zapisujemy w osobnej macierzy
(tablicy), skąd bierze się nazwa gry dwumacierzowe.
Rozróżnią się dwa rodzaje gier dwumacierzowych: 1) niekooperacyjne oraz 2) kooperacyjne.

W grach dwumacierzowych niekooperacyjnych jakiekolwiek porozumienie (np.
skorelowane strategie czy wypłaty uboczne) jest zabronione.

W przypadku dwumacierzowych gier kooperacyjnych różnego rodzaju współpraca między
obu graczami jest dozwolona.

Teoria wieloosobowych gier niekooperacyjnych niewiele różni się od teorii dwuosobowych
gier niekooperacyjnych o sumie dowolnej. W przypadku wieloosobowych gier kooperacyjnych
występuje pojęcie koalicji, która może powstać i utrzymać się przez pewien czas tylko pod
warunkiem, że poszczególni jej członkowie powinni osiągnąć pewnego rodzaju równowagę lub
stabilność.

2. Gry macierzowe o sumie zero

W ogólnym przypadku gra macierzowa
definiuje się przez prostokątną macierz
wymiaru m x n. Numer i wiersza macierzy
odpowiada numeru strategii A

i

gracza P, oraz

numer kolumny B

j

odpowiada numeru

strategii gracza D.

11

12

1

21

22

2

1

2

...
...

...

... ... ...

...

n

n

m

m

mn

a

a

a

a

a

a

A

a

a

a































B

1

B

2

...

B

n

A

1

a

11

a

12

...

a

1n

A

2

a

21

a

22

...

a

2n

...

...

...

...

...

A

m

a

m1

a

m2

...

a

mn

Elementy macierzy a

ij

są wartości rzeczywiste i

odpowiada sumie, wygranej przez graca P u gracza
D, jeśli P wybiera strategie A

i

, oraz D wybiera

strategie B

j

. Macierz A zwykle nazywa się macierzą

wypłat.

Przykład. Rzucanie monety. Pierwszy gracz P

wybiera jedną z dwóch stron monety. Drugi gracz D
nie znając wyboru pierwszego, też wybiera jedną ze
stron monety. Reguły gry są następujące: gracz D
zapłaci 1 zł graczowi P, jeśli po jednoczesnym rzucaniu
monet graczami P i D wypadli takie same stronę
(orzeł-orzeł lub reszka-reszka), w przeciwnych
przypadkach (orzeł-reszka lub reszka-orzeł) 1 zł płaci
gracz P graczowi D (gracz P wygrywa (–1) zł). Przy
takim przypuszczeniu mówimy, że gracz D gra na
minimum, oraz gracz P – na maksimum.

Strategii

graczy

D

orzeł

reszk

a

P

orzeł

1

-1

reszka

-1

1

maxmin

ij

j

i

a

a



minmax

ij

i

j

b

a



Dolną czystą ceną gry (maksyminem) nazywa się

wartość

Górną czystą ceną gry (minimaksem) nazywa się

wartość

Strategii graczy, odpowiadające maksyminu (minimaksu), nazywają się straregii
maksyminowymi (minimaksowymi).

Przykład. Znaleźć się strategii maksyminowe i minimaksowe w grze macierzowej:

3

-3

4

6

3

8

7

4

5

1

4

8

4

6

2

9

B

1

B

2

B

3

B

4

a

A

1

3

-3

4

6

-3

A

2

3

8

7

4

3

A

3

5

1

4

8

1

A

4

4

6

2

9

2

b

5

8

7

9

Dla każdego wiersza znajdziemy najmniejszą wartość i
zapiszemy w kolumnę a: (-3, 3, 1, 2).

To oznacza, że dla dowolnej strategii gracza D najgorsza

wygrana gracza P będzie odpowiednie (-3, 3, 1, 2). Z
drugiej strony, gracz P powinien wybrać taką strategie
(wiersz), żeby maksymalizować swoją wygraną. Wtedy a
= max(-3, 3, 1, 2) = 3 i strategią maksyminową dla gracza
P będzie strategia A2.

Analogicznie znajdziemy minimaksową strategie gracza

D. Ponieważ gracz D wybiera strategii według kolumn,
wtedy w najgorszym przypadku on może przegrać
odpowiednie 5, 8, 7, 9. Dla minimalizacji przegranej gracz
D wybiera strategię dla min(5, 7, 8, 9), tj. minmaksowi: b =
min(5, 7, 8, 9) = 5. Z macierzy wypłat widać, że strategią
minimaksową gracza D będzie B1.

Sytuacją równowagi a = b reprezentuje

punkt

siodłowy

, utworzony przez pary strategii Ai i Bj

odpowiednio graczy P i D, przy których osiągana jest
relacja:

maxmin

minmax

ij

ij

j

i

i

j

a

a



3. Czysty i mieszany strategii

Wyróżniają strategii czyste i mieszane.

Czysta strategia

Ai (i=1,2,...,m) pierwszego gracza P (czysta strategia Bj

(j=1,2,...,n) drugiego gracza D) — są to możliwa strategia pierwszego (drugiego)
gracza wybrana z prawdopodobieństwem p=1.





1

2

; ;...; ;...;

i

m

p

p p

p

p



0 ( 1,2,..., )

i

p

i

m





1

1

m

i

i

p











1

2

; ;...; ;...;

j

n

q

q q

q

q



1

1

n

j

j

q







Mieszaną strategią

pierwszego (drugiego) gracza nazywa się wektor

, gdzie

i

(wektor

, gdzie

Ponieważ gracze wybierają swoje czyste strategii losowo i niezależnie od drugiego
graczy, gra ma przypadkowy charakter i wielkość wygranej (przegranej) też będzie
wartością losową. Wtedy średnia wartość wygranej (przegranej) — wartość
oczekiwana — jest funkcją od mieszanych strategii р, q:

1

1

( , )

m

n

ij i j

i

j

f p q

a pq









Czyste strategii gracza wchodzące do jego optymalnej mieszanej strategii z

prawdopodobieństwami nie równymi zero, nazywają się aktywnymi strategiami
gracza.

Jest prawidłowe twierdzenie o aktywnych strategiach (bez dowodu).
Twierdzenie. Jeśli jeden z graczy wykorzystuje swoją optymalną mieszaną

strategię, to jego wygrana zostanie niezmiennej i równa się cenie gry niezależnie
od tego, jaką strategie stosuje inny gracz, jeżeli tylko on nie wychodzi za przedziały
swoich aktywnych strategii.

Na podstawie twierdzenia rozwiązanie gry macierzowej będzie uproszczono, jeśli

wyjaśnić dominowanie jednych strategii nad innymi.

Przykład. Uprościć grę macierzową
Rozwiązanie. Ponieważ elementy drugiego i czwartego

wiersza są równe, tj. mamy dwa dublujących się wierszy.
Wyeliminujemy, na przykład, czwarty wiersz.

Porównujemy elementy wierszy. Wszystkie elementy

drugiego wierszu są mniejszy od odpowiednich elementów
trzeciego wierszu. Wtedy strategia A

2

jest niewygodna

graczowi P. Wyeliminujemy również drugi wiersz.

Porównujemy elementy kolumn. Elementy pierwszej

kolumny są dominujące nad elementami trzeciej i szóstej
kolumny (są najmniejszy). Wyeliminujemy 3-cią i 6-tą
kolumnę. Analogicznie, elementy drugiej kolumny są
dominujące nad elementami czwartej kolumny. Graczowi D
jest niewygodnie wykorzystać strategii B

3

, B

4

, B

6

.

Otrzymujemy uproszczoną macierz gry:

Jeżeli potrzebujemy macierz z dodatnimi elementami,

wystarczy dodać do wszystkich elementów, na przykład,
wartość +4.

-4 -2 2

3

5

1

2

1

5

-4 -2

5

1

2

7

1

2

4

3

0

1

0

3

5

6

7

1

9

1

2

4

3

0

1

0

2

1

3

6

5

4

4. Metoda Brown’a rozwiązania zadań teorii gier

Krok gracza

2

1

2

3

4

5

6

7

8

9

10

2

0

9

6

9*

9

9

9

15

21*

23*

23*

23*

23

Krok

gracza

1

1

3

6

0

6

9*

12*

15*

15*

15

16

19

22

25*

4

2

1

3

1

3

5

7

10

13

17

19

21

23

9

9

12

15

15

21

23

23

23

25

max

1

5

1

4

2

1*

3

1

min

4

5

2

6

2*

10

9

2

0

0

3

7

5*

16

9

5

4

8

8*

22

9

8

5

9

11

28

9*

9

0

3

1

1

6

10

14

34

9*

9

7

12

*

14

43

15

12

8

14

14*

52

21

14

9

16

14*

61

27

14

10

18

14*

70

33

14

1

6

1

2

9

15

5

5

v

 

1 4 0

0 3 1 1

, ,

,

, , ,

5 5 5

5 5 5 5

x

y





























14

25

10

10

v

 

5 5 0

1 6 1 3

,

,

,

,

,

,

10 10 10

10 10 10 10

x

y





























Stopień przybliżenia do rozwiązania zależy od wyboru pierwszego kroku i od ilości
kroków. Na przykład, dla n=5

n=10

5. Zadania teorii gier a zadania planowania liniowego

Niech mamy grę rozmiarem m x n z macierzą { aij } :

11

12

1

21

22

2

1

2

...
...

...

... ... ...

...

n

n

m

m

mn

a

a

a

a

a

a

A

a

a

a



































*

*

*

*

*

1

2

; ;...; ;...;

i

m

p

p p

p

p







*

*

*

*

*

1

2

; ;...; ;...;

j

n

q

q q

q

q



11 1

21 2

1

12 1

22 2

2

1

1

2

2

...
...

...

...

m

m

m

m

n

n

mn m

a p a p

a p

v

a p a p

a p

v

a p a p

a p

v



 









 













 





1

1,

0, 1,2,..., .

m

i

i

i

p

p

i

m











Zaznaczymy przez

i

optymalne mieszane strategii graczy P i D. Strategia р* gracza P gwarantuje

jemu wygraną nie niższą niż v niezależnie od wyboru strategii B

j

graczem D. Ten fakt

możemy zapisać w postaci:

gdz

ie

Analogicznie, strategia q* gracza D gwarantuje jemu przegraną nie wyższą niż v
niezależnie od wyboru strategii Ai graczem P. Ten fakt możemy zapisać w postaci:

11 1

12 2

1

12 1

22 2

2

1 1

2 2

...
...

...

...

n n

n n

m

m

mn n

a q a q

a q

v

a q a q

a q

v

a q a q

a q

v



 









 













 





gdzie

1

1,

0, 1,2,..., .

n

j

j

j

q

q

j

n











,

, ( 1,2,..., ; 1,2,..., )

j

i

i

j

q

p

x

y

i

m j

n

v

v









11 1

21 2

1

12 1

22 2

2

1

1

2

2

...

1

...

1

...

...

1

m m

m

m

n

n

mn m

a x a x

a x

a x a x

a x

a x a x

a x



 









 













 





1

1

,

0, 1,2,..., .

m

i

i

i

x

x

i

m

v











Przekształcimy układy nierówności. Dla tego podzielmy nierówności na v>0 i
wprowadzimy zaznaczenia

Otrzymuj

emy:

gdzie

11 1

12 2

1

12 1

22 2

2

1 1

2 2

...

1

...

1

...

...

1

n n

n n

m

m

mn n

a y a y

a y

a y a y

a y

a y a y

a y



 









 













 





gdzie

1

1

,

0, 1,2,..., .

n

j

j

j

y

y

j

n

v











v

1

v

Ponieważ gracz P dąży do maksymalizacji ceny gry

, wtedy

będzie minimalizowana

Optymalna mieszana strategia gracza D jest dualną do zadania PL dla gracza P:

1

v

będzie

maksymalizowana.

Rozwiązując parę dualnych zadań PL metodą simplex (lub graficznej dla dwóch
zmiennych), znajdziemy:

*

*

*

*

*

*

*

*

1

1

1

1

1

1

,

,

, ( 1,2,..., ; 1,2,..., )

j

i

i

j

m

n

m

n

i

j

i

j

i

j

i

j

y

x

v

p

q

i

m

j

n

x

y

x

y



























