The Price of Anarchy in Selfish Queuing Systems: Learning and Patience (Streaming via Zoom)

Abstract: A fundamental aim at the intersection of economics and computer science is to understand the efficiency of systems when the dynamics are governed by the actions of strategic and competitive agents. Numerous works have focused on bounding the price of anarchy, which quantifies the gap between the social welfare of selfish outcomes and the social optimum. Moreover, a line of work has shown that these quantitative bounds often extend to outcomes when these games are repeated and agents use no-regret learning algorithms, which are simple and efficient.

However, a critical assumption underlying these results is that the repeated games are completely “independent”: the past sequence of play only impacts the choices of the agents, but not the nature of the game itself. In many settings, like packet routing or repeated auctions with budgets, this assumption is not reasonable. Towards understanding such games, in this talk, we consider price-of-anarchy-style results in queuing systems where there are strong dependencies between rounds as packets that fail to clear must be re-sent in later rounds. We approach this problem in two ways: first, we establish such bounds when queues use vanilla no-regret learning to choose servers. However, we will show how this form of learning can be incredibly myopic in these systems with state. We then study a patient version of the game where queues choose randomizations to optimize their long-run aging rate. We study the probabilistic and game-theoretic aspects of this formulation and establish tighter bounds than can be achieved by the no-regret property.

This is joint work with Eva Tardos and partially appeared at EC 2020.

Bio: Jason Gaitonde is a third-year PhD student in Computer Science at Cornell University advised by √Čva Tardos. He previously graduated with a BS in Mathematics and a BA in Economics from Yale University. He is broadly interested in theoretical computer science, and his research so far has mostly focused on questions in game theory, learning theory, and network dynamics