# Learning in Strategic Queuing Systems with Small Buffers

arXiv: https://arxiv.org/abs/2502.08898 · HTML: https://mlsanity.com/paper/2502.08898/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 29 references that are in the map.
- First posted on arXiv 13 Feb 2025.

## Builds on (most cited first, 11 of 11)

- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Auctions Between Regret-Minimizing Agents](https://mlsanity.com/paper/2110.11855/) (2021)
- [Budget Pacing in Repeated Auctions: Regret and Efficiency without Convergence](https://mlsanity.com/paper/2205.08674/) (2022)
- [How and Why to Manipulate Your Own Agent: On the Incentives of Users of Learning Agents](https://mlsanity.com/paper/2112.07640/) (2021)
- [Stability and Learning in Strategic Queuing Systems](https://mlsanity.com/paper/2003.07009/) (2020)
- [Decentralized Learning in Online Queuing Systems](https://mlsanity.com/paper/2106.04228/) (2021)
- [Liquid Welfare Guarantees for No-Regret Learning in Sequential Budgeted Auctions](https://mlsanity.com/paper/2210.07502/) (2022)
- [Stability of Decentralized Queueing Networks Beyond Complete Bipartite Cases](https://mlsanity.com/paper/2210.07632/) (2022)
- [Strategic Behavior and No-Regret Learning in Queueing Systems](https://mlsanity.com/paper/2302.03614/) (2023)
- [Learning in Budgeted Auctions with Spacing Objectives](https://mlsanity.com/paper/2411.04843/) (2024)

## Built on by (most cited first, 1 of 1)

- [Learning in Strategic Queuing with Geometric Recharge: From Bandits to Systems](https://mlsanity.com/paper/2610.19179/) (2026)

## Abstract (arXiv)

We consider learning outcomes in games with carryover effects between rounds: when outcomes in the present round affect the game in the future. An important example of such systems is routers in networking, as they use simple learning algorithms to find the best way to deliver packets to their desired destination. This simple, myopic, and distributed decision process makes large queuing systems easy to operate, but at the same time, the system needs more capacity than would be required if all traffic were centrally coordinated. Gaitonde and Tardos (EC 2020 and JACM 2023) initiated the study of such systems, modeling them as an infinitely repeated game in which routers compete for servers and the system maintains a state (the number of packets held at each queue) that results from outcomes of previous rounds. However, their model assumes that servers have no buffers at all, so routers have to resend all packets that were not served successfully, which makes their system model unrealistic. They show that in their model, even with hugely increased server capacity relative to what is needed in the centrally coordinated case, ensuring that the system is stable requires the use of timestamps and priority for older packets. We consider a system with two important changes, which make the model more realistic and allow for much higher traffic rates: first, we add a very small buffer to each server, allowing the server to hold on to a single packet to be served later (if it fails to serve it immediately), and second, we do not require timestamps or priority to older packets. Using theoretical analysis and simulations, we show that when queues are learning, a small constant-factor increase in server capacity, compared to what would be needed if centrally coordinating, suffices to keep the system stable, even if servers select randomly among packets arriving simultaneously.