[talks] Distinguished colloquium today: Eva Tardos

[Sanjeev Arora]

In Room 105 of CS Building, 4:30pm.

---------
Games in Networks: the price of anarchy and learning
Eva Tardos
Cornell

Network games play a fundamental role in understanding behavior in many 
domains, ranging from communication networks through markets to social 
networks. Such networks are used, and also evolve due to selfish 
behavior of the users and owners. In light of these competing forces, it 
is surprising how efficient these networks are. It is an exciting 
challenge to understand the operation and success of these networks in 
game theoretic terms: what principles of interaction lead selfish 
participants to form such efficient networks? We will focus on 
congestion games, and study the degradation of quality of solution 
caused by the selfish behavior of users. We model users as learning 
algorithms, and show that natural learning behavior can avoid bad 
outcomes predicted by the price of anarchy in atomic congestion games 
such as the load-balancing game. We use tools from the theory of 
dynamical systems and algebraic geometry to show when players use a 
class of natural learning algorithms the distribution of play converges 
to the set of weakly stable equilibria, and that the set of weakly 
stable equilibria are the pure Nash equilibria with probability 1 when 
congestion costs are selected at random independently on each edge (from 
any monotonically parametrized distribution). The talk is a survey and 
self-contained.

----- About the speaker: Eva Tardos is a Professor of Computer Science 
at Cornell University where she is currently chair. Her research is in 
Algorithm Design and Algorithmic Game Theory. Algorithmic game theory is 
an emerging new area of designing systems and algorithms for selfish 
users. She is a winner of the Fulkerson Prize and the Dantzig Prize.