Richard M. Karp Distinguished Lecture — Stability and Learning in Repeated Games

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.

This event will be held in person and virtually. 

Please read on for important information regarding logistics for those planning to register to attend the workshop in-person at Calvin Lab.

Proof of Vaccination
Given current public health directives from state, local, and university authorities, all participants in Simons Institute events must be prepared to demonstrate proof of full vaccination: a vaccination card or photo of the card along with a valid photo ID, or a green or blue Campus Access Badge via the UC Berkeley Mobile app (additional details regarding proof of vaccination can be found here).

Masks
Masks are strongly encouraged for all participants. The latest masking requirements on campus can be found here.

Refreshments
Light refreshments will be provided before the lecture. Please note due to current health conditions, we will set up just outside the building. There will be signs to direct you. Please note there is no food or drink allowed in the auditorium. Thank you for helping us to keep the auditorium clean.

Please note: the Simons Institute regularly captures photos and video of activity around the Institute for use in videos, publications, and promotional materials.