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