[NRG] FW: BUCS Colloquium by Eva Tardos on Games in Networks: The Price of Anarch and Learning [Mon 10/18 @ 11am]
best at bu.edu
Fri Oct 15 09:32:22 EDT 2010
I am forwarding this since some NRG members are not on the colloq list. --Azer
Boston University -- Computer Science Department
C O L L O Q U I U M
Monday October 18, 2010
11:00am - 12:30pm
School of Hospitality (SHA) is located at 928 Commonwealth Avenue
Games in Networks: The Price of Anarchy and Learning
Abstract: Network games play a fundamental role in understanding behavior in manomains, 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 parameterized distribution).
Short Bio: Eva Tardos is the Jacob Gould Schurman Professor of Computer Science at Cornell University, and was department chair 2006-2010. She received her BA and PhD from Eotvos University in Budapest.
Tardos won the Fulkerson Prize, awarded jointly by the Mathematical Programming Society and the American Mathematical Society, and the Dantzig prize awarded jointly by Mathematical Programming Society and the Society for Industrial and Applied Mathematics. She was awarded a number of research fellowships (among others Alfred P. Sloan, a NSF Presidential Young Investigator, Packard Foundation, Guggenheim). She is an ACM Fellow, INFORMS fellow, and SIAM fellow, is a member of the American Academy of Arts and Sciences and was elected to the National Academy of Engineering. 2003-2009 she was editor-in-chief of SIAM Journal on Computing, and she is on the editorial board of Journal of the ACM and Combinatorica.
Tardos's research interest is algorithms and algorithmic game theory, the subarea of computer science theory of designing systems and algorithms for selfish users. Her research focuses on algorithms and games on networks. She is most known for her work on network-flow algorithms, approximation algorithms, and quantifying the efficiency of selfish routing.
Host: Peter Gacs
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the NRG-L