Sharp multiserver pricing guarantees and the worst congestion load
Unrefereed research candidate. A service with several servers can set a single fixed price and cap the number of customers in the system. Bergquist and Elmachtoub (Stochastic Systems, 2026) gave worst-case guarantees for a particular construction of this kind, which offers arrivals at the accepted throughput of an optimal dynamic policy, and conjectured that their multiserver profit, revenue and congestion bounds cannot be improved. This candidate proves that for every number of servers C and every capacity N, with uniform valuations. Example. With C=5 and N=7 the construction keeps at least 81.85% of optimal revenue and raises mean occupancy by at most a factor 1.01003, and neither number can be improved. The worst congestion occurs at an offered load of about 2.59, and the worst revenue as the load approaches 5. Results. Within the suggested linear-demand family, the optimal throughput is an analytic, strictly increasing bijection onto (0,C). A quartic Q_C decides whether the congestion ratio peaks below critical load, and the same transition decides whether the worst revenue and congestion ratios can be approached together. Its waiting-capacity threshold is asymptotic to 1.7882539728 sqrt(C). With c sqrt(C) waiting places the maximal ratio and its maximising load converge to an explicit optimisation problem. Theorem 4.3 gives the exact worst-case revenue-congestion frontier, and Theorem 8.1 proves the companion sojourn-time guarantees sharp, with both constants always approached together. Theorem 7.1 gives finite-parameter bounds on the approach. Limits. The results concern the specified throughput-matched construction, not the best static policy, which remains open: the throughput t* is a proof device, because anyone who can compute it could simply optimise the price. The occupancy ratio can hide a queue: with C=100 and N=120 the worst ratio is 1.033, while the mean queue at critical load is about 6.3. The frontier and sojourn proofs are elementary and have close antecedents. Pacheco (1994) has the same threshold at C=1, and the transitions differ at C=2. This record is not a priority claim. The archive contains the manuscript (PDF and Markdown source), four check scripts with retained output, figures and SHA-256 sums. Assurance: written proofs; internal AI-assisted review only (not human peer review, independent reproduction or proof-assistant verification). Creator: Anonymous. Text CC0-1.0; code MIT.
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-04
- DOI
- https://doi.org/10.5281/zenodo.23953351
- Primary Topic
- Advanced Queuing Theory Analysis
- Type
- preprint