Abstact:
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. However, these results assume that there is no carry-over effects between rounds: outcomes in one round have no effect on the game in the future. Many repeated games have an evolving state resulting in direct carry-over effect, such as repeated auctions with budgets, as well as queuing systems. In this talk we will study 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 required excess server capacity needed to guarantee that all packets get served in two different 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, was chair of the Department of Computer Science 2006-2010 and 2020-2023. She was Interim Dean for Computing and Information Sciences 2012-2013. 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-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.
https://www.cs.cornell.edu/~eva/