Selfish Learners in Queueing Systems with Small Buffers.

Abstract: 

Algorithmic Game Theory has provided a good understanding of the impact of strategic behavior on outcomes in many one-shot games, including traffic routing and online auctions. This has been extended to repeated games under the assumption players use some form of (no-regret) learning. However, in many real-life scenarios, rounds are not repetitive and may involve carryover effects from one round to the next. This is the case of budgeted auctions and queuing systems.

In this talk, we analyze a queueing system modeling packet routing in data centers. Routers compete for getting their packets treated by servers. Rejected packets must be resent in subsequent rounds, creating dependencies across time. We study the resulting process and show bounds on the excess server capacity needed to guarantee that all packets get served despite the selfish and myopic behavior of the routers.

Posted on Aug 18, 2025 in ACGO, Seminars