Stability and Learning in Strategic Games

Over the last two decades we have developed 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. We will review how this area evolved since its early days, and also discuss some of the new frontiers, including when repeated interactions have carry-over effects between rounds: when outcomes in one round effect the game in the future, as is the case in many applications. In this talk, we study this phenomenon in the context of a game modeling repeated auction with budgets and queuing systems: routers compete for servers, where packets that do not get served need to be resent, resulting in a system where the number of packets at each round depends on the success of the routers in the previous rounds. In joint work with Giannis Fikioris and Jason Gaitonde respectively, we analyze the resulting highly dependent random processes, and show bounds on the resulting budgeted welfare for auctions and the excess server capacity needed to guarantee that all packets get served in the queuing system despite the selfish (myopic) behavior of the participants.

É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 was Interim Dean for Computing and Information Sciences 2012-2013 and was Associate Dean for Diversity & Inclusion 2019-2020 at Cornell University. 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 Editor-in-Chief of the Journal of the ACM and of the SIAM Journal of Computing, and was  editor of several other journals, and was program committee member and chair for several ACM and IEEE conferences in her area.

View the event details on the CLIMB website here: https://climb.berkeley.edu/eva-tardos-seminar/

===================================================================

Light refreshments will be available prior to the start of the talk and at the conclusion of the talk.

The Simons Institute regularly captures photos and video of activity around the Institute for use in publications and promotional materials. 

If you require special accommodation, please contact our access coordinator at simonsevents [at] berkeley.edu with as much advance notice as possible.