EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Efficiency-Reward Trade-Off in Queues with Dynamic Arrivals

Tianze Qu, Sushil Mahavir Varma

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →