Kontinuální hra - Continuous game

tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: "Kontinuální hra"  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Březen 2009) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

A nepřetržitá hra je matematický koncept používaný v herní teorie, který zobecňuje myšlenku běžné hry, jako je tic-tac-toe (kostky a kříže) nebo dáma (drafty). Jinými slovy, rozšiřuje představu diskrétní hry, kde si hráči vybírají z konečné sady čistých strategií. Koncepty kontinuální hry umožňují, aby hry zahrnovaly obecnější sady čistých strategií, které mohou být nespočetně nekonečný.

Obecně platí, že hra s nespočetně nekonečnými sadami strategií nemusí nutně mít Nashova rovnováha řešení. Pokud se však vyžaduje, aby byly sady strategií kompaktní a obslužné funkce kontinuální, pak bude zaručena Nashova rovnováha; je to zobecněním Glicksberga Kakutaniho věta o pevném bodě. Třída spojitých her je z tohoto důvodu obvykle definována a studována jako podmnožina větší třídy nekonečných her (tj. Her s nekonečnými sadami strategií), ve kterých jsou sady strategií kompaktní a funkce obsluhy spojité.

Formální definice

Definujte n- nepřetržitá hra hráče ${displaystyle G = (P, mathbf {C}, mathbf {U})}$ kde

${displaystyle P = {1,2,3, ldots, n}}$ je sada ${displaystyle n,}$ hráči,

${displaystyle mathbf {C} = (C_ {1}, C_ {2}, ldots, C_ {n})}$ kde každý ${displaystyle C_ {i},}$ je kompaktní sada, v metrický prostor, což odpovídá ${displaystyle i,}$ th hráčova sada čistých strategií,

${displaystyle mathbf {U} = (u_ {1}, u_ {2}, ldots, u_ {n})}$ kde ${displaystyle u_ {i}: mathbf {C} o mathbb {R}}$ je užitečná funkce přehrávače ${displaystyle i,}$

Definujeme ${displaystyle Delta _ {i},}$ být sadou Borela pravděpodobnostní opatření na ${displaystyle C_ {i},}$, což nám dává smíšený strategický prostor hráče i.

Definujte strategický profil ${displaystyle {oldsymbol {sigma}} = (sigma _ {1}, sigma _ {2}, ldots, sigma _ {n})}$ kde ${displaystyle sigma _ {i} v Delta _ {i},}$

Nechat ${displaystyle {oldsymbol {sigma}} _ {- i}}$ být strategickým profilem všech hráčů kromě hráče ${displaystyle i}$. Stejně jako u diskrétních her můžeme definovat a nejlepší odpověď korespondence pro hráče ${displaystyle i,}$, ${displaystyle b_ {i}}$. ${displaystyle b_ {i},}$ je vztah od množiny všech rozdělení pravděpodobnosti přes profily soupeřových hráčů k množině hráčů ${displaystyle i}$Strategie, tak, aby každý prvek

${displaystyle b_ {i} (sigma _ {- i}),}$

je nejlepší odpověď na ${displaystyle sigma _ {- i}}$. Definovat

${displaystyle mathbf {b} ({oldsymbol {sigma}}) = b_ {1} (sigma _ {- 1}) imes b_ {2} (sigma _ {- 2}) imes cdots imes b_ {n} (sigma _ {-n})}$.

Strategický profil ${displaystyle {oldsymbol {sigma}} *}$ je Nashova rovnováha kdyby a jen kdyby${displaystyle {oldsymbol {sigma}} * v mathbf {b} ({oldsymbol {sigma}} *)}$Existenci Nashovy rovnováhy pro každou souvislou hru s nepřetržitými užitnými funkcemi lze prokázat pomocí Irving Glicksberg zevšeobecnění Kakutaniho věta o pevném bodě.^[1] Obecně nemusí být řešení, pokud povolíme strategické prostory, ${displaystyle C_ {i},}$které nejsou kompaktní nebo pokud povolíme nespojité obslužné funkce.

Oddělitelné hry

A oddělitelná hra je spojitá hra, kde pro libovolné i funkce utility ${displaystyle u_ {i}: mathbf {C} o mathbb {R}}$ lze vyjádřit ve formě součtu produktů:

${displaystyle u_ {i} (mathbf {s}) = součet _ {k_ {1} = 1} ^ {m_ {1}} ldots součet _ {k_ {n} = 1} ^ {m_ {n}} a_ { i ,,, k_ {1} ldots k_ {n}} f_ {1} (s_ {1}) ldots f_ {n} (s_ {n})}$, kde ${displaystyle mathbf {s} v mathbf {C}}$, ${displaystyle s_ {i} v C_ {i}}$, ${displaystyle a_ {i ,,, k_ {1} ldots k_ {n}} v mathbb {R}}$a funkce ${displaystyle f_ {i ,,, k}: C_ {i} o mathbb {R}}$ jsou spojité.

A polynomiální hra je oddělitelná hra, kde každý ${displaystyle C_ {i},}$ je kompaktní interval zapnutý ${displaystyle mathbb {R},}$ a každá obslužná funkce může být zapsána jako vícerozměrný polynom.

Obecně se smíšené Nashovy rovnováhy oddělitelných her počítají snáze než nerozlučné hry, jak vyplývá z následující věty:

Pro každou oddělitelnou hru existuje alespoň jedna Nashova rovnováha, kde hráč i směsi maximálně ${displaystyle m_ {i} +1,}$ čisté strategie.^[2]

Zatímco rovnovážná strategie pro neoddělitelnou hru může vyžadovat nespočetně nekonečný Podpěra, podpora, je zaručeno, že oddělitelná hra bude mít alespoň jednu Nashovu rovnováhu s konečně podporovanými smíšenými strategiemi.

Příklady

Oddělitelné hry

Polynomiální hra

Zvažte hru mezi hráči s nulovým součtem pro dva hráče X a Y, s ${displaystyle C_ {X} = C_ {Y} = vlevo [0,1ight]}$. Označme prvky ${displaystyle C_ {X},}$ a ${displaystyle C_ {Y},}$ tak jako ${displaystyle x,}$ a ${displaystyle y,}$ resp. Definujte funkce obslužného programu ${displaystyle H (x, y) = u_ {x} (x, y) = - u_ {y} (x, y),}$ kde

${displaystyle H (x, y) = (x-y) ^ {2},}$.

Vztahy mezi nejlepší odpovědí čisté strategie jsou:

${displaystyle b_ {X} (y) = {egin {cases} 1, & {mbox {if}} yin left [0,1 / 2ight) 0 {ext {or}} 1, & {mbox {if}} y = 1/2 0, a {mbox {if}} yin vlevo (1 / 2,1ight] konec {případů}}}$

${displaystyle b_ {Y} (x) = x,}$

${displaystyle b_ {X} (y),}$ a ${displaystyle b_ {Y} (x),}$ neprotínají se, takže existuje

žádná čistá strategie Nashova rovnováha. Měla by však existovat smíšená strategická rovnováha. Chcete-li ji najít, vyjádřete očekávanou hodnotu, ${displaystyle v = mathbb {E} [H (x, y)]}$ jako lineární kombinace prvního a druhého momenty rozdělení pravděpodobnosti X a Y:

${displaystyle v = mu _ {X2} -2mu _ {X1} mu _ {Y1} + mu _ {Y2},}$

(kde ${displaystyle mu _ {XN} = mathbb {E} [x ^ {N}]}$ a podobně pro Y).

Omezení na ${displaystyle mu _ {X1},}$ a ${displaystyle mu _ {X2}}$ (s podobnými omezeními pro y,) jsou dány Hausdorff tak jako:

${displaystyle {egin {aligned} mu _ {X1} geq mu _ {X2} mu _ {X1} ^ {2} leq mu _ {X2} end {aligned}} qquad {egin {aligned} mu _ {Y1} geq mu _ {Y2} mu _ {Y1} ^ {2} leq mu _ {Y2} konec {zarovnáno}}}$

Každá dvojice omezení definuje kompaktní konvexní podmnožinu v rovině. Od té doby ${displaystyle v,}$ je lineární, jakékoli extrémy s ohledem na první dva momenty hráče budou ležet na hranici této podmnožiny. Rovnovážná strategie hráče i bude ležet

${displaystyle mu _ {i1} = mu _ {i2} {ext {or}} mu _ {i1} ^ {2} = mu _ {i2}}$

Všimněte si, že první rovnice umožňuje pouze směsi 0 a 1, zatímco druhá rovnice umožňuje pouze čisté strategie. Navíc, pokud nejlepší reakce v určitém bodě na hráče leží, leží na ${displaystyle mu _ {i1} = mu _ {i2},}$, bude ležet na celém řádku, takže 0 i 1 jsou nejlepší odpovědí. ${displaystyle b_ {Y} (mu _ {X1}, mu _ {X2}),}$ jednoduše dává čistou strategii ${displaystyle y = mu _ {X1},}$, tak ${displaystyle b_ {Y},}$ nikdy nebude dávat 0 i 1. Nicméně ${displaystyle b_ {x},}$ dává 0 i 1, když y = 1 / 2. Nashova rovnováha existuje, když:

${displaystyle (mu _ {X1} *, mu _ {X2} *, mu _ {Y1} *, mu _ {Y2} *) = (1 / 2,1 / 2,1 / 2,1 / 4), }$

To určuje jednu jedinečnou rovnováhu, kde hráč X hraje náhodnou směs 0 na 1/2 času a 1 na druhou 1/2 času. Hráč Y hraje čistou strategii 1/2. Hodnota hry je 1/4.

Neoddělitelné hry

Racionální funkce výplaty

Zvažte hru mezi hráči s nulovým součtem pro dva hráče X a Y, s ${displaystyle C_ {X} = C_ {Y} = vlevo [0,1ight]}$. Označme prvky ${displaystyle C_ {X},}$ a ${displaystyle C_ {Y},}$ tak jako ${displaystyle x,}$ a ${displaystyle y,}$ resp. Definujte funkce obslužného programu ${displaystyle H (x, y) = u_ {x} (x, y) = - u_ {y} (x, y),}$ kde

${displaystyle H (x, y) = {frac {(1 + x) (1 + y) (1-xy)} {(1 + xy) ^ {2}}}.}$

Tato hra nemá čistou strategii Nashova rovnováha. Může se to ukázat^[3] že existuje jedinečná smíšená strategie Nashova rovnováha s následující dvojicí funkce hustoty pravděpodobnosti:

${displaystyle f ^ {*} (x) = {frac {2} {pi {sqrt {x}} (1 + x)}} qquad g ^ {*} (y) = {frac {2} {pi {sqrt {y}} (1 + y)}}.}$

Hodnota hry je ${displaystyle 4 / pi}$.

Vyžaduje distribuci Cantor

Zvažte hru mezi hráči s nulovým součtem pro dva hráče X a Y, s ${displaystyle C_ {X} = C_ {Y} = vlevo [0,1ight]}$. Označme prvky ${displaystyle C_ {X},}$ a ${displaystyle C_ {Y},}$ tak jako ${displaystyle x,}$ a ${displaystyle y,}$ resp. Definujte funkce obslužného programu ${displaystyle H (x, y) = u_ {x} (x, y) = - u_ {y} (x, y),}$ kde

${displaystyle H (x, y) = součet _ {n = 0} ^ {infty} {frac {1} {2 ^ {n}}} vlevo (2x ^ {n} - vlevo (vlevo (1- {frac { x} {3}} ight) ^ {n} -left ({frac {x} {3}} ight) ^ {n} ight) ight) left (2y ^ {n} -left (left (1- {frac {y} {3}} ight) ^ {n} -left ({frac {y} {3}} ight) ^ {n} ight) ight)}$.

Tato hra má jedinečnou rovnováhu smíšené strategie, kde každý hráč hraje smíšenou strategii s kantor singulární funkce jako kumulativní distribuční funkce.^[4]

Další čtení

• H. W. Kuhn a A. W. Tucker, eds. (1950). Příspěvky k teorii her: sv. II. Annals of Mathematics Studies 28. Princeton University Press. ISBN  0-691-07935-8.

Viz také

• Graf spojitý

Reference