Vi studerar den försämring i nätverksprestanda som orsakas av det själviska beteendet hos icke-kooperativa nätverksanvändare. Vi anser att en modell för självisk routing där den latens som nättrafiken upplever i en utkant av nätet är en funktion av kantstockningen, och nätanvändarna antas själviskt leda trafiken på minimala latensvägar. Kvaliteten på en färdväg mäts med summan av restiderna, som också kallas den totala latensen. Resultatet av självisk routing-a Nash jämvikt-gör inte i allmänhet minimera den totala latency; därför, själviskt beteende bär kostnaden för minskad nätverksprestanda. Vi kvantifierar denna försämring i nätets prestanda genom priset på anarki, det värsta möjliga förhållandet mellan den totala latensen av en Nash jämvikt och en optimal ruttning av trafiken. Vi visar priset på anarki bestäms endast av de enklaste nätverken. Särskilt bevisar vi att under svaga hypoteser om klassen tillåtna kant latensfunktioner, uppnås det värsta förhållandet mellan den totala latensen hos en Nash-jämvikt och en minimal latency routing för alla multicommodity flow network av en enda kommodity instans på ett nätverk av parallella länkar. I det speciella fallet där klassen tillåtna latensfunktioner omfattar alla konstanta funktioner, bevisar vi att ett nätverk med endast två parallella länkar räcker för att uppnå det sämsta möjliga förhållandet. Vår garanti att enkla nätverk alltid ger sämsta möjliga exempel ger en kraftfull metod för att beräkna priset på anarki med avseende på en godtycklig klass av latensfunktioner. Vi tillämpar denna metod på funktionsklasser som har varit väl studerade i litteraturen, inklusive examensbundna polynom och köande fördröjningsfunktioner. Dessa är de första snäva analyserna av priset på anarki för betydande klasser av latensfunktioner utanför klassen av linjära funktioner.
REF visar att för denna inställning är det faktiskt klassen tillåtna latensfunktioner och inte den specifika topologin för ett nätverk som bestämmer priset på anarki.
The Price of Anarchy is Independent of the Network Topology
{'venue': 'Journal of Computer and System Sciences', 'journal': None, 'mag_field_of_study': ['Computer Science']}