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.