Cena anarchie

Cena anarchie ( anglicky Price of Anarchy , PoA ) [1] je pojem v ekonomii a teorii her , který měří, jak moc se snižuje efektivita systému kvůli sobeckému chování jeho agentů.

Neformální diskuse

Cena anarchie je obecný koncept, který lze rozšířit na různé systémy a koncepty efektivity. Vezměme si například dopravní systém ve městě, kde se mnoho agentů snaží cestovat z nějakého počátečního bodu do nějakého konečného bodu. Efektivitou se v tomto případě rozumí průměrná doba, za kterou se agent dostane na místo určení. V „centralizovaném“ řešení může ústřední orgán každému agentovi sdělit, jakou cestou by se měl agent ubírat, aby se minimalizovala průměrná doba cestování. V „decentralizované“ verzi si každý agent volí trasu podle vlastního uvážení. Cena anarchie odráží poměr průměrných cestovních dob pro tyto dva případy.

Typicky je systém modelován jako hra a účinnost je určitou funkcí výsledku hry (např. maximální latence sítě, dopravní zácpa, sociální přínos v aukcích atd.). Různé koncepty rovnováhy mohou být použity k modelování sobeckého chování agentů a mezi nimi je nejobecnějším konceptem Nashova rovnováha . Různé variace Nashovy rovnováhy vedou k variacím konceptu nákladů anarchie, jako jsou náklady čisté anarchie (pro deterministické rovnováhy), náklady smíšené anarchie (pro randomizované rovnováhy) a náklady anarchie Bayes-Nash (pro hry s neúplnými informacemi). Jiné pojmy než Nashova rovnováha vedou k možnostem, jako je cena ponoření [2] .

Termín „cena anarchie“ poprvé použili Elias Koutsoupias a Christos Papadimitriou [1] , ale myšlenka měření rovnovážné neefektivity je starší [3] . Koncept ve své současné podobě měl být analogický k „faktoru aproximace“ v aproximačním algoritmu nebo „úrovni konkurenceschopnosti“ v online algoritmu . Termín je v souladu s moderním trendem analýzy her pomocí algoritmických čoček ( Algorithmic Game Theory ).

Matematická definice

Zvažte hru definovanou sadou hráčů , sadami strategií pro každého hráče a užitečnou funkcí (která se také nazývá sada výsledků). Můžeme definovat míru efektivity každého výsledku, kterou nazveme funkce přínosu . Přirozenými kandidáty jsou součet užitků hráčů (cílové užitky), minimální užitek (cílová spravedlivost nebo rovnostářství) ... nebo jakákoliv funkce, která má smysl pro konkrétní analyzovanou hru a která by měla být maximalizována. $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),$

Podmnožinu můžeme definovat jako množinu strategií v rovnováze (například množinu Nashových rovnováh ). Cena anarchie je pak definována jako poměr optimálního „centralizovaného“ řešení a „nejhorší rovnováhy“: $Equil\subseteq S$

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

Pokud namísto „dobra“, které chceme maximalizovat, je funkce měření účinnosti „funkcí nákladů“ , kterou chceme minimalizovat (jako je zpoždění sítě), použijeme (podle konvencí přijatých v aproximačních algoritmech): $Cena:S\rightarrow \mathbb {R}$

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

Souvisejícím konceptem je cena stability ( PoS ) , která měří vztah mezi „nejlepší rovnováhou“ a optimálně „centralizovaným“ řešením:

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

nebo v případě cenových funkcí:

$PoS={\frac {\min _{s\in Equil}Cena(y)}{\min _{s\in S}Cena(y)))$

Známe to z definice. Očekává se, že ztráta účinnosti kvůli omezením teorie her bude ležet někde mezi PoS a PoA. $1\leqslant PoS\leqslant PoA$

Obě hodnoty, PoS i PoA, byly vypočteny pro různé typy her. Některé příklady jsou uvedeny níže.

Vězeňovo dilema

Zvažte hru 2x2 s názvem Prisoner 's Dilemma, která je dána následující maticí nákladů:

	Spolupracovat	zradit
Spolupracovat	1 ; jeden	7 ; 0
zradit	0 ; 7	5 ; 5

a nechme funkci ceny být Nyní bude minimální cena, když oba hráči spolupracují a výsledná cena bude . Nashova rovnováha je však pozorována pouze tehdy, když oba zradí, v takovém případě je cena . Potom bude hodnota PoA této hry rovna . $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$

Protože hra má jedinečnou Nashovu rovnováhu, hodnota PoS je PoA, což je také 5.

Rozdělení práce

Přirozenějším příkladem je jeden z problémů s plánováním práce . Jsou tam hráči a každý z nich má nějakou práci, kterou musí udělat. Mohou si vybrat jeden ze strojů k provedení práce. Náklady na anarchii srovnávají situaci, kdy je výběr strojů určován centrálně, a situaci, kdy si každý hráč vybírá auto tak, aby svou práci dokončil rychleji. $N$ $M$

Každý stroj má rychlost Každá práce má váhu Hráč si vybere stroj, který vykoná jeho/její práci. Strategie každého hráče tedy budou Definujte zatížení stroje jako: $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}}}.

Cena pro hráče je rovna , to znamená, že se rovná zatížení stroje, které si hráč vybere. Budeme uvažovat funkci rovnostářské ceny , která se zde nazývá obdobím zpracování. $i$ $c_{i}(a)=L_{a_{i}}(a),$ ${\mbox{MS}}(a)=\max _{j}L_{j}(a)$

Budeme zvažovat dva koncepty rovnováhy – čistou Nashovu strategii a smíšenou Nashovu strategii . Je jasné, že smíšený PoA je čistý PoA, protože jakákoli čistá Nashova rovnováha je také smíšená Nashova rovnováha (nerovnice se může ukázat jako přísná, jsoukdyžnapříklad ). První věc, kterou musíme udělat, je ukázat existenci čisté Nashovy rovnováhy. $\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$

Prohlášení . Pro každou hru na distribuci práce existuje alespoň jedna čistá rovnovážná strategie Nash.

Důkaz . Potřebujeme získat společensky optimální soubor strategií . To může jednoduše znamenat soubor strategií, u kterých je doba zpracování minimální. To však nestačí. Může existovat několik takových sad strategií, které vedou k řadě různých rozložení zatížení (všechny mají stejné maximální zatížení). Navíc se omezíme na to, že je zde druhá nejnižší zátěž. Opět to vede k mnoha možným rozložením zatížení a postup opakujeme, dokud nedosáhneme tého nejlepšího (tj. nejmenšího) zatížení, kde může být pouze jedno rozložení zatížení (jediné až po permutaci). To lze také nazvat lexikograficky nejmenším vektorem tříděných stahování. $a^{*}$ $M$

Tvrdíme, že jde o čistou strategii Nashovy rovnováhy. Prokážeme protikladem. Předpokládejme, že některý hráč může zlepšit svůj výkon tím, že přechází ze stroje na stroj . To znamená, že zvýšené zatížení stroje po přechodu zůstává menší než zatížení stroje před přechodem. Vzhledem k tomu, že zatížení stroje by se mělo v důsledku přechodu snížit a žádný další stroj není ovlivněn, což znamená, že nová konfigurace zaručuje snížení --té největší zátěže v distribuci. To však porušuje předpoklad lexikografické minimalizace . Q.E.D. $i$ $j$ $k$ $k$ $j$ $j$ $j$ $A$

Prohlášení . U žádné hry pro distribuci práce nepřekračuje čistá strategie PoA . $M$

Důkaz . Je snadné shora svázat dobro získané jako jakákoli smíšená strategie Nashovy rovnováhy podle vzorce $\sigma$

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

Zvažte pro jasnost jakoukoli sadu čistých strategií , pak je to jasné $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}}}}.

Protože výše uvedené platí i pro sociální optimum, porovnání poměrů toto tvrzení potvrzuje . Q.E.D $w(\sigma )$ $w(a)$

Sobecké směrování

Braesův paradox

Zvažte síť silnic, po kterých musí pevný počet řidičů cestovat ze společného výchozího bodu do společného koncového bodu. Předpokládejme, že každý řidič volí trasu sobecky a že doba jízdy závisí lineárně na počtu řidičů, kteří si trasu volí.

Tyto podmínky můžeme formalizovat jako problém výběru trasy v orientovaném souvislém grafu , ve kterém chceme poslat jednotku toku ze zdrojového uzlu do uzlu sink (představme si, že tok se skládá ze zvolených tras různých řidičů). Konkrétně nechť je tok funkcí, která každé hraně přiřadí nezáporné reálné číslo, a uvažujme sadu lineárních funkcí , které mapují tok hranou ke zpoždění hrany. Definujme také společenské dobro toku jako $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)))))$

Vezměme si příklad na obrázku – pokud není k dispozici tečkovaná cesta, získá se Nashova rovnováha ve smíšených strategiích, když si každý hráč zvolí horní cestu a dolní cestu se stejnou pravděpodobností – tato rovnováha má sociální náklady 1,5 a trvá 1,5 jednotky času pro každého řidiče ke každému řidiči projet z do . V naději na zlepšení průjezdu sítí může zákonodárce rozhodnout o otevření tečkované silnice pro řidiče s malým zpožděním. V tomto případě může Nashova rovnováha nastat pouze v případě, že kterýkoli řidič použije novou silnici, takže společenské náklady se zvýší o 2 a každému řidiči nyní trvá cesta z do 2 jednotky času . $s$ $t$ $s$ $t$

Dochází proto k neobvyklému výsledku – legislativní zákaz používání rychlejší silnice v některých případech může mít pozitivní výsledek.

Zobecněný problém se směrováním

Problém směrování prezentovaný v Braesově paradoxu lze zobecnit na mnoho různých toků na stejném grafu současně.

Definice (Generalized Stream) . Nechť , a je definováno stejným způsobem jako výše, a předpokládejme, že chceme předat hodnoty přes každý jiný pár uzlů v . Tok je definován jako rozdělení reálných nezáporných čísel na každou cestu procházející z do , s omezeními $G=(V,E)$ $L$ $w$ ${\displaystyle R=\{r_{1},r_{2},\tečky ,r_{k},\;|\;r_{i}>0\))$ $\Gamma =\{(s_{1},t_{1}),(s_{2},t_{2}),\dots ,(s_{k},t_{k})\}\subseteq (V\krát 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 .

Tok procházející určitou hranou grafu je definován jako $G$

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

Pro stručnost napíšeme , pokud je to jasné z kontextu. $f_{e}$ $\Gamma ,R$

Definice (Nashův rovnovážný tok) . Tok je Nashův rovnovážný tok tehdy a jen tehdy a od do ${\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})}.

Tato definice úzce souvisí s tím, o čem mluvíme, když smíšená strategie udržuje Nashovu rovnováhu ve hrách v normální formě.

Definice (Conditional Flow Good) . Dovolit a být dva proudy spojené s množinami a . V následujícím vynecháme index, abychom si usnadnili zápis. Představte si pevná zpoždění generovaná funkcemi v grafu — podmíněný statek s ohledem na je definován jako ${\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)))))

Fakt 1 . Pokud existuje Nashův rovnovážný tok a jakýkoli jiný tok , . $F$ $f^{*}$ $w(f)=w^{f}(f)\leqslant w^{f}(f^{*})$

Důkaz (z konverzace) . Předpokládejme, že . Podle definice, $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})<\součet _{i=1}^{k}\součet _{p:s_{i}\šipka doprava t_{i}}f_{p}\cdot \součet _ {e\in p}l_{e}(f_{e})

Protože a souvisí se stejnými množinami , víme to $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.

Proto musí existovat dvojice a dvě cesty od do takové, že , , a $(s_{i},t_{i})$ $p,q$ $s_{i}$ $t_{i}$ ${\displaystyle f_{p}^{*}>f_{p))$ $f_{q}^{*}<f_{q}$

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

Jinými slovy, tok může získat pouze menší užitek, než když dvě cesty od do mají různé ceny a když přesměruje nějaký tok z cesty s vysokými náklady na cestu s nižšími náklady. Je jasné, že tato situace je neslučitelná s předpokladem, že jde o Nashův rovnovážný tok. Q.E.D. $f^{*}$ $F$ $s_{i}$ $t_{i}$ $f^{*}$ $F$ $F$

Všimněte si, že skutečnost 1 neznamená žádnou konkrétní strukturu množiny . $L$

Fakt 2 . Jsou-li dána dvě reálná čísla a , . $X$ $y$ $x\cdot y\leqslant x^{2}+y^{2}/4$

Důkaz . Toto je další způsob, jak vyjádřit správnou nerovnost . Q.E.D. $(xy/2)^{2}\geqslant 0$

Věta . PoA čisté strategie pro jakýkoli zobecněný problém se směrováním s lineárním zpožděním se rovná . $(G,L)$ $\leqslant 4/3$

Důkaz . Všimněte si, že tato věta je ekvivalentní tvrzení, že každý Nashův rovnovážný tok , , kde je jakýkoli jiný tok. Podle definice $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} .

Pomocí Fakta 2 dostaneme

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

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

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

protože

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

Můžeme dojít k závěru, že , a tvrzení dokázat pomocí Faktu 1. který bylo požadováno dokázat. $w^{f}(f^{*})\leqslant w(f^{*})+w(f)/4$

Všimněte si, že v důkazu jsme hojně využívali předpokladu, že funkce v jsou lineární. Ve skutečnosti platí obecnější fakta. $L$

Věta . Vzhledem k zobecněnému problému směrování na grafu a funkcím polynomiálního stupně zpoždění s nezápornými koeficienty je PoA čistá strategie . $G$ $d$ $\leqslant d+1$

Všimněte si, že PoA může růst jako . Uvažujme příklad znázorněný na obrázku, kde předpokládáme jednotkový tok: Nashovy rovnovážné toky mají sociální statek 1. Nejlepšího statku je však dosaženo , když v tomto případě $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}}}.

Hodnota se blíží nule, když se blíží nekonečnu. $d$

Viz také

Tragédie sdílených zdrojů
Umístění předmětů (konkurenční hra) je hra s malou cenou anarchie.
Cena anarchie v aukcích

Poznámky

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

Literatura

Elias Koutsoupias, Christos Papadimitriou . Equilibria v nejhorším případě // Recenze informatiky. - 2009. - Květen ( díl 3 , číslo 2 ). Archivováno z originálu 13. března 2016.
Vijay V. Vazirani, Noam Nisan, Tim Roughgarden, Eva Tardos. Kapitola 17 Úvod do neefektivity rovnováhy // Teorie algoritmických her . - Cambridge, UK: Cambridge University Press, 2007. - ISBN 0-521-87282-0 .
Goemans M., Mirrokni V., Vetta A. Sink equilibria and convergence // 46. výroční sympozium IEEE o základech počítačových věd (FOCS'05). - IEEE, 2005. - (Sborník konference IEEE). — ISBN 0769524680 .
Dubey P. Neefektivita Nashových rovnováh // Math. Operat. Res .. - 1986. - T. 11 , no. 1 .
Tim Roughgarden. Sobecké směrování a cena anarchie. - MIT Press , 2005. - ISBN 0-262-18243-2 .

Čtení pro další čtení

Fabio Cunial, Cena anarchie Archivováno 10. září 2008 na Wayback Machine

Herní teorie
Základní pojmy	Vzájemná a společná znalost Hráč Hierarchie vír Iracionální zesílení strategie ( dominance ) Reverzní indukce
Typy her	Simultánní , sekvenční a opakující se Nekooperativní a kooperativní S úplnými , neúplnými , dokonalými a nedokonalými informacemi V normální i rozšířené podobě Antagonistický Rozdíl Stochastické Bitva pohlaví Lov na jelena
Koncepce řešení	Riziková dominance Korelovaná rovnováha Rovnováha třesoucí se ruky Nashova rovnováha Dokonalá rovnováha podhry Racionalizovatelnost Sekvenční vyvážení silná rovnováha Vlastní bilance Evolučně stabilní strategie Epsilon-rovnováha Paretova účinnost Jádro
Příklady her	Vězňovo dilema Úkol baru "El Farol" Model Bertrand Cournotův model Stackelbergův model Orlyanka Tragédie sdílených zdrojů jestřábi a holubice
Epistemická teorie her Konstrukce mechanismu Spravedlivé rozdělení