1. MATEMATICKÉ MODELY ROZHODOVACÍCH SITUACÍ

Markl: Matematické modely rozhodovacích situací /nhry1.doc/

Strana 1

1. MATEMATICKÉ MODELY ROZHODOVACÍCH SITUACÍ

Popis obecné rozhodovací situace (rozhodovacího procesu) vyžaduje zadání následujících údajů: 1. Výčet všech účastníků rozhodovací situace (procesu). 2. Souhrn všech představitelných výsledků, ve které může rozhodování vyústit. 3. Popis možnosti jednotlivých účastníků jak ovlivnit výsledek rozhodování. 4. Popis závislosti výsledku na jednání účastníků. 5. Subjektivní hodnocení možných výsledků z pohledu jednotlivých účastníků. Je-li počet účastníků rozhodovací situace alespoň dva, pak se zpravidla jedná o situaci konfliktní. Matematickou formalizací intuitivní představy o rozhodovací situaci či procesu) jsou následující dva pojmy: • Hra v normálním (strategickém) tvaru. Tento pojem modeluje jednorázové rozhodovací situace bez časového průběhu (statické rozhodování). • Hra v rozvinutém (extenzivním) tvaru. Tento pojem reflektuje rozhodovací procesy probíhající v čase (dynamické rozhodování).

1.1. Hry v normálním tvaru bez účasti náhody Definice 1.1.1: Hra v normálním tvaru (s preferenčními systémy) je pětice , kde • I je konečná a neprázdná množina nazývaná množinou hráčů, • Ω je neprázdná množina nazývaná prostorem výsledků, • Ai, i∈I, jsou neprázdné množiny, tzv. prostory strategií jednotlivých hráčů, • ρ je zobrazení typu A1×A2×...×An→Ω nazývané výsledkovou funkcí. • Ui, i∈I, jsou binární totální relace na množině Ω, tzv. preferenční systémy jednotlivých hráčů, systém relací {Ui: i∈I} nazýváme preferenčním schematem hry.

Poznámky 1.1.1: 1. 2.

4.

4.

Hráče (účastníky konfliktní situace) označujeme zpravidla přirozenými čísly, tj. klademe I={1,2,...,n}. Prvek ai∈Ai nazýváme strategií i-tého hráče a interpretujeme ji jako přesný a úplný popis jednání hráče v celém průběhu konfliktu (v každé možné pozici časově rozvinuté hry). Různé strategie i-tého hráče budeme rozlišovat horními indexy. Výsledkovou funkci často zapisujeme ve tvaru ρ(a)=ρ(a1,a2,...,an), kde a=(a1,a2,...,an), ai∈Ai , je vektor strategií zvolený jednotlivými hráči. Množinu A=A 1×A2×...×An všech vektorů strategií budeme nazývat prostorem vektorů strategií, neboli prostorem profilů strategií. Trojici <{Ω, Ai: i∈I},ρ> nazýváme pravidly hry (v normálním tvaru). Relace Ui interpretujeme takto: vztah ωUiω znamená, že i-tý hráč slabě preferuje výsledek ω oproti výsledku ω . Ke každé relaci Ui jsou přidruženy relace indiference ∼i a relace ostré preference >i definované takto: ω∼iω ⇔ ωUiω ∧ ω Uiω , ω>iω ⇔ ωUiω ∧ ¬ ω∼iω ,


5. 6.

Strana 2

kde ω, ω ∈Ω. Je-li relace Ui úplným uspořádáním, pak relace ∼i je ekvivalencí a relace >i ostrým uspořádáním. Čtveřici nazýváme někdy objektivní bází hry, zatímco preferenční schema hry {Ui: i∈I} charakterizující vlastní konflikt zájmů nazýváme subjektivní bází hry. Formální pětici interpretujeme v souladu s následujícími principy: • Princip realizace hry: každý hráč i∈I volí některou svou strategii ai∈Ai aniž zná volby ostatních hráčů. Tím je určen vektor strategií a=(a1,a2,...,an), kterému je přiřazen výsledkovou funkcí ρ výsledek ρ(a)=ρ(a1,a2,...,an)∈Ω. • Princip motivace jednání: jednání každého hráče i∈I je určeno výhradně jeho preferenčním systémem Ui, tj. když se z nějakého důvodu domnívá, že volba strategie ai∈Ai povede k výsledku ω a volba strategie ai ∈Ai k výsledku ω , přičemž ostře preferuje výsledek ω proti výsledku ω , tj. ω
Definice 1.1.2: Užitková funkce ui i-tého hráče pro preferenční systém ≥i je zobrazení ui: Ω→R (kde R je množina reálných čísel) s následující vlastností: ⇔ ui(ω ) ≤ ui(ω ). (∗) ω ≤i ω

Poznámky 1.1.2: 1. 2.

3.

Symbol "≤i" je ve formuli (∗) užit ve dvojím různém významu: nejdříve ve významu uspořádání na množině výsledků Ω a potom ve významu uspořádání na množině reálných čísel R. Hodnotu veličiny ui(ω) interpretujeme jako užitek přisuzovaného i-tým hráčem výsledku ω. Pokud neklademe na užitkovou funkci jiné podmínky než (∗), pak hodnoty užitkové funkce vypovídají pouze o uspořádání výsledků, nepodávají však žádnou informaci o tom, "o kolik" nebo "kolikrát" je jeden výsledek lepší než druhý. Aby užitková funkce měla i tuto vypovídací schopnost, je nutné přidat k podmínce (∗) ještě jednu podmínku, a to: (∗∗) u i((1-λ)ω + λω ) = (1-λ)ui(ω ) + λui(ω ), kde λ ∈<0,1>. Vlastnost (∗∗) požaduje, aby užitek směsi výsledků byl roven téže směsi užitků směšovaných výsledků. Tento požadavek vyjadřuje tzv. hypotézu (axióm) o středním užitku a je ekvivalentní s požadavkem, aby užitek byl aditivní veličinou, tj. aby "součet užitků byl roven užitku součtu". Užitkovou funkci splňující podmínku (∗) nazýváme ordinální užitkovou funkcí a ordinální funkci splňující navíc podmínku (∗∗) nazýváme kardinální užitkovou funkcí. Preferenční systém s jen ordinální užitkovou funkcí nazýváme ordinálním preferenčním systémem a preferenční systém vyjadřitelný kardinální užitkovou funkcí nazýváme kardinálním preferenčním systémem. Pomocí pojmu užitkové funkce lze výrazně zjednodušit pojem hry v normálním tvaru a usnadnit tak jejich matematické zpracování. Složíme-li výsledkovou funkci ρ: A=A1×A2×...×An→Ω a užitkovou funkci i-tého hráče u i: Ω→R dostáváme tzv. výplatní funkci i-tého hráče H i: A=A1× A2×...×An→R. Neboli Hi(a)=ui(ρ(a)), neboli Hi(a1,a2,...,an)=ui(ρ(a1,a2,...,an)). Viz dále definice 1.1.3.

Věta 1.1.1: 1.

2.

Nech ui(ω) je užitková funkce pro ordinální preferenční systém ≥i. Potom také funkce ui´(ω) = f(ui(ω)), kde f je libovolná reálná rostoucí funkce je rovněž užitkovou funkcí pro daný preferenční systém. Nech ui(ω) je užitková funkce pro kardinální preferenční systém ≥i. Potom také funkce ui´(ω) = α.ui(ω) + β, kde α, β jsou reálná čísla, α > 0, je rovněž užitkovou funkcí pro daný preferenční systém.


Strana 3

Důkaz: 1. 2.

Ukažeme, že má-li funkce ui vlastnost (∗), pak ji má i funkce ui´: ⇔ ui(ω ) ≥ ui(ω ) ⇔ f(ui(ω )) ≥ f(ui(ω )) ⇔ ui´(ω ) ≥ ui´(ω ) . ω ≥i ω Ukažeme, že má-li funkce ui vlastnosti (∗) a (∗∗), pak je má i funkce ui´: ⇔ ui(ω ) ≥ ui(ω ) ⇔ α.ui(ω )+β ≥ α.ui(ω )+β ⇔ ui´(ω ) ≥ ui´(ω ) . (∗) ω ≥i ω (∗∗) ui´[(1-λ)ω + λω ] = αui[...]+β = α(1-λ)ui(ω ) + αλui(ω ) + (1-λ+λ)β = = (1-λ) ui´(ω ) + λ ui´(ω ).

Definice 1.1.2: Hra v normálním tvaru s výplatními funkcemi je trojice , kde • I je konečná a neprázdná množina nazývaná množinou hráčů, • Ai, i∈I, jsou neprázdné množiny, tzv. prostory strategií jednotlivých hráčů, • Hi, i∈I, jsou zobrazení typu A1×A2×...×An→R, kde R označuje množinu reálných čísel, nazývané výplatními funkcemi.

Poznámky 1.1.3: 1.

2.

Formální trojici interpretujeme v souladu s následujícími principy: • Princip realizace hry: každý hráč i∈I volí některou svou strategii ai∈Ai aniž zná volby ostatních hráčů. Tím je určen vektor strategií a=(a1,a2,...,an), ke kterému jsou přiřazeny výplatními funkcemi výplaty jednotlivých hráčů H i(a)=Hi(a1,a2,...,an)∈R, i∈I. • Princip motivace jednání: jednání (tj. volba strategie) každého hráče i∈I je určeno výhradně jeho výplatní funkcí Hi, tj. když se z nějakého důvodu domnívá, že volba strategie a i∈Ai povede k (ostře) větší výplatě než volba strategie a i ∈Ai , pak nikdy nezvolí strategii ai . Každou hru v normálním tvaru lze převést na tvar s výplatnimi funkcemi (kanonická, standardní forma) - viz 2. bod poznámek 1.1.2.

Příklad 1.1.1: Uvažujme hru dvou hráčů spočívající v tom, že každý hráč ukáže jeden nebo dva prsty. Je-li součet počtu ukázaných prstů lichý (sudý), pak prvý (druhý) hráč vyplatí druhému (prvému) sumu rovnající se tomuto součtu. Zde: • I={1,2} • A1=A2={j,d}, A=A1×A2={(j,j),(j,d),(d,j),(d,d)} • Ω={s2, s3, s4)} • ρ: ρ(j,j)=s2, ρ(j,d)=ρ(d,j)=s3, ρ(d,d)=s4 • U1: s4 >1 s2 >1 s3 U2: s3 >2 s2 >2 s4 • u1: u1(s2)=2, u1(s3)=−3, u1(s4)=4 u2: u2(s2)=−2, u2(s3)=3, u2(s4)=−4 • H1: H1(j,j)=2, H1(j,d)=H1(d,j)=−3, H1(d,d)=4 H2: H2(j,j)=−2, H2(j,d)=H2(d,j)=3, H2(d,d)=−4

1.2. Hry v normálním tvaru s účastí náhody V této kapitole zobecníme model z předcházející kapitoly pro případ, kdy výsledek rozhodovací (konfliktní) situace je určen nejenom jednorázovými volbami jednotlivých účastníků, ale navíc i jednorázově provedeným náhodným pokusem. Provedení náhodného pokusu můžeme považovat za zásah přírody, kterou formálně můžeme považovat za 0-tého hrače (pseudohráče). Tento 0-tý hráč se liší od ostatních skutečných hráčů (i=1,2,...,n) ve dvou bodech:


• •

Strana 4

nemá preferenční systém (výsledky hry jsou mu lhostejné, všechny výsledky jsou v relaci indiference), jeho strategie (tj. výsledky náhodného pokusu) se realizují v souladu s jistým pravděpodobnostním rozdělením.

Hra vždy objektivně skončí v určitém konkrétním výsledku z jisté úplné množiny navzájem se vylučujících elementárních výsledků. Tuto množinu nazýváme prostorem elementárních výsledků E a její prvky elementárními výsledky e∈E. Žádný hráč a ani kooperace všech hráčů nemůže předem zaručit předem zvolený elementární výsledek. Volba každého hráče však může ovlivnit pravděpodobnostní rozložení na množině elementárních výsledků směrem k žádoucímu rozdělení z pohledu daného hráče. Množinu všech pravděpodobnostních rozložení na množině elementárních výsledků nazýváme prostorem smíšených výsledků ΩE a jeho prvky smíšenými výsledky ω∈ΩE . Nech E={e1,e2,...,ek} je množina elementárních výsledků a ω=(ω(e1),ω(e2),...,ω(ek))∈ΩE smíšený výsledek nad prostorem elementárních výsledků E. Souřadnice ω(ei) vektoru ω udává pravděpodobnost, že náhodný pokus skončíl výsledkem e i. Protože {e1,e2,...,ek} je úplný systém navzájem se vylučujích událostí, musí platit: 0≤ω(ei)≤1 pro i=1,2,...,k, ω(e1)+ω(e2)+...+ω(ek)=1 Prostor smíšených výsledků ΩE má následující vlastnosti: • ω1,ω2∈ΩE ∧ 0≤λ≤1 ⇒ (ω=(1-λ)ω1+λω2) ∈ΩE , tj. patří-li do množiny ΩE dva výsledky, pak do ní patří i jejich konvexní kombinace, tj. množina smíšených výsledků ΩE představuje lineární konvexní prostor. • Obecněji platí: •

•

ω1,ω2,...,ωr∈ΩE ∧ 0≤λj≤1 ∧ Σ1..rλj=1 ⇒ Σ1..rλjωj ∈ ΩE . Každý smíšený výsledek lze považovat za směs (konvexní kombinaci) elementárních výsledků: ω = Σe∈E ω(e)e . Každý elementární výsledek lze považovat za smíšený výsledek: ωe = e.

Definice 1.2.1: Hra v normálním tvaru (s preferenčními systémy) a s vlivem náhody je pětice ,{Ai: i∈I}, ρE, {Ui: i∈I}>, kde • I ={1,2,...,n} je množina hráčů, • ΩE je prostor smíšených výsledků nad prostorem elementárních výsledků E={e 1,e2,...,ek}, • {Ui: i∈I} jsou preferenční systémy jednotlivých hráčů; Ui jsou jsou libovolné totální relace na množině smíšených výsledků ΩE, • Σ={σ1,σ2,...,σr} je prostor stavů ("strategií") přírody a p=(p1,p2,...,pr) je pravděpodobnostní rozdělení na tomto prostoru Σ; dvojici <Σ,p> nazýváme pravděpodobnostním prostorem stavů přírody, p(σi)=pi je pravděpodobnost stavu σi; • {Ai: i∈I} jsou prostory strategií jednotlivých hráčů, • ρE je zobrazení (tzv. elementární výsledková funkce) typu Σ×A→E , kde A=A1×A2×...×An s vlastnostmi (i) (∀e∈E)(∃σ∈Σ)(∃a∈A)[ρE(σ,a)=e] (ii) (∀σ∈Σ)(∀a∈A)(∃e∈E)[ρE(σ,a)=e]

Poznámky 1.2.1: 1. 2. 3.

Vlastnosti (i), (ii) zabezpečují, že množina E představuje právě všechny možné konkrétní výsledky hry, tj. E={ρE(σ,a): σ∈Σ, a∈A}. Je-li Σ={σ1}, pak p(σ1)=1, Ω=ΩE=E, ρE(σ,a)=ρ(a) a jedná se o hru v normálním tvaru s preferenčními systémy a bez vlivu náhody podle definice 1.1.1. Formální šestici ,{Ai: i∈I},ρE>


Strana 5

interpretujeme v souladu s principy: • Princip realizace hry: každý hráč i∈I volí některou svou strategii ai∈Ai aniž zná volby ostatních hráčů a výsledek σ náhodného pokusu reprezentujícího stav přírody. Tím je určen vektor strategií (σ,a1,a2,...,an), kterému je přiřazen výsledkovou funkcí ρE výsledek ρ(σ,a)=ρ (σ,a1,a2,...,an)∈E. • Princip motivace jednání: jednání každého hráče i∈I je určeno výhradně jeho preferenčním systémem Ui, tj. když se z nějakého důvodu domnívá, že volba strategie a i∈Ai povede k smíšenému výsledku ω a volba strategie ai ∈Ai k smíšenému výsledku ω , přičemž ostře preferuje výsledek ω proti výsledku ω , tj. ω - viz definice 1.1.1. K tomu stačí položit Ω=ΩE a symbolicky definovat výsledkovou funkci takto

ρ(a) = Σσ∈Σ p(σ)(ρE(σ,a)). V tomto symbolickém zápisu ρ(a) značí smíšený výsledek (ω1,ω2,...,ωk), kde ωi je pravděpodobnost jevu ρE(σ,a) = ei. Eliminace náhody je tak vykoupena přechodem od elementárních ke smíšeným výsledkům. 5. Možný je i převod na normální hru bez náhody a s výplatními funkcemi, tj. na hru ve tvaru - viz definice 1.1.3. K tomu stačí definovat výplatní funkce hráčů takto: Hi(a) = ui(ρ(a)) = ui(Σσ∈Σ p(σ).(ρE(σ,a))) = Σσ∈Σ p(σ).ui(ρE(σ,a)), i∈I, neboli

Hi(a1,a2,...,an) = ... = Σσ∈Σ p(σ).ui(ρE(σ,a1,a2,...,an)), i∈I. Eliminace náhody je v tomto případě vykoupena přechodem od konkrétních realizací náhodných veličin k jejich očekávaným (středním) hodnotám.

Příklad 1.2.1: Tento příklad je rozšířením příkladu 1.1.1. Uvažujeme hru dvou hráčů spočívající v tom, že každý hráč ukáže jeden (j) nebo dva (d) prsty. Oproti příkladu 1.1.1 zde navíc hraje i náhoda ("příroda", "0-tý hráč"), která může "ukázat" jeden (j), dva (d) nebo žádný, tj. nula (n) prstů, a to s pravděpodobnostmi 1/4, 1/4 a 1/2. Je-li součet počtu všech ukázaných prstů (včetně těch "ukázaných" přírodou) lichý, pak prvý hráč vyplatí druhému částku rovnající se tomuto součtu. Je-li součet počtu všech ukázaných prstů sudý, pak naopak druhý hráč vyplatí prvému částku rovnající se součtu. Zde: • Hráči: I={1,2} • Praděpodobnostní prostor <Σ,p>: Σ =A0 ={n, j, d}, p = (1/2, 1/4 , 1/4). • Strategie hráčů: A1=A2={j, d}, • Profily strategií: A=A1×A2={(j, j), (j, d), (d, j), (d, d)} • Prostor výsledků: Ω={s2, s3, s4, s5, s6}, zde např. sk značí "součet = k" • Elementární výsledky: E = Σ×A1×A2={(n,j,j), (n,j,d), (n,d,j), (n,d,d), (j,j,j), (j,j,d), (j,d,j), (j,d,d), (d,j,j), (d,j,d), (d,d,j), (d,d,d)} •

Elementární výsledková funkce ρE : funkce je zadána tabulkou ve které řádky odpovídají stavům přírody a sloupce strategickým profilům hračů (j, j) (j, d) (d, j) (d, d) n j d

0.5 0.25 0.25

(n, j, j) (j, j, j) (d, j, j)

(n, j, d) (j, j, d) (d, j, d)

(n, d, j) (j, d, j) (d, d, j)

(n, d, d) (j, d, d) (d, d, d)

•

Prostor smíšených výsledků ΩE : { 0.5(n, j, j) + 0.25(j, j, j) + 0.25(d, j, j), 0.5(n, j, d) + 0.25(j, j, d) + 0.25(d, j, d), 0.5(n, d, j) + 0.25(j, d, j) + 0.25(d, d, j), 0.5(n, d, d) + 0.25(j, d, d) + 0.25(d, d, d) }

•

Výsledková funkce ρ:

ρ(j,j)= 0.5(n, j, j) + 0.25(j, j, j) + 0.25(d, j, j),


Strana 6

ρ(j,d)= 0.5(n, j, d) + 0.25(j, j, d) + 0.25(d, j, d), ρ(d,j)= 0.5(n, d, j) + 0.25(j, d, j) + 0.25(d, d, j), ρ(d,d)= 0.5(n, d, d) + 0.25(j, d, d) + 0.25(d, d, d). •

Preferenční systém U 1: (d, d, d) >1 (n, d, d) ∼1 (j, j, d) ∼1 (j, d, j) ∼1 (d, j, j) >1(n, j, j) >1(n, j, d) ∼1 (n, d, j) ∼1 ∼1 (j, j, j) >1 (j, d, d) ∼1 (d, j, d) ∼1 (d, d, j) Preferenční systém U 2: (d, d, d) <1 (n, d, d) ∼1 (j, j, d) ∼1 (j, d, j) ∼1 (d, j, j) <1(n, j, j) <1(n, j, d) ∼1 (n, d, j) ∼1 ∼1 (j, j, j) <1 (j, d, d) ∼1 (d, j, d) ∼1 (d, d, j)

•

u1: u1(s2)=2, u1(s3)=−3, u1(s4)=4 u2: u2(s2)=−2, u2(s3)=3, u2(s4)=−4

•

Výplatní funkce 1. hráče H 1: H1(j,j) = u1(ρ(j,j))= u1(0.5(n, j, j) + 0.25(j, j, j) + 0.25(d, j, j)) = = 0.5.u1(n, j, j) + 0.25.u1(j, j, j) + 0.25.u1(d, j, j) = = 0.5 . 2 + 0.25 . (-3) + 0.25 . 4 = 1.25 H1(j,d) = u1(ρ(j,d))= u1(0.5(n, j, d) + 0.25(j, j, d) + 0.25(d, j, d)) = = 0.5.u1(n, j, d) + 0.25.u 1(j, j, d) + 0.25.u1(d, j, d) = = 0.5 . (-3) + 0.25 . 4 + 0.25 . (-5)= -1.75 H1(d,j) = u1(ρ(d,j))= u1(0.5(n, d, j) + 0.25(j, d, j) + 0.25(d, d, j)) = = 0.5.u1(n, d, j) + 0.25.u 1(j, d, j) + 0.25.u1(d, d, j) = = 0.5 . (-3) + 0.25 . 4 + 0.25 . (-5)= -1.75 H1(d,d)= u1(ρ(d,d))= u1(0.5(n, d, d) + 0.25(j, d, d) + 0.25(d, d, d)) = = 0.5.u1(n, d, d) + 0.25.u 1(j, d, d) + 0.25.u 1(d, d, d) = = 0.5 . 4 + 0.25 . (-5) + 0.25 . 6 = 2.25 Výplatní funkce 2. hráče H 2: H2(j,j) = u2(ρ(j,j))= u2(0.5(n, j, j) + 0.25(j, j, j) + 0.25(d, j, j)) = = 0.5.u2(n, j, j) + 0.25.u2(j, j, j) + 0.25.u2(d, j, j) = = 0.5 . (-2) + 0.25 . 3 + 0.25 . (-4) = -1.25 H2(j,d) = ... = 1.75 H2(d,j) = ... = 1.75 H2(d,d)= ... = -2.25

1.3. Hry v rozvinutém tvaru s dokonalou informací Model konfliktní situace popsaný v předešlé kapitole nereflektuje skutečnost, že konfliktní situace zpravidla probíhá v čase a že její účastníci mohou do ní postupně zasahovat v jisté časové posloupnosti. V této kapitole, nahradíme jednoduchý matematický model pravidel hry složitějším a podrobnějším matematickým popisem vyplývajícím z našich představ o časovém průběhu konfliktu. V této kapitole se omezíme na speciální jednodušší případ her v rozvinutém tvaru a to na strategické hry s dokonalou informací. Tyto hry se vyznačují tím, že každý hráč v okamžiku, kdy má provést zásah do hry (je na tahu) zná pozici, ve které se nachází, z čehož vyplývá ( - viz následující definice grafu herních pozic), že zná celý dosavadní průběh hry (tj. všechny zásahy své i ostatních hráčů, které byly dosud provedeny).

Definice 1.3.1: Graf (herních) pozic je dvojice , kde • Z je neprázdná konečná množina nazývaná prostorem pozic, • Γ je zobrazení typu Z→2Z s následujícími vlastnostmi: (1) Existuje právě jedna pozice z(0)∈Z, pro kterou platí Γ-1z(0)=∅. (2) Je-li z∈Z a z≠z(0), pak Γ-1 z obsahuje právě jeden prvek.


Strana 7

(3) Je-li z∈Z a z≠z(0), pak existuje celé kladné číslo k a pozice z(1),z(2),...,z(k-1),z(k ) takové, že z(k )=z a z(j) = Γz(j-1) pro j=1,2,...,k.

Poznámky 1.3.1: 1.

2.

3.

4.

5.

6.

7.

Dvojice , kde Γ je zobrazení typu Z→2Z reprezentuje orientovaný graf: Z je množina uzlů a zobrazení Γ přiřazuje ke každému uzlu množinu uzlů Γz, do kterých vede orientovaná hrana z daného uzlu. Zápis z ∈Γz značí, že z uzlu z vede hrana do uzlu z . Zápis Γ-1z označuje množinu všech těch prvků množiny Z, ze kterých vede hrana do uzlu z, tj. Γ-1z={z : z∈Γz }. Pozice z∈Z představuje okamžitý stav v časovém vývoji hry. Prostor pozic Z zahrnuje všechny a priori možné stavy hry. Dvojici pozic (z,z ), kde z ∈Γz (neboli z∈Γ-1z ) nazýváme tahem hry, pozici z pozicí bezprostředně předcházející pozici z a pozici z pozicí bezprostředně následující za pozicí z. Pozici z(0), o které hovoří podmínka (1), nazýváme výchozí pozicí. Této pozici nepředchází žádná jiná pozice. Podmínka (2) říká, že každá pozice (s vyjímkou výchozí) má právě jedinou bezprostředně předcházející pozici. Podmínka (3) vyjadřuje požadavek, aby každá pozice z∈Z byla dosažitelná z výchozí pozice z(0) posloupností tahů. Pozice z∈Z na daném grafu pozic se nazývá výslednou pozicí, jestliže nemá žádné následující pozice, tj. platí-li Γz=∅. Z předpokladů (1) - (3) o grafu pozic vyplývá, že existuje aspoň jedna výsledná pozice. Důkaz: kdyby graf pozic neobsahoval žádnou výslednou pozici, pak by množina pozic nemohla být konečná, jak se předpoklácá. Trajektorie (délky k, kde k je nezáporné celé číslo) na grafu pozic je posloupnost (z 0,z1,...,zk) pozic splňujících podmínku zj∈Γzj-1 pro j=1,2,...,k. Pojem trajektorie je zobecněním pojmu tahu: tah je trajektorie délky 1. Partie hry o k tazích je trajektorie (z0,z1,...,zk) taková, že z0=z(0) a Γzk=∅. Tah (zj-1,zj) nazýváme j-tým tahem této partie. Množinu všech partií (na daném grafu pozic) označíme symbolem P a její prvky generickým symbolem π (s případnými rozlišovacími indexy). Z předpokladů (1) - (3) o grafu pozic vyplývá, že v každé partii (a obecněji v každé trajektorii) se každá pozice vyskytuje nejvýše jednou. Důkaz sporem: partie by musela obsahovat cyklus a aspoň jedna z pozic, které se v partii vyskytují více než jednou, by musela mít dva různé předchůdce; to však podle předpokladu (2) není možné.

Příklad 1.3.1: Obvyklý pojem pozice šachové hry (pouhé rozmístění figur na šachovnici spolu s uvedením, který z hráčů je na tahu) splňuje sice podmínku (3) ( každou šachovou pozici lze odvodit posloupností tahů z výchozí pozice), ale nesplňuje ani podmínku (1) (není pravda, že výchozí pozici nepředchází žádná pozice) ani podmínku (2) (není pravda, že každá pozice má právě jednu bezprostředně předcházející pozici). Ad (1): Výchozí šachová pozice může vzniknout z několika různých nevýchozích pozic návratem koní na výchozí postavení. Ad (2): Do téže šachové pozice se lze často dostat mnoha různými posloupnostmi tahů a to i takovými, které se liší posledním tahem a tím i poslední předcházející pozicí. Jednoduchými modifikacemi obvyklého pojmu šachové pozice lze docílit, aby graf nově pojatých šachových pozic vyhověl všem požadavkům (1) - (3) z definice 1.2.1. Toho dosáhneme, jestliže např. šachovou pozici budeme nově definovat jako následující skupinu údajů: (a) šachová pozice v původním smyslu, tj. rozmístění figur na šachovnici spolu s označením hráče, který je na tahu (b) údaj, zda je možné provést rošádu ( zda dosud nebylo taženo králem nebo věží) (c) údaj, zda je možné provést braní pěšcem mimochodem (d) posloupnost všech šachových pozic (v původním smyslu) od posledního braní nebo od posledního tahu pěšcem, spolu s údajem kolikrát se pozice opakovaly. Údaje (b) a (c) zabezpečují jednoznačné určení množiny Γz pro každou pozici z. Údaj (d) zabezpečuje splnění obou podmínek (1) a (2) pro nově definované pozice a také splnění podmínky (3), je-li tato


Strana 8

podmínka splněna pro pozice v původním smyslu (a to je). Konečnost množiny všech pozic je zaručena pravidlem o nepřípustnosti více než třikrát opakované pozice (v původním obvyklém smyslu).

Věta 1.3.1: Libovolný konečný graf splňující požadavky (1) a (3) pro některý prvek z(0)∈Z (viz definice 1.2.1) je možné nahradit grafem, který vyhovuje všem třem předpokladům (1),(2),(3) s výchozí pozicí z(0) tak, že obsahová interpretace grafu zůstane zachována. Je nutné pouze vhodně definovat pojem pozice.

Důkaz: Každou pozici nahradíme trajektorii vedoucí z výchozí pozice do dané pozice (v původním smyslu). Po této transformaci pojmu pozice graf pozic zajisté splňuje podmíku (2). V konkrétních případech postačí upravit pojem pozice méně radikálním způsobem - viz např. příklad 1.2.1.

Definice 1.3.2: Hra v rozvinutém tvaru s dokonalou informací a bez náhodových tahů je šestice , ρP, h, {Ui: i∈I}>, kde • I je množina hráčů (viz definice 1.1.1), • Ω je prostor výsledků (viz definice 1.1.1), • {Ui: i∈I} je preferenční schéma hry (viz definice 1.1.1), • je graf pozic (viz definice 1.3.1), • ρP je zobrazení typu P→Ω (kde P je množina všech partií nad grafem pozic - viz poznámky 1.3.1, 6.bod), nazývané výsledkovou funkcí pro rozvinutý tvar, • h je zobrazení typu Z →I (kde Z je množina všech nevýsledných pozic) zvané index tahu.

Poznámky 1.3.2: 1. 2. 3.

Výsledková funkce ρP přiřazuje každé partii π∈P výsledek ρP(π)∈Ω. Index tahu h přiřazuje každé pozici z∈Z hráče h(z)∈I, který je v této pozici na tahu. Trojice <,ρP, h> představuje pravidla hry s úplnou informací. Princip realizace hry: • Je-li výchozí pozice z(0)také výslednou pozicí, tj. je-li Γz(0)=∅, pak (z(0)) je partie a výsledek hry je ρP((z(0))). • Není-li z(0)také výslednou pozicí, pak hráč h(z (0)) volí některou ze svých alternativ, které má k dispozici v pozici z(0), tj. některou pozici z(1)∈Γz(0). Tím stav hry přejde v pozici z(1), a pokud tato pozice není výsledná, hráč h(z(1)) volí některou pozici z(2)∈Γz(1). Hra pokračuje tak dlouho, dokud pro nějaké n není pozice z (n), zvolená hráčem h(z(n-1)), výslednou pozicí. V tomto případě je posloupnost π=(z(0),z(1),...,z(n )) partie a výsledek hry je ρP(π). Princip motivace jednání: V každé pozici z∈Z se hráč h(z) řídí ve svém jednání výhradně podle svého systému preferencí Uh(z). Očekává-li z nějakého důvodu, že volba alternativy z ∈Γz povede k výsledku ω a volba alternativy z ∈Γz povede k výsledku ω , přičemž preferuje výsledek ω před výsledkem ω , tj. ω
Věta 1.3.2: Každou strategickou hru s úplnou informací v rozvinutém tvaru lze normalizovat, tj. převést ji do ekvivalentního normalizovaného tvaru.

Důkaz:


Strana 9

Na základě pravidel hry v rozvinutém tvaru <,ρP, h> stanovíme pravidla ekvivalentní hry v normálním tvaru <{Ai: i∈I},ρ>. Strategii ai∈Ai pro všechna i∈I definujeme jako zobrazení Zi→Z, kde Zi={z∈Z: h(z)=i ∧ Γz≠∅}, je definiční obor zobrazení (množina všech nevýsledných pozic ve kterých je i-tý hráč na tahu) a které splňuje podmínku z´=ai(z)∈Γz ((z,z´) je tah provedený i-tým hráčem v pozici z). Normalizovaná výsledková funkce ρ(a)=ρ(a1,...,an) je pak dána výrazem ρ(a)=ρP(π(a))=ρP(π(a1,...,an)), kde π(a))=π(a1,...,an) je partie, která proběhne při realizaci vektoru strategií a=(a1,...,an).

Poznámky 1.3.3: 1.

2.

Funkci ai definovanou v důkazu věty 1.3.2 nazýváme rozvinutou strategií hráče i∈I ve hře s úplnou informací. Rozvinutá strategie i-tého hráče stanoví pro každou pozici z∈Z, ve které je i-tý hráč na tahu a která současně není výsledná jaký tah (z,ai(z)) z možných tahů, tj. tahů splňujících podmínku ai(z)∈Γz, učiní. Písmenem Ai označujeme množinu všech (rozvinutých) strategií hráče i a písmenem A prostor vektorů (rozvinutých) strategií. To je v souladu se značením zavedeném pro hry v normálním tvaru.

Příklad 1.3.1: Hra "Nim". Hry se zúčastní dva hráči, kteří se střídají v tazích. Na začátku máme několik hromádek s obecně různým počtem předmětů téhož druhu (např. zápalek). Hráč, který je na tahu volí jednu hromádku a odebere z ní libovolný nenulový počet předmětů. Vyhrává ten hráč, který odebere poslední předměty tak, že všechny hromádky jsou prázdné. Počáteční stav (pozice) hry je charakterizována počtem hromádek n, počty předmětů v každé z nich (k10,k20,...,kn0) a stanovením hráče i0, který hru zahajuje. Tah hráče je popsán dvojicí čísel (r, s), kde r je přadové číslo hromádky a s je počet odebraných předmětů. Volba čísel r, s je omezena podmínkou, že volit je nutno pouze neprázdnou hromádku a odebrat alespoň jeden předmět. Pozice hry je charakterizována (n+1)-ticí(i,k1,k2,...,kn), kde i je pořadové číslo tahu a vektor(k1,k2,...,kn) udává aktuální počty předmětů v jednotlivých hromádkách. Kvůli určitosti a jednoduchosti analýzy předpokládejme n=2, k1=k2=2. Na obr.1.3.1 je zobrazen graf pozic této hry a to ve tvaru orientovaného stromu (všechny hrany jsou orientovány směrem vzhůru). Kořen stromu, vyznačený tučným kroužkem, reprezentuje výchozí pozici a listy stromu, vyznačené plným kroužkem, označují výslednou pozici. Každé větvi stromu odpovídá jedna partie hry. (-,(0,0)) (-,(0,0)) (-,(0,0))

(-,(0,0))

(-,(0,0))

1 (2,1)

(-,(0,0)) (-,(0,0)) (-,(0,0))

2

2

2

2

2

2

(2,1)

(2,1)

(1,1)

(2,1)

(1,1)

(1,1)

(2,(0,1)) (2,(0,1))

(2,(1,0)) (-,(0,0))

1 (2,2)

(2,1)

(1,1)

(1,1)

(2,1)

(2,(0,1)) (2,(1,0)) (2,(1,0)) (-,(0,0))

(-,(0,0))

1

(-,(0,0))

1

1

1 (2,1)

(1,1)

(2,1)

(1,1)

(1,2)

(1,1) (-,(0,0)) 2 (1,(1,0))

(-,(0,0))

2 (2,2)

(1,(0,1)) (2,1)

(1,(0,2))

(1,1)

(2,(0,2)) (1,2)

(1,(1,1))

(2,1)

(1,(1,0))

(2,2)

(1,(0,1))

(1,2)

(2,(1,2))

(2,(2,1))

(1,1)

(2,1)

(1,(1,1))

(1,1)

(2,1)

(1,(2,0))

(1,1)

(1,2)

(2,(2,0)) (2,2)

(1,(2,2))

Obr. 1.3.1


Strana 10

Příklad 1.3.2: Speciální případ hry Nim (viz příklad 1.3.1) s jedinou hromádkou obsahující 5 předmětů a a možností odebirat maximálně dva předměty v jednom tahu. Graf pozic je zobrazen stromem na obr. 1.3.2. Pozice je identifikována s trajektorií, která spojuje daný stav s počátečním stavem. Tak např. pozice označená 5431 představuje trajektorii (5,4,3,1) spojující počáteční stav "5 předmětů" s koncovým stavem "1 předmět". Ohodnocení hran vyjadřuje počet odebraných předmětů. 1

5

1

2

2 54 1

2

1 543

2 5432 1 1 54321

1

1

542

2 5431 1

2 54320 2. vyhrál

54310 2. vyhrál

2

531 1

1 532

1

2

1

2 53

1

2

2 5421 1

2 5321

2 5420 1. vyhrál

1

2 5320 1. vyhrál

5310 1. vyhrál

1 54210 2. vyhrál

53210 2. vyhrál

1 543210 1. vyhrál

Obr. 1.3.2 Rozklad množiny pozic: - Výchozí pozice: 5 - Z1={5, 543, 542, 532, 531, 54321} ... pozice, ve kt. je na tahu 1. hráč (trajekt. s lichou délkou) - Z2={54, 53, 5432, 5431, 5421, 5321} ... pozice, ve kt. je na tahu 2. hráč (trajekt. se sudou délkou) - Výsledné pozice, ve kterých vyhrává 1.hráč ={543210, 5420, 5320, 5310} - Výsledné pozice, ve kterých vyhrává 2.hráč ={54320, 54310, 54210,53210}

1.4. Hry v rozvinutém tvaru s náhodnými tahy a nedokon. informací V této kapitole se budeme zabývat následujícími obecnějšími typy her v rozvinutém tvaru: • Hry s náhodovými tahy. V těchto hrách je výsledek hry určen nejenom jednáním racionálních hráčů 1,2,...,n , ale i výsledky náhodných pokusů prováděných v průběhu hry, neboli "jednáním" náhody personifikované tzv. "nultým" hráčem. Tento pseudohráč, na rozdíl od reálných racionálních hráčů, nemá žádný zájem na výsledku hry a své alternativy realizuje v souladu s daným pravděpodobnostním rozložením . • Hry s nedokonalou informací. V těchto hrách nemusí hráč v okamžiku svého zásahu do průběhu hry znát přesně herní pozici ve které se nachází. Má pouze informaci o tom, že skutečná okamžitá pozice hry se nachází v určité množině pozic. Informovanost hráče o průběhu hry je tedy nedokonalá.

Definice 1.4.1: Hra v rozvinutém tvaru s dokonalou informací a bez náhodových tahů je sedmice , ρP, , h, {Ui: i∈I}>, kde prvky I, , ρP, h, {Ui: i∈I} mají podobný význam jako v definici 1.3.2. Nový prvek je definovaný takto:


•

•

Strana 11

Z0 je podmnožina množiny nevýsledných pozic (Z 0 ⊆ Z - Ze, kde Ze={z∈Z: Γz=∅}) ve kterých není na tahu žádný z hráčů množiny I={1,2,...,n} a ve kterých o následné pozici rozhoduje náhodný pokus ("příroda", "nultý hráč"). pz je pravděpodobnostní rozložení na množině Γz následníků pozice z∈Z0, ve které je prováděn náhodný pokus, tj. p z (z´) je pravděpodobnost, že z množiny následníků Γz bude vybrána právě pozice z´, tj. pravděpodobnost náhodného tahu (z,z´). Dvojice (Γz,pz) představuje pravděpodobnostní prostor pozic bezprostředně následujících za pozicí z.

Poznámky 1.4.1: 1.

2.

Systém množin {Z0,Z1,Z2,...,Zn,Ze} je rozklad na množině pozic Z. Z0 je množina pozic, ve kterých se provádí náhodný pokus (na tahu je "nultý" hráč, hráč bez preferencí - příroda). Zi, i∈I={1,2,...,n}, je množina pozic, ve kterých je na tahu i-tý hráč s preferencemi U i. Ze je množina výsledných pozic, v nichž hra končí a na tahu není nikdo. Formální sedmici z definice 1.4.1 interpretujeme v souladu s následujícími principy: • Princip realizace hry: Nech z(k)je pozice, ve které se hra nachází. Je-li z(k)∈Ze, tj. je-li Γz(k)=∅, pak (z(0),z(1),...,z(k)) je ukončená partie π a výsledek hry je ρP(π)= ρP((z(0),z(1),...,z(k))). Je-li z(k)∈Z0, pak se následující pozice z(k+1) určí náhodným pokusem v pravděpodobnostním prostoru (Γz(k),pz(k)). Je-li z(k)∈Zi, i∈I, pak následující pozici z(k+1) určí i-tý hrač výběrem z množiny Γz(k). • Princip motivace jednání: V každé pozici z∈Zi, i∈I, se hráč h(z)=i řídí ve svém jednání výhradně podle svého systému preferencí U i. Očekává-li z nějakého důvodu, že volba alternativy z ∈Γz povede k výsledku ω a volba alternativy z ∈Γz povede k výsledku ω , přičemž preferuje výsledek ω před výsledkem ω , tj. ω
Věta 1.4.1: Každou hru v rozvinutém tvaru a s náhodovými tahy lze normalizovat, tj. převést do ekvivalentního normálního tvaru podle definice 1.2.1 a následně i do normalizovaného tvaru podle definice (viz věta 1.4.1).

Důkaz: Na základě pravidel hry v rozvinutém tvaru , ρP, , h stanovíme pravidla ekvivalentní hry v normálním tvaru <Σ,p>, {Ai: i∈I}, ρE - viz definice 1.2.1. Nech Zi={z∈Z: h(z)=i } je množina všech pozic ve kterých je i-tý hráč na tahu. Strategii ai∈Ai pro všechna i∈I={1,2,...,n} definujeme jako zobrazení (funkci) Z i→Z, splňující podmínku z´=ai(z)∈Γz. Vektor funkcí a=(a1,...,an) z prostoru A=A1×...×An určuje jednoznačně chování všech účastníků konfliktní situace. Příroda je na tahu v pozicích z∈Z0. V těchto pozicích se provádí náhodné pokusy v pravděpodobnostních prostorech (Γz,pz): z∈Z0. Představme si, že globální náhodný pokus spočívající v současném provedení všech těchto pokusů. Tento pokus je pokusem v pravděpodobnostním prostoru <Σ,p> popisující celkové chování ("strategii") přírody v konfliktu. Jeho konkrétní výsledek σ∈Σ určuje spolu s konkrétním vektorem strategií hráčů a∈A jedinečný průběh hry, tj. partii π(σ,a))= π(σ,a1,...,an). Elementární výsledková funkce je pak dána vztahem ρE(σ,a)=ρP(π(σ,a))=ρP(π(σ,a1,...,an)). kde π(a) = π(a1,...,an) je partie, která proběhne při realizaci vektoru strategií a=(a1,...,an).

Definice 1.4.2: Hra v rozvinutém tvaru s nedokonalou informací a bez náhodových tahů je sedmice , ρP, h, <J,∆>, {Ui: i∈I}>, kde prvky I,Ω,{Ui: i∈I},,ρP, h mají týž význam jako v definici 1.2.2 a J, ∆ jsou nové prvky definované takto:


•

•

Strana 12

J je rozklad na množině všech nevýsledných pozic Z-Z e, kde Ze={z∈Z: Γz=∅}. Prvky(třídy, bloky) rozkladu J∈J nazýváme informačními množinami. Předpokládáme, že rozklad J má následující vlastnosti: (1) z,z ∈J∈J ⇒ h(z)=h(z ), tj. v pozicích patřících do informační množiny je na tahu vždy jeden a týž hráč, (2) (z,z ∈J∈J) ∧ (z≠z ) ⇒ (v grafu pozic neexistuje trajektorie spojující pozice z a z ), tj. každá trajektorie hry má s každou informační množinou společnou nejvýše jedinou pozici (podminka isovalence). ∆ je funkce přiřazující každé informační množině J rozklad ∆J na množině následníků všech jejich pozic, tj. na množině ΓJ = {z ∈Z: (∃z∈J)[z =Γz]}. Prvky rozkladu ∆J = {A1,A2, ... ,Ak} nazýváme alternativami příslušnými k inform. množině J. Předpokládáme, že rozklad ∆J splňuje podmínku: (3) (A∈∆J) ∧ (z∈J) ⇒ ( A ∩ Γz je jednoprvková množina ), tj. každá alternativa obsahuje právě jednoho následníka každého prvku informační množiny.

Poznámky 1.4.2: 1. 2.

3.

4.

Čtveřice <,ρP, h, <J,∆>> představuje úplná pravidla hry (s neúplnou informací a bez náhodových tahů). Dvojice <J,∆> je tzv. pravidlo pro volbu alternativ. Hra s úplnou informací je speciálním případem hry s neúplnou informací pro kterou platí: • J = {{z}: z∈Z}, tj. všechny informační množiny jsou jednoprvkové, • ∆{z} = {{z }: z ∈Γz}, tj. množina alternativ příslušná k dané pozici splývá s množinou následníků této pozice. Z vlastnosti (1) plyne, že každé informační množině J∈J můžeme přiřadit hráče h*(J)=h(z) pro některé (libovolné) z∈J, který je na dané informační množině na tahu. Označíme-li symbolem Zi množinu všech pozic, v nichž je na tahu i-tý hráč , tj. Zi={z∈Z: h(z)=i}, pak systém informačních množin Ji = {J∈J: h*(J)=i} představuje rozklad množiny Zi. Tento rozklad, tvořený všemi informačními množinami v nichž je i-tý hráč na tahu, nazýváme informačním schématem i-tého hráče. Z podmínky (3) vyplývá: • |Γz1| = |Γz2| = ... = |Γzk| • |J| = |A1| = |A2| = ... = |Ak| Situace je ilustrována na obr. 1.4.1. J

A 1

5.

ΓJ

A 2

A 3

Obr.1.4.1

Princip realizace hry: • Výchozí informační množina je jednoprvková množina {z (0)}. Je-li ∆{z(0)}=∅, tj. je-li Γz=∅, pak (z(0)) je partie a ρP(z(0)) je její výsledek. • Je-li ∆{z(0)}≠∅, pak hráč h(z(0) volí některou alternativu A1={z(1)} ze svých alternativ Γ ∆{z(0)} =Γz(0). Představme si, že partie již proběhla pozicemi z(0),z(1),...,z(k). Je-li (k) (k) (0) (1) (k) z =∅, pak z je výsledná pozice, pak π=(z ,z ,...,z ) je partie a ρP(π) je její výsledek. Jestliže Γz(k)≠∅, pak hráč h(z(k)), rozhodující se na informační množině J k, jednoznačně určené pozicí z(k), má k dispozici neprázdnou množinu alternativ ∆Jk ze které volí některou


6.

Strana 13

alternativu Ak. Následná pozice z(k+1 ) hry je jednoznačně dána jednoprvkovým průnikem Ak ∩Γz(k) ={z(k+1 )}. Princip motivace jednání: Na každé informační množině J se hráč i=h*(J) rozhoduje pouze podle svého systému preferencí Ui. Očekává-li, že alternativa A∈∆J vede k výsledku ω a alternativa A ∈∆J vede k výsledku ω a přitom ω >i ω , potom nikdy nezvolí alternativu A .

Věta 1.4.2: Každou hru v rozvinutém tvaru s nedokonalou informací a bez náhodových tahů lze normalizovat, tj. převést do ekvivalentního normalizovaného tvaru.

Důkaz: Na základě pravidel hry v rozvinutém tvaru <,ρP, h, <J,∆>> stanovíme pravidla ekvivalentní hry v normálním tvaru <{Ai: i∈I},ρ>. Symbolem Ji ={J∈J: h*(J)=i, ∆J≠∅} označme množinu informačních množin ve kterých je i-tý hráč na tahu. Na každé množině Ji, i∈I, definujeme funkci ai∈Ai přiřazující ke každé informační množině i-tého hráče J∈Ji jistou alternativu ai(J)∈∆J z množiny jeho alternativ ∆J. Funkce ai popisuje tedy jednoznačně způsob chování i-tého hráče v průběhu hry a vektor funkcí a=(a 1,a2,...,an) jednoznačně determinuje celý průběh hry. Volba alternativy na libovolné informační množině J∈J je tedy dána funkcí a(J)=ah*(J)(J). Pro skutečný konkrétní průběh hry π=(z(0), z(1),...,z(k)) platí z(j)=J(j) ∧ z(j+1)=Γz(j)∩a(J(j)) pro j=0,1,...,k-1 a Γz(k)=∅. Ke každému vektoru strategií a∈A=A1×A2×...×An existuje tedy právě jedna partie π(a). Normalizovaná výsledková funkce je pak definována takto: ρ(a)=ρP(π(a)).

Příklad 1.4.1: V tomto příkladu uvádíme různé varianty dále popsané hry v rozvinutém tvaru. V prvém kroku této hry voli příroda (provedením náhodného pokusu) jedno z čísel 0, 1 a to se stejnou pravděpodobností, tj. s pravděpodobnostmi 1/2, 1/2. V druhém kroku volí 1.hráč jedno z čísel 1, 2 a ve třetím (a posledním) kroku volí 2.hráč opět jedno z čísel 1, 2. Je-li součet všech zvolených čísel sudý, vyhrává 1.hráč tento součet a 2.hráč tento součet prohrává. Je-li součet všech zvolených čísel lichý, pak naopak 2.hráč vyhrává tento součet a 1.hráč tento součet prohrává. Na všech dále uvedených obrázcích 1.4.2-5 je zobrazen graf pozic této hry. Horní uzel zobrazuje pozici, kdy je na tahu příroda, dva uzly v dalším řádku jsou pozice 1.hráče, čtyři uzly v dalším řádku jsou pozice ve kterých je nahu 2.hráč a konečné uzly v nejnižší řádku představují tzv. terminální pozice vekterých již není na tahu nikdo a hra skončila. Ohodnocení hran udávají čísla volená hráči, kteří jsou na tahu v horní pozici hrany. Dvojice čísel ohodnocujících terminální pozice jsou výhry (hodnoty výplatní funkce) pro 1. a 2. hráče v případě, že partie skončila v dané terminální pozici. Varianty zobrazené na obrázcích 1.4.2-5 se navzájem liší způsobem rozkladu množiny pozic v nichž jsou na tahu 1. a 2. hráč na systém informačních množin, tj. podle míry informovanosti těchto hráčů o stavu hry v okamžicích, kdy se rozhodují. Informační množiny 1. hráče jsou na obrázcích zobrazeny čárkovanými ovály a informační množiny 2. hráče tečkovanými ovály. Všimněme si, že rozklady na všech obrázcích splňují podmínky (1), (2), (3) z definice 1.4.2.


Strana 14

příroda 0 (1/2)

1 (1/2) 1. hráč

1

2

1

2 2. hráč

1

2,-2

1

2

-3,3

2

-3,3

2

1 4,-4

terminální pozice

4,-4

4,-4

-3,3

2

1

-5,5

Obr.1.4.2

Na obr.1.4.2 je zobrazen případ, kdy ani tah přírody ani tah 1. hráče není zveřejněn. V tomto případě 1. hráč v okamžiku své volby neví v které ze dvou možných pozic se hra nachází a 2. hráč v okamžiku svého rozhodování neví v které ze čtyř možných pozic se hra nachází. Všichni účastníci hry, přiroda a oba racionální hráči, provádí své volby nezávisle na volbách zbývajících dvou účastníků. Je to totéž jakoby se všichni účastnici hry rozhodovali současně (a nebo v libovolném pořadí). Informovanost obou hráčů o stavu hry je nulová. příroda 0 (1/2)

1 (1/2) 1. hráč

1

2

1

2 2. hráč

1

1

2

2,-2

-3,3

2

-3,3

2

1 4,-4

4,-4

-3,3

2

1

4,-4

-5,5

terminálni pozice

Obr.1.4.3 Na obr.1.4.3 je zobrazen případ, kdy tah přírody (výsledek náhodného pokusu) zveřejněn není, ale následující tah 2. hráče zveřejněn je. Míra informovanosti 2. hráče se zlepšila: v okamžiku, kdy je na tahu, ví v které ze dvou informačních množin se nachází. Nicméně jeho informovanost není dokonalá, nebo tyto informační množiny jsou dvouprvkové a on neví v které ze dvou pozic se hra nachází. příroda 0 (1/2)

1 (1/2) 1. hráč

1

2

1

2 2. hráč

1

2,-2

2

-3,3

1

-3,3

2

1 4,-4

-3,3

2

1

4,-4

4,-4

2 terminální pozice

-5,5

Obr.1.4.4

Na obr.1.4.4 je zobrazen opačný případ vzhledem k předchozímu, kdy výsledek náhodného pokusu (tah přírody) zveřejněn je, ale volba (tah) 1. hráče zveřejněna není. V tomto případě je 1. hráč dokonale informován, ale druhý jen částečně (ví v které ze dvou dvouprvkových informačních množin se nachází, ale neví v které ze dvou pozic té či oné informační množiny).


Strana 15

příroda 0 (1/2)

1 (1/2) 1.hráč

1

2

1

2 2.hráč

1

2,-2

2

-3,3

1

-3,3

2

1 4,-4

-3,3

2

1

4,-4

4,-4

2 terminální pozice

-5,5

Obr.1.4.5

Na obr.1.4.5 je zobrazen případ, který je protikladný k prvému případu zobrazenému na obr.1.4.2: volby všech účastníků rozhodovacího procesu jsou veřejné a oba hráči v okamžicích rozhodování znají přesně pozici, ve které se hra nachází, tj. disponují dokonalou informovaností. Všechny informační množiny jsou jednoprvkové. Obrázky 1.4.2-5 (grafy pozic spolu se zobrazením informačních množin) definují čtyři různé hry v rozvinutém (extenzivním) tvaru. Převe te tyto hry do normálního tvaru. Jedná se o antagonistické hry (konečné hry dvou hráčů s nulovým součtem maticové hry) a až s naučíte tyto hry řešit (viz kap. 2.1 těchto textů) řešte je, tj. popište racionální jednání obou racionálních hráčů v uvedených čtyřech situacích.

Definice 1.4.3: Hra v rozvinutém tvaru s nedokonalou informací a s náhodovými tahy je osmice , ρP, , h, <J,∆>, {Ui: i∈I}>, kde význam prvků I,ΩE,{Ui: i∈I},,ρP,, h je objasněn v definici 1.4.1 a význam prvku <J,∆> v definici 1.4.2. Použitím postupů vysvětlených v kapitolách 1.3-1.4 lze hry v rozvinutém tvaru s nedokonalou informací a s náhodovými tahy normalizovat, tj. eliminovat z nich náhodu, neurčitost i čas. Normalizace jakékoliv konečné hry je tedy v principu vždy možná, prakticky je však proveditelná jen v případě velmi jednoduchých her. Cenu, kterou za pojmové zjednodušení platíme, spočívá totiž v podstatném zvětšení prostoru výsledků a prostorů možných strategií jednotlivých hráčů. V případě reálných her (např. karetních) jsou většinou graf pozic, systém informačních množin a sdružená pravděpodobnostní rozdělení natolik složitými objekty, že jejich úplné zobrazení (a natož pak analýza hry) jsou mimo současné možnosti výpočetní techniky.

1. MATEMATICKÉ MODELY ROZHODOVACÍCH SITUACÍ

Recommend Documents