Anarkian hinta

Anarkian hinta ( englanniksi Price of Anarchy , PoA ) [1] on taloustieteen ja peliteorian käsite , joka mittaa kuinka paljon järjestelmän tehokkuus heikkenee sen agenttien itsekkäästä käytöksestä johtuen .

Epävirallinen keskustelu

Anarkian hinta on yleinen käsite, joka voidaan laajentaa erilaisiin järjestelmiin ja tehokkuuskonsepteihin. Harkitse esimerkiksi liikennejärjestelmää kaupungissa, jossa monet agentit yrittävät matkustaa jostain aloituspisteestä johonkin päätepisteeseen. Olkoon tehokkuus tässä tapauksessa keskimääräistä aikaa, jonka agentti pääsee määränpäähän. "Keskitetyssä" ratkaisussa keskusviranomainen voi kertoa kullekin edustajalle, mikä reitti edustajan tulee kulkea keskimääräisen matka-ajan minimoimiseksi. "Hajautetussa" versiossa jokainen agentti valitsee reitin oman harkintansa mukaan. Anarkian hinta heijastaa näiden kahden tapauksen keskimääräisten matka-aikojen suhdetta.

Tyypillisesti järjestelmä mallinnetaan peliksi ja tehokkuus on jokin pelin tuloksen funktio (esim. verkon maksimiviive, liikenneruuhkat, huutokaupan sosiaaliset edut jne.). Agenttien itsekkään käyttäytymisen mallintamiseen voidaan käyttää erilaisia tasapainokäsitteitä, joista yleisin on Nash-tasapaino . Nashin tasapainon erilaiset muunnelmat johtavat anarkiakustannusten käsitteen vaihteluihin, kuten puhdas anarkiakustannus (deterministisille tasapainoille), sekalainen anarkiakustannus (satunnaistetuille tasapainoille) ja Bayes-Nash-anarkiakustannus (peleille, joissa on puutteellisia tietoja). Muut käsitteet kuin Nash-tasapaino johtavat vaihtoehtoihin, kuten upotushintaan [2] .

Termiä "anarkian hinta" käyttivät ensin Elias Koutsoupias ja Christos Papadimitriou [1] , mutta ajatus tasapainon tehottomuuden mittaamisesta on vanhempi [3] . Käsite nykyisessä muodossaan oli tarkoitettu vastaamaan "likiarvotekijää" approksimaatioalgoritmissa tai "kilpailukykytasoa" online-algoritmissa . Termi on linjassa nykyaikaisen pelianalyysin suuntauksen kanssa algoritmisilla linsseillä ( Algorithmic Game Theory ).

Matemaattinen määritelmä

Harkitse peliä , jonka määrittelee pelaajajoukko , kunkin pelaajan strategiat ja hyödyllisyysfunktio (jota kutsutaan myös tulosjoukoksi). Voimme määritellä kunkin tuloksen tehokkuuden mittarin, jota kutsumme hyötyfunktioksi . Luonnollisia ehdokkaita ovat pelaajien hyötyjen summa (kohdeapuohjelmat), minimihyöty (tavoite oikeudenmukaisuus tai tasa-arvoisuus) ... tai mikä tahansa analysoitavalle pelille järkevä toiminto, joka tulisi maksimoida. $G=(N,S,u)$ $N$ $Si}$ $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),$

Voimme määritellä osajoukon tasapainossa olevien strategioiden joukoksi (esimerkiksi Nash-tasapainojen joukko ). Anarkian hinta määritellään sitten optimaalisen "keskitetyn" ratkaisun ja "pahimman tasapainon" suhteeksi: $Equil\subseteq S$

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

Jos sen "hyvän" sijasta, jonka haluamme maksimoida, tehokkuusmittausfunktio on "kustannusfunktio" , jonka haluamme minimoida (kuten verkkoviiveet), käytämme (noudattamalla approksimaatioalgoritmeissa käytettyjä käytäntöjä): $Hinta:S\rightarrow \mathbb {R}$

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

Tähän liittyvä konsepti on vakauden hinta ( PoS ) , joka mittaa "parhaan tasapainon" ja optimaalisesti "keskitetyn" ratkaisun välistä suhdetta:

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

tai hintafunktioiden tapauksessa:

$PoS={\frac {\min _{s\in Equil}kustannus(tta)}{\min _{s\in S}kustannus(tta)))$

Tiedämme sen määritelmän mukaan. Peliteorian rajoituksista johtuvan tehokkuuden menetyksen odotetaan olevan jossain PoS:n ja PoA:n välissä. $1\leqslant PoS\leqslant PoA$

Molemmat arvot, PoS ja PoA, laskettiin eri tyyppisille peleille. Alla on joitain esimerkkejä.

Vangin dilemma

Harkitse 2x2-peliä nimeltä Prisoner 's Dilemma, joka esitetään seuraavan kustannusmatriisin avulla:

	Tehdä yhteistyötä	pettää
Tehdä yhteistyötä	1 ; yksi	7 ; 0
pettää	0 ; 7	5 ; 5

ja anna hintafunktion olla Nyt minimihinta on, kun molemmat pelaajat tekevät yhteistyötä ja tuloksena oleva hinta on . Nash-tasapaino havaitaan kuitenkin vain, kun molemmat pettävät, jolloin hinta on . Silloin tämän pelin PoA:n arvo on yhtä suuri kuin . $C(s_{1},s_{2})=u_{1}(s_{1},s_{2})+u_{2}(s_{1},s_{2}).$ ${\näyttötyyli 1+1=2}$ $5+5=10$ $10/2=5$

Koska pelissä on ainutlaatuinen Nash-tasapaino, PoS-arvo on PoA, joka on myös 5.

Työn jakautuminen

Luonnollisempi esimerkki on yksi työaikatauluongelmista . Pelaajia on ja jokaisella heistä on tehtävää. He voivat valita yhden koneista työn suorittamiseen. Anarkian hinta vertailee tilannetta, jossa koneiden valinta määräytyy keskitetysti, ja tilannetta, jossa jokainen pelaaja valitsee auton siten, että työnsä valmistuu nopeammin. $N$ $M$

Jokaisella koneella on nopeus Jokaisella työllä on painonsa Pelaaja valitsee koneen suorittaakseen työnsä. Siten jokaisen pelaajan strategiat ovat Määrittele koneen kuormitus seuraavasti: $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}}}.

Pelaajan hinta on sama , eli se on yhtä suuri kuin pelaajan valitseman koneen kuormitus. Tarkastellaan tasa -arvoista hintafunktiota , jota kutsutaan tässä käsittelyjaksoksi. $i$ $c_{i}(a)=L_{a_{i}}(a),$ ${\mbox{MS}}(a)=\max _{j}L_{j}(a)$

Tarkastelemme kahta tasapainon käsitettä - puhdasta Nash-strategiaa ja sekoitettua Nash-strategiaa . On selvää, että sekoitettu PoA on puhdas PoA, koska mikä tahansa puhdas Nash-tasapaino on myös sekoitettu Nash-tasapaino (epäyhtälö voi osoittautua tiukaksi kun,esimerkiksi ). Ensimmäinen asia, joka meidän on tehtävä, on osoittaa puhtaan Nash-tasapainon olemassaolo. $\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$

lausunto . Jokaiselle työnjakopelille on olemassa vähintään yksi puhdas Nash-tasapainostrategia.

Todiste . Meidän on saatava sosiaalisesti optimaalinen joukko strategioita . Tämä voi yksinkertaisesti tarkoittaa joukkoa strategioita, joiden käsittelyaika on minimaalinen. Tämä ei kuitenkaan riitä. Tällaisia strategioita voi olla useita, mikä johtaa useisiin erilaisiin kuormitusjakaumiin (kaikilla on sama maksimikuorma). Lisäksi rajoitamme siihen, että kuorma on toiseksi pienin. Tämä taas johtaa moniin mahdollisiin kuormitusjakaumiin, ja toistamme prosessia, kunnes saamme th parhaan (eli pienimmän) kuorman, jossa voi olla vain yksi kuormajakauma (ainoa permutaatioon asti). Tätä voidaan kutsua myös leksikografisesti pienimmäksi lajiteltujen latausten vektoriksi. $a^{*}$ $M$

Väitämme, että tämä on puhdas strategia Nash-tasapaino. Todistamme ristiriidalla. Oletetaan, että joku pelaaja voi parantaa suorituskykyään siirtymällä koneelta toiselle . Tämä tarkoittaa, että lisääntynyt konekuormitus siirtymän jälkeen jää pienemmäksi kuin koneen kuormitus ennen siirtymää. Koska koneen kuormituksen pitäisi laskea siirtymän seurauksena eikä se vaikuta muihin koneisiin, mikä tarkoittaa, että uusi konfiguraatio takaa jakelun -:nneksi suurimman kuormituksen pienenemisen. Tämä kuitenkin rikkoo leksikografista minimaalisuusoletusta . Q.E.D. $i$ $j$ $k$ $k$ $j$ $j$ $j$ $a$

lausunto . Minkään työnjakopelin puhdas strategia PoA ei ylitä . $M$

Todiste . Ylhäältä on helppo sitoa mikä tahansa Nashin tasapainosekoitusstrategiana saatu hyvä kaavalla $\sigma$

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

Harkitse selvyyden vuoksi mitä tahansa puhdasta strategiaa , niin se on selvää $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}}}}.

Koska edellä oleva pätee myös sosiaaliseen optimiin, suhdelukujen vertailu vahvistaa väitteen . Q.E.D $w(\sigma )$ $w(a)$

Itsekäs reititys

Braesin paradoksi

Harkitse tieverkostoa, jolla tietyn määrän kuljettajia on kuljettava yhteisestä lähtöpisteestä yhteiseen päätepisteeseen. Oletetaan, että jokainen kuljettaja valitsee reitin itsekkäästi ja että matka-aika riippuu lineaarisesti reitin valitsevien kuljettajien lukumäärästä.

Voimme formalisoida nämä ehdot reitinvalintaongelmaksi suunnatussa yhdistetyssä graafissa , jossa halutaan lähettää virtausyksikkö lähdesolmusta nielusolmuun (kuvitellaan, että virtaus koostuu eri kuljettajien valituista reiteistä). Olkoon virtaus erityisesti funktio, joka määrittää ei-negatiivisen reaaliluvun kullekin reunalle, ja harkitse joukkoa lineaarisia funktioita , jotka kuvaavat reunan läpi kulkevan virtauksen reunan viiveeseen. Määritellään myös virtauksen sosiaalinen hyöty $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)))))$

Tarkastellaan kuvan esimerkkiä - jos pistekatkoista tietä ei ole saatavilla, Nash-tasapaino sekastrategioissa saadaan, kun jokainen pelaaja valitsee ylemmän reitin ja alemman reitin samalla todennäköisyydellä - tämän tasapainon sosiaalinen kustannus on 1,5, ja se Kuljettajalta kuluu 1,5 yksikköä aikaa kullekin kuljettajalle siirtymiseen paikasta . Verkon läpikulun parantamisen toivossa lainsäätäjä voi päättää avata pienillä viiveillä kuljettajille katkotien. Tässä tapauksessa Nash-tasapaino voi tapahtua vain, jos kuka tahansa kuljettaja käyttää uutta tietä, joten sosiaaliset kustannukset kasvavat 2:lla ja kullekin kuljettajalle kuluu nyt 2 yksikköä ajaa paikasta kohteeseen . $s$ $t$ $s$ $t$

Siksi saadaan epätavallinen tulos - lainsäädännöllinen kielto käyttää nopeampaa tietä voi joissain tapauksissa olla positiivinen.

Yleinen reititysongelma

Braesin paradoksissa esitetty reititysongelma voidaan yleistää useisiin eri virtauksiin samassa graafissa samanaikaisesti.

Määritelmä (yleistetty stream) . Olkoon , ja määritellään samalla tavalla kuin edellä, ja oletetaan, että haluamme välittää arvot jokaisen eri solmuparin kautta . Vuo määritellään todellisten ei-negatiivisten lukujen jakamiseksi kullekin polulle , joka kulkee kohteesta , rajoituksin $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\kertaa V)$ ${\displaystyle f_{\Gamma ,R))$ $p\mapsto \Re$ $s$ $si}$ $t_{i}$ $\in \Gamma$

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

Tietyn graafin reunan läpi kulkeva virtaus määritellään seuraavasti $G$

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

Kirjoitamme lyhyyden vuoksi, jos asiayhteys on selvää. $f_{e}$ $\Gamma ,R$

Määritelmä (Nash-tasapainovirtaus) . Virtaus on Nash-tasapainovirtaus silloin ja vain silloin ja välillä kohteeseen ${\displaystyle 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})}.

Tämä määritelmä liittyy läheisesti siihen, mistä puhumme, kun sekastrategia ylläpitää Nash-tasapainoa normaalimuodossa olevissa peleissä.

Määritelmä (ehdollinen virtaushyvä) . Antaa ja olla kaksi virtaa liittyvät joukkoja ja . Jäljempänä jätämme indeksin pois merkinnän helpottamiseksi. Kuvittele graafin funktioiden generoimat kiinteät viiveet — ehdollinen hyvä suhteessa on määritelty ${\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)))))

Fakta 1 . Jos on Nash-tasapainovirtaus ja mikä tahansa muu virtaus , . $f$ $f^{*}$ $w(f)=w^{f}(f)\leqslant w^{f}(f^{*})$

Todistus (käänteisestä) . Oletetaan, että . Määritelmän mukaan $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})

Koska ja liittyvät samoihin joukkoihin , tiedämme sen $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.

Siksi on oltava pari ja kaksi polkua sellaiseen , että , , ja ${\näyttötyyli (s_{i},t_{i})}$ $p,q$ $si}$ $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}).

Toisin sanoen virta voi saada vain pienemmän hyödyn kuin jos kahdella reitillä on eri hinnat, ja jos se ohjaa osan virtauksesta kalliilta reitiltä halvemmalle polulle. On selvää, että tämä tilanne on ristiriidassa sen oletuksen kanssa, että kyseessä on Nashin tasapainovirta. Q.E.D. $f^{*}$ $f$ $si}$ $t_{i}$ $f^{*}$ $f$ $f$

Huomaa, että Fakta 1 ei tarkoita mitään tiettyä joukkorakennetta . $L$

Fakta 2 . Jos kaksi reaalilukua ja , annetaan . $x$ $y$ $x\cdot y\leqslant x^{2}+y^{2}/4$

Todiste . Tämä on toinen tapa ilmaista oikea eriarvoisuus . Q.E.D. $(xy/2)^{2}\geqslant 0$

Lause . Puhtaan strategian PoA kaikille yleisille reititysongelmille lineaarisilla viiveillä on yhtä suuri kuin . ${\näyttötyyli (G,L)}$ $\leqslant 4/3$

Todiste . Huomaa, että tämä lause vastaa sanomista, että jokainen Nash-tasapainovirtaus , , jossa on mikä tahansa muu virtaus. Määritelmän mukaan $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} .

Käyttämällä Fact 2 saamme

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) +\summa _{e\in E}a_{e}(f_{e})^{2}/4

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

koska

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

Voimme päätellä, että , ja todistaa väite tosiasian 1. avulla, joka oli todistettava. $w^{f}(f^{*})\leqslant w(f^{*})+w(f)/4$

Huomaa, että todistuksessa käytimme laajasti olettamusta, että funktiot ovat lineaarisia. Itse asiassa yleisemmät tosiasiat pitävät paikkansa. $L$

Lause . Kun otetaan huomioon yleinen reititysongelma graafissa ja polynomiasteviivefunktiot ei-negatiivisilla kertoimilla, PoA on puhdas strategia . $G$ $d$ $\leqslant d+1$

Huomaa, että PoA voi kasvaa . Tarkastellaan kuvassa esitettyä esimerkkiä, jossa oletetaan yksikkövirtaa: Nash-tasapainovirtojen sosiaalinen hyöty on 1. Paras hyöty kuitenkin saavutetaan , kun tässä tapauksessa $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}}\oikea)^{\sqrt {d +1))+{\frac {1}{\sqrt {d+1))))

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

Arvo lähestyy nollaa, kun se lähestyy ääretöntä. $d$

Katso myös

Yhteisten resurssien tragedia
Esineiden sijoittaminen (kilpailupeli) on peli, jolla on pieni anarkian hinta.
Anarkian hinta huutokaupoissa

Muistiinpanot

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

Kirjallisuus

Elias Koutsoupias, Christos Papadimitriou . Pahimman tapauksen tasapaino // Computer Science Review. - 2009. - Toukokuu ( osa 3 , numero 2 ). Arkistoitu alkuperäisestä 13. maaliskuuta 2016.
Vijay V. Vazirani, Noam Nisan, Tim Roughgarden, Eva Tardos. Luku 17 Johdatus tasapainojen tehottomuuteen // Algoritminen peliteoria . - Cambridge, Iso-Britannia: 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. Nash-tasapainon tehottomuus // Math. Toimi. Res .. - 1986. - T. 11 , no. 1 .
Tim Roughgarden. Itsekäs reititys ja anarkian hinta. - MIT Press , 2005. - ISBN 0-262-18243-2 .

Lue lisää lukemista varten

Fabio Cunial, Price of anarchy Arkistoitu 10. syyskuuta 2008 Wayback Machinessa

Peliteoria
Peruskonseptit	Keskinäinen ja yhteinen tieto Pelaaja Uskontojen hierarkia Irrationaalinen vahvistus Strategia ( dominanssi ) Käänteinen induktio
Pelityypit	Samanaikainen , peräkkäinen ja toistuva Yhteistyökyvyttömiä ja yhteistyöhaluisia Täydellisillä , epätäydellisillä , täydellisillä ja epätäydellisillä tiedoilla _ Normaalissa ja pidennetyssä muodossa _ Antagonistinen Ero Stokastinen Sukupuolten taistelu Hirven metsästys
Ratkaisukonseptit	Riskin hallitseva asema Korreloitu tasapaino Vapivan käden tasapaino Nashin tasapaino Alapelin täydellinen tasapaino Rationalisoitavuus Peräkkäinen saldo vahva tasapaino Oma saldo Evoluutiossa vakaa strategia Epsilon-tasapaino Pareto-tehokkuus Nucleus
Peliesimerkkejä	Vangin dilemma Baarin "El Farol" tehtävä Bertrand malli Cournot malli Stackelbergin malli Orlyanka Yhteisten resurssien tragedia haukat ja kyyhkyset
Episteeminen peliteoria Mekanismin suunnittelu Reilu jako