Abstrakt. Vi betraktar lösningskonceptet stokastisk stabilitet, och föreslår priset på stokastisk anarki som ett alternativ till priset på (Nash) anarki för att kvantifiera kostnaden för själviskhet och brist på samordning i spel. Som en lösning koncept, Nash jämvikt har nackdelar att uppsättningen av stokastiskt stabila tillstånd i ett spel undvika: till skillnad från Nash ekvilibria, stokastiskt stabila tillstånd är resultatet av naturliga dynamiken av beräkningsbart avgränsade och decentraliserade agenter, och är motståndskraftiga mot små störningar från perfekt spel. Priset på stokastisk anarki kan ses som en smidig analys av priset på anarki, skilja jämvikt som är motståndskraftiga mot buller från de som inte är det. För att illustrera nyttan av stokastisk stabilitet studerar vi lastbalanseringsspelet på orelaterade maskiner. Detta spel har ett obundet stort pris på Nash anarki även när det är begränsat till två spelare och två maskiner. Vi visar att i de två spelare fallet, priset på stokastisk anarki är 2, och att även i det allmänna fallet, priset på stokastisk anarki är begränsad. Vi antar att priset på stokastisk anarki är O(m), matcha priset på stark Nash anarki utan att kräva spelarsamordning. Vi förväntar oss att stokastisk stabilitet kommer att vara användbar för att förstå den relativa stabiliteten av Nash equilibria i andra spel där den värsta equilibria verkar vara i sig sprött.
Chung m.fl. REF studera priset på stokastisk anarki för lastbalanseringsspelet på orelaterade maskiner, som kan ses som en utjämnad analys av priset på anarki i en miljö där spelarna är ofullkomliga, som med viss liten sannolikhet gör misstag, spelar slumpmässiga åtgärder snarare än bästa svar.
The price of stochastic anarchy
{'venue': 'In SAGT ’08: Proceedings of the First Annual International Symposium on Algorithmic Game Theory', 'journal': None, 'mag_field_of_study': ['Economics', 'Computer Science']}