http://www.cs.cmu.edu/~katrina

AG 1, AG 3, AG 5, RG2, AG 2, AG 4, RG1, SWS   Info

AG Audience

English

45 Minutes

Saarbrücken

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
problem.

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