Pith. sign in

REVIEW 2 major objections 5 minor 42 references

How to Beat FCFS

T0 review · 2 major / 5 minor · reviewed 2026-08-16 · deepseek-v4-flash

Pith's one-line read A service queue can beat an identical FCFS competitor and capture a strict majority of arrivals solely by reordering its waitlist, even though its own average wait is longer.

desk verdict A genuinely novel scheduling rule that deserves a serious referee, but the main theorem's proof has a real gap in the coupled-chain stability argument that needs fixing. read the letter →

arxiv 2608.11710 v1 pith:4P3LV343 submitted 2026-08-12 econ.TH

classification econ.TH MSC 60K2591A1090B22
keywords queueingcompetitionservicerulesFirst-Come-First-ServedLedgerrulemarketsharestrategicroutingwaitingtimescommitment
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks whether a queue can win more customers than an identical rival queue without changing price or capacity, only the order in which it serves people. It answers yes: against a First-Come-First-Served queue, the other queue can use a slot-placement rule called the Ledger and attract a strict majority of all arrivals in steady state. The result does not require the Ledger queue to have shorter waits on average; it only requires that each arriving agent receives an individually better expected wait from the Ledger than from FCFS. The paper also proves caps on how much market share any work-conserving rule can take from FCFS, $1/\sqrt{2}$ for preemptive rules and $1/\Phi$ for non-preemptive ones, where $\Phi$ is the golden ratio.

What carries the argument

The load-bearing object is the Ledger rule itself, a state-based service rule that maintains a list of occupied slots and decides where each arrival goes, whom to serve, and how to shift survivors after service. Its defining move is to offer an arriving agent a slot no worse than the slot FCFS would offer at the rival queue while deliberately leaving empty slots below that position, building a buffer for future arrivals. The proof machinery around it is a coupling among three systems on the same event-time realization, followed by a renewal-reward step; the required stability is supplied by proving positive recurrence of the Ledger-FCFS state process through fluid limits and a Lyapunov function $W_\varepsilon=V+\varepsilon Q$, where $h_A$ is one plus the highest occupied Ledger slot and $b$ is the FCFS queue length, so $V=\max\{h_A,b+1\}$ tracks both queue heights while $Q$ tracks total congestion.

What would settle it

Run a long simulation of the Ledger rule against FCFS at $\lambda=1.9$ and measure both the frequency of visits to the state where both queues are empty and the asymptotic arrival share to queue A; Theorem 2 predicts the share exceeds $0.95$, so an estimate at or below $0.95$ with reliable confidence would contradict it, as would growing gaps between returns to the empty state.

Watch

Extended reading notes

Core claim

The central discovery is Theorem 2: if queue A uses the Ledger rule or its non-preemptive variant and queue B uses FCFS, then queue A has an asymptotic arrival rate strictly greater than $\lambda/2$ for every arrival rate $\lambda\in(0,2)$. The Ledger rule places each arriving agent in the highest available slot at or below the length of the FCFS queue whenever possible, and otherwise in the lowest open slot; service is always from the lowest occupied slot. This creates and preserves gaps that can be used to win later arrivals. The proof couples three systems on one realization of arrivals, services, and tie-breaks: Ledger versus FCFS, FCFS versus FCFS with a one-sided device that sometimes forces arrivals to queue A, and pure FCFS versus FCFS. The Ledger arrival process equals the device system and weakly dominates the pure FCFS system, and a positive-probability event starting and ending with both queues idle yields one extra arrival under the Ledger; the renewal reward theorem turns this into a strictly positive long-run advantage.

Load-bearing premise

The proof depends on the Ledger-versus-FCFS state process being positive recurrent for every arrival rate below two, meaning the system returns to the empty state often enough to make the renewal-reward argument valid; if that stability claim fails for some $\lambda$, the strict majority conclusion does not follow.

Editorial extensions

If this is right

  • If Theorem 2 is right, a queue that can commit to a service rule has a unilateral profitable deviation from FCFS-FCFS, so FCFS-FCFS is not an equilibrium under commitment.
  • Against FCFS, no work-conserving queue can exceed a $1/\sqrt{2}\approx0.707$ share of arrivals; the non-preemptive version of the same bound is $1/\Phi\approx0.618$.
  • For $\lambda<1/2$, Protected LCFS, a rule that protects exactly one agent from preemption while serving everyone else LCFS, is a symmetric equilibrium with equal demand but longer average waits than symmetric FCFS.
  • Without commitment, the FCFS-FCFS outcome with shortest-queue routing is a subgame-perfect equilibrium, so commitment changes both whether FCFS survives and the identity of equilibrium service rules.
  • Simulations place the Ledger's peak advantage near $\lambda=0.9$ for the preemptive rule (roughly 52% of arrivals) and near $\lambda=1.3$ for the non-preemptive rule (roughly 50.4%).

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Extension the paper does not claim: the caps $1/\sqrt{2}$ and $1/\Phi$ are proved only against an FCFS rival; against a rival that also tailors its service order, achievable shares may be lower, which would require equilibrium analysis beyond the $\lambda<1/2$ Protected LCFS regime.
  • Extension: the strictness of the Ledger advantage rests on a tie-breaking event in the coupling; quantifying how the advantage changes under tie-breaking distributions other than uniform is a direct next question.
  • Connection the authors leave implicit: their open question about beating FCFS without observing the rival's state parallels the idea that a firm can infer a competitor's price from its own demand; testing whether an unobservable-state analogue of the Ledger still beats FCFS would clarify how much information the tactic needs.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper studies two observable M/M/1 queues with unit service rates and Poisson arrivals at rate λ∈(0,2); each arriving agent joins the queue that minimizes expected waiting time, with ties broken uniformly. The paper constructs the Ledger rule and a non-preemptive variant, and claims that when the competing queue uses FCFS, the Ledger queue obtains an asymptotic arrival rate strictly larger than λ/2 (Theorems 1–2). It also proves parameter-free upper bounds on the market share any work-conserving rule can capture against FCFS (Theorem 3), a symmetric equilibrium with commitment at low congestion based on a novel 'Protected LCFS' rule (Theorem 4), and an FCFS–FCFS subgame-perfect equilibrium without commitment (Theorem 5). The proof of Theorem 2 uses a fixed-ω coupling to show pathwise dominance of the Ledger over FCFS, a positive-probability event with strictly more Ledger arrivals before both systems empty, and a renewal-reward argument over cycles between joint-empty states of the coupled process.

Significance. The central claim is striking and, if fully established, important for the literature on queue competition: a queue can win a strict majority of demand purely through its service order, even while generating longer average waits on its own queue. The paper has several concrete strengths: the Ledger rule is explicit and state-based; the pathwise coupling is clean and parameter-free; the upper-bound results are crisp and falsifiable; the simulations quantify the effect; and the supplemental stability appendix is detailed. The main reservation is that the theorem's renewal-reward step depends on positive recurrence of the coupled (Ledger, FCFS–FCFS) Markov chain, and that step is not convincingly proved in the manuscript.

major comments (2)
  1. [Section 5.2, Lemma 5 and Proposition 2] The proof of Theorem 2 requires the coupled process (X1,X3) to visit the joint-empty state with finite mean return time, because the renewal-reward argument uses E[C1]<∞. Proposition 2 asserts this, but its proof is not complete. Lemma 5 claims that positive recurrence of System 1 together with Kingman's stability of the two-FCFS system implies positive recurrence of the coupled chain, citing Glynn (1985). Marginal positive recurrence does not, in general, imply joint positive recurrence under an arbitrary common-random-number coupling; one needs common regeneration times or another verifiable regenerative structure. The manuscript does not state or verify such hypotheses, and the joint transition kernel is not a product kernel, so the two marginal stabilities do not combine. The supplemental appendix, Theorem 8, proves positive recurrence only of System 1. Thus the key condition that the cycle lengths C_m have finite mean is not established, and the strict-inequality conclusion of Theorem 2 is not justified by the argument as written. This is a load-bearing gap; it needs either a direct proof of positive recurrence of the coupled chain or a precise citation with verified hypotheses.
  2. [Section 5.2, proof of Theorem 2] Even if Proposition 2 were established, the proof of Theorem 2 would benefit from making explicit why the pairs {(C_m,W_m)} are i.i.d. and why the asymptotic rate of the FCFS–FCFS system is λ/2 for both queues. The symmetry claim is plausible by exchangeability, but it is stated without proof. More importantly, the current text's assertion that 'By Proposition 2... cycle lengths C_m have finite mean' is the only support for the renewal-reward theorem; the gap identified in the previous comment is therefore not a cosmetic issue but the main missing step in the central theorem.
minor comments (5)
  1. [Section 5.2, proof of Lemma 2] In the sentence 'If the device forces routing to queue A in system 1, the inequality is obviously satisfied,' the reference should be to system 2, not system 1. The waitlist comparisons via Lemma 1 that justify the phrase 'A is weakly more attractive' are only implicit and should be written out.
  2. [Section 5.2, proof of Theorem 2] The claim that in system 3 each FCFS queue has asymptotic arrival rate λ/2 is used without proof. This follows from symmetry and exchangeability of the two queues, but it should be stated explicitly for completeness.
  3. [Section 4.2 and Section 7] There are small typos: 'in which most one agent' should be 'at most one agent', and 'remains an interesting direction for future' should be 'future work'.
  4. [Section 5.4, proof of Theorem 4] The text says 'it can attract at most λ agents in expectation'; the bound is correct, but the wording could be misread as a pathwise bound. I suggest 'at most λ agents in expectation' with the expectation made explicit.
  5. [Section 3 and Section 5.5] The notation b=|S_B| is used as the number of agents in queue B when defining the Ledger, while in Theorem 5 the queue size Q_q includes the agent in service. Please make the convention uniform or state explicitly how the agent in service is counted in each definition, so that the slot comparisons in the Ledger rule and the proof of Theorem 5 can be compared directly.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main claims are derived from model primitives; citations to the authors' prior work are background context, not load-bearing inputs.

full rationale

The paper's central results are proved analytically from the stated model primitives rather than from fitted parameters or from the authors' earlier theorems. Theorem 2 is established by a coupling construction (Systems 1-3), a positive-probability strict-dominance event, and a renewal-reward argument whose ingredients are Proposition 1 (pathwise dominance), Lemma 4 (strict advantage event), and Proposition 2 / Supplemental Appendix S.1 (positive recurrence). The Ledger rule is explicitly constructed and then analyzed; no parameter is fitted to data and then renamed as a prediction. The upper bounds in Theorem 3 follow from flow-balance inequalities and the service-rate capacity constraint, not from the constructed Ledger rule. Self-citations (Ashlagi et al. 2010, 2013) appear only in the related-literature discussion and are not used to justify any theorem. The citation to Glynn (1985) in Lemma 5 and to Kingman (1961) are external mathematical references; even if the coupling argument were incomplete or the cited implication needed additional hypotheses, that would be a correctness or completeness concern rather than a circularity, because the paper does not define its conclusion into its assumptions. The positive-recurrence proof is deferred to the supplemental appendix, but it is a substantive independent argument based on a Lyapunov function and fluid limits, not a restatement of the theorem being proved. Thus no step in the derivation chain reduces, by construction or by self-citation, to its own inputs.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters are fitted. The theoretical results rest on standard Poisson/exponential queueing assumptions, the behavioral assumption of expected-wait minimization with uniform tie-breaking, work conservation, and external stability theorems. The Ledger rule and Protected LCFS are defined constructs, not new physical entities.

assumptions (5)
  • domain assumption Arrivals to the system follow a Poisson process with rate lambda in (0,2), and service times at each queue are i.i.d. exponential with rate 1.
    Model primitives in Section 3; memorylessness is used to pass to the embedded discrete-time chain and to compute expected waits in Theorem 5.
  • domain assumption Agents observe the states of both queues and join the queue minimizing expected waiting time, breaking ties uniformly at random.
    Adopted in Section 3; uniform tie-breaking is used in the coupling proof and in the upper-bound arguments.
  • domain assumption Both queues are work-conserving: they serve whenever nonempty.
    Assumed for all rules; used in Lemma 1 and in the flow-balance bounds of Theorem 3.
  • standard math Two competing FCFS queues with shortest-queue routing are positive recurrent (Kingman, 1961).
    Used in Lemma 5 to reduce positive recurrence of the coupled system to positive recurrence of the Ledger-FCFS system.
  • standard math Fluid-limit stability criteria (Dai 1995; Meyn and Tweedie 1994) and the regenerative coupling result of Glynn (1985) are valid in this setting.
    Used in Supplemental Appendix S.1 to prove positive recurrence of the Ledger-FCFS chain.

how reviews work

0 comments
Cite this review

Pith. "Pith review of How to Beat FCFS." pith.science (2026). https://pith.science/paper/4P3LV343

@misc{pith2026260811710,
  author       = {Pith},
  title        = {Pith review of: How to Beat FCFS},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4P3LV343}},
  note         = {Machine review of arXiv:2608.11710}
}
read the original abstract

We study two observable queues with identical service rates, serving agents who arrive stochastically over time. Agents join the queue that minimizes their expected waiting time. Assuming one queue uses the ubiquitous First-Come-First-Served (FCFS) service rule, we show that by simply modifying its service order, the other queue can capture a strict majority of the demand. We establish an upper bound on the arrival share any rule can capture against FCFS. When both queues can design their service order, we show a novel variant of Last-Come-First-Served (LCFS) is an equilibrium in a low congestion regime. Without commitment, the picture changes, and there is an equilibrium where both queues use FCFS, and agents route to the queue with the shorter waitlist.

Figures

Figures reproduced from arXiv: 2608.11710 by the authors.

Figure 1
Figure 1. This shows the evolution of the two queues in the event described above. [PITH_FULL_IMAGE:figures/full_fig_p024_1.png] view at source ↗
Figure 2
Figure 2. Upper bounds on queue A’s share of arrivals when facing FCFS under any [PITH_FULL_IMAGE:figures/full_fig_p029_2.png] view at source ↗
Figure 3
Figure 3. The share of arrivals that route to the Ledger rule when facing FCFS as a [PITH_FULL_IMAGE:figures/full_fig_p032_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: The difference in empirical distributions of wait times for queues [PITH_FULL_IMAGE:figures/full_fig_p033_4.png]
Figure 5
Figure 5. Figure 5: Average waiting time under symmetric Protected LCFS versus symmetric [PITH_FULL_IMAGE:figures/full_fig_p033_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

42 extracted references · 39 canonical work pages

  1. [1]

    arXiv preprint arXiv:2505.22862 , year=

    Optimal Auction Design for Dynamic Stochastic Environments: Myerson Meets Naor , author=. arXiv preprint arXiv:2505.22862 , year=

  2. [2]

    Management Science , volume=

    Design of lotteries and wait-lists for affordable housing allocation , author=. Management Science , volume=. 2020 , publisher=

  3. [3]

    Proceedings of the 22nd ACM Conference on Economics and Computation , pages=

    Optimal queue design , author=. Proceedings of the 22nd ACM Conference on Economics and Computation , pages=

  4. [4]

    Journal of Political Economy , year=

    Optimal Queue Design , author=. Journal of Political Economy , year=

  5. [5]

    Operations Research Letters , volume=

    Regulating an observable M/M/1 queue , author=. Operations Research Letters , volume=. 2016 , publisher=

  6. [6]

    Management science , volume=

    On the advantage of being the first server , author=. Management science , volume=. 1996 , publisher=

  7. [7]

    Operations Research Letters , volume=

    On equilibrium threshold strategies when choosing between observable and unobservable queues , author=. Operations Research Letters , volume=. 2022 , publisher=

  8. [8]

    The Bell Journal of Economics , pages=

    Is the price system or rationing more effective in getting a commodity to those who need it most? , author=. The Bell Journal of Economics , pages=. 1977 , publisher=

Show all 42 references
  1. [9]

    The Journal of Law and Economics , volume=

    A theory of rationing by waiting , author=. The Journal of Law and Economics , volume=. 1974 , publisher=

  2. [10]

    Journal of Health Economics , volume=

    The effect of a private sector on the waiting time in a national health service , author=. Journal of Health Economics , volume=. 1997 , publisher=

  3. [11]

    The American economic review , volume=

    Rationing by waiting lists , author=. The American economic review , volume=. 1984 , publisher=

  4. [12]

    Journal of Health Economics , volume=

    A theory of hospital waiting lists , author=. Journal of Health Economics , volume=. 1993 , publisher=

  5. [13]

    Journal of Public Economics , volume=

    Competition and waiting times in hospital markets , author=. Journal of Public Economics , volume=. 2008 , publisher=

  6. [14]

    Mathematics of Operations Research , volume=

    Optimal provision-after-wait in healthcare , author=. Mathematics of Operations Research , volume=. 2016 , publisher=

  7. [15]

    arXiv preprint arXiv:2401.13812 , year=

    A Characterization of Optimal Queueing Regimes , author=. arXiv preprint arXiv:2401.13812 , year=

  8. [16]

    Manufacturing & Service Operations Management , volume=

    Patient choice in kidney allocation: The role of the queueing discipline , author=. Manufacturing & Service Operations Management , volume=. 2004 , publisher=

  9. [17]

    , author=

    Notes and comments on the optimality of first come last served queues. , author=. Econometrica , volume=

  10. [18]

    American Economic Journal: Microeconomics , volume=

    Dynamic assignment of objects to queuing agents , author=. American Economic Journal: Microeconomics , volume=. 2017 , publisher=

  11. [19]

    Management Science , volume=

    Information design for congested social services: Optimal need-based persuasion , author=. Management Science , volume=. 2023 , publisher=

  12. [20]

    American Economic Review , volume=

    Dynamic matching in overloaded waiting lists , author=. American Economic Review , volume=. 2022 , publisher=

  13. [21]

    Games and Economic Behavior , volume=

    On the efficiency of queueing in dynamic matching markets , author=. Games and Economic Behavior , volume=. 2025 , publisher=

  14. [22]

    Theoretical Economics , volume=

    Queueing to learn , author=. Theoretical Economics , volume=. 2025 , publisher=

  15. [23]

    Handbook of the Economics of Matching , volume=

    Dynamic matching , author=. Handbook of the Economics of Matching , volume=. 2025 , publisher=

  16. [24]

    Theoretical Economics , volume=

    Optimal dynamic matching , author=. Theoretical Economics , volume=. 2020 , publisher=

  17. [25]

    Management Science , volume=

    Optimal service speeds in a competitive environment , author=. Management Science , volume=. 1992 , publisher=

  18. [26]

    2003 , publisher=

    To queue or not to queue: Equilibrium behavior in queueing systems , author=. 2003 , publisher=

  19. [27]

    Operations research , volume=

    Pricing, production, scheduling, and delivery-time competition , author=. Operations research , volume=. 1997 , publisher=

  20. [28]

    2016 , publisher=

    Rational queueing , author=. 2016 , publisher=

  21. [29]

    Queueing Systems , volume=

    Equilibrium customers’ choice between FCFS and random servers , author=. Queueing Systems , volume=. 2009 , publisher=

  22. [30]

    Management Science , volume=

    Competition in service industries with segmented markets , author=. Management Science , volume=. 2009 , publisher=

  23. [31]

    Proceedings of the AAAI conference on artificial intelligence , volume=

    Competing schedulers , author=. Proceedings of the AAAI conference on artificial intelligence , volume=

  24. [32]

    Proceedings of the AAAI Conference on Artificial Intelligence , volume=

    Equilibria of online scheduling algorithms , author=. Proceedings of the AAAI Conference on Artificial Intelligence , volume=

  25. [33]

    Econometrica: journal of the Econometric Society , pages=

    The regulation of queue size by levying tolls , author=. Econometrica: journal of the Econometric Society , pages=. 1969 , publisher=

  26. [34]

    Available at SSRN 5805802 , year=

    When Strategic Customers Meet Strategic Servers: Individual and Social Optimization in Many-Server Queueing Systems , author=. Available at SSRN 5805802 , year=

  27. [35]

    The Annals of Applied Probability , volume=

    On positive Harris recurrence of multiclass queueing networks: a unified approach via fluid limit models , author=. The Annals of Applied Probability , volume=. 1995 , publisher=

  28. [36]

    IEEE Transactions on automatic control , volume=

    Stability and convergence of moments for multiclass queueing networks via fluid limit models , author=. IEEE Transactions on automatic control , volume=. 1995 , publisher=

  29. [37]

    The Annals of Applied Probability , pages=

    State-dependent criteria for convergence of Markov chains , author=. The Annals of Applied Probability , pages=. 1994 , publisher=

  30. [38]

    Carothers, N. L. , title =. 2000 , doi =

  31. [39]

    Kingman, J. F. C. , title =. The Annals of Mathematical Statistics , volume =. 1961 , doi =

  32. [40]

    , title =

    Glynn, Peter W. , title =. Operations Research Letters , volume =. 1985 , doi =

  33. [41]

    Journal of political Economy , volume=

    A theory of oligopoly , author=. Journal of political Economy , volume=. 1964 , publisher=

  34. [42]

    IEEE transactions on Automatic Control , volume=

    A simple dynamic routing problem , author=. IEEE transactions on Automatic Control , volume=. 1980 , publisher=

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.