TEORIE HER V dosavadních přednáškách jsme probírali jedno či vícekriteriální optimalizaci, ale v těchto úlohách byly předem pevně dané podmínky a ty se nijak neměnily v závislosti na našem rozhodnutí. Také jsme uvažovali modely (rozhodování za rizika a nejistoty), kde nejsou podmínky pro rozhodování jisté, neboť závisí ještě na dalších okolnostech, o kterých nemáme jistotu, jak dopadnou. Teorie her se zabývá rozhodováním v tzv. konfliktních situacích. Jedná se o situace, kdy okolí na naše rozhodnutí může nějakým způsobem zareagovat, udělat nějaké protiopatření, čímž se může zcela změnit naše situace. Příklad: Příkladem takové situace z ekonomie je oligopol. Pokud se bude rozhodovat jeden oligopolista sám a nebude brát v úvahu okolí, stanoví svůj objem výroby tak, aby maximalizoval své tržby. Spočte si své jednotkové náklady závislé na objemu produkce, podle statistik dopočte, kolik bude jednotkový zisk v závislosti na objemu produkce dodávané na trh (uvažuje, že na trh dodává sám) a odtud stanoví optimální výrobní plán. Pokud nebude brát v úvahu ostatní oligopolisty a pokud i oni budou vyrábět, potom se cena na trhu sníží (není sám, kdo dodává zboží), a jeho zisky vůbec nemusí být, pro jím stanovený objem výroby, optimální. Právě takovými situacemi se zabývá teorie her. Základní pojmy teorie her • hra - je každá konfliktní situace. • hráč - účastník hry, který svým chováním může ovlivnit její výsledek; hráč může být buď racionální (usiluje o optimální výsledek hry) nebo indiferentní (výsledek hry je mu lhostejný) • strategie - předpis, kterým je určena jedna alternativa chování hráče při hře • výplata hráče - kvantitativně vyjádřený výsledek hry, posuzovaný z hlediska uvažovaného hráče (kladná hodnota - užitek, záporná hodnota - prohra) • výplatní funkce hráče - předpis pro výplatu v závislosti na zvolené strategii
Klasifikace her podle různých kritérií • podle počtu hráčů - hry 2 a n hráčů, kde n > 2 • podle součtu výplat hráčů - hry s konstantním a hry s nekonstantním součtem; zvláštní případ hry s konstantním součtem je hra s nulovým součtem • podle velikosti prostoru strategií - hra konečná a nekonečná • podle informace - pokud hráči mají informace o dosavadních tazích protihráčů, hovoříme o hrách s úplnou informací, pokud ne, potom o hrách s neúplnou informací • podle zájmů hráčů - hry antagonistické a hry neantagonistické ; neantagonistické hry se dále člení na hry kooperativní a hry nekooperativní; v kooperativní hře lze vytvářet koalice 1
• podle informací o důsledcích volby - hry deterministické ; zvolíme-li strategii, víme přesně, kolik získáme a hry stochastické - do hry vstupuje náhoda, zvolíme- li strategii, výplata má nějaké pravděpodobnostní rozdělení • podle racionality hráčů - hry hrané podle minimaxu a hry hrané proti přírodě Důležitou roli v teorii her mají konečné hry dvou hráčů s nulovým součtem, které nazýváme maticové hry. Abychom mohli naše teorie srozumitelně zapisovat, budeme používat následující (běžné) značení. Účastníky hry budeme značit písmeny A a B. Hru sledujeme z hlediska jednoho hráče, většinou z hlediska hráče A. Jeho výplata se nazývá výhra a výplata druhého hráče se nazývá prohra. Hráč A má k dispozici m strategiií a hráč B má k dispozici n strategií. A . . . prostor strategií prvního hráče B . . . prostor strategií druhého hráče Ai . . . i-tá strategie strategie prvního hráče, kde i = 1, 2, ..., m Bj . . . j -tá strategie druhého hráče, kde j = 1, 2, ..., n Všechny dvojice strategií Ai , Bj lze zapsat do matice typu m × n. Tato matice se nazývá výplatní maticí nebo maticí hry. Pokud označíme prvky výplatní matice aij , platí aij = M1 (Ai , Bj ). Pak M1 (Ai , Bj ) je výplatní funkce hráče A. Výplatní funkce hráče B je M2 (Ai , Bj ). Ve hře s nulovým součtem platí M1 (Ai , Bj ) = −M2 (Ai , Bj ), proto vystačíme se zápisem M (Ai , Bj )(viz dále). Hra je dána výčtem strategií jednotlivých hráčů a výplatními funkcemi. Smysl značení si ukážeme na následujících příkladech. Příklad: Uvažujme hru o jednom tahu, ve které hráč A volí mezi dvěma čísly 1 a 2 a hráč B rovněž volí mezi dvěma čísly 1 a 2. Při výplatě dostává hráč A od hráče B 1 Kč v případě, jsou-li zvolená čísla různá a hráč A zaplatí 1 Kč hráči B v případě, že jsou tato čísla stejná. Výplatní matice hráče A je následující. ”1” ”2” ”1” -1 1 ”2” 1 -1 Příklad: Předpokládáme, že slečna vlastní kožich, jehož hodnota je 5000 Kč. Může si tento kabát za 100 Kč pojistit a v případě, že jí bude kožich zničen požárem, bude jí škoda nahrazena. V této hře je jedním hráčem slečna a druhým „přírodaÿ. Strategie prvního hráče, tj. slečny jsou pojistit a nepojistit si kabát. Strategie „přírodyÿ jsou kabát slečně shoří a nestane se s kabátem nic. Výplatní funkce slečny (u „přírodyÿ nemají smysl) jsou podle ceny kabátu, ceny pojištění a ceny náhrady, kterou pojišťovna slečně poskytne. Pro slečnu můžeme napsat výplatní matici. Výplatní matice slečny má tedy následující tvar: pojistí nepojistí
OK -100 0
zničen -100 -5000
V tomto příkladě je jeden hráč racionální (předpokládáme to o slečně) a jeden indiferentní. V tom případě se jedná o tutéž situaci jako v rozhodování za nejistoty. 2
Antagonistický konflikt s konečným počtem strategií Antagonistickým konfliktem rozumíme konflikt, kde proti sobě stojí dva racionální hráči a zisk jednoho hráče je roven ztrátě druhého hráče (př. sázky mezi dvěma lidmi). Nebo obecněji o co jeden získá více, o to druhý více ztratí (mají si nějakým způsobem rozdělit fixní částku). Lze říci, že takový typ konfliktu lze zapsat jako maticová hra hraná podle minimaxu. Cílem je maximální výhra hráče A a minimální prohra hráče B. Hra může mít řešení buď v ryzích nebo ve smíšených strategiích. • ryzí strategie - jedna z možných strategií hráče Ryzí optimální strategii hráče A budeme značit A0 a tato strategie přinese hráči A maximální výhru, ať již hráč B volí jakoukoliv strategii. Ryzí optimální strategii hráče B budeme značit B0 . Je to strategie, která zaručí hráči B minimální prohru, ať již hráč A volí jakoukoliv strategii. Pro strategie i = 1, 2, ..., m a j = 1, 2, ..., n platí M (Ai , B0 ) ≤ M (A0 , B0 ) ≤ M (A0 , Bj ) Lze tedy říci, že jakýkoliv hráč si pohorší, pokud se odkloní od své optimální ryzí strategie. Cena hry(v ) je hodnota výplatní funkce M (A0 , B0 ). Pokud je cena hry nulová, jedná se o hru spravedlivou, pokud není nulová, jedná se o hru nespravedlivou. • smíšená strategie - náhodné střídání strategií hráče, přičemž je dáno rozdělení pravděpodobnosti na prostoru ryzích strategií Výplata hráčů je zde náhodná veličina a její očekávanou hodnotu značíme E(x, y). Pokud volí hráči strategie nezávisle na sobě, pro očekávanou výhru platí E(x, y) =
P P i
j
aij xi yj
Pro hráče A smíšenou strategii značíme x = [x1 , x2 , ..., xm ] , smíšenou strategii hráče B značíme y = [y1 , y2 , ..., yn ] . Složky těchto vektorů jsou nezáporná čísla, jejichž součet je roven jedné. Ryzí strategie je pak zvláštním případem smíšené strategie, kdy jeden prvek je 1 a ostatní 0. Stejně jako u ryzích strategií, lze i zde zavést pojem optimální strategie, které budeme značit [x0 , y0 ]. E(x, y0 ) ≤ E (x0 , y0 ) ≤ E (x0 , y) Řešení hry v ryzích strategiích reprezentují tyto údaje: A0 , B0 , v, řešení hry ve smíšených strategiích reprezentují tyto údaje: x0 , y0 , v . Matematickým modelem hry s konstantním součtem je M1 (Aij , Bij ) + M2 (Aij , Bij ) = k. My můžeme uvažovat hry se součtem nula, neboť všechny hry s konstantním součtem je možné převést na hry se součtem nula. Vlastnosti řešení maticových her
3
Máme-li konečný prostor strategií, tzv. konečnou hru, můžeme hru přepsat do matice A, kde řádky budou tvořit možné strategie prvního hráče a sloupce možné strategie druhého hráče. Prvek aij matice nám udává výplatu prvního hráče, pokud první zvolí i-tou strategii, tj. strategii Ai , a druhý hráč zvolí j-tou strategii, tj. strategii Bj . Protože se jedná o antagonistický konflikt, potom je aij s opačným znaménkem, tj. −aij , výplatou druhého hráče, při stejných strategiích (viz výše). A tedy jedná se o tzv. jednomaticovou hru. Poznámka: Všimněme si, že v této terminologii (uvažujeme ryzí strategie) tedy první hráč usiluje o maximalizaci: max aij , i
přičemž on může ovlinit pouze volbu i a volbu j ovlinit nemůže, kdežto druhý hráč usiluje o minimalizaci min aij , j
kde druhý hráč může ovlinit volbu j, ale ne i. Příklad: Uvažujme následující hru. Hrají dva hráči. Každý má pět sirek. Teď si každý může vzít do ruky kolik chce (z těch pěti sirek) a na povel ruce otevřou. Kdo bude mít v ruce více sirek, vyhrál, pokud mají stejně, je remíza. Ze zadání příkladu je zřejmé, že je rozumné, aby každý hráč vzal do ruky všech pět sirek. Ukažme si, že stejně nám dovede poradit i teorie her. Napišme si matici A výplatní matici prvního hráče a matici B výplatní matici druhého hráče. V obou maticích budou řádky odpovídat jednotlivým strategiím prvního hráče, postupně 1, 2,. . . , 5 sirkám v jeho ruce (předpokládejme, že musí alespoň jednu vzít) a sloupce steným způsobem jednotlivým strategiím druhého hráče. Výplatní matice mají tedy tvar: A=
0 −1 −1 −1 −1 1 0 −1 −1 −1 1 1 0 −1 −1 1 1 1 0 −1 1 1 1 1 0
B=
0 1 1 1 −1 0 1 1 −1 −1 0 1 −1 −1 −1 0 −1 −1 −1 −1
1 1 1 1 0
Všimněme si, že skutečně platí A = −B, a tedy je zbytečné pro zápis takovéto hry používat dvě matice.
Řešení jednomaticových her - sedlový bod Hledáme-li optimální řešení antagonistického konfliktu, hledáme vlastně stabilní řešení. Stabilní v tom smyslu, že ani jednomu hráči se nevyplatí od této strategie „utéciÿ, tj. má to být takové řešení, aby pokud pouze první hráč změní strategii a druhý hráč zůstane u své strategie, potom si první hráč pohorší. Stejně tak s druhým hráčem. Strategie hráče A je maximinová, neboť hráč A předpokládá, že inteligentní B zvolí strategii, při níž je jeho prohra minimální a vybere si z těchto minimálních výher v řádcích maxima. Strategie, při které je toto maximum největší, je pro hráče A optimální. Této maximinové strategii se říká také dolní cena hry. Strategie hráče B je minimaxová, neboť hráč B zjistí, kolik při každé strategii může prohrát nejvíce (maxima ve sloupcích) a z těchto největších proher vybere minimum. Tato minimaxová strategie se označuje jako horní cena hry.
4
Odtud vyplývá, že optimální řešení antagonistického konfliktu (v ryzích strategiích) existuje, pokud platí: min max aij = max min aij . (1) j
i
i
j
Pokud je tato rovnost splněna, v matici existuje prvek, který je nejmenší ve svém řádku a největší ve svém sloupci. Tento prvek nazýváme sedlový bod.
z sedlo
y x
Obrázek 1: Sedlový bod Obecně matice mohou mít žádný, jeden nebo více sedlových bodů. Pokud nemají žádný, neexistuje optimální ryzí strategie, pokud mají jeden, určuje optimální strategii, pokud jich mají více, určují alternativní rovnovážné strategii. Napišme si matici hry Kámen – nůžky – papír. Všimněme si, že nemá sedlový bod. Neexistuje tedy rovnovážné řešení v ryzích strategiích. Pokud má alespoň jeden hráč nekonečně mnoho strategií, potom se jedná o tzv. nekonečnou hru.
Dominované a nedominované strategie Stejně jako ve vícekriteriálním hodnocení variant, i zde se můžeme setkat s tzv. dominovanými a nedominovanými variantami, resp. strategiemi. Řekneme, že strategie Ak prvního hráče dominuje strategii Al tohoto hráče, jestliže pro všechny možné strategie Bj druhého hráče platí, že M (Ak , Bj ) ≥ M (Al , Bj ) a zároveň existuje alespoň jedna strategie Bq taková, že M (Ak , Bq ) > M (Al , Bq ). 5
Nebo-li pro jakoukoliv strategii druhého hráče platí, že výplata prvního hráče je při strategii Ak větší nebo stejná než při strategii Al a alespoň při jedné strategii je ostře lepší. Dominovanost lze určit i u strategií hráče B. Vlastnosti řešení maticových her Hráč A má možnost volit strategie A1 , A2 , . . . , Am , hráč B má možnost volit mezi strategiemi B1 , B 2 , . . . , B n . • Je dána cena hry v, vektor x = [x1 , x2 , . . . , xm ], pro jednotlivé složky tohoto vektoru P platí xi ≥ 0 a m i=1 xi = 1. Vektor x je optimální strategií hráče A tehdy, když platí E(x, Bj ) ≥ v pro j = 1, 2, . . . , n. • Je dána cena hry v, vektor y = [y1 , y2 , . . . , yn ], pro jednotlivé složky tohoto vektoru P platí yj ≥ 0 a nj=1 yj = 1. Vektor y je optimální strategií hráče B tehdy, když platí E(Ai , y) ≤ v pro i = 1, 2, . . . , m. • Optimální strategie hráčů A a B ve hře s cenou v jsou x0 =[x01 , x02 , ..., x0m ] a y0 =[y01 , y02 , ..., y0n ]. Potom pokud: a) E(x0 , Bj ) > v , platí y0j = 0; 1 ≤ j ≤ n b) E(Ai , y0 ) < v , platí x0i = 0; 1 ≤ i ≤ m c) x0i > 0, platí E(Ai , y0 )= v; 1 ≤ i ≤ m d) y0j > 0, platí E(x0 , Bj )= v; 1 ≤ j ≤ n. Tyto vztahy vyplývají ze vztahů mezi duálně sdruženými úlohami. • Pokud není optimální strategie hráče dána jednoznačně, každá konvexní kombinace optimálních strategií tohoto hráče představuje rovněž optimální strategii. • Jsou-li prvky aij výplatní matice A změněny o libovolnou konstantu k > 0, např. aij + k, kaij , těmto hrám odpovídají stejné optimální strategie. Cena hry je rovněž změněna o tuto konstantu. Jedná se o strategicky ekvivalentní hry. Startegicky ekvivalentní hru je možné získat i převodem hry s konstantním součtem na hru s nulovým součtem, popř. vynecháním dominovaných strategií (viz předchozí přednáška). Řešení maticových her 2x2 bez sedlového bodu Výplatní matice hry je Ã
A=
a11 a12 a21 a22
!
.
Tato hra nemá sedlový bod a my hledáme optimální smíšené strategie obou hráčů a cenu hry. Nejprve budeme určovat optimální smíšené strategie hráče A. Vzhledem k tomu, že hra nemá řešení v ryzích strategiích, obě složky vektoru optimální smíšené strategie hráče B musí být kladné. Neboli musí být splněny rovnosti a11 x01 + a21 x02 = v a a12 x01 + a22 x02 = v. Tyto dvě rovnice můžeme dále zapsat jako a11 x01 + a21 x02 = a12 x01 + a22 x02 6
Pokud vezmeme v úvahu, že x01 +x02 = 1, pak řešením soustavy dvou rovnic o dvou neznámých získáme následující řešení: x01 =
a22 − a21 , x02 = a11 + a22 − a12 − a21
a11 −a12 . a11 +a22 −a12 −a21
Po zjištění optimální strategie hráče A lze dopočítat i cena hry. Nyní určíme optimální smíšenou strategi hráče B. Zde budeme vycházet z rovnosti a11 y01 + a12 y02 = a21 y01 + a22 y02 Opět vezmem v úvahu, že y01 + y02 = 1 a vyjádříme vztah pro výpočet optimálních smíšených strategií hráče B. Řešením je y01 =
a22 −a12 , a11 +a22 −a12 −a21
a11 −a21 . a11 +a22 −a12 −a21
y02 =
Příklad 1: Určete optimální smíšené strategie obou hráčů, znáte-li výplatní matici A Ã
A= Výsledky příkladu 1: 1−(−2) x01 = 1+1−0−(−2) = 34 , x02 = v = 43 − 24 = 14 .
1−0 1+1−0−(−2)
1 0 −2 1
!
.
= 41 , y01 =
1−0 1+1−0−(−2)
= 14 , y02 =
1−(−2) 1+1−0−(−2)
= 34 ,
Grafické řešení maticových her Pokud je hra m×2 nebo 2×n, lze ji řešit jednoduchým grafickým způsobem. Vzpomeňte na grafické odvozování velikosti koeficientu α u Hurwitzova přístupu při rozhodování za nejistoty. Do podobné soustavy souřadnic budeme zakreslovat prvky výplatní matice. Pokud budeme řešit hru 2 × n, na ose x budeme zjišťovat, jaké jsou smíšené strategie hráče A. Na osu v (kolmice na osu x v bodě 0) budeme vynášet číslo , které je ve výplatní matici na pozici 1, k, kde k = 12, . . . , n. Na osu z (kolmice na osu x v bodě 1) budeme vynášet číslo, které je ve výplatní matici na pozici 2k, kde k = 1, 2, . . . , n. Oba body (prvky výplatní matice), příslušející jedné strategii hráče B, vždy spojíme přímkou. Když máme zakreslené všechny úsečky příslušející strategiím hráče B, hledáme část úsečky, pod kterou se nenachází body jiné úsečky. Tato část představuje graf minimální očekávané výhry hráče A. Pokud řešíme hry typu m × 2 vynášíme na souřadnoice v,z prohry hráče B při jednotlivých strategiích hráče A. Postup budeme ilustrovat na následujícíh příkladech. Příklad 2: Mějme matici Ã
A= Výsledky příkladu 2: x01 =
4 , x02 11
=
1 −2 5 3 4 0 7 ,v 11
=
!
.
20 . 11
Grafické řešení viz obrázek 1.
Příklad 3: Mějme matici Ã
A=
1 −1 3 4 −5 2
!
.
Výsledky příkladu 3: x01 = 1, x02 = 0, v = −1. Grafické řešení viz obrázek 2Příklad 4: Mějme matici 7
5 −2 B = 3 1 . 2 0 Výsledky příkladu 4: y01 = 0, y02 = 1, v = 1. Grafické řešení viz obrázek 3. Příklad 5: Mějme matici Ã
B=
2 −1 1 3
!
.
Výsledky příkladu 5: y01 = 54 , y02 = 15 , v = 57 . Grafické řešení viz obrázek 4. Řešení maticových her metodami LP Mějme výplatní matici
A=
a11 a21 .. .
a12 a22 .. .
am1 am2
. . . a1n . . . a2n .. .. . . . . . amn
.
Následující soustavou nerovnic lze vyjádřit požadavek, aby optimální strategie hráče A tomuto hráči zajistila výhru nejméně v hodnotě ceny hry v, ať už hráč B volí jakoukoliv ze svých ryzích strategií: a11 x01 + a21 x02 + · · · + am1 x0m ≥ v a12 x01 + a22 x02 + · · · + am2 x0m ≥ v .. . a1n x01 + a2n x02 + · · · + amn x0m ≥ v V případě, že matice obsahuje záporná čísla, ke všem jejím prvkům přičteme dostatečně velké kladné číslo. Tím získáme strategicky ekvivalentní hru, jejíž cena bude o přičítanou konstantu vyšší. Pokud je nezápornost prvků matice splněna, vydělíme cenou každou nerovnici soustavy a podíly xv0i nahradíme symbolem ti , pro i = 1, 2, . . . , m. Soustava má pak tvar a11 t1 + a21 t2 + · · · + am1 tm ≥ 1 a12 t1 + a22 t2 + · · · + am2 tm ≥ 1 .. . a1n t1 + a2n t2 + · · · + amn tm ≥ 1 Do podmínky
Pm
i=1
x0i = 1 za x0i dosadíme součin vti . Potom platí v
Xm
t = 1, neboli i=1 i 8
m P i=1
ti = v1 .
Danou úlohu můžeme zapsat jako úlohu LP. Na množině nezáporných řešení souP stavy lineárních rovnic hledáme minimum lineární funkce f = m i=1 ti . Cena hry se rovná převrácené hodnotě účelové funkce a pro optimální strategii hráče A platí x0i = vti pro i = 1, 2, . . . , m. Potom platí v
Pm
i=1 ti
= 1, neboli
Pm
i=1 ti
= v1 .
Nyní zformulujeme model z hlediska hráče B. Očekávaná prohra hráče B nesmí být větší než cena hry, ať už hráč A volí kteroukoliv ze svých ryzích strategií. Musí platit a11 y01 + a12 y02 + · · · + a1n y0n ≤ v a21 y01 + a22 y02 + · · · + a2n y0n ≤ v .. . am1 y01 + am2 y02 + · · · + amn y0n ≤ v I u hráče B upravíme výplatní matici tak, aby cena hry byla kladná a položíme 1, 2, . . . , n. Soustavu pak můžeme napsat ve tvaru
y0j v
= sj , j =
a11 s1 + a12 s2 + · · · + a1n sn ≤ 1 a21 s1 + a22 s2 + · · · + a2n sn ≤ 1 .. . am1 s1 + am2 s2 + · · · + amn sn ≤ 1 Do podmínky
Pn
j=1
y0j = 1 za y0j dosadíme součin vsj . Potom platí v
Pn
j=1
sj = 1, neboli
Pn
j=1
sj = v1 . P
Snaha hráče A je minimalizovat cenu hry neboli maximalizovat součet nj=1 sj . Stejně jako u hráče A, i zde je možné úlohu zformulovat jako úlohu LP. Na množině nezáporných P řešení soustavy lineárních nerovnic hledáme maximum lineární funkce z = nj=1 sj . Úlohy jsou duálně sdružené. Příklad:Pro hru kámen - nůžky - papír zapíšeme výplatní matici (strategie jsou v pořadí kámen, nůžky, papír) a určíme optimální smíšené strategie pomocí LP.
0 1 −1 1 A = −1 0 . 1 −1 0 Výplatní matici upravíme přičtením čísla 1, aby matice neobsahovala záporná čísla.
1 2 0 A = 0 1 2 . 2 0 1 Z hlediska hráče A je model následující: 9
t1 + 2t3 ≥ 1 2t1 + t2 ≥ 1 2t2 + t3 ≥ 1 t1 , t 2 , t 3 ≥ 0 f = t1 + t2 + t3 → min Z hlediska hráče B je model následující: s1 + 2s2 ≤ 1 s2 + 2s3 ≤ 1 2s1 + s3 ≤ 1 s1 , s2 , s3 ≥ 0 f = s1 + s2 + s3 → max Výsledky pro A: t1 = 13 , t2 = 13 , t3 = 13 , f = 1 ⇒ v ‘ = 1, v = v ‘ − 1 = 0 Výsledky pro B: s1 = 13 , s2 = 13 , s3 = 13 , z = 1 ⇒ v ‘ = 1, v = v ‘ − 1 = 0
v
0 x02
1 x01
Obrázek 2: Grafické řešení příkladu 2 Hry hrané proti přírodě V tomto typu her hledáme optimální strategie hráče A, neboť hráč B (příroda) je indiferentní. S tímto přístupem jsme se již setkali u jednokriteriálního rozhodování za rizika a nejistoty. • můžeme předpokládat, že příroda je zákeřná a řešit hru podle principu minimaxu • můžeme hru řešit přístupy, které známe z rozhodování za nejistoty
10
0 v
1 x01
Obrázek 3: Grafické řešení příkladu 3
v y02
Obrázek 4: Grafické řešení příkladu 4 Příklad 1: Výrobce vyrábí určité výrobky, z nichž některé mohou být vadné. Servisní organizace účtuje tomuto výrobci za záruční opravu 8 PJ/kus. Výrobce však může provést před expedicí výrobku kontrolu kvality (stoprocentně účinnou) a vadné výrobky ještě před expedicí opravit. Průměrné náklady na opravu jednoho výrobku před expedicí činí 4 PJ/kus a náklady na kontrolu činí 3 PJ/kus. Zisk z prodeje jednoho kusu výrobku činí 9 PJ/kus. Výrobce se rozhoduje, zda má dělat výstupní kontrolu. Příklad 2: Majitel penzionu se má rozhodnout, jakou zásobu uhlí si má v létě udělat. Zná následující údaje: Mírná zima Normální zima Chladná zima
Potřeba uhlí v tunách 4 5 6
Průměrná cena za tunu 7,0 7,5 8,0
Tyto ceny (v tisících Kč) odpovídají nákupu během zimy. V létě lze koupit uhlí za 6,0 tis.Kč za tunu, v domku je možnost uskladnit maximálně 6 tun. Uhlí, které po zimě zbyde, musí majitel odepsat. Jaká je optimální strategie tohoto majitele penzionu? 11
v y02
y01
Obrázek 5: Grafické řešení příkladu 5
Hry dvou hráčů s nekonstantním součtem Model neantagonistického konfliktu dvou hráčů Při neantagonistickém konfliktu každý z hráčů sleduje své zájmy, které ovšem nemusí být v protikladu se zájmy svého protihráče. Jedná se o hry s nekonstantním součtem. Hráč A má opět možnost volit strategie A1 , A2 , . . . , Am , hráč B má možnost volit mezi strategiemi B1 , B2 , . . . , Bn . Výplatu hráče A při volbě strategií Ai , Bj značíme M1 (Ai , Bj ). Výplata hráče B je M2 (Ai , Bj ). U her s konstantním součtem bylo možné z výplaty jednoho hráče odvodit i výplatu protihráče. U neantagonistického konfliktu toto možné není, neboť platí M1 (Ai , Bj ) + M2 (Ai , Bj ) 6= konst. Z tohoto důvodu je nutné pro každého hráče napsat matici jeho výplat. Tyto hry se proto nazývají dvojmaticové hry. Hry tohoto typu mohou být nekooperativní a kooperativní. Kooperativní hry pak můžeme rozdělit na hry s přenosnou výhrou (hráči se dohodnou na rozdělení společné výhry) a na hry s nepřenosnou výhrou (hráči se dohodnou pouze na volbě strategií). Nekooperativní hry Tak jako u her s konstantním součtem jsme hledali optimální strategie hráčů, i v tomto typu her hledáme optimální strategie - zde hledáme Nashův rovnovážný bod. Tento bod reprezentuje dvojici strategií (A0 , B0 ) - tzv. rovnovážné strategie. M1 (Ai , B0 ) ≤ M1 (A0 , B0 ) M2 (A0 , Bj ) ≤ M2 (A0 , B0 ) U her s nekonstantním součtem si při odchýlení od optimální strategie hráč sám pohorší a může způsobit i zhoršení výplaty protihráče. U her s konstantním součtem hráč, který se odchýlil, zajistí protihráči vyšší výplatu. Příklad 3: Uvažujme dva investory, kteří přemýšlejí o vstupu na trh ve třech různých odvětvích, ve kterých si mohou konkurovat. Každý z nich volí jedno odvětví, do kterého se rozhodne vstoupit, to znamená, nejprve si tam udělá reklamu a poté tam vstoupí. Tabulka uvádí zisky jednotlivých investorů v jednotlivém odvětví v případě, že tam vstoupí sami či oba. 12
zisk sami 1. odvětví 9,5 2. odvětví 9,8 3. odvětví 12 1. odvětví 8,9 2. odvětví 9 3. odvětví 10
1. investor
2. investor
oba 6 6 8 5,5 6 7
Obecně zapíšeme jako matice A a B.
1. odvětví 2. odvěví 3. odvětví
1. odvětví (6 , 5,5) (9,8 , 8,9) (12, 8,9)
2. odvětví (9,5 , 9) (6,6) (12, 9)
3. odvětví (9,5 , 10) (9,8 , 10) (8,7)
Pokusíme se najít Nashův rovnovážný bod, který se hledá následujícím způsobem: • V matici, reprezentující výplaty hráče A, nalezneme ve sloupcích maxima a příslušné dvojice zapíšeme do množiny Q. • V matici B najdeme maxima v řádcích a příslušné dvojice strategií zapíšeme do množiny R. • Vytvoříme průnik množiny Q a R (Q ∩ R), který představuje množinu rovnovážných bodů. Je-li Nashův rovnovážný bod jeden, máme návod k optimálnímu jednání, není-li, nastává problém. Může se totiž stát, že každý hráč zvolí jiný, a potom se dostanou do oboustranně nevýhodné pozice. V našem příkladu jsou dva rovnovážné body. Řešení je možné buď kooperací, nebo smíšenými strategiemi. V případě dvou rovnovážných bodů a více rovnovážných bodů ještě musíme rozlišit situace, kdy jeden rovnovážný bod pro oba hráče dominuje ostatní, potom tento bod dává návod na rovnovážné řešení. Příklad 4: 1 2
1 (4 , -4) (3, 4)
2 (-9 , -8) (-4,5)
1 2
1 (4 , 5) (-1, 0)
2 (-1 , -2) (8,9)
Příklad 5:
Příklad 6:
13
1 2 3
1 (-3 , -2) (-1, -1) (8, 9)
2 (-1 , -2) (4,4) (-1,-2)
3 (8 , 9) (-4,-3) (-3,-3)
1 2 3
1 (8,9) (-1, -1) (8, 9)
2 (-1 , -2) (4,4) (-1,-2)
3 (8 , 9) (0,-1) (8,9)
Příklad 7:
Příklad 8: 1 2
1 (0 , 4) (1, 2)
2 (2 , 3) (0,4)
Známé příklady nekooperativních her Vězňovo dilema je model konfliktu, ve kterém obtížnost situace spočívá v tom, že oboustranně výhodné řešení existuje, ale je nedostupné vzhledem k tomu, že jednostranné porušení solidárního jednání vede k podstatné výhodě pro toho, kdo porušil a k nevýhodě pro toho, kdo na oboustrannou solidárnost spoléhal. Z P
Z (2 , 2) (1, 10)
P (10 , 1) (6, 6)
Konflikt typu manželský spor se užívá pro modelování situace, kdy existuje více dvojic rovnovážných strategií, z nichž žádná není dominující. Například máme matici K S
K (2 , 1) (0, 0)
S (0 , 0) (1,2)
V manželském páru má jeden zájem o kulturu a druhý o sport. Pokud se oba zúčastní kulturní akce, má nižší užitek hráč 2. Pokud se oba zúčastní sportovní akce, má nižší užitek hráč 1. Jestliže se hráči rozdělí, užitek každého z nich je ještě nižší (rozladění ze sporu mezi hráči). V konfliktu typu kuřata se jedná o situace, kdy strany jednají tak, aby neztratily svou prestiž. Mějme např. dvojmaticovou hru U N
U (0 , 0) (5, -5)
N (-5 , 5) (-100,-100)
Každý z hráčů může buď ustoupit nebo neustoupit. Pokud oba hráči ustoupí, je výsledek neutrální, jednostranná ústupnost vede ke ztrátě prestiže toho, kdo ustoupil, oboustranná neústupnost vede ke krajně nepříznivým výsledkům u obou hráčů. Kooperativní hry s přenosnou výhrou 14
Pokud by hráčům dohoda přinesla větší výhry, je ji výhodné uzavřít. Hráči nejprve zjistí, kolik jsou schopni uhrát sami. Tyto výhry budeme značit v(A) a v(B). Buďto budeme a) maximalizovat zaručenou výhru, nebo budeme b) hledat rovnovážný bod. Ad a: Pro velikost výhry, kterou nemůže spoluhráč ohrozit platí: v(A) = maxi minj M1 (Ai , Bj ) v(B) = maxj mini M2 (Ai , Bj ) Pro maximální společnou výhru v(A, B) platí v(A, B) = maxi,j [M1 (Ai , Bj ) + M2 (Ai , Bj )], což je největší číslo v matici A a B. Dohoda se vyplatí uzavírat, pokud platí v(A, B) > v(A) + v(B) Další konflikt může nastat při dělení společné výhry. Částky, které dostanou hráči ze společné výhry, nejsou určeny jednoznačně a musí splňovat následující podmínku: ξ1 + ξ2 = v(A, B), ξ1 ≥ v(A), ξ2 ≥ v(B). Pro rozdělení výher bylo stanoveno několik postupů. 1. rozdělení na polovinu ξ1 = ξ2 =
v(A, B) 2
2. dělení v poměru přínosu hráčů ke společné výhře ξ1 : ξ2 = [v(A, B) − v(B)] : [v(A, B) − v(A)] 3. každý hráč si vezme částku, kterou je schopen uhrát sám a o zbytek se dělí buď na polovinu nebo opět v poměru přínosů k výhře Kooperativní hry s nepřenosnou výhrou Zde se sleduje odděleně výhra každého hráče v(A) a v(B). Ve dvoumatici pak hledáme čísla M1 (Ar , Bs ) a M2 (Ar , Bs ) tak, aby platilo M1 (Ar , Bs ≥ v(A), M2 (Ar , Bs ) ≥ v(B). Pokud tato čísla existují, je výhodné alespoň pro jednoho hráče smlouvu o kooperaci, která by mu zajistila větší výhru, než kdyby hrál samostatně.
15
Modely oligopolu Cournotův model Předpokládejme, že v odvětví působí dvě firmy (duopol). Cournotův model vychází z předpokladů konkurence v objemu produkce. Objemy produkce výrobců: q1 - objem výroby prvního výrobce, q2 - objem výroby druhého výrobce. Cena produkce je funkcí celkového objemu produkce p = g(q1 + q2 ), která je klesající, s růstem nabídky cena klesá. Příjmová funkce i-té firmy je součinem objemu produkce této firmy a ceny Ri (q1 , q2 ) = pqi . Mezní příjem udává změnu příjmu při jednotkové změně produkce ∂Ri (q1 , q2 )qi = g(q1 , q2 ) + qi ∂g(q1 , q2 )∂qi = p + qi ∂p∂qi . Nákladová funkce i-té firmy je rostoucí v závislosti na objemu produkce Ci (qi ). Mezní náklady udávají změnu celkových nákladů v závislosti na jednotkové změně výroby. Zisková funkce i-té firmy závisí na chování obou firem zi (q1 , q2 ) = pqi − Ci (qi ) Obě firmy se snaží maximalizovat svůj zisk vzhledem ke strategii konkurenta. Například druhá firma zvolí svoji strategii stanovením objemu výroby q2 ◦ . První firma maximalizuje svůj zisk, který bude záviset na jejím objemu výroby i na objemu výroby druhé firmy. Pro dosažení maxima musí platit podmínka ∂z1 (q1 , q2 ◦ )∂q1 = ∂R1 (q1 , q2 ◦ )∂q1 − dC1 (q1 )dq1 = 0 Pokud druhá firma zvolí svoji strategii stanovením objemu výroby q1 ◦ . Druhá firma maximalizuje svůj zisk, který bude záviset na jejím objemu výroby i na objemu výroby první firmy. Pro dosažení maxima musí platit podmínka ∂z2 (q1 ◦ , q2 )∂q2 = ∂R2 (q1 ◦ , q2 )∂q2 − dC2 (q2 )dq2 = 0 Rovnovážný stav je určen dvojicí strategií q1 , q2 , které splňují zároveň bě podmínky. V rovnovážném stavu je mezní příjem rovný mezním nákladům u obou firem. Z těchto rovnic můžeme odvodit funkce reakce chování duopolistů, která popisuje velikost produkce jednoho výrobce v závislosti na velikosti produkce druhého výrobce q1 = ϕ1 (q2 ), q2 = ϕ2 (q1 ). V Cournotově modelu obě se chovají obě firmy jako následníci, ani jedna z nich není v pozici vůdce. Příklad: Cena produkce je dána funkcí 16
p = 100 − (q1 − q2 ). Nákladové funkce obou firem jsou C1 (q1 ) = 150 + 12q1 , C2 (q2 ) = q2 2 Stackelbergův model Vychází ze stejných předpokladů, jako Cournotův, je jeho rozšířením. Jedna z firem je zde v pozici vůdce a druhá je v pozici následníka. Předpokládejme, že vůdcem je první firma, která stanoví svůj objem výroby q1 . Tato firma předpokládá, že druhá firma bude následníkem a určí svůj objem produkce podle funkce reakce q2 = ϕ2 (q1 ). První firma maximalizuje svůj zisk z1 = (q1 , q2 ) = z1 (q1 , ϕ2 (q1 )), 1 což je funkce jedné proměnné q1 . Z podmínky pro maximum ziskové funkce dz = 0 dostaneme dq1 velikost objemu produkce vůdce. Z funkce reakce vypočteme velikost produkce následníka. Dosazením těchto čísel do cenové funkce získáme i rovnovážnou cenu. Ve Stackelbergově modelu může být vždy jedna firma následníkem a jedna vůdcem, popř. obě firmy budou chtít být vůdci a toto vede ke Stackelbergově nerovnováze. Příklad Budeme vycházet ze stejného zadání jako v předchozím případě a nejprve budeme uvažovat první firmu jako vůdce a druhou jako následníka. Model kartelu Opět budeme uvažovat dvojici firem, jejichž objemy výroby značíme q1 , q2 . Cena je opět funkcí produkce, tato funkce je klesající. Nákladová funkce je rostoucí. Celkový zisk kartelu se vypočte podle vztahu
z(q1 , q2 ) = p(q1 + q2 ) − C1 (q1 ) − C2 (q2 ). Zisk je tedy funkcí objemu produkce obou duopolistů. Výrobní kvóty obou duopolistů, které maximalizují společný zisk, vychází z podmmínek ∂z∂q1 = 0, ∂z∂q2 = 0. Zisk je potřeba rozdělit mezi oba duopolisty tak, aby žádná z firem nedopadla hůře než u Cournotova modelu.
17
