Efficiency-Reward Trade-Off in Queues with Dynamic Arrivals
ACM SIGMETRICS Performance Evaluation Review · 20.07.2026 · 54 (1) · 153-155
DOI: 10.1145/3820171.3806908 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM SIGMETRICS Performance Evaluation Review, online erschienen am 27.07.2026. Verfasst von Tianze Qu und 1 weiteren Autor:innen. Die Arbeit nennt 8 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
Motivated by emerging applications in various online marketplaces, such as ride-hailing platforms and payment channel networks, we study a single-server queue with service rate μ and state (queue length) dependent arrival rate λ(q) ∈ [0, λ max ]. The service operator receives a reward of F(λ) by setting an arrival rate of λ, where F can be used to model objectives like throughput, revenue, and social welfare. The goal is to design a control policy {λ(q)} q ∈ Z + that is both reward-optimal and efficient. Specifically, we consider the long-run average reward E[F(λ(q))] and the steady-state expected queue length E[q], where q denotes the steady-state queue length, and characterize the Pareto frontier between these two objectives. We first establish a benchmark upper bound on the operating reward and define regret with respect to this benchmark. We then constrain the regret to be at most ε and focus on minimizing E[q]. Under mild smoothness assumptions on F , we show that in the small-market regime (λ max ≤ μ), any control policy incurs E[q] ≥ Ω(1/ε). In contrast, in the large-market regime (λ max >> μ), the system is significantly more efficient: E[q] = Θ(1/√ε) when F is concave-like near capacity, and E[q] = Θ(log (1/ε)) otherwise. In both cases, we establish matching lower bounds and construct state-dependent control policies that achieve them. These results provide a unified view of efficiency–reward trade-offs and can be interpreted as a non-asymptotic heavy-traffic theory for queues with dynamic arrivals.
Zitieren
APA
Qu, T., & Varma, S. M. (2026). Efficiency-Reward Trade-Off in Queues with Dynamic Arrivals. ACM SIGMETRICS Performance Evaluation Review, 54(1), 153-155. https://doi.org/10.1145/3820171.3806908
Vancouver
Qu T, Varma SM. Efficiency-Reward Trade-Off in Queues with Dynamic Arrivals. ACM SIGMETRICS Performance Evaluation Review. 2026;54(1):153-155. doi:10.1145/3820171.3806908
BibTeX
@article{Qu2026,
author = {Qu, Tianze and Varma, Sushil Mahavir},
title = {Efficiency-Reward Trade-Off in Queues with Dynamic Arrivals},
journal = {ACM SIGMETRICS Performance Evaluation Review},
year = {2026},
volume = {54},
number = {1},
pages = {153--155},
doi = {10.1145/3820171.3806908}
}
EUVIMED