Regret Minimization and the Price of Total Anarchy

Avrim Blum, MohammadTaghi Hajiaghayi, Katrina Ligett, Aaron Roth
[PDF]


Traditionally when studying price of anarchy, it is assumed that selfish players will play according to a Nash equilibrium. This is often unrealistic, and brittle to the introduction of Byzantine players. We show that under strictly weaker assumptions about rational agents, it is still possible to prove guarantees about the social welfare of a game, which we term “the price of total anarchy”. We study three broad classes of games, and show that in many cases, the price of total anarchy exactly matches the price of anarchy, while at the same time allowing for Byzantine (irrational, arbitrary, adversarial, etc.) players, about whom we make no assumptions. I discuss this research direction a bit here.