33254

Evropský sociální fond Praha & EU: Investujeme do vaší budoucnosti

Tento materiál vznikl díky Operačnímu programu Praha Adaptabilita CZ.2.17/3.1.00/33254

Manažerské kvantitativní metody II - přednáška č.11 Teorie her

Teorie her 1926 von Neumann, Morgenstern – zakladatelé teorie her 1996 J.Nash dostal Nobelova cenu Model konfliktní rozhodovací situace (RS) I R  1,2,...m I I  1,2,...n

množina racionálních účastníků RS

množina indiferentních účastníků RS

X  X 1 xX 2 x... X m

množina možných strategií racionálních účastníků

Y  Y1 xY2 x...Yn

množina možných strategií indiferentních účastníků

Z1 , Z 2 ,...Z m

efekty, které racionální účastníci od rozhodování očekávají

Dosud jsme viděli rozhodovací situace tohoto typu: I R  1

I R  1, I I  1

 lineární programování, dynamické programování  stochastické programování

Teorie her Pojmový aparát více racionálních účastníků  konflitk hra...konfliktní rozhodovací situace hráč...subjekt rozhodování strategie...množina alternativ bod hry...vektor přijatých strategií X 1  x1 j 

X 2  x2 j  ... X m  xmj 

 X  x1 j , x2 j ,...xmj 

výhra...dosažená hodnota účelové funkce

Teorie her Typy her Konečné hry – množiny Xj jsou konečné Konečné hry – množiny Xj jsou nekonečné m

Hry s konstantním součtem výhry – platí-li pro každé x  X , že  zi  K i 1 Hry s nulovým součtem výhry – platí-li pro každé x  X , že K  0 Hra v normálním stavu – platí-li I I  0 m

Hra antagonistická – co jeden získá, druhý ztratí m Hra neantagonistická -  zi není konstantní i 1

I R  m1

z i 1

i

K

Teorie her Antagonistické hry Hra 2 hráčů v normálním tvaru Zjednodušený zápis

I R  1,2; X 1  x1 j , X 2  x2 j , z1 , z2 z1  z2  K

I R  i

X 1  i

i  1,2 i  1,2,...m j  1,2,...n

z1 i, j 

výhra 1.hráče

X 2   j

z 2 i, j 

výhra 2.hráče

závislé na volbě strategie i-tého a j-tého hráče, protože

z1 i, j   z2 i, j   K

z2 i, j   K  z1 i, j 

Lze pracovat jen s výhrou například 1.hráče z1 i, j   aij

Teorie her Antagonistické hry Tedy: I R  1,2; X1 , X 2 , z1 i, j   aij Výhry lze zapsat do matice a11a12...a1n  a a ...a  A   21 22 2 n  ...    a a ... a  m1 m 2 mn 

maticová výhra

Pojem optimální strategie i, j Každý usiluje o maximalizaci své výhry. strategie je optimální tehdy, jestliže odchylka od ní znamená zhoršení výhry za předpokladu, že druhý zvolí optimum. Tedy:

    z i, j   z i, j  z1 i, j  z1 i, j 2

2

(1) (2)

Teorie her Antagonistické hry Je-li K=0, pak platí, že z1 i, j    z 2 i, j 

    z i, j   z i, j  z i, j   z i, j   z i, j 

 z 2 i, j   z 2 i, j

 

1

1

1

1

1

(3)

Vektor x  i, j , který splňuje rovnici (3), je řešením hry a strategie i, j jsou čisté strategie.

Teorie her Antagonistické hry Postup nalezení i, j 1.hráč

2.hráč

Volbou i usiluje o maximalizaxi aij MAXIMALIZUJÍCÍ HRÁČ Minimálně může získat

min aij 

Volbou j maximalizuje K-aij, tj. minimalizuje aij MINIMALIZUJÍCÍ HRÁČ Volbou i může 1.hráč získat maximálně

max aij  i

j

To chce 2.hráč volbou j minimalizovat, tedy

a to maximalizuje, tedy

max min a  i

j

ij

min max a  j

i

ij

Teorie her Antagonistické hry Lze dokázat, že

max min a   min max a  j

i

Důkaz:

ij

i

j

ij

min aij   aij j

max aij   aij i

 min aij   max aij  j

i

Levá strana je nezávislá na volbě j Pravá strana je nezávislá na volbě i

min aij   min max aij  j

j

i

max min a   min max a  i

j

ij

j

i

ij

Slovně: Největší z výher, které se snaží 1.hráč dosáhnout nemůže překročit největší výhru, kterou se snaží 2.hráč minimalizovat.

Teorie her Antagonistické hry aij   min max aij  pak má hra řešení v čistých strategiích i, j Platí-li max min j i j i Postup: i\j

1

2

... n

1

a11

2

a21 a22 ... a2n

min aij 

i\j 1

j

a12 ... a1n

...

...

...

... ...

m

am1 am2 ... amn

max aij 

max min a  i

j

j

i

ij

4

min j

240 300 200 390 200

2

180 240 120 330 120

3

280 360 240 480 240

4

90

ij

i

min max a 

3

1

max

i

2

150 0

240 0

280 360 240 480 240 Dvojice (3,3) je řešením. Výhra 1.hráče je 240.

Teorie her Antagonistické hry

min aij min max aij  max Pokud platí jen, že j i j i nemá hra řešení v čistých strategiích. Lze ho najít v tzv. smíšených strategiích. Jiná situace. Nehledáme 1 řešení, ale jejich posloupnost. tedy, pro případy opakovaných rozhodnutí, v nichž hráči střídají strategie tak, aby v průměru m dosáhli maximální výhry. X 1  x ; X  1;X  0 X 1 1i

 i 1

1i

1i

X 2  x2 j ;  X 2 j  1;X 2 j  0 n

j 1

1i

X2 j 1

Xij – pravděpodobnosti, s nimiž budou hráči strategie střídat. i\j 1

2

3

4

min j

1

210 300 240 500 210

2

200 410 280 200 120

3

240 400 250 30

max i

240 410 280 500 min max  240 j 1

i 3

30

max min  210 i 1

j 1

Teorie her Antagonistické hry Střední hodnota výhry

z   x1i  aij  x2 j i

j

z T x1  A  x2

Von Neumann: Každá hra má řešení ve smíšených strategiích. Důkaz (a zároveň návod na řešení): Nechť aij > 0 (toho lze dosáhnout přičtením konstanty), pak lze pro zadaný x1 najít takové z, pro které pro všechna x2  X 2 platí nerovnost

z T x1  A  x2

Teorie her Antagonistické hry Stačí, aby nerovnost platila pro jednotlivé vektory, musí pak platit i pro jejich lineární kombinace. x2  1,0...0

 0,1...0 ...  0,0...1

 vektory čistých strategií

x11, x12 ,...x1m a11a12...a1n

 1   z a a ...a     21 22 2 n   0  ...  ...     am1am 2 ...amn  0 

x11, x12 ,...x1m  a11a12...a1n

x11, x12 ,...x1m  a11a12...a1n

 0   z a a ...a     21 22 2 n   1  ...  ...     am1am 2 ...amn  0 

......

a11  x11  a21  x12  ...  am1  x1m  z a12  x11  a22  x12  ...  am 2  x1m  z ... a1n  x11  a2 n  x12  ...  amn  x1m  z

T

x1  A  e  z

1  1  e  ...   1 

m

 0   z a a ...a     21 22 2 n   0  ...  ...     am1am 2 ...amn  1 

Teorie her Antagonistické hry Analogicky pro zadaný x2 lze najít z, pro které pro všechna x1  X 1 platí nerovnost

z T x1  A  x2 Opět stačí dokázat platnost pro jednotlivé vektory x1  1,0...0

 0,1...0  vektory čistých strategií ...  0,0...1

1,0...0 a11a12...a1n

  x21   z a a ...a   x   21 22 2 n    22  ...  ...      am1am 2 ...amn   x2 n 

0,0...1 a11a12...a1n

0,1...0 a11a12...a1n

  x21   z a a ...a   x   21 22 2 n    22  ...  ...      am1am 2 ...amn   x2 n 

  x21   z a a ...a   x   21 22 2 n    22  ...  ...      am1am 2 ...amn   x2 n 

......

a11  x21  a12  x22  ...  a1n  x2 n  z a21  x21  a22  x22  ...  a2 n  x2 n  z ... am1  x21  am 2  x22  ...  amn  x2 n  z

A  x2  f  z

1  1  f   ...   1 

n

Teorie her Antagonistické hry

x1  A  e  z / :z > 0  x1i  x1i  X 1 z  T x1  A  e

A  x2  f  z

T

m

x

1i

i 1

1

x2 j z

 x2 j  X 2

/ :z > 0 

 A  x2  f n

x

/ :z > 0

j 1

m

1  x   1i z i 1

2j

n

 x j 1

2j

1 

/ :z > 0

1 z

1.hráč chce maximalizovat svou výhru, tedy minimalizovat 1/z 2.hráč chce minimalizovat výhru 1.hráče, tedy maximalizovat 1/z  dvojice primárních m n a duálních úloh min  x1i i 1



x1  A  e  x1  0

T

max  x2 j j 1

 A  x2  f  x2  0

Teorie her Antagonistické hry 12 0

6

0

16 -4

6

-4

8

8

10≠8 nemá řešení v čistých strategiích 

10

20 0

10

12 16 14

12 10 8

16 12 10

10   x12   x13  min z1  x11   20 x12   12 x13  1 16 x11

  x22   x23  min z 2  x21   4 x22   10 x23  1 16 x21

  0 x12   16 x13  1 4 x11   10 x12   14 x13  1 10 x11

  0 x22   10 x23  1 20 x21   16 x22   14 x23  1 12 x21

 0 x11   0,0125 x12

  0,05 x21   0,025 x22

  0,0605 x13

z 2  0,075

z1  0,075

x21  0,05 / 0,075  0,666

x12  0,0125 / 0,075  0,167

x22  0,025 / 0,075  0,334

x13  0,0605 / 0,075  0,833

16 4

Teorie her Hry s nekonečným součtem her – nejsou už v přímém antagonistickém rozporu Dvě matice:

A  aij  B  bij 

aij  z1 i, j 

Příklady: McDonalds X KFC město X majitelé pozemků a11a12...a1n  a a ...a  A   21 22 2 n  ...    a a ... a  m1 m 2 mn 

b11b12...b1n  b b ...b  B   21 22 2 n  ...    b b ... b  m1 m 2 mn 

bij  z2 i, j 

Teorie her Hry s nekonečným součtem her Postup hledání i, j z1 i, j  max z1 i, j

 

    z i, j   max z i, j  i

2

j

2

V matici A najdeme sloupcová maxima  R1 V matici B najdeme řádková maxima  R2 Průnik RR= R1∩ R2 je množina rovnovážných bodů, ale • může jich být více • výhry mohou mít různý poměr mezi z1 a z2

  pro nějž platí: pro všechny rovnovážné body i, j  R  R  R i, j  z i, j   z i, j  je-li 1  K z i, j   z i, j  Někdy pomůže dominující rovnovážný bod i, j 1

1

2

1

2

2

D

Teorie her Hry s nekonečným součtem her – příklady s jedním rovnovážným bodem A

B

i\j

1

2

1

2

max (1,1)

1

10 0

4

0

4

2

9

13 10 13

4

(2,1)

R1  R2  1,1, 2,1 1,1, 2,2  1,1 Jeden rovnovážný bod (1,1)  K

max 10 4 (1,1)(2,2)

A

B

i\j

1

2

1

2

max (1,1)

1

10 0

4

0

4

2

9

13 14 14

4

max 10 4 (1,1)(2,2)

(2,2)

R1  R2  1,1, 2,2 1,1, 2,2  1,1, 2,2 Zvolí-li 1.hráč 1 a 2.hráč 2  (1,2)=0 Sejdou se na nejhorším výsledku.

Teorie her Hry s nekonečným součtem her – příklady s jedním rovnovážným bodem A

B

i\j

1

2

1

10 0

12 2

12

(1,1)

2

9

5

6

(2,2)

4

max 10 4 (1,1)(2,2)

1

2

6

max

R1  R2  1,1, 2,2 Dominuje (1,1)

z1 2,2 z1 1,1

z 2 2,2 z1 1,1

410 612

Teorie her Hry s nekonečným součtem her – více rovnovážných bodů Je-li jich více, může jít o záměnné rovnovážné body Jde o body, u nichž se hodnoty z1 a z2 nemění, dosadíme-li za i a j libovolné body z množiny RD, nechť je to RZ Řešením mohou být optimální rovnovážné body. Jde o body patřící do průniku RZ∩ RD Pokud RD = (0) lze opět najít řešení ve smíšených strategiích RR  RD  RZ  RZ  RD  optimální rovnovážný bod

Teorie her Hry s nekonečným součtem her R1  R2  RR 1 bod  K

 

více bodů i, j

dominující RD

  z i, j   z i, j  z i, j   z i, j 

RD i, j 1

2

1 dominující bod  K

1

2

záměnné RZ - Hodnoty z1 a z2 se nezmění,

 

dosadíme-li za i a j libovolné strategie z RD i, j optimální RO

RO  RZ  RD

Teorie her Hry s nekonečným součtem her – příklad s více rovnovážnými body A

B

i\j

1

2

3

1

2

3

max

1

6

7

16 6

8

14

14

(1,3)

2

7

13 8

13

8

13

(2,2)

3

16 8

6

14

(3,1)

6

8

14 7

max 16 13 16 (3,1) (2,2) (1,3) Záměnné (3,1) z1+z2=16+14=30 Záměnné (1,3) z1+z2=16+14=30  Dominují bodu (2,2) = 13+13=26 Pokud se nedohodnou , mohou se sejít na nejhorším výsledku: 1.hráč volí (1,3)  6+6=12 2.hráč volí (3,1)  6+6=12

R1  R2  1,3, 2,2, 3,1

Teorie her Hráči nejsou v antagonistickém rozporu, nemusejí tajit rozhodnutí náhodným pokusem. Smíšené rozšíření je tedy přijatelné v případech, kdy nemáme řešení jiné. 1.hráč T x1  x11, x12 ,...x1m 

2.hráč T x2   x21, x22 ,...x2 n  n

m

 x 1 A  a 

 x 1 B  b 

střední hodnota výhry: T x1  A  x2  z1

střední hodnota výhry: T x1  B  x2  z2

i 1

1i

j 1

ij

2j

ij





Má-li být bod x1 , x2 rovnovážný bod, musí platit nerovnosti: T

x1  A  x2 T x1  A  x2  z1 T x1  A  x2  z1

T

x1  B  x2 T x1  B  x2  z2 T x1  B  x2  z2

Teorie her Stačí opět platnost pro jednotkové vektory: T T x1  1,0,...0 x2  1,0,...0  0,1,...0  0,1,...0 ... ...  0,0,...1  0,0,...1

1,0...0 a

a ...a1n   x21  a a ...a   x   21 22 2 n    22  ...  ...      am1am 2 ...amn   x2 n  11 12

 z1

x11, x12 ,...x1m  b

b ...b1n  1  b b ...b     21 22 2 n   0  ...  ...     bm1bm 2 ...bmn  0  11 12

 z2

a11  x21  a12  x22  ...  a1n  x2 n  z1

b11  x11  b21  x12  ...  bm1  x1m  z 2

a21  x21  a22  x22  ...  a2 n  x2 n  z1

b12  x11  b22  x12  ...  bm 2  x1m  z 2

... am1  x21  am 2  x22  ...  amn  x2 n  z1

... b1n  x11  b2 n  x12  ...  bmn  x1m  z 2

A  x2  e  z1

T

B  x1  f  z2

Teorie her Úprava:

Podmínky:

A  x2  e  z1 / : z1  A  x2  e   T  T x1  A  x2  e  x1

1

 x1i

B  x1  f  z 2 / : z2  T B  x1  f   T  T x1  B  x2  f  x2 T

 x2 j

1

T f  x 2  1 / : z2 e  x1  1 / : z1   T T f  x 1 e  x1  1 2   T   T x  B  x  1 / z2 x1  A  x2  1 / z1 1 2       Formulace úlohy: max z T x1  A  x2 T e  x1  T x1  B  x2 T f  x2  A x  e  Bx  f   x ,x 0

T

2

T

1

1

2

Teorie her Příklad:

A

B

i\j

1 2

1

6 10 8 7

2

7 8

max 7 10 (2,1)(1,2)

1 2

R1  R2  0

max 8

6 10 10

(1,1) (2,2)

T



x1  x11 , x12   x21  x2     x22  

z  x11 , x12  6;10  x21   x11 , x12  8;7   x21   1;1  x11   1;1  x21   x   x  7;8    x  6;10   x     22     22   12   22  z  14 x11 x21  13x12 x21  17 x11 x22  18 x11 x22  x11  x12  x21  x22 6 x21  10 x22  1 7 x21  8 x22  1 8 x11  6 x12  1 7 x11  10 x12  1

Teorie her Kooperativní hry Možnost dohody o rozdělení výher Kdy má smysl? min z1 i, j   z1 Nechť 1. si může zajistit max j i 2. si může zajistit

max min z 2 i, j   z 2 i j

Při dohodě bude společná výhra:

z1 i, j   z2 i, j  z1, 2  max i, j Je-li

z1, 2  z1  z 2

má dohoda smysl  PODSTATNÁ HRA

z1, 2  z1  z 2 z1, 2  z1  z 2

 NEPODSTATNÁ HRA nemůže nastat

Nalezení je jasné, vybereme v A a B tu, v níž je z1,2  max

Teorie her Kooperativní hry - příklad A

2

B

i\j

1

3

1

2

3

max

1

19 29 29 19 10

2

10 15 20 29 120 20 120

(2,2)

3

10 20 25 29 20

(3,1)

10 19 25 29

(1,1)

max 19 29 29 (1,1) (1,2)(1,3)

Bez dohody: Dohoda:

R1  R2  1,1

z1  z2  19  19  38

2,2  z  z  15  120  135 1

2

Teorie her Kooperativní hry Další konflikt – Jak rozdělit z1,2? a a  z Rozdělení hry a , a 1

2

1

2

1, 2

a1  z1 a2  z 2 Jádro hry – opět množina {a1,a2} , splňující pravidlo 1.

Různá pravidla: 1. charita z a a  2 2. v poměru přínosů 1, 2

1

2

a1 z1, 2  z 2  a2 z1, 2  z1

3. každý své a zbytek napůl

z1, 2  z1  z 2 2 z  z1  z 2 a 2  z 2  1, 2 2 a1  z1 

4. každý své a zbytek podle přínosů a1  z1   z1, 2  z1  z 2  

z1, 2  z 2 z1, 2  z1

a2  z 2   z1, 2  z1  z 2  

z1, 2  z1 z1, 2  z 2

5. individuální dohoda

Teorie her Kooperativní hry Další konflikt – Jak rozdělit z1,2? z1, 2  15  120  135 a2  135  a1 jádro hry

140

135  67,5 2 a1 135  19  a2 135  19

a1  a2 

120

100 80 60 40 20

0

20 40 60 80 100 120 140

(19,19)

Teorie her Hry proti přírodě  I R  1, X , Y , Z1   I  1   I 

X...strategie racionálního účastníka Y...náhodné stavy

p(j) 0,3 0,6 0,1 i\j 1 2 3 1

5

-1

-3

5*0,3-1*0,6-3*0,1=0,6

2

3

8

-2

3*0,3+8*0,6-2*0,1=5,5

3

2

4

10

2*0,3+4*0,6+10*0,1=4

max  5,5 i

1. Bayes – známe-li p(j) – rozhodování za rizika Maximalizace střední hodnoty výhry max  p( j )  aij i

j

Teorie her Hry proti přírodě 2. Laplace – neznáme-li p(j) – rozhodování za nejistoty Předpoklad: p(j) = konst. j aij Maximalizace střední hodnoty max i

n

i\j 1

2

3

1

5

-1

-3

(5-1-3)/3=0,3

2

3

8

-2

3

2

4

10

max  5,3 (3+8-2)/3=3 i (2+4+10)/3=5,3 min j

3. Waldovo pravidlo 1 Maximalizace minimálně dosažitelného přínosu

-3

2

-2

3

2

max min aij i

j

max  2 i

Teorie her Hry proti přírodě 4. Savageovo pravidlo z  zij  max aij  aij Matice ztrát



i



min max zij i

i\j 1 2

1

3

5 -1 -3

2

3 8

-2

3

2 4

10

j

1

1

5-5=0 8-(-1)=9 10-(-3)=13 13

2

5-3=2 8-5=0

10-(-2)=12 12

3

5-2=3 8-4=4

10-10=0

max aij 5 i

2

8

3

max zij

i\j

10

j

4

max  4 i

Teorie her Hry proti přírodě 5. Hurwitzovo pravidlo Koeficient optimismu k  0;1 max  k  max aij  1  k   min aij  j i  j 

Volíme k=0,6 3

max min

i\j

1 2

1

5 -1 -3 5

-3

0,6*5+0,4*(-3)=1,8

2

3 8

-2 8

-2

0,6*8+0,4*(-2)=4

3

2 4

10 10

2

0,6*10+0,4*2=6,8

j

j

max  6,8 i

Evropský sociální fond Praha & EU: Investujeme do vaší budoucnosti

Tento materiál vznikl díky Operačnímu programu Praha Adaptabilita CZ.2.17/3.1.00/33254