Campus Event Calendar

Event Entry

What and Who

Regret Minimization and the Price of Total Anarchy

Katrina Ligett
Carnegie Mellon University
AG 1, AG 3, AG 5, RG2, AG 2, AG 4, RG1, SWS  
AG Audience

Date, Time and Location

Wednesday, 7 May 2008
45 Minutes
E1 4


We propose weakening the assumption made when studying the price of
anarchy: Rather than assume that self-interested players will play
according to a Nash equilibrium (which may even be computationally hard
to find), we assume only that selfish players play so as to minimize a
quantity known as regret. Regret minimization can be done via simple,
efficient algorithms even in many settings where the number of action
choices for each player is exponential in the natural parameters of the

In this talk we'll see that despite our weakened assumptions, in several
broad classes of games, this "price of total anarchy'' matches the Nash
price of anarchy, even though play may never converge to Nash
equilibrium. In contrast to the price of anarchy and the recently
introduced price of sinking, which require all players to behave in a
prescribed manner, we show that the price of total anarchy is in many
cases resilient to the presence of Byzantine players, about whom we make
no assumptions. Finally, because the price of total anarchy is an upper
bound on the price of anarchy even in mixed strategies, for some games
our results yield as corollaries previously unknown bounds on the price
of anarchy in mixed strategies.


Evangelia Pyrga
--email hidden
passcode not visible
logged in users only

Evangelia Pyrga, 04/23/2008 20:38
Evangelia Pyrga, 04/23/2008 20:36 -- Created document.