Vi anser att priset på stabilitet för Nash och korrelerad jämvikt av linjär trängsel spel. Priset på stabilitet är det optimistiska priset på anarki, förhållandet mellan kostnaden för den bästa Nash eller korrelerad jämvikt över den sociala optimal. Vi visar att för summan sociala kostnader, som motsvarar den genomsnittliga kostnaden för spelarna, varje linjär trängsel spel har Nash och korrelerade priset på stabilitet på högst 1,6. Vi ger också en nästan matchande nedre gräns på 1 + ε 3/3 = 1.577. Vi betraktar också priset på anarki för korrelerad jämvikt. Vi utvidgar några av resultaten i [2, 4] till korrelerad jämvikt och visar att för summan samhällskostnad, priset på anarki är 2.5. Samma gräns håller för symmetriska spel också. Detta motsvarar de nedre gränser som ges i [2, 4] för ren Nash equilibria. Vi utökar också resultaten i [2] för viktade trängselspel till korrelerad jämvikt. Särskilt visar vi att när den sociala kostnaden är den totala latency, priset för anarki är (3 + 5)/2 = 2.618.
Dessa gränser håller också när man överväger priset på anarki av generaliseringar av PNE såsom blandade Nash equilibria och korrelerade equilibria, som visas av Christodoulou och Koutsoupias i REF.
On the Price of Anarchy and Stability of Correlated Equilibria of Linear Congestion Games
{'venue': 'ESA', 'journal': None, 'mag_field_of_study': ['Computer Science']}