Az anarchia ára

Az anarchia ára ( angolul Price of Anarchy , PoA ) [1] egy olyan közgazdaságtani és játékelméleti fogalom , amely azt méri, hogy a rendszer hatékonysága mennyire csökken ügynökeinek önző viselkedése miatt .

Kötetlen beszélgetés

Az anarchia költsége egy általános fogalom, amely kiterjeszthető különböző rendszerekre és hatékonysági koncepciókra. Vegyünk például egy közlekedési rendszert egy olyan városban, ahol sok ügynök próbál eljutni valamelyik kiindulási ponttól egy végpontig. Jelenítse a hatékonyság ebben az esetben azt az átlagos időt, ameddig az ügynök eljut a rendeltetési helyre. Egy "központosított" megoldásban a központi hatóság megmondhatja minden ügynöknek, hogy az ügynöknek melyik útvonalat kell megtennie az átlagos utazási idő minimalizálása érdekében. A „decentralizált” változatban minden ügynök saját belátása szerint választja ki az útvonalat. Az anarchia ára e két esetben az átlagos utazási idők arányát tükrözi.

A rendszert általában játékként modellezik , és a hatékonyság a játék kimenetelének valamilyen függvénye (pl. maximális hálózati késleltetés, forgalmi torlódás, aukciókon nyújtott társadalmi haszon stb.). Különféle egyensúlyi fogalmak használhatók az ágensek önző viselkedésének modellezésére, ezek közül a legáltalánosabb a Nash-egyensúly . A Nash-egyensúly különböző változatai az anarchia költség fogalmának eltéréseihez vezetnek, mint például a tiszta anarchia költség (determinisztikus egyensúlyok esetén), vegyes anarchia költség (véletlenszerű egyensúly esetén) és Bayes-Nash anarchia költség (hiányos információkat tartalmazó játékok esetén). A Nash-egyensúlytól eltérő fogalmak olyan opciókhoz vezetnek, mint például a merítés ára [2] .

Az "anarchia ára" kifejezést először Elias Koutsoupias és Christos Papadimitriou [1] használta , de az egyensúlyi hatástalanság mérésének ötlete régebbi [3] . A koncepciót jelenlegi formájában a közelítési algoritmusban a "közelítési tényezővel" vagy az online algoritmusban a "versenyképességi szinttel" analógnak szánták . A kifejezés összhangban van az algoritmikus lencséket használó játékelemzés modern irányzatával ( Algorithmic Game Theory ).

Matematikai definíció

Tekintsünk egy játékot , amelyet játékosok halmaza határoz meg, az egyes játékosok stratégiái és egy segédfüggvény (amit eredményhalmaznak is neveznek). Az egyes eredmények hatékonyságának mértékét meghatározhatjuk, amelyet haszonfüggvénynek nevezünk . A természetes jelöltek közé tartozik a játékosok hasznosságának összege (cél segédprogramok), a minimális hasznosság (cél méltányosság vagy egalitarizmus) ..., vagy bármely olyan funkció, amely az elemzett játék szempontjából értelmes, és amelyet maximalizálni kell. $G=(N,S,u)$ $N$ $S_{i}$ $u_{i}:S\rightarrow \mathbb {R}$ ${\displaystyle 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),$

Egy részhalmazt az egyensúlyi stratégiák halmazaként definiálhatunk (például a Nash-egyensúlyok halmaza ). Az anarchia költségét ezután az optimális „centralizált” megoldás és a „legrosszabb egyensúly” arányaként határozzuk meg: $Equil\subseteq S$

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

Ha a maximalizálni kívánt "jó" helyett a hatékonyságmérő függvény az a "költségfüggvény" , amelyet minimalizálni szeretnénk (például a hálózati késések), akkor (a közelítő algoritmusokban elfogadott konvenciókat követve): $Költség:S\rightarrow \mathbb {R}$

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

Ehhez kapcsolódó fogalom a Stabilitás ára ( PoS ) , amely a "legjobb egyensúly" és az optimálisan "centralizált" megoldás közötti kapcsolatot méri:

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

vagy költségfüggvények esetén:

$PoS={\frac {\min _{s\in Equil}Költség(ek)}{\min _{s\in S}Költség(ek)))$

Ezt definícióból tudjuk. A játékelméleti korlátok miatti hatékonyságvesztés várhatóan valahol a PoS és a PoA között lesz. $1\leqslant PoS\leqslant PoA$

Mindkét értéket, a PoS-t és a PoA-t különböző típusú játékokra számítottuk ki. Néhány példa az alábbiakban látható.

Fogolydilemma

Tekintsük a Prisoner 's Dilemma nevű 2x2-es játékot , amelyet a következő költségmátrix adja meg:

	Együttműködik	elárul
Együttműködik	1 ; egy	7 ; 0
elárul	0 ; 7	5 ; 5

és legyen az árfüggvény. Most a minimális ár akkor lesz, ha mindkét játékos együttműködik, és a kapott ár a következő lesz . A Nash-egyensúly azonban csak akkor figyelhető meg, ha mindkettő elárulja, ebben az esetben az ár . Ekkor ennek a játéknak a PoA értéke egyenlő lesz . $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$

Mivel a játéknak egyedi Nash-egyensúlya van, a PoS értéke PoA, ami szintén 5.

Munka elosztása

Természetesebb példa az egyik munkaütemezési probléma . Vannak játékosok, és mindegyiküknek van tennivalója. A munka elvégzésére választhatnak egyet a gépek közül. Az anarchia költsége összehasonlítja azt a helyzetet, amikor a gépek kiválasztását központilag határozzák meg, és egy olyan helyzetet, amikor minden játékos úgy választ egy autót, hogy gyorsabban végezze el munkáját. $N$ $M$

Minden gépnek van sebessége Minden munkának súlya van A játékos kiválaszt egy gépet a feladat elvégzéséhez. Így minden játékos stratégiája a következőképpen alakul : Határozza meg a gép terhelését : $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}}}.

A játékos ára egyenlő , azaz megegyezik a játékos által választott gép terhelésével. Figyelembe vesszük az egalitárius árfüggvényt , amelyet itt feldolgozási időszaknak nevezünk . $én$ $c_{i}(a)=L_{a_{i}}(a),$ ${\mbox{MS}}(a)=\max _{j}L_{j}(a)$

Az egyensúly két fogalmát fogjuk megvizsgálni – a tiszta Nash-stratégiát és a vegyes Nash-stratégiát . Nyilvánvaló, hogy a vegyes PoA tiszta PoA, mivel bármely tiszta Nash-egyensúly egyben vegyes Nash-egyensúly is (az egyenlőtlenség szigorúnak bizonyulhat példáulha, ). Az első dolog, amit meg kell tennünk, hogy megmutatjuk a tiszta Nash-egyensúly létezését. $\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$

nyilatkozat . Minden álláselosztási játékhoz létezik legalább egy Nash-egyensúlyi tiszta stratégia.

Bizonyíték . Társadalmilag optimális stratégiát kell kialakítanunk . Ez egyszerűen egy olyan stratégiát jelenthet, amelynek feldolgozási ideje minimális. Ez azonban nem elég. Több ilyen stratégiakészlet is létezhet, amelyek számos különböző terheléseloszlást eredményeznek (mindegyiknek ugyanaz a maximális terhelése). Ezenkívül korlátozzuk magunkat arra a tényre, hogy van egy második legalacsonyabb terhelés. Ez ismét sok lehetséges terheléseloszláshoz vezet, és addig ismételjük a folyamatot, amíg meg nem kapjuk a legjobb (azaz a legkisebb) terhelést, ahol csak egy terheléseloszlás lehet (az egyetlen egy permutációig). Ezt nevezhetjük a rendezett letöltések lexikográfiailag legkisebb vektorának is. $a^{*}$ $M$

Azt állítjuk, hogy ez egy tiszta stratégiai Nash-egyensúly. Ellentmondásokkal fogjuk bizonyítani. Tételezzük fel, hogy néhány játékos javíthatja a teljesítményét, ha gépről gépre mozog . Ez azt jelenti, hogy az átállás után megnövekedett gépterhelés kisebb marad, mint az átállás előtti gépterhelés. Mivel az átállás következtében a gép terhelése csökkennie kell, és más gépet nem érint, ami azt jelenti, hogy az új konfiguráció garantálja az elosztás -. legnagyobb terhelésének csökkenését. Ez azonban sérti a lexikográfiai minimalitás feltételezését . Q.E.D. $én$ $j$ $k$ $k$ $j$ $j$ $j$ $a$

nyilatkozat . Bármely munkaelosztási játék esetében a tiszta stratégiai PoA nem haladja meg a . $M$

Bizonyíték . Könnyű felülről megkötni a kapott jószágot bármely Nash -egyensúlyi vegyes stratégiaként a képlettel $\sigma$

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

Az egyértelműség kedvéért vegye figyelembe a tiszta stratégiák bármely halmazát , akkor egyértelmű $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}}}}.

Mivel a fentiek a társadalmi optimumra is érvényesek, az arányok összehasonlítása igazolja az állítást. Q.E.D $w(\sigma )$ $w(a)$

Önző útválasztás

Braes paradoxona

Vegyünk egy olyan úthálózatot, amelyen meghatározott számú járművezetőnek kell eljutnia egy közös kezdőponttól egy közös végpontig. Tételezzük fel, hogy minden vezető önző módon választ egy útvonalat, és az utazási idő lineárisan függ az útvonalat választó járművezetők számától.

Ezeket a feltételeket útvonalválasztási problémaként formalizálhatjuk egy irányított összefüggő gráfban , amelyben egy áramlási egységet akarunk küldeni egy forráscsomópontból egy nyelőcsomópontba (képzeljük el, hogy az áramlás különböző meghajtók választott útvonalaiból áll). Legyen az áramlás olyan függvény, amely minden élhez egy nem negatív valós számot rendel, és vegyünk egy sor lineáris függvényt , amely az élen keresztüli áramlást az él késleltetésére képezi le. Határozzuk meg a flow társadalmi javát is úgy $G=(V,E)$ $s\in 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$ ${\displaystyle w(f)=\sum _{e}{f_{e}\cdot l_{e}(f_{e)))))$

Tekintsük az ábrán látható példát - ha pontozott út nem áll rendelkezésre, vegyes stratégiák esetén Nash-egyensúlyt kapunk, ha minden játékos azonos valószínűséggel választja a felső és az alsó útvonalat - ennek az egyensúlynak 1,5 társadalmi költsége van, és 1,5 egységnyi időbe telik, amíg minden járművezető és minden járművezető között átjut a -tól -ig . A hálózaton való áthaladás javításának reményében a jogalkotó dönthet úgy, hogy szaggatott utat nyit meg a kis késéssel közlekedők előtt. Ebben az esetben a Nash-egyensúly csak akkor következhet be, ha bármelyik sofőr használja az új utat, így a társadalmi költség 2-vel nő, és most 2 egységnyi időbe telik minden járművezetőnek eljutni ig . $s$ $t$ $s$ $t$

Ezért szokatlan eredményt kapunk - a gyorsabb út használatának törvényi tilalma bizonyos esetekben pozitív eredménnyel járhat.

Általános útválasztási probléma

A Braes-paradoxonban bemutatott útválasztási probléma ugyanazon a gráfon egyidejűleg sok különböző folyamra általánosítható.

Meghatározás (Általános adatfolyam) . Legyen , és ugyanúgy definiálva, mint fent, és tegyük fel, hogy az értékeket minden egyes csomópontpáron keresztül szeretnénk átadni . Az áramlást úgy definiáljuk, mint a valós nemnegatív számok eloszlását az egyes útvonalak között, amelyek -tól -ig haladnak , korlátozásokkal $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\x V)$ ${\displaystyle f_{\Gamma ,R))$ $p\mapsto \Re$ $p$ $s_{i}$ $t_{i}$ $\in \Gamma$

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

Egy adott gráfélen áthaladó áramlást a következőképpen határozzuk meg $G$

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

A rövidség kedvéért megírjuk, ha a szövegkörnyezetből egyértelmű. $f_{e}$ $\Gamma ,R$

Definíció (Nash-egyensúlyi áramlás) . Az áramlás akkor és csak akkor és csak akkor Nash - egyensúlyi áramlás ${\displaystyle f_{\Gamma ,R))$ $\forall (s_{i},t_{i})\in \Gamma$ $\forall p,q$ $s_{i}$ $t_{i}$

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

Ez a meghatározás szorosan összefügg azzal, amiről beszélünk, amikor egy vegyes stratégia fenntartja a Nash-egyensúlyt a normál formában lévő játékokban.

A (feltételes áramlási jó) definíciója . Legyen és két patak a halmazokhoz és . A továbbiakban a jelölés megkönnyítése érdekében elhagyjuk az indexet. Képzelje el a függvények által generált rögzített késleltetéseket egy grafikonon – a feltételes jószág a következőképpen van definiálva ${\displaystyle 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)))))

1. tény . Ha van Nash-egyensúlyi áramlás és bármilyen más áramlás , . $f$ $f^{*}$ $w(f)=w^{f}(f)\leqslant w^{f}(f^{*})$

Bizonyítás (ellentétből) . Tegyük fel, hogy . Definíció szerint, $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})

Mivel és ugyanazokhoz a halmazokhoz kapcsolódnak , ezt tudjuk $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.

Ezért kell lennie egy párnak és két olyan útnak , amelyre , , és $(s_{i},t_{i})$ $p,q$ $s_{i}$ $t_{i}$ ${\displaystyle f_{p}^{*}>f_{p))$ ${\displaystyle f_{q}^{*}<f_{q))$

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

Más szóval, egy áramlás csak kisebb haszonhoz juthat, mint ha két útvonalon eltérő árai vannak, és ha átirányít egy áramlást egy magas költségű útvonalról egy alacsonyabb költségű útvonalra. Nyilvánvaló, hogy ez a helyzet összeegyeztethetetlen azzal a feltételezéssel, hogy egy Nash-egyensúlyi áramlás. Q.E.D. $f^{*}$ $f$ $s_{i}$ $t_{i}$ $f^{*}$ $f$ $f$

Ne feledje, hogy az 1. tény nem jelent semmilyen meghatározott halmazstruktúrát . $L$

2. tény . Ha két valós szám és , adott . $x$ $y$ $x\cdot y\leqslant x^{2}+y^{2}/4$

Bizonyíték . Ez egy másik módja a helyes egyenlőtlenség kifejezésének . Q.E.D. $(xy/2)^{2}\geqslant 0$

Tétel . A tiszta stratégia PoA értéke bármely általánosított útválasztási problémára lineáris késleltetéssel egyenlő . ${\megjelenítési stílus (G, L)}$ $\leqslant 4/3$

Bizonyíték . Vegyük észre, hogy ez a tétel egyenértékű azzal, hogy minden Nash-egyensúlyi áramlás , , ahol bármely más áramlás. Definíció szerint $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} .

A 2. tényt használva azt kapjuk

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)),

mert a

(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}.

Megállapíthatjuk, hogy , és igazolni kellett az állítást az 1. tény segítségével, amelyet bizonyítani kellett. $w^{f}(f^{*})\leqslant w(f^{*})+w(f)/4$

Megjegyezzük, hogy a bizonyítás során széles körben alkalmaztuk azt a feltételezést, hogy a függvények lineárisak. Valójában általánosabb tények érvényesek. $L$

Tétel . Adott egy általánosított útválasztási probléma gráfon és polinomiális fokozatú késleltetési függvények nem negatív együtthatókkal, a PoA egy tiszta stratégia . $G$ $d$ $\leqslant d+1$

Vegye figyelembe, hogy a PoA . Tekintsük az ábrán látható példát, ahol egységnyi áramlást feltételezünk: A Nash-egyensúlyi áramlások társadalmi jószága 1. A legjobb jót azonban akkor érjük el , ha ebben az esetben $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}}\jobb)^{\sqrt {d +1))+{\frac {1}{\sqrt {d+1))))

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

Az érték a végtelenhez közeledve a nullához közelít. $d$

Lásd még

A megosztott erőforrások tragédiája
Tárgyak elhelyezése (versenyjáték) egy kis anarchia árú játék.
Az anarchia ára az aukciókon

Jegyzetek

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

Irodalom

Elias Koutsoupias, Christos Papadimitriou . A legrosszabb eset egyensúlya // Computer Science Review. - 2009. - május ( 3. köt. 2. szám ). Az eredetiből archiválva : 2016. március 13.
Vijay V. Vazirani, Noam Nisan, Tim Roughgarden, Eva Tardos. 17. fejezet Bevezetés az egyensúlyok hatástalanságába // Algoritmikus játékelmélet . - Cambridge, Egyesült Királyság: Cambridge University Press, 2007. - ISBN 0-521-87282-0 .
Goemans M., Mirrokni V., Vetta A. Sink equilibria and convergence // 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05). - IEEE, 2005. - (IEEE Conference Proceedings). — ISBN 0769524680 .
Dubey P. A Nash-egyensúlyok hatástalansága // Math. Oper. Res .. - 1986. - T. 11 , sz. 1 .
Tim Roughgarden. Önző útválasztás és az anarchia ára. - MIT Press , 2005. - ISBN 0-262-18243-2 .

Olvasás további olvasáshoz

Fabio Cunial, Price of anarchy Archiválva : 2008. szeptember 10. a Wayback Machine -nél

Játékelmélet
Alapfogalmak	Kölcsönös és közös tudás Játékos A hitek hierarchiája Irracionális erősítés Stratégia ( dominancia ) Fordított indukció
A játékok típusai	Egyidejű , szekvenciális és ismétlődő Nem együttműködő és együttműködő Teljes , hiányos , tökéletes és tökéletlen információkkal _ Normál és kiterjesztett formában _ Ellentétes Differenciális Sztochasztikus A nemek harca Szarvasvadászat
Megoldási koncepciók	Kockázati dominancia Korrelált egyensúly Remegő kéz egyensúlya Nash egyensúly A részjáték tökéletes egyensúlya Racionalizálhatóság Szekvenciális egyensúly erős egyensúly Saját mérleg Evolúciósan stabil stratégia Epszilon-egyensúly Pareto hatékonyság Sejtmag
Játékpéldák	A fogoly dilemmája Az "El Farol" bár feladata Bertrand modell Cournot modell Stackelberg modell Orlyanka A megosztott erőforrások tragédiája sólymok és galambok
Episztemikus játékelmélet Mechanizmus tervezés Tisztességes felosztás