Efficiency-Reward Trade-Off in Queues with Dynamic Arrivals

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 $\epsilon$-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\mathrm{/}\epsilon$. 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 $\mathrm{\Theta }(1\mathrm{/}\sqrt{\epsilon })$; otherwise, it scales as $\mathrm{\Theta }(\log (1\mathrm{/}\epsilon ))$. 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.