Efficiency-Reward Trade-Off in Queues with Dynamic Arrivals
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917236815429632 |
|---|---|
| author | Qu, Tianze Varma, Sushil Mahavir |
| author_facet | Qu, Tianze Varma, Sushil Mahavir |
| contents | Motivated by applications in online marketplaces such as ride-hailing platforms and payment channel networks, we study a single-server queue with state-dependent arrival control. The service operator dynamically chooses the arrival rate as a function of the current queue length and receives a reward determined by the induced rate, capturing objectives such as throughput, revenue, or social welfare. The goal is to design control policies that simultaneously achieve high long-run operating reward and low congestion, measured by the expected steady-state queue length.
We adopt a regret-based framework relative to an optimal benchmark and characterize the efficiency--reward trade-off under an $\varepsilon$-optimal reward constraint. Our results reveal a sharp dichotomy between small-market and large-market regimes. In small markets, including state-independent policies, any admissible control incurs poor efficiency, with the expected queue length growing on the order of $1/\varepsilon$. In contrast, in large markets, state-dependent policies can achieve substantially better performance. When the reward function exhibits sufficient curvature, the optimal queue length scales as $Θ(1/\sqrt{\varepsilon})$; otherwise, it scales as $Θ(\log(1/\varepsilon))$.
For each regime, we establish universal lower bounds on the achievable efficiency and construct simple state-dependent policies that attain these bounds. Our results provide a non-asymptotic heavy-traffic characterization for queues with dynamic arrivals and offer structural insights into the design of efficient pricing and admission control policies. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_00351 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Efficiency-Reward Trade-Off in Queues with Dynamic Arrivals Qu, Tianze Varma, Sushil Mahavir Optimization and Control Probability Motivated by applications in online marketplaces such as ride-hailing platforms and payment channel networks, we study a single-server queue with state-dependent arrival control. The service operator dynamically chooses the arrival rate as a function of the current queue length and receives a reward determined by the induced rate, capturing objectives such as throughput, revenue, or social welfare. The goal is to design control policies that simultaneously achieve high long-run operating reward and low congestion, measured by the expected steady-state queue length. We adopt a regret-based framework relative to an optimal benchmark and characterize the efficiency--reward trade-off under an $\varepsilon$-optimal reward constraint. Our results reveal a sharp dichotomy between small-market and large-market regimes. In small markets, including state-independent policies, any admissible control incurs poor efficiency, with the expected queue length growing on the order of $1/\varepsilon$. In contrast, in large markets, state-dependent policies can achieve substantially better performance. When the reward function exhibits sufficient curvature, the optimal queue length scales as $Θ(1/\sqrt{\varepsilon})$; otherwise, it scales as $Θ(\log(1/\varepsilon))$. For each regime, we establish universal lower bounds on the achievable efficiency and construct simple state-dependent policies that attain these bounds. Our results provide a non-asymptotic heavy-traffic characterization for queues with dynamic arrivals and offer structural insights into the design of efficient pricing and admission control policies. |
| title | Efficiency-Reward Trade-Off in Queues with Dynamic Arrivals |
| topic | Optimization and Control Probability |
| url | https://arxiv.org/abs/2602.00351 |