Stability and Learning in Repeated Games

Éva Tardos (Cornell University)
https://simons.berkeley.edu/events/rmklectures2022-spring-3
Richard M. Karp Distinguished Lecture

Over the last two decades, the research community has developed a good understanding of how to quantify the impact of strategic user behavior on outcomes in many games (including traffic routing and online auctions) and showed that the resulting bounds extend to repeated games, assuming players use a form of no-regret learning to adapt to the environment. This talk will discuss the results as well as their limitations. In both packet routing and online auctions, the state of the game evolves depending on outcomes in previous rounds, which makes the extension inapplicable. In the context of simple routing games, we find that the no-regret condition for learning is strong enough to guarantee stability, assuming a constant factor increase in server capacity, but examples also suggest that no-regret learning may not be a good enough learning strategy in such environments.

Éva Tardos is a Jacob Gould Schurman Professor of Computer Science, currently chair of the Department of Computer Science for a second term after being chair 2006-2010. She has also served as Interim Dean for Computing and Information Sciences and as Associate Dean for Diversity & Inclusion. She received her BA and PhD from Eötvös University in Budapest. She joined the faculty at Cornell in 1989. Tardos’s research interest is algorithms and interface of algorithms and incentives. She is most known for her work on network-flow algorithms and quantifying the efficiency of selfish routing. She has been elected to the National Academy of Engineering, the National Academy of Sciences, the American Philosophical Society, the American Academy of Arts and Sciences, and to the Hungarian Academy of Sciences. She is the recipient of a number of fellowships and awards including the Packard Fellowship, the Gödel Prize, Dantzig Prize, Fulkerson Prize, ETACS prize, and the IEEE von Neumann Medal. She co-wrote the widely used textbook Algorithms Design. She has been editor-in-Chief of the Journal of the ACM and earlier of SIAM Journal of Computing, and editor of several other journals, and was program committee member and chair for several ACM and IEEE conferences in her area.

Видео Stability and Learning in Repeated Games канала Simons Institute