Cena stability - Price of stability - Wikipedia

Tento článek obsahuje a seznam doporučení, související čtení nebo externí odkazy, ale jeho zdroje zůstávají nejasné, protože mu chybí vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Leden 2014) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

tento článek může být pro většinu čtenářů příliš technická na to, aby je pochopili. Prosím pomozte to vylepšit na aby to bylo srozumitelné pro neodborníky, aniž by byly odstraněny technické podrobnosti. (Leden 2014) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v herní teorie, cena stability (PoS) hry je poměr mezi hodnotou nejlepší objektivní funkce jedné z jejích rovnováh a optimálním výsledkem. PoS je relevantní pro hry, ve kterých existuje nějaká objektivní autorita, která může hráče trochu ovlivnit a možná jim pomůže konvergovat k dobrému Nashova rovnováha. Při měření toho, jak efektivní je Nashova rovnováha v konkrétní hře, často mluvíme také o cena anarchie (PoA).

Příklady

Další způsob vyjádření PoS je:

${ displaystyle { text {PoS}} = { frac { text {hodnota nejlepší Nashovy rovnováhy}} { text {hodnota optimálního řešení}}}, { text {PoS}} geq 0.}$

V následujícím vězňovo dilema protože existuje jediná rovnováha (B, R), máme PoS = PoA = 1/2.

Na tomto příkladu, který je verzí hry bitvy o pohlaví, existují dva rovnovážné body (T, L) a (B, R) s hodnotami 3 a 15. Optimální hodnota je 15. PoS = 1, zatímco PoA = 1/5.

Pozadí a milníky

Cena stability byla nejprve studována A. Schulzanem a N. Mosesem a byla takzvaná ve studiích E. Anshelevicha. Ukázali, že čistá strategie Nashova rovnováha vždy existuje a cena za stabilitu této hry je nanejvýš n harmonické číslo v orientovaných grafech. U neorientovaných grafů Anshelevich a další představili pevnou vazbu na cenu stability 4/3 pro případ jednoho zdroje a dvou hráčů. Jian Li dokázal, že pro neorientované grafy s významným cílem, ke kterému se všichni hráči musí připojit, je cena stability hry Shapely network design ${ displaystyle O ( log n / log log n)}$ kde ${ displaystyle n}$ je počet hráčů. Na druhou stranu cena anarchie je o ${ displaystyle n}$ v této hře.

Hry se síťovým designem

Založit

Hry se síťovým designem mají velmi přirozenou motivaci pro cenu stability. V těchto hrách může být cena anarchie mnohem horší než cena stability.

Zvažte následující hru.

• ${ displaystyle n}$ hráči;
• Každý hráč ${ displaystyle i}$ si klade za cíl spojit ${ displaystyle s_ {i}}$ na ${ displaystyle t_ {i}}$ na orientovaném grafu ${ displaystyle G = (V, E)}$;
• Strategie ${ displaystyle P_ {i}}$ pro hráče jsou všechny cesty z ${ displaystyle s_ {i}}$ na ${ displaystyle t_ {i}}$ v ${ displaystyle G}$;
• Každá hrana má cenu ${ displaystyle c_ {i}}$;
• „Spravedlivé rozdělení nákladů“: Kdy ${ displaystyle n_ {e}}$ hráči si vyberou výhodu ${ displaystyle e}$, náklady ${ displaystyle textstyle d_ {e} (n_ {e}) = { frac {c_ {e}} {n_ {e}}}}$ je mezi nimi rozdělen rovnoměrně;
• Cena hráče je ${ displaystyle textstyle C_ {i} (S) = součet _ {e v P_ {i}} { frac {c_ {e}} {n_ {e}}}}$
• Sociální náklady jsou součtem hráčových nákladů: ${ displaystyle textstyle SC (S) = součet _ {i} C_ {i} (S) = součet _ {e v S} n_ {e} { frac {c_ {e}} {n_ {e }}} = součet _ {e v S} c_ {e}}$.

Síťový design hra s ${ displaystyle Omega (n)}$ Cena anarchie

Cena anarchie

Cena anarchie může být ${ displaystyle Omega (n)}$. Zvažte následující hru o návrhu sítě.

Hra Pathological Price of Stability

Zvažte v této hře dvě různé rovnováhy. Pokud všichni sdílejí ${ displaystyle 1+ varepsilon}$ okraj, sociální náklady jsou ${ displaystyle 1+ varepsilon}$. Tato rovnováha je skutečně optimální. Pamatujte však, že každý, kdo sdílí ${ displaystyle n}$ edge je také Nashova rovnováha. Každý agent má náklady ${ displaystyle 1}$ v rovnováze a přepnutí na druhý okraj zvyšuje jeho cenu ${ displaystyle 1+ varepsilon}$.

Dolní mez ceny stability

Zde je místo toho patologická hra ve stejném duchu pro cenu stability. Zvažte ${ displaystyle n}$ hráči, z nichž každý pochází z ${ displaystyle s_ {i}}$ a snaží se připojit k ${ displaystyle t}$. Cena neoznačených okrajů se považuje za 0.

Optimální strategií je, aby každý sdílel ${ displaystyle 1+ varepsilon}$ okraj, což přináší celkové sociální náklady ${ displaystyle 1+ varepsilon}$. Pro tuto hru však existuje jedinečný Nash. Pamatujte, že když je hráč v optimu, platí každý ${ displaystyle textstyle { frac {1+ varepsilon} {n}}}$a hráč 1 může snížit své náklady přepnutím na ${ displaystyle textstyle { frac {1} {n}}}$ okraj. Jakmile k tomu dojde, bude v zájmu hráče 2 přepnout na ${ displaystyle textstyle { frac {1} {n-1}}}$ hrana atd. Agenti nakonec dosáhnou Nashovy rovnováhy placení za své vlastní výhody. Tato alokace má sociální náklady ${ displaystyle textstyle 1 + { frac {1} {2}} + cdots + { frac {1} {n}} = H_ {n}}$, kde ${ displaystyle H_ {n}}$ je ${ displaystyle n}$^th harmonické číslo, který je ${ displaystyle Theta ( log n)}$. I když je neomezená, cena stability je v této hře exponenciálně lepší než cena anarchie.

Horní hranice ceny stability

Všimněte si, že hry podle návrhu sítě jsou hry s přetížením, a proto připouštějí potenciální funkci ${ displaystyle textstyle Phi = součet _ {e} součet _ {i = 1} ^ {n_ {e}} { frac {c_ {e}} {i}}}$.

Teorém. [Věta 19.13 z Reference 1] Předpokládejme, že existují konstanty ${ displaystyle A}$ a ${ displaystyle B}$tak, že pro každou strategii ${ displaystyle S}$,

${ displaystyle A cdot SC (S) leq Phi (S) leq B cdot SC (S).}$

Pak je cena stability nižší než ${ displaystyle B / A}$

Důkaz. Globální minimum ${ displaystyle NE}$ z ${ displaystyle Phi}$ je Nashequilibrium, takže

${ Displaystyle SC (NE) leq 1 / A cdot Phi (NE) leq 1 / A cdot Phi (OPT) leq B / A cdot SC (OPT).}$

Nyní si připomeňme, že sociální náklady byly definovány jako součet nákladů přes hranice, takže

${ displaystyle Phi (S) = součet _ {e v S} součet _ {i = 1} ^ {n_ {e}} { frac {c_ {e}} {i}} = součet _ {e in S} c_ {e} H_ {n_ {e}} leq sum _ {e in S} c_ {e} H_ {n} = H_ {n} cdot SC (S).}$

Triviálně máme ${ displaystyle A = 1}$a výše uvedený výpočet dává ${ displaystyle B = H_ {n}}$, takže můžeme vyvolat větu o horní hranici ceny stability.

Viz také

• Konkurenční hra o umístění zařízení - hra bez stability ceny.

Reference

1. Vazirani, Vijay V.; Nisan, Noame; Roughgarden, Tim; Tardos, Éva (2007). Algoritmická teorie her (PDF). Cambridge, Velká Británie: Cambridge University Press. ISBN  0-521-87282-0.
2. L. Agussurja a H. C. Lau. Cena stability v sobeckých programovacích hrách. Web Intelligence and Agent Systems: An International Journal, 9: 4, 2009.
3. Jian Li. An ${ displaystyle O ( log n / log log n)}$ horní hranice ceny stability pro neorientované hry Shapely network design. Information Processing Letters 109 (15), 876-878, 2009.