Prisen på stabilitet

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 9. marts 2022; checks kræver 16 redigeringer .

Prisen på stabilitet ( engelsk price of stability , PoS) for spillet er forholdet mellem den optimale værdi af den objektive funktion i en af dens ligevægtstilstande og det optimale resultat. Prisen på stabilitet giver mening for spil, der har en højere styrke eller spilbetingelser, der påvirker spillernes position på en eller anden måde og kan hjælpe dem med at konvergere til Nash-ligevægten . Når man måler effektiviteten af Nash-ligevægten i ethvert spil, giver det mening at overveje prisen på anarki ( Eng. Price of Anarchy , PoA).

Eksempler

PoS kan udtrykkes som følger:

PoS={\frac {N}{S)),\ PoS\geqslant 0.

Her er værdien af den bedste Nash-ligevægt og er værdien af den optimale løsning. ${\tekststil N}$ ${\textstyle S}$

I Prisoner 's Dilemma -spillet nedenfor vil spillerne ikke altid samarbejde med hinanden, selvom det er i deres bedste interesse, da der kun er én ligevægt ( , ), vi har . ${\tekststil B}$ ${\textstyle R}$ $PoS=PoA={\tfrac {1}{2}}$

Fangens dilemma

	${\tekststil L}$	${\textstyle R}$
${\textstyle T}$	(2.2)	(0,3)
${\tekststil B}$	(3,0)	(1.1)

Dette eksempel er en version af kampen mellem kønnene . Den har to ligevægtspunkter, ( , ) og ( , ) med henholdsvis værdierne 3 og 15. Den optimale værdi er 15. Så mens . ${\textstyle T}$ ${\tekststil L}$ ${\tekststil B}$ ${\textstyle R}$ $PoS=1$ $PoA={\tfrac {1}{5}}$

Kønnenes kamp

	${\tekststil L}$	${\textstyle R}$
${\textstyle T}$	(2.1)	(0,0)
${\tekststil B}$	(0,0)	(5,10)

Baggrund og milepæle

Prisen på stabilitet blev først studeret af A. Shultzan og N. Mozes, og selve udtrykket optrådte i E. Anshelevichs værker. De viste, at Nash-ligevægten altid eksisterer i rene strategier, og stabilitetsomkostningerne for dette spil overstiger ikke det n'te harmoniske tal i rettede grafer. For urettede grafer præsenterede Anshelevich et al. en hård stabilitetsgrænse på 4/3 for tilfældet med én kilde og to spillere. Yen Lee beviste, at for sådanne grafer med forskellige destinationer for alle spillere, som alle spillere skal have forbindelse til, er prisen for et stabilt spilflow for at opbygge et Shapley-netværk, hvor antallet af spillere er. På den anden side er omkostningerne ved anarki for spillet ca. $O(\log n/\log \log n),$ $n$ $n$

Netværksbygningsspil

Vilkår for spille

Netværksopbygningsspil har en naturlig begrundelse for prisen på stabilitet. I disse spil kan prisen på anarki være meget mindre end prisen på stabilitet.

Et eksempel på følgende spil:

$n$ spillere;
Målet for hver spiller er at forbinde hjørner og i en rettet graf ; $jeg$ $s_{i}$ $t_{i}$ $G=(V,E)$
Strategierne for spilleren er alle stier fra til i grafen ; $P_{i}$ $s_{i}$ $t_{i}$ $G$
Hver bue har en pris ; $c_{i}$
"Fair prisfordeling": Hvis spillerne vælger en bue , fordeles prisen ligeligt mellem dem; $n_{e}$ $e$ $d_{e}(n_{e})={\frac {c_{e}}{n_{e}}}$
Prisen for spilleren er ; $C_{i}(S)=\sum _{e\in P_{i}}{\frac {c_{e}}{n_{e}}}$
De sociale omkostninger er lig med summen af priserne for spillerne: . $SC(S)=\sum _{i}C_{i}(S)=\sum _{e\in S}n_{e}{\frac {c_{e}}{n_{e}} }=\sum _{e\in S}c_{e}$

Prisen på anarki

Prisen for anarki kan være . Et eksempel på følgende netværksopbygningsspil. $\omega(n)$

Der er 2 forskellige balancer i dette spil. Hvis alle deler buen , så er de sociale omkostninger . Desuden er denne balance optimal. Dog er opdelingen af alle buer også en Nash-ligevægt. Enhver agent har en pris i ligevægtsstrategien, og hvis den skiftes til en anden bue, hæves prisen til . $1+\varepsilon$ $1+\varepsilon$ $n$ $en$ $1+\varepsilon$

Den nedre grænse for stabilitetsprisen

Her er et patologisk spil med samme adfærd, men til prisen for stabilitet. Der er spillere, som hver starter i toppen og forsøger at forbinde den til toppen . Lad os sige, at priserne på umærkede buer er 0. $n$ $s_{i}$ $t$

Den optimale strategi for alle spillere er at dele buen , hvilket resulterer i en social omkostning . Der er dog kun én Nash-ligevægtsstrategi for dette spil. I tilfælde af optimalitet betaler hver spiller, og spiller 1 kan reducere sin pris ved at skifte til buen . Hvis dette sker, bliver det rentabelt for spiller 2 at skifte til buen , og så videre. Til sidst vil agenterne nå en Nash-ligevægt ved at betale deres egen separate bue. En sådan fordeling har en social omkostning , hvor er det th harmoniske tal , som er lig med . Selvom denne værdi ikke er begrænset, er omkostningerne ved stabilitet eksponentielt bedre end omkostningerne ved anarki i dette spil. $1+\varepsilon$ $1+\varepsilon$ $\textstyle {\frac {1+\varepsilon }{n))$ ${\tfrac {1}{n))$ ${\tfrac {1}{n-1))$ $1+{\tfrac {1}{2}}+\cdots +{\tfrac {1}{n}}=H_{n}$ $H_n$ $n$ $\Theta (\log n)$

Øvre grænse for stabilitetsprisen

Per definition er netværksopbygningsspil overløbsspil , så de tillader en potentiel funktion . $\Phi =\sum _{e}\sum _{i=1}^{n_{e}}{\frac {c_{e}}{i}}$

Sætning. [Sætning 19.13 fra bog 1] Antag, at der er konstanter og sådan for enhver strategi $EN$ $B$ $S$

A\cdot SC(S)\leqslant \Phi (S)\leqslant B\cdot SC(S).

Så er prisen på stabilitet mindre $B/A$

Bevis. Funktionens globale minimum er en Nash-ligevægt, således at $NE$ $\Phi$

SC(NE)\leqslant 1/A\cdot \Phi (NE)\leqslant 1/A\cdot \Phi (OPT)\leqslant B/A\cdot SC(OPT).

Den sociale pris blev defineret som summen af priserne over buerne, således at

\Phi (S)=\sum _{e\in S}\sum _{i=1}^{n_{e}}{\frac {c_{e}}{i}}=\sum _ {e\in S}c_{e}H_{n_{e}}\leqslant \sum _{e\in S}c_{e}H_{n}=H_{n}\cdot SC(S).

Trivielt opnår vi og beregningerne ovenfor giver , så vi kan påberåbe os sætningen for den øvre grænse for stabilitetsomkostningerne. $A=1$ $B=H_{n}$

Se også

Fordeling af objekter (konkurrerende spil) er et spil uden prisen for stabilitet.

Noter

Litteratur

Vijay V. Vazirani, Noam Nisan, Tim Roughgarden, Eva Tardos. Algoritmisk spilteori . - Cambridge, Storbritannien: Cambridge University Press, 2007. - ISBN 0-521-87282-0 .
L. Agussurja, H. C. Lau. The Price of Stability in Selfish Scheduling Games // Web Intelligence and Agent Systems: An International Journal. - 2009. - T. 9 , no. 4 .
Jian Li. En øvre grænse for prisen på stabilitet for urettede Shapely netværksdesignspil // Information Processing Letters. - 2009. - T. 109 , no. 15 . - S. 876-878 . $O(\log n/\log \log n)$

Spilteori
Basale koncepter	Gensidig og fælles viden Spiller Hierarki af trosretninger Irrationel forstærkning Strategi ( dominans ) Omvendt induktion
Typer af spil	Samtidig , sekventiel og gentagne Ikke -samarbejdsvillig og samarbejdsvillig Med fuldstændig , ufuldstændig , perfekt og ufuldkommen information I normal og udvidet form Antagonistisk Differential Stokastisk Kønnenes kamp Hjortejagt
Løsningskoncepter	Risiko dominans Korreleret ligevægt Balancen af en skælvende hånd Nash ligevægt Subgame perfekt ligevægt Rationaliseringsevne Sekventiel balance stærk balance Egen balance Evolutionært stabil strategi Epsilon-ligevægt Pareto effektivitet Nucleus
Eksempler på spil	Fangens dilemma Barens opgave "El Farol" Bertrand model Cournot model Stackelberg model Orlyanka Tragedien med delte ressourcer høge og duer
Epistemisk spilteori Mekanisme design Fair opdeling