Prețul anarhiei

Prețul anarhiei ( English Price of Anarchy , PoA ) [1] este un concept din economie și teoria jocurilor care măsoară cât de mult se degradează eficiența unui sistem din cauza comportamentului egoist al agenților săi.

Discuție informală

Costul anarhiei este un concept general care poate fi extins la diferite sisteme și concepte de eficiență. De exemplu, luați în considerare un sistem de transport într-un oraș în care mulți agenți încearcă să călătorească de la un punct de plecare la un punct final. Fie că eficiența în acest caz înseamnă timpul mediu pentru care agentul ajunge la destinație. Într-o soluție „centralizată”, o autoritate centrală poate spune fiecărui agent pe ce rută ar trebui să o ia agentul pentru a minimiza timpul mediu de călătorie. În varianta „descentralizată”, fiecare agent alege traseul la propria discreție. Prețul anarhiei reflectă raportul dintre timpul mediu de călătorie pentru aceste două cazuri.

De obicei, sistemul este modelat ca un joc , iar eficiența este o anumită funcție a rezultatului jocului (de exemplu, latența maximă a rețelei, congestionarea traficului, beneficiul social în licitații etc.). Diverse concepte de echilibru pot fi folosite pentru a modela comportamentul egoist al agenților, iar dintre acestea, cel mai general concept este echilibrul Nash . Diferite variații ale echilibrului Nash duc la variații ale conceptului de cost anarhie, cum ar fi costul anarhiei pur (pentru echilibrele deterministe), costul anarhiei mixte (pentru echilibrele randomizate) și costul anarhiei Bayes-Nash (pentru jocuri cu informații incomplete). Alte concepte decât echilibrul Nash conduc la opțiuni precum prețul imersiunii [2] .

Termenul „prețul anarhiei” a fost folosit pentru prima dată de Elias Koutsoupias și Christos Papadimitriou [1] , dar ideea de măsurare a ineficienței echilibrului este mai veche [3] . Conceptul în forma sa actuală a fost menit să fie analog cu „factorul de aproximare” dintr- un algoritm de aproximare sau „nivelul de competitivitate” dintr- un algoritm online . Termenul este în conformitate cu tendința modernă de analiză a jocurilor folosind lentile algoritmice ( Teoria jocurilor algoritmice ).

Definiție matematică

Luați în considerare un joc definit de un set de jucători , seturi de strategii pentru fiecare jucător și o funcție de utilitate (care mai este numită și un set de rezultate). Putem defini o măsură a eficacității fiecărui rezultat, pe care o vom numi funcție de beneficiu . Candidații naturali includ suma utilităților jucătorilor (utilitățile țintă), utilitatea minimă (echitatea țintei sau egalitarismul) ... sau orice funcție care are sens pentru jocul analizat și care ar trebui să fie maximizată. $G=(N,S,u)$ $N$ $Si}$ $u_{i}:S\rightarrow \mathbb {R}$ $S=S_{1}\times ...\times S_{n)$ $Welf:S\rightarrow \mathbb {R}$ $Welf(s)=\sum _{i\in N}u_{i}(s),$ $Welf(s)=\min _{i\in N}u_{i}(s),$

Putem defini o submulțime ca setul de strategii aflate în echilibru (de exemplu, mulțimea echilibrelor Nash ). Costul anarhiei este definit apoi ca raportul dintre soluția optimă „centralizată” și „cel mai prost echilibru”: $Equil\subseteq S$

$PoA={\frac {\max _{s\in S}Welf(s)}{\min _{s\in Equil}Welf(s)))$

Dacă, în locul „bunului” pe care vrem să-l maximizăm, funcția de măsurare a eficienței este „funcția de cost” pe care dorim să o minimizăm (cum ar fi întârzierile de rețea), folosim (urmând convențiile adoptate în algoritmii de aproximare): $Cost: S\rightarrow \mathbb {R}$

$PoA={\frac {\max _{s\in Equil}Cost(e)}{\min _{s\in S}Cost(e))}$

Un concept înrudit este prețul stabilității ( PoS ) , care măsoară relația dintre „cel mai bun echilibru” și soluția optim „centralizată”:

$PoS={\frac {\max _{s\in S}Welf(s)}{\max _{s\in Equil}Welf(s)))$

sau în cazul funcțiilor de cost:

$PoS={\frac {\min _{s\in Equil}Cost(e)}{\min _{s\in S}Cost(e))}$

Știm asta prin definiție. Pierderea de eficiență din cauza constrângerilor teoriei jocurilor este de așteptat să se situeze undeva între PoS și PoA. $1\leqslant PoS\leqslant PoA$

Ambele valori, PoS și PoA, au fost calculate pentru diferite tipuri de jocuri. Câteva exemple sunt date mai jos.

Dilema prizonierului

Luați în considerare un joc 2x2 numit Prisoner 's Dilemma, dat de următoarea matrice a costurilor:

	Coopera	trăda
Coopera	1 ; unu	7 ; 0
trăda	0 ; 7	5 ; 5

și lasă funcția de preț să fie Acum prețul minim va fi atunci când ambii jucători cooperează și prețul rezultat va fi . Totuși , echilibrul Nash este observat numai atunci când ambele trădează, caz în care prețul este . Atunci valoarea PoA a acestui joc va fi egală cu . $C(s_{1},s_{2})=u_{1}(s_{1},s_{2})+u_{2}(s_{1},s_{2}).$ $1+1=2$ $5+5=10$ $10/2=5$

Deoarece jocul are un echilibru Nash unic, valoarea PoS este PoA, care este, de asemenea, 5.

Repartizarea muncii

Un exemplu mai firesc este unul dintre problemele de programare a locurilor de muncă . Există jucători și fiecare dintre ei are ceva de făcut. Ei pot alege una dintre mașini pentru a face treaba. Costul anarhiei compară o situație în care alegerea mașinilor este determinată la nivel central și o situație în care fiecare jucător își alege o mașină în așa fel încât să își termine munca mai rapid. $N$ $M$

Fiecare mașină are o viteză Fiecare sarcină are o greutate Jucătorul alege o mașină pentru a-și îndeplini munca. Astfel, strategiile fiecărui jucător vor fi Definiți sarcina pe mașină ca: $s_{1},\ldots ,s_{M}>0.$ $w_{1},\ldots ,w_{N}>0.$ $A_{i}=\{1,2,\ldots, M\}.$ $j$

L_{j}(a)={\frac {\sum _{i:a_{i}=j}w_{i}}{s_{j}}}.

Prețul pentru jucător este egal , adică este egal cu sarcina mașinii pe care o alege jucătorul. Vom lua în considerare funcția de preț egalitar , care se numește aici perioada de procesare. $i$ $c_{i}(a)=L_{a_{i}}(a),$ ${\mbox{MS}}(a)=\max _{j}L_{j}(a)$

Vom lua în considerare două concepte de echilibru - strategia Nash pură și strategia Nash mixtă . Este clar că un PoA mixt este un PoA pur, deoarece orice echilibru Nash pur este și un echilibru Nash mixt (inegalitatea se poate dovedi strictă, de când,exemplu ). Primul lucru pe care trebuie să-l facem este să arătăm existența unui echilibru Nash pur. $\geqslant$ $N=2$ $w_{1}=w_{2}=1$ $M=2$ $s_{1}=s_{2}=1$ $\sigma _{1}=\sigma _{2}=(1/2,1/2)$ $\leqslant 4/3$

Declarație . Pentru orice joc de distribuție a locurilor de muncă, există cel puțin o strategie pură de echilibru Nash.

Dovada . Trebuie să obținem un set de strategii optim din punct de vedere social . Aceasta poate însemna pur și simplu un set de strategii pentru care timpul de procesare este minim. Cu toate acestea, acest lucru nu este suficient. Pot exista mai multe astfel de seturi de strategii care au ca rezultat un număr de distribuții diferite ale sarcinii (toate având aceeași sarcină maximă). În plus, ne vom limita la faptul că există a doua cea mai mică sarcină. Din nou, acest lucru duce la multe distribuții posibile de încărcare și repetăm procesul până când obținem cea mai bună (adică, cea mai mică) sarcină, unde poate exista o singură distribuție a sarcinii (singura până la o permutare). Acesta poate fi numit și cel mai mic vector lexicografic al descărcărilor sortate. $a^{*}$ $M$

Pretindem că aceasta este o strategie pură de echilibru Nash. Vom dovedi prin contradicție. Să presupunem că un jucător își poate îmbunătăți performanța trecând de la o mașină la alta . Aceasta înseamnă că sarcina crescută a mașinii după tranziție rămâne mai mică decât sarcina mașinii înainte de tranziție. Deoarece sarcina pe mașină ar trebui să scadă ca urmare a tranziției și nicio altă mașină nu este afectată, ceea ce înseamnă că noua configurație garantează o reducere a celei de -a-a-a încărcături ca mărime din distribuție. Acest lucru, totuși, încalcă ipoteza minimalității lexicografice . Q.E.D. $i$ $j$ $k$ $k$ $j$ $j$ $j$ $A$

Declarație . Pentru orice joc de distribuție de lucru, strategia pură PoA nu depășește . $M$

Dovada . Este ușor să legați de sus bunul obținut ca orice strategie mixtă de echilibru Nash , prin formula $\sigma$

w(\sigma)\leqslant {\frac {\sum _{i}{w_{i)}}{\max _{j}{s_{j)))).

Luați în considerare pentru claritate orice set de strategii pure , atunci este clar că $A$

w(a)\geqslant {\frac {\sum _{i}{w_{i)}}{\sum _{j}{s_{j))))\geqslant {\frac {\sum _ {i}{w_{i}}}{M\cdot \max _{j}{s_{j}}}}.

Deoarece cele de mai sus sunt valabile și pentru optimul social, compararea rapoartelor dovedește afirmația. Q.E.D $w(\sigma )$ $w(a)$

Dirijare egoistă

Paradoxul lui Braes

Luați în considerare o rețea de drumuri pe care un număr fix de șoferi trebuie să circule de la un punct de plecare comun la un punct final comun. Să presupunem că fiecare șofer alege o rută în mod egoist și că timpul de călătorie depinde liniar de numărul de șoferi care aleg ruta.

Putem formaliza aceste condiții ca o problemă de selecție a rutei într-un graf conex direcționat în care dorim să trimitem o unitate de flux de la un nod sursă la un nod receptor (să ne imaginăm că fluxul constă din rutele alese ale diferiților drivere). În special, să fie fluxul o funcție care atribuie un număr real nenegativ fiecărei muchii și să ia în considerare un set de funcții liniare care mapează fluxul prin margine la întârzierea muchiei. Să definim, de asemenea, binele social al fluxului ca $G=(V,E)$ $s\în V$ $t\in V$ $f:E\mapsto \Re$ $L=\{l_{e}(f_{e})=a\cdot f_{e}+b\;|\;e\in E,\;a\geqslant 0,\;b\geqslant 0 \}$ $f$ $w(f)=\sum _{e}{f_{e}\cdot l_{e}(f_{e))))$

Luați în considerare exemplul din figură - dacă un drum punctat nu este disponibil, se obține un echilibru Nash în strategii mixte atunci când fiecare jucător alege ruta superioară și ruta inferioară cu aceeași probabilitate - acest echilibru are un cost social de 1,5 și el durează 1,5 unități de timp pentru ca fiecare șofer să treacă de la la . În speranța îmbunătățirii trecerii prin rețea, legiuitorul poate decide deschiderea unui drum punctat șoferilor cu întârziere redusă. În acest caz, echilibrul Nash se poate întâmpla numai dacă orice șofer folosește noul drum, astfel încât costul social crește cu 2 și acum este nevoie de 2 unități de timp pentru fiecare șofer pentru a călători de la . $s$ $t$ $s$ $t$

Prin urmare, se obține un rezultat neobișnuit - o interdicție legislativă privind utilizarea unui drum mai rapid poate avea în unele cazuri un rezultat pozitiv.

Problemă generalizată de rutare

Problema de rutare prezentată în paradoxul lui Braes poate fi generalizată la mai multe fluxuri diferite pe același grafic în același timp.

Definiție (flux generalizat) . Fie , și definită în același mod ca mai sus și să presupunem că dorim să trecem valori prin fiecare pereche diferită de noduri în . Fluxul este definit ca distribuția numerelor reale nenegative către fiecare cale care trece de la la , cu restricții $G=(V,E)$ $L$ $w$ ${\displaystyle R=\{r_{1},r_{2},\dots ,r_{k},\;|\;r_{i}>0\))$ $\Gamma =\{(s_{1},t_{1}),(s_{2},t_{2}),\dots,(s_{k},t_{k})\}\subseteq (V\ori V)$ $f_{\Gamma,R)$ $p\mapsto \Re$ $p$ $si}$ $t_{i}$ $\in \Gamma$

\sum _{p:\,s_{i}\rightarrow t_{i}}{f_{p}}=r_{i}\;\;\forall (s_{i},t_{i}) \in \gamma .

Fluxul care trece printr-o anumită margine a graficului este definit ca $G$

f_{e,\Gamma,R}=\sum _{p:\,e\in p}{f_{p)).

Pentru concizie, vom scrie dacă este clar din context. $f_{e}$ $\Gamma ,R$

Definiție (fluxul de echilibru Nash) . Un flux este un flux de echilibru Nash dacă și numai dacă și de la până la $f_{\Gamma,R)$ $\forall (s_{i},t_{i})\in \Gamma$ $\forall p,q$ $si}$ $t_{i}$

f_{p}>0\Rightarrow \sum _{e\in p}{l_{e}(f_{e})}\leqslant \sum _{e\in q}{l_{e}(f_ {e})}.

Această definiție este strâns legată de ceea ce vorbim atunci când o strategie mixtă menține un echilibru Nash în jocuri în formă normală.

Definiția (bun de flux condiționat) . Fie și să fie două fluxuri în asociate cu seturile și . În cele ce urmează, vom omite indexul pentru a ușura notarea. Imaginați-vă întârzierile fixe generate de funcțiile dintr-un grafic - bunul condiționat în raport cu este definit ca $f_{\Gamma,R)$ $f_{\Gamma ,R}^{*}$ $G$ $\Gamma$ $R$ $f$ $f^{*}$ $f$

{\displaystyle w^{f}(f^{*})=\sum _{e\in E}{f_{e}^{*}\cdot l_{e}(f_{e)))))

Faptul 1 . Dacă există un flux de echilibru Nash și orice alt flux , . $f$ $f^{*}$ $w(f)=w^{f}(f)\leqslant w^{f}(f^{*})$

Dovada (din converse) . Să presupunem că . Prin definitie, $w^{f}(f^{*})<w^{f}(f)$

\sum _{i=1}^{k}\sum _{p:s_{i}\rightarrow t_{i}}f_{p}^{*}\cdot \sum _{e\in p }l_{e}(f_{e})<\sum _{i=1}^{k}\sum _{p:s_{i}\rightarrow t_{i}}f_{p}\cdot \sum _ {e\in p}l_{e}(f_{e})

Deoarece și sunt legate de aceleași seturi , știm că $f$ $f^{*}$ $\Gamma ,R$

\sum _{p:s_{i}\rightarrow t_{i}}f_{p}=\sum _{p:s_{i}\rightarrow t_{i}}f_{p}^{*} =r_{i}\;\;\forall i.

Prin urmare, trebuie să existe o pereche și două căi de la la astfel încât , , și $(s_{i},t_{i})$ $p,q$ $si}$ $t_{i}$ $f_{p}^{*}>f_{p)$ $f_{q}^{*}<f_{q}$

\sum _{e\in p}l_{e}(f_{e})<\sum _{e\in q}l_{e}(f_{e}).

Cu alte cuvinte, un flux poate obține doar un beneficiu mai mic decât dacă două căi de la au prețuri diferite și dacă redirecționează un flux de la o cale cu costuri mari către o cale cu costuri mai mici. Este clar că această situație este incompatibilă cu ipoteza că este un flux de echilibru Nash. Q.E.D. $f^{*}$ $f$ $si}$ $t_{i}$ $f^{*}$ $f$ $f$

Rețineți că Faptul 1 nu implică nicio structură de set anume . $L$

Faptul 2 . Dacă sunt date două numere reale și , . $X$ $y$ $x\cdot y\leqslant x^{2}+y^{2}/4$

Dovada . Acesta este un alt mod de a exprima inegalitatea corectă . Q.E.D. $(xy/2)^{2}\geqslant 0$

Teorema . PoA a strategiei pure pentru orice problemă generalizată de rutare cu întârzieri liniare este egală cu . $(G,L)$ $\leqslant 4/3$

Dovada . Rețineți că această teoremă este echivalentă cu a spune că fiecare flux de echilibru Nash , , unde este orice alt flux. Prin definitie $f$ $w(f)\leqslant (4/3)\cdot \min _{f^{*}}\{w(f^{*})\}$ $f^{*}$

w^{f}(f^{*})=\sum _{e\in E}f_{e}^{*}(a_{e}\cdot f_{e}+b_{e})

=\sum _{e}(a_{e}f_{e}f_{e}^{*})+\sum _{e\in E}f_{e}^{*}b_{e} .

Folosind Faptul 2 obținem

w^{f}(f^{*})\leqslant \sum _{e\in E}\left(a_{e}\cdot \left((f_{e}^{*})^{ 2}+(f_{e})^{2}/4\right)\right)+\sum _{e\in E}f_{e}^{*}\cdot b_{e}

=\left(\sum _{e\in E}a_{e}(f_{e}^{*})^{2}+f_{e}^{*}b_{e}\right) +\sum _{e\in E}a_{e}(f_{e})^{2}/4

\leqslant w(f^{*})+{\frac {w(f)}{4)),

pentru că

(1/4)\cdot w(f)=(1/4)\cdot \sum _{e\in E}f_{e}(a_{e}f_{e}+b_{e})

=(1/4)\cdot \sum _{e\in E}(f_{e})^{2}+\underbrace {(1/4)\cdot \sum _{e\in E} f_{e}b_{e}} _{\geqslant 0}.

Putem concluziona că , și dovedim afirmația cu ajutorul Faptului 1. care se cerea a fi demonstrat. $w^{f}(f^{*})\leqslant w(f^{*})+w(f)/4$

Rețineți că în demonstrație am folosit pe scară largă ipoteza că funcțiile din sunt liniare. De fapt, fapte mai generale sunt valabile. $L$

Teorema . Având în vedere o problemă de rutare generalizată pe un grafic și funcții de întârziere de grad polinomial cu coeficienți nenegativi, PoA este o strategie pură . $G$ $d$ $\leqslant d+1$

Rețineți că PoA poate crește ca . Luați în considerare exemplul prezentat în figură, în care presupunem un flux unitar: fluxurile de echilibru Nash au un bun social de 1. Cu toate acestea, cel mai bun bun este obținut atunci când , în acest caz, $d$ $x=1-1/{\sqrt {d+1}}$

{\displaystyle w=\left(1-{\frac {1}{\sqrt {d+1}}}\right)^{d}\cdot \left(1-{\frac {1}{\sqrt { d+1))}\right)+1\cdot {\frac {1}{\sqrt {d+1))))

{\displaystyle =\left(\left(1-{\frac {1}{\sqrt {d+1}}}\right)^{\sqrt {d+1}}\right)^{\sqrt {d +1))+{\frac {1}{\sqrt {d+1))))

\leqslant e^{-{\sqrt {d+1}}}+{\frac {1}{\sqrt {d+1}}}.

Valoarea se apropie de zero pe măsură ce se apropie de infinit. $d$

Vezi și

Tragedia resurselor partajate
Plasarea obiectelor (joc competitiv) este un joc cu un mic preț de anarhie.
Prețul anarhiei în licitații

Note

↑ 1 2 Koutsoupias, Papadimitriou, 2009 , p. 65–69.
↑ Goemans, Mirrokni, Vetta, 2005 , p. 142-154.
↑ Dubey, 1986 , p. 1-8.

Literatură

Elias Koutsoupias, Christos Papadimitriou . Echilibrul în cel mai rău caz // Computer Science Review. - 2009. - Mai ( vol. 3 , numărul 2 ). Arhivat din original pe 13 martie 2016.
Vijay V. Vazirani, Noam Nisan, Tim Roughgarden, Eva Tardos. Capitolul 17 Introducere în ineficiența echilibrului // Teoria jocurilor algoritmice . - Cambridge, Marea Britanie: Cambridge University Press, 2007. - ISBN 0-521-87282-0 .
Goemans M., Mirrokni V., Vetta A. Sink equilibria and convergence // Al 46-lea simpozion anual IEEE privind fundamentele informaticii (FOCS'05). - IEEE, 2005. - (IEEE Conference Proceedings). — ISBN 0769524680 .
Dubey P. Ineficiența echilibrelor Nash // Math. Operat. Res .. - 1986. - T. 11 , nr. 1 .
Tim Roughgarden. Dirijarea egoistă și prețul anarhiei. - MIT Press , 2005. - ISBN 0-262-18243-2 .

Lectură pentru lecturi suplimentare

Fabio Cunial, Prețul anarhiei Arhivat 10 septembrie 2008 la Wayback Machine

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ă