Efficiency-Reward Trade-Off in Queues with Dynamic Arrivals

Abstract

Motivated by applications in online marketplaces such as ride-hailing platforms and payment channel networks, we study a single server queue with service rate $\mu$ and queue-length-dependent arrival rate $\lambda (q)\in [0,{\lambda }_{\max }]$. The system operator receives a reward $F(\lambda )$ by setting an arrival rate $\lambda$, where $F$ can represent objectives such as throughput, revenue, or social welfare. The goal is to characterize the Pareto frontier between long-run average reward and expected queue length ($\mathbb{E}[q]$). We first establish a fluid upper bound on the reward achievable under any control policy $\{\lambda (q)\}$, and define regret as the gap from this upper bound. We then minimize $\mathbb{E}[q]$ subject to the regret being at most $\epsilon$. In the small-market regime $({\lambda }_{\max }\le \mu )$, we show that no control policy can improve over the classical heavy-traffic scaling of $\mathbb{E}[q]=\Omega (1/\epsilon )$. In contrast, in the large-market regime $({\lambda }_{\max }>\mu )$, we substantially improve over the classical scaling by explicitly constructing control policies with expected queue lengths at most $O(1/\sqrt{\epsilon })$ or $O(\log (1/\epsilon ))$, depending on the curvature structure of \(F\). Moreover, we establish universal lower bounds of $\Omega (1/\sqrt{\epsilon })$ or $\Omega (\log (1/\epsilon ))$ respectively under any general control policy. These results can be viewed as (non asymptotic) heavy-traffic theory for queues with dynamic arrivals.

arXiv commentAccepted and published as an extended abstract in SIGMETRICS 2026