Priset på anarki (POA) är ett värsta fall mått på ineffektivitet av själviskt beteende, definieras som förhållandet mellan objektiv funktion värde av en värsta Nash jämvikt i ett spel och ett optimalt resultat. Denna åtgärd förutsätter implicit att spelarna framgångsrikt nå några Nash jämvikt. Denna nackdel motiverar sökandet efter ineffektivitet gränser som mer allmänt gäller svagare begrepp om jämvikt, såsom blandade Nash och korrelerad jämvikt; eller sekvenser av resultat som genereras av naturliga experiment strategier, såsom på varandra följande bästa svar eller samtidig ånger-minimering. Vi bevisar ett allmänt och grundläggande samband mellan priset på anarki och dess till synes starkare släktingar i spelklasser med ett absolut mål. Först identifierar vi en "kanonisk tillräcklig villkor" för en övre gräns av POA för ren Nash jämvikt, som vi kallar en släthet argument. För det andra visar vi att varje bundet som härleds via en släthet argument sträcker sig automatiskt, utan någon kvantitativ nedbrytning i det bundna, till blandade Nash jämvikt, korrelerad jämvikt, och det genomsnittliga objektiva funktionsvärdet av ångra-minimerande spelare (eller "priset för total anarki"). Smidighetsargumenten har också automatiska konsekvenser för ineffektiviteten hos ungefärliga och Bayesian-Nash-ekvilibria och, under milda ytterligare antaganden, för bikriteriagränser och för sekvenser med bäst respons i polynomlängd. Vi identifierar också klasser av spel - framför allt trängselspel med kostnadsfunktioner som begränsas till en godtycklig fast uppsättning - som är snäva, i den meningen att smidighet argument garanteras att producera en optimal värsta fall övre gräns på POA, även för den minsta uppsättningen av intresse (ren Nash equilibria). Biprodukter av vårt bevis på detta resultat inkluderar de första snäva gränserna på POA i trängselspel med icke-polynomiska kostnadsfunktioner, och den första *
Priset på anarki fångar själviskhetens inverkan på effektiviteten och definieras som det värsta förhållandet mellan de sociala kostnaderna i en ren Nash-jämvikt och det sociala optimala (se REF och hänvisningarna där för snäva gränser för trängselspel).
Intrinsic robustness of the price of anarchy
{'venue': "STOC '09", 'journal': None, 'mag_field_of_study': ['Computer Science']}