Operační výzkum. Teorie her cv. Hra v normálním tvaru. Optimální strategie. Maticové hry

Operační výzkum Teorie her – cv. Hra v normálním tvaru. Optimální strategie. Maticové hry.

Operační program Vzdělávání pro konkurenceschopnost Název projektu: Inovace magisterského studijního programu Fakulty ekonomiky a managementu Registrační číslo projektu: CZ.1.07/2.2.00/28.0326

Maticové hry řešené v oboru smíšených strategií

Maticové hry řešené v oboru smíšených strategií V případech, kdy α < β,

a tedy

max min aij < min max aij (∗) i

j

j

i

musíme MH řešit v oboru smíšených strategií. Definice: Smíšenou strategií 1. hráče m P rozumíme m-tici ~x = (x1 , . . . , xm ), kde xi ≥ 0 a xi = 1. i=1

Smíšenou strategií 2. hráče n P rozumíme n-tici ~y = (y1 , . . . , yn ), kde yj ≥ 0 a yj = 1. j=1

Poznámka: xi vyjadřuje pravděpodobnost, s jakou 1. hráč užívá i-tou čistou strategii Ai , yj vyjadřuje pravděpodobnost, s jakou 2. hráč užívá j-tou čistou strategii Bj .

Michal Šmerek

Teorie her.


Maticové hry řešené v oboru smíšených strategií Nemá-li hra sedlový bod je pro oba hráče výhodné své jednotlivé (čisté) strategie rozumně střídat. m P n P Výraz E (~x , ~y ) = aij xi yj nazýváme střední cena hry (= očekávaná výhra i=1 j=1

1. hráče = očekávaná prohra 2. hráče). Definice: Smíšené strategie ~x0 , ~y0 , pro které platí rovnost max min E (~x , ~y ) = min max E (~x , ~y ) = E (~x0 , ~y0 ), ~ x

~ y

~ y

~ x

se nazývají optimální smíšené strategie. Cena hry pak je v = E (~x0 , ~y0 ). Základní věta teorie MH: Každá maticová hra má řešení v oboru smíšených strategií. Poznámka: Existuje řada metod řešení MH. Vždy jde o to nalézt optimální smíšené strategie obou hráčů ~x0 , ~y0 a cenu hry v = E (~x0 , ~y0 ). Michal Šmerek

Teorie her.


Maticové hry typu 2 × 2 Předpokládejme, že MH daná platební maticí „ « a11 a12 A= nemá sedlový bod. a21 a22 Hledáme tedy optimální smíšené strategie ~x0 = (x1 , x2 ), ~y0 = (y1 , y2 ), přičemž x1 + x2 = 1, y1 + y2 = 1; x1 , x2 , y1 , y2 ≥ 0. Pro tyto optimální smíšené strategie musí platit: a11 x1 + a21 x2 = v , a12 x1 + a22 x2 = v ,

a11 y1 + a12 y2 = v , a21 y1 + a22 y2 = v .

Řešením této soustavy rovnic získáme neznámé x1 , x2 , y1 , y2 , v : x1 =

a22 − a21 , a

x2 =

a12 − a11 , a

y1 =

a22 − a12 , a

y2 =

a11 − a21 , a

det(A) , a kde a = a11 + a22 − a12 − a21 , det(A) = a11 a22 − a12 a21 . v=

Michal Šmerek

Teorie her.


Maticové hry typu 2 × 2 „ Př: Řešte MH s platební maticí A =

4 1

2 3

« .

Řešení: Optimální strategie získáme dosazením do vzorců: a = a11 +a22 −a12 −a21 = 4+3−1−2 = 4, det(A) = a11 a22 −a12 a21 = 4.3−1.2 = 10, a22 − a21 3−1 1 = = , a 4 2 3−2 1 a22 − a12 y1 = = = , a 4 4

a12 − a11 4−2 1 = = , a 4 2 a11 − a21 4−1 3 y2 = = = , a 4 4 10 5 v= = . 4 2

x1 =

x2 =

Tedy: „ ~x0 =

1 1 , 2 2

«

„ , ~y0 =

Michal Šmerek

1 3 , 4 4

«

Teorie her.

, v=

5 . 2


Maticové hry typu 2 × 2

„ Př: Řešte MH s platební maticí A =

10 −4

−1 5

« .

Řešení: Optimální strategie obou hráčů a cena hry jsou: « „ « „ 3 7 23 9 11 ~x0 = , ~y0 = , v= , , . 20 20 10 10 10 Hra je nespravedlivá, zvýhodňuje hráče A.

Michal Šmerek

Teorie her.




7 2

3 2

« .

Řešení: Optimální strategie obou hráčů a cena hry jsou: ~x0 = (1, 0), ~y0 = (0, 1), v = 3. Hra je nespravedlivá, zvýhodňuje hráče A.

Poznámka: Při řešení předchozí MH bylo potřeba si uvědomit, že v platební matici exituje sedlový bod (α = β), čili řešení v čistých strategiích. Formální dosazení do vzorců by dalo špatné výsledky!

Michal Šmerek

Teorie her.


Princip dominování

Rozměry platební matice je často možno při řešení MH zmenšovat na základě principu dominování. Definice: Řekneme, že vektor ~a = (a1 , . . . , an ) dominuje vektor ~b = (b1 , . . . , bn ), jestliže ai ≥ bi , ∀i = 1, . . . , n. Mějme MH s platební maticí A = (aij )m×n . Jestliže i-tý řádek platební matice dominuje k-tý řádek, můžeme k-tý řádek vynechat s tím, že xk = 0 a dále řešíme hru se zmenšenou maticí, která má stejné řešení jako původní hra. Jestliže j-tý sloupec platební matice dominuje k-tý řádek, můžeme j-tý sloupec vynechat s tím, že yj = 0 a dále řešíme hru se zmenšenou maticí, která má stejné řešení jako původní hra.

Michal Šmerek

Teorie her.


Princip dominování 0

−4 Př: Řešte MH s platební maticí A = @ −3 2

6 −3 −3

1 3 6 A. 4

Řešení: 0

1 −4 6 3 A = @ −3 −3 6 A ⇒ 3. sloupec dominuje 1. sloupec (y3 = 0) −→ 2 −3 4 0 1 −4 6 0 A = @ −3 −3 A ⇒ 3. řádek dominuje 2. řádek (x2 = 0) −→ 2 −3 « „ −4 6 A00 = 2 −3 Nyní vyřešíme MH s platební matící A00 podle vzorců pro MH typu 2 × 2:

Michal Šmerek

Teorie her.



Nyní vyřešíme MH s platební matící A00 podle vzorců pro MH typu 2 × 2: x100 = x1 =

1 3

x200 = x3 =

2 , 3

y100 = y1 =

3 , 5

y200 = y2 =

2 , 5

v 00 = v = 0. Optimální strategie obou hráčů a cena hry jsou: „ « „ « 1 2 3 2 ~x0 = , 0, , ~y0 = , , 0 , v = 0. Hra je spravedlivá. 3 3 5 5

Michal Šmerek

Teorie her.


Maticové hry typu 2 × n. Grafická metoda.

Hry typu 2 × n „ Předpokládejme, že MH daná platební maticí A =

a11 a21

a12 a22

... ...

a1n a2n

«

nemá sedlový bod. Hledáme tedy optimální smíšené strategie ~x0 = (x1 , x2 ), ~y0 = (y1 , y2 , . . . , yn ), přičemž x1 + x2 = 1, y1 + y2 + · · · + yn = 1; x1 , x2 , y1 , y2 , . . . , yn ≥ 0. Uvažujme funkce Mj (x1 ) = a1j x1 + a2j x2 = (a1j − a2j )x1 + a2j ,

j = 1, . . . , n.

Znázorníme graficky části těchto přímek v intervalu x1 ∈ h0, 1i. Použijeme principu minimaxu.

Michal Šmerek

Teorie her.


Maticové hry typu 2 × n. Grafická metoda. Použijeme principu minimaxu. Cílem 2. hráče je minimalizovat výhru 1. hráče. Určíme proto funkci M(x1 ) = min Mj (x1 ). j

Cílem 1. hráče je vhodnou volbou hodnoty x1 maximalizovat svoji výhru. Hledáme tedy hodnotu x10 takovou, že M(x10 ) = max M(x1 ). x1

Řešením hry je pak v = M(x10 ), ~x0 = (x10 , 1 − x10 ). V optimální smíšené strategii 2. hráče jsou nenulové hodnoty yk , yl , které odpovídají přímkám Mk (x1 ), Ml (x1 ) protínajícím se v bodě (x10 , v ). Hodnoty yk , yl určíme řešením MH s platební maticí (typu 2 × 2) „ « a1k a1l A0 = . a2k a2l Michal Šmerek

Teorie her.


Maticová hra typu 2 × n. Grafická metoda.


2 7

3 5

11 2

« .

Řešení: α = 2, β = 5 ⇒ sedlový bod neexistuje. MH budeme řešit graficky. Do grafu znázorníme přímky: M1 (x1 ) = 2x1 + 7x2 = −5x1 + 7,

[0, 7], [1, 2],

M2 (x1 ) = 3x1 + 5x2 = −2x1 + 5,

[0, 5], [1, 3],

M3 (x1 ) = 11x1 + 2x2 =

[0, 2], [1, 11].

Michal Šmerek

9x1 + 2,

Teorie her.



Obrázek: Grafické řešení MH Michal Šmerek

Teorie her.



Funkce M(x1 ) je zřejmá z grafu. Maximum funkce M(x1 ) nabývá v průsečíku přímek M2 ∩ M3 . Proto y1 = 0. Ostatní složky určíme řešením MH s platební maticí (2. a 3. sloupec): „ « 3 11 A0 = . 5 2 Optimální strategie obou hráčů a cena hry jsou: „ « „ « 3 8 9 2 49 ~x0 = , , ~y0 = 0, , , v= . 11 11 11 11 11 Hra je nespravedlivá, zvýhodňuje hráče A.

Michal Šmerek

Teorie her.


Maticové hry typu m × 2. Grafická metoda. Hry typu m × 2 Řeší se analogicky jako hry typu 2 × n, ale z pohledu 2. hráče. 0 a11 a12 B a21 a22 B Předpokládejme, že MH daná platební maticí A = B . .. @ .. . am1 am2 sedlový bod.

1 C C C nemá A

Hledáme tedy optimální smíšené strategie ~x0 = (x1 , x2 , . . . , xm ), ~y0 = (y1 , y2 ), přičemž x1 + x2 + · · · + xm = 1, y1 + y2 = 1; x1 , x2 , . . . , xm , y1 , y2 ≥ 0. Uvažujme funkce Ni (x1 ) = ai1 y1 + ai2 y2 = (ai1 − ai2 )y1 + ai2 ,

i = 1, . . . , m.

Znázorníme graficky části těchto přímek v intervalu y1 ∈ h0, 1i. Použijeme principu maximinu. Michal Šmerek

Teorie her.


Maticové hry typu m × 2. Grafická metoda. Použijeme principu maximinu. Určí se funkce N(y1 ) = max Ni (y1 ). i

Cílem 2. hráče je vhodnou volbou hodnoty y1 minimalizovat svou prohru (=maximalizovat svoji výhru). Hledáme tedy hodnotu y10 takovou, že N(y10 ) = min N(y1 ). y1

Řešením hry je pak v = N(y10 ), ~y0 = (y10 , 1 − y10 ). V optimální smíšené strategii 1. hráče jsou nenulové hodnoty xk , xl , které odpovídají přímkám Nk (y1 ), Nl (y1 ) protínajícím se v bodě (y10 , v ). Hodnoty xk , xl určíme řešením MH s platební maticí (typu 2 × 2) „ « ak1 al1 0 A = . ak2 al2

Michal Šmerek

Teorie her.


Maticová hra typu m × 2. Grafická metoda.

0

−2 Př: Řešte MH s platební maticí A = @ 1 0

1 1 −5 A. −1

Řešení: α = −1, β = 1 ⇒ sedlový bod neexistuje. MH budeme řešit graficky. Do grafu znázorníme přímky: N1 (y1 ) = −2y1 + y2 = −3y1 + 1,

[0, 1], [1, −2],

N2 (y1 ) =

y1 − 5y2 =

4y1 − 5,

[0, −5], [1, 1],

N3 (y1 ) =

− y2 =

y1 − 1,

[0, −1], [1, 0].

Michal Šmerek

Teorie her.



Obrázek: Grafické řešení MH

Michal Šmerek

Teorie her.



Funkce N(y1 ) je zřejmá z grafu. Maximum funkce N(y1 ) nabývá v průsečíku přímek N1 ∩ N3 . Proto x2 = 0. Ostatní složky určíme řešením MH s platební maticí (1. a 3. řádek): „ « −2 1 A0 = . 0 −1

Optimální strategie obou hráčů a cena hry jsou: „ « „ « 1 3 1 1 1 ~x0 = , 0, , ~y0 = , , v =− . 4 4 2 2 2 Hra je nespravedlivá, zvýhodňuje hráče B.

Michal Šmerek

Teorie her.



0

1 4 3 A. 1

1 Př: Řešte MH s platební maticí A = @ 3 5

Řešení: α = 3, β = 4 ⇒ sedlový bod neexistuje. MH budeme řešíme graficky. Do grafu znázorníme přímky: N1 (y1 ) = y1 + 4y2 = −3y1 + 4,

[0, 4], [1, 1],

N2 (y1 ) = 3y1 + 3y2 =

3,

[0, 3], [1, 3],

N3 (y1 ) = 5y1 + 1y2 =

4y1 + 1,

[0, 1], [1, 5].

Michal Šmerek

Teorie her.



Obrázek: Grafické řešení MH

Michal Šmerek

Teorie her.



Funkce N(y1 ) je zřejmá z grafu. Maximum funkce N(y1 ) nabývá na úsečce mezi průsečíky přímek N1 ∩ N2 a N2 ∩ N3 . Celá tato úsečka představuje nekonečně mnoho optimálních řešení. Proto x2 = 1 (přímka N2 je konstantní).

Optimální strategie obou hráčů a cena hry jsou: fi ~x0 = (0, 1, 0), ~y0 = (y1 , 1 − y1 ) , kde y1 ∈ Hra je nespravedlivá, zvýhodňuje hráče A.

Michal Šmerek

Teorie her.

1 1 , 3 2

fl , v = 3.

Operační výzkum. Teorie her cv. Hra v normálním tvaru. Optimální strategie. Maticové hry

Recommend Documents