SPEAKER: Aaron Roth.

TIME: Wednesday 12-1pm, May 16, 2007.

PLACE: NSH 1507

TITLE: Selfishness without Nash: Two Alternatives to Price of Anarchy

ABSTRACT:
Price of Anarchy aims to measure the cost to a system when decisions are made 
by local, selfish agents, rather than mandated by a central authority. How do 
selfish agents behave? Traditionally, it is assumed that they play according 
to a Nash equilibrium -- but this is unrealistic, because in general, Nash 
equilibria can be both hard to compute and to coordinate. We study a much 
weaker and more realistic assumption about selfish behavior, introducing the 
term "Price of Total Anarchy" and show that in several broad classes of 
games, these weaker assumptions are enough to derive guarantees for the price 
of total anarchy that match the price of anarchy exactly, even though play 
provably does not necessarily converge to Nash equilibria. We do not assume 
that agents play using any particular algorithm, or that they have more than 
local information about the game state. We also show that our guarantees are 
resilient to the presence of Byzantine players -- additional agents about 
whom we make no assumptions, who may be nonrational or adversarial. When 
studying -anarchy-, it seems essential to account for players who do not 
behave according to any fixed set of assumptions, but this has been largely 
ignored up until now. We also survey a recent independent generalization of 
price of anarchy by Goemans, Mirrokni, and Vetta, the "price of sinking", and 
use Valid Games (which have been analyzed to get tight bounds for their price 
of anarchy, price of total anarchy, and price of sinking) as a lens through 
which to observe the differences between models.

Joint work with: Avrim Blum, Katrina Ligett, Mohammad Taghi Hajiaghayi