Prețul stabilității

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 9 martie 2022; verificările necesită 16 modificări .

Prețul de stabilitate ( English price of stability , PoS ) pentru joc este raportul dintre valoarea optimă a funcției obiectiv într-una dintre stările sale de echilibru și rezultatul optim. Prețul stabilității are sens pentru jocurile care au o putere mai mare sau condiții de joc care afectează într-un fel poziția jucătorilor și îi pot ajuta să converge către echilibrul Nash . Când se măsoară eficacitatea echilibrului Nash în orice joc, este logic să luăm în considerare prețul anarhiei ( Eng. Price of Anarchy , PoA).

Exemple

PoS poate fi exprimat astfel:

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

Aici , este valoarea celui mai bun echilibru Nash și este valoarea soluției optime. ${\textstyle N}$ ${\textstyle S}$

În jocul Dilema prizonierului de mai jos , jucătorii nu vor coopera întotdeauna între ei, chiar dacă este în interesul lor, deoarece există un singur echilibru ( , ), avem . ${\textstyle B}$ ${\textstyle R}$ $PoS=PoA={\tfrac {1}{2)}$

Dilema prizonierului

	${\textstyle L}$	${\textstyle R}$
${\textstyle T}$	(2,2)	(0,3)
${\textstyle B}$	(3,0)	(1,1)

Acest exemplu este o versiune a jocului bătălia sexelor . Are două puncte de echilibru, ( , ) și ( , ) cu valorile 3 și, respectiv, 15. Valoarea optimă este 15. Apoi , în timp ce . ${\textstyle T}$ ${\textstyle L}$ ${\textstyle B}$ ${\textstyle R}$ $PoS=1$ $PoA={\tfrac {1}{5}}$

Bătălia sexelor

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

Context și repere

Prețul stabilității a fost studiat pentru prima dată de A. Shultzan și N. Mozes, iar termenul în sine a apărut în lucrările lui E. Anselevich. Ei au arătat că echilibrul Nash există întotdeauna în strategiile pure, iar costul de stabilitate al acestui joc nu depășește numărul armonic a n-a în graficele direcționate. Pentru graficele nedirecționate, Anshelevich și colab. au prezentat o limită de stabilitate rigidă de 4/3 pentru cazul unei surse și a doi jucători. Yen Lee a demonstrat că pentru astfel de grafice cu destinații diferite pentru toți jucătorii, cu care toți jucătorii trebuie să aibă o conexiune, prețul unui flux de joc stabil pentru construirea unei rețele Shapley este unde este numărul de jucători. Pe de altă parte, costul anarhiei pentru joc este de aproximativ . $O(\log n/\log \log n),$ $n$ $n$

Jocuri de construire a rețelei

Condiții de joc

Jocurile de construire a rețelei au o rațiune naturală pentru prețul stabilității. În aceste jocuri, prețul anarhiei poate fi mult mai mic decât prețul stabilității.

Un exemplu din următorul joc:

$n$ jucători;
Scopul fiecărui jucător este să conecteze vârfuri și într-un grafic direcționat ; $i$ $si}$ $t_{i}$ $G=(V,E)$
Strategiile pentru jucător sunt toate căile de la până la din grafic ; $P_{i}$ $si}$ $t_{i}$ $G$
Fiecare arc are un preț ; $c_{i}$
„Distribuire corectă a prețului”: Dacă jucătorii aleg un arc , atunci prețul este distribuit în mod egal între ei; $n_{e}$ $e$ $d_{e}(n_{e})={\frac {c_{e}}{n_{e}}}$
Prețul pentru jucător este de ; $C_{i}(S)=\sum _{e\in P_{i}}{\frac {c_{e}}{n_{e}}}$
Costul social este egal cu suma prețurilor pentru jucători: . $SC(S)=\sum _{i}C_{i}(S)=\sum _{e\in S}n_{e}{\frac {c_{e}}{n_{e}} }=\sum _{e\in S}c_{e}$

Prețul anarhiei

Prețul anarhiei poate fi . Un exemplu al următorului joc de construire a rețelei. $\omega(n)$

Există 2 solduri diferite în acest joc. Dacă toată lumea împarte arcul , atunci costul social este . Mai mult, acest echilibru este optim. Cu toate acestea, împărțirea pe toate arcurile este, de asemenea, un echilibru Nash. Orice agent are un preț în strategia de echilibru, iar trecerea acestuia la un alt arc îi crește prețul la . $1+\varepsilon$ $1+\varepsilon$ $n$ $unu$ $1+\varepsilon$

Limita inferioară a prețului de stabilitate

Iată un joc patologic cu același comportament, dar la prețul stabilității. Există jucători, fiecare dintre care începe din partea de sus și încearcă să-l conecteze la vârf . Să presupunem că prețurile arcurilor neetichetate sunt 0. $n$ $si}$ $t$

Strategia optimă pentru toți jucătorii este împărțirea arcului , ceea ce are ca rezultat un cost social . Cu toate acestea, există o singură strategie de echilibru Nash pentru acest joc. În cazul optimității, fiecare jucător plătește și jucătorul 1 își poate reduce prețul trecând la arcul . Dacă se întâmplă acest lucru, atunci devine profitabil pentru jucătorul 2 să treacă la arc și așa mai departe. În cele din urmă, agenții vor ajunge la un echilibru Nash plătindu-și propriul arc separat. O astfel de distribuție are un cost social , unde este numărul armonic al treilea , care este egal cu . Deși această valoare nu este plafonată, costul stabilității este exponențial mai bun decât costul anarhiei în acest joc. $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)$

Limita superioară a prețului de stabilitate

Prin definiție, jocurile de construire a rețelei sunt jocuri overflow , deci permit o funcție potențială . $\Phi =\sum _{e}\sum _{i=1}^{n_{e}}{\frac {c_{e}}{i}}$

Teorema. [Teorema 19.13 din cartea 1] Să presupunem că există constante și astfel încât pentru orice strategie $A$ $B$ $S$

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

Atunci prețul stabilității este mai mic $B/A$

Dovada. Minimul global al funcției este un echilibru Nash, astfel încât $NE$ $\Phi$

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

Prețul social a fost definit ca suma prețurilor peste arce, astfel încât

\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).

Trivial obținem și calculele de mai sus dau , așa că putem invoca teorema pentru limita superioară a costului de stabilitate. $A=1$ $B=H_{n}$

Vezi și

Distribuția obiectelor (joc competitiv) este un joc fără prețul stabilității.

Note

Literatură

Vijay V. Vazirani, Noam Nisan, Tim Roughgarden, Eva Tardos. Teoria jocurilor algoritmice . - Cambridge, Marea Britanie: Cambridge University Press, 2007. - ISBN 0-521-87282-0 .
L. Agussurja, H. C. Lau. Prețul stabilității în jocurile de programare egoistă // Web Intelligence și sisteme de agenți: un jurnal internațional. - 2009. - T. 9 , nr. 4 .
Jian Li. O limită superioară a prețului stabilității pentru jocurile de design de rețea Shapely nedirecționate // Scrisori de procesare a informațiilor. - 2009. - T. 109 , nr. 15 . - S. 876-878 . $O(\log n/\log \log n)$

Teoria jocului
Noțiuni de bază	Cunoaștere comună și comună Jucător Ierarhia credințelor Amplificare irațională Strategie ( dominanță ) Inductie inversa
Tipuri de jocuri	Simultan , secvenţial şi repetitiv Non -cooperativ și cooperant Cu informații complete , incomplete , perfecte și imperfecte În formă normală și extinsă Antagonist Diferenţial Stochastic Bătălia sexelor Vânătoarea de căprioare
Concepte de soluție	Dominanța riscului Echilibrul corelat Echilibrul unei mâini tremurânde Echilibru Nash Echilibru perfect sub-joc Raționalizare Echilibru secvenţial echilibru puternic Echilibrul propriu Strategie stabilă evolutiv Epsilon-echilibru Eficiența Pareto Nucleu
Exemple de jocuri	Dilema prizonierului Sarcina barului „El Farol” modelul Bertrand Modelul Cournot Modelul Stackelberg Orlyanka Tragedia resurselor partajate șoimi și porumbei
Teoria jocurilor epistemice Proiectarea mecanismului Diviziune corectă