CAM Colloquium - PhD Recruitment Talk - Éva Tardos, Cornell University "Learning in Strategic Queuing"

Description

Title: Learning in Strategic Queuing

Abstract: Over the last two decades we have developed good understanding 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 learning (no-regret learning) to adapt to the environment.

In this talk, we will focus on repeated interactions that have carry-over effects between rounds: when outcomes in one round effect the game in the future, as in repeated auctions with budgets, as well as queuing systems. We will consider this phenomenon in the context of a game modeling 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. We study the resulting highly dependent random process and show bounds on the excess server capacity needed to guarantee that all packets get served in two different the queuing systems (with or without buffers) despite the selfish (myopic) behavior of the participants.  

Bio: Éva Tardos is a Jacob Gould Schurman Professor of Computer Science, ws chair of the Department of Computer Science 2006-2010 and 2020-2023. 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. 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 and Austrian Academies 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 has been editor of several other journals, and was program committee member and chair for several ACM and IEEE conferences in her area.