{"id":"8c0d3dd6-22ed-4166-a1a8-cf022e978781","arxiv_id":"2608.11710","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A strategically reordered \"Ledger\" queue attracts strictly more arrivals than a first-come-first-served competitor, with any work-conserving rule capped at about a 70.7% share.","lead":"A queue can win more customers just by serving people in a cleverer order, even when its waits are longer on average. This paper proves that a \"Ledger\" scheduling rule beats first-come-first-served and can capture a strict majority of arrivals.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2's renewal argument needs finite-mean joint-empty reset times, but Proposition 2 is only backed by Lemma 5, which lifts recurrence from System 1 to the coupled chain without a verified proof.","rationale":"The reader accepted with moderate confidence and flagged positive recurrence as the weakest assumption. My reading agrees that stability is the risk, but the specific gap is more precise: the appendix establishes only the Ledger-FCFS system's recurrence, while the renewal argument needs the joint system to revisit the empty state with finite mean. Lemma 5's citation does not obviously supply this, and positive recurrence of marginals does not in general imply positive recurrence of their coupling. I am not claiming Theorem 2 is false; the concern is a missing proof. A CONDITIONAL verdict is appropriate: the central claim is accepted provided the coupled positive recurrence is supplied or the appeal to Glynn is verified.","tokens_in":32456,"tokens_out":38714,"duration_ms":433893,"concrete_test":"Check whether Lemma 5 actually follows from the cited Glynn (1985): obtain the theorem and verify its hypotheses for the coupled chain (X1,X3), which has state-dependent routing and no product structure. If the cited theorem is inapplicable, replace the one-sentence citation with a direct Lyapunov proof of joint positive recurrence, such as a drift condition for W_epsilon(X1)+W_epsilon(X3) outside a finite set. Without such a derivation, the finite-mean reset times used in Theorem 2 remain unproved.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The paper's central result, Theorem 2, is proved by renewal reward over cycles that begin and end when both the Ledger system (X1) and the FCFS-FCFS comparison system (X3) are empty. For the cycles to be i.i.d. with finite mean, the coupled chain (X1,X3) must be positive recurrent, which is exactly Proposition 2. The proof of Proposition 2, however, is not completed. Lemma 5 asserts that positive recurrence of System 1 and of System 3 implies positive recurrence of the coupled chain, citing Glynn (1985). That implication is not valid for arbitrary couplings and is not shown to hold here. The appendix proves positive recurrence only for System 1; System 3 is stable by Kingman, but the joint transition kernel is not a product kernel, so the two stabilities do not combine. The hypotheses that would make Glynn's result applicable, such as common regeneration times or a regenerative embedding with finite mean cycles, are neither stated nor checked. If the coupled chain is null recurrent or has infinite mean return to the joint-empty state, then E[C1] in the renewal-reward formula need not be finite, and the strict-majority conclusion does not follow from the argument given. This leaves the main theorem's proof incomplete, even if the conjecture is true.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":32736,"tokens_out":29456,"duration_ms":348340,"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":[{"comment":"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.","section":"Section 5.2, Lemma 5 and Proposition 2"},{"comment":"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.","section":"Section 5.2, proof of Theorem 2"}],"minor_comments":[{"comment":"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.","section":"Section 5.2, proof of Lemma 2"},{"comment":"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.","section":"Section 5.2, proof of Theorem 2"},{"comment":"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'.","section":"Section 4.2 and Section 7"},{"comment":"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.","section":"Section 5.4, proof of Theorem 4"},{"comment":"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.","section":"Section 3 and Section 5.5"}],"recommendation":"major_revision","confidential_remarks":"The main theorem is interesting, and the gap in Proposition 2 appears fixable: the authors could prove positive recurrence of the coupled chain directly, for example with a product Lyapunov function or a regeneration argument for the joint-empty state. If they supply such a proof, I would be supportive of acceptance. I would not reject on the basis of the current gap alone, because the rest of the paper is careful and the claim is plausible. However, the positive-recurrence appendix is long and uses nonstandard fluid-limit tools; it may be worth a specialist's second opinion on the supplemental stability argument."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Ledger rule is a genuinely new idea and the paper earns attention: it shows a queue can beat FCFS by scheduling alone, gives clean upper bounds, and constructs a neat equilibrium. But the proof of Theorem 2 currently rests on an unproved assertion about the coupled process, and that has to be fixed before the result is solid.\n\nWhat's good: the Ledger construction is simple and the intuition is right. The coupling in Section 5.2 is elegant—the one-sided device representation works because the Ledger only ever makes queue A look better on the margin. The upper bounds in Theorem 3 are short and transparent. Protected LCFS is a nice equilibrium, and the contrast between commitment and no commitment is worth having. The paper situates itself well in the literature.\n\nWhere it is soft: Proposition 2 is load-bearing and not proved. The renewal-reward argument in Theorem 2 requires the coupled (System 1, System 3) chain to have finite-mean returns to the joint-empty state. The main text says this follows because System 1 is positive recurrent (by the appendix) and System 3 is positive recurrent (Kingman), citing Glynn (1985). But positive recurrence of the marginals does not imply positive recurrence of an arbitrary coupling; the hypotheses of Glynn's result are not stated or checked. The joint chain here is not a product chain, so the two stabilities don't automatically combine. The supplemental appendix proves positive recurrence of System 1 in detail, but that is not the same as the coupled chain. As written, the strict-majority conclusion doesn't follow from their argument. This is a significant gap, though not obviously a fatal one—the claim may well be true, and the apparatus in the appendix might be extendable.\n\nMinor issues: simulations are described but no code or data are shipped, which limits reproducibility of the quantitative claims. The paper also moves quickly past the fact that the full-range stability result lives in a supplemental appendix, which will matter for a referee.\n\nWho should read it: anyone working on queueing competition or market design of service rules. I'd send it to a serious referee but ask them specifically to check the coupling stability argument, and I'd expect major revision. The core idea is too good to desk reject.","headline":"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.","tokens_in":33223,"tokens_out":2662,"would_cite":true,"duration_ms":31130,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60K25","91A10","90B22"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["queueing competition","service rules","First-Come-First-Served","Ledger rule","market share","strategic routing","waiting times","commitment"],"falsifier":"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.","tokens_in":32277,"feed_emoji":"📈","tokens_out":9403,"duration_ms":96915,"temperature":0.7,"pith_summary":"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.","feed_headline":"A queue rule beats FCFS and captures a strict majority","feed_subtitle":"By leaving strategic gaps in its waitlist, a queue can win more demand while making its own customers wait longer.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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%)."],"supporting_citations":[{"why":"establishes positive recurrence of two parallel FCFS queues with shortest-queue routing, used as the baseline system in the coupling.","marker":"Kingman (1961)"},{"why":"supplies the regenerative-structure result that lets the coupled Ledger-FCFS chain inherit positive recurrence from system 1.","marker":"Glynn (1985)"},{"why":"provides the fluid-limit method for proving positive Harris recurrence that underlies the stability argument.","marker":"Dai (1995)"},{"why":"gives the state-dependent Markov-chain criteria used with the fluid-limit approach.","marker":"Meyn and Tweedie (1994)"},{"why":"extends the fluid-limit stability criteria and is cited in the stability discussion.","marker":"Dai and Meyn (1995)"},{"why":"numerically compares FCFS and Random service in a related customer-choice model, serving as the benchmark showing naive rules do not beat FCFS.","marker":"Hassin (2009)"}],"fun_headline_variants":["Ledger rule beats FCFS, captures strict majority demand","Strategic gaps in service order beat FCFS","Beat FCFS: leave gaps in your waitlist to win demand","Queue design trick beats FCFS and wins majority"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Ledger rule beats FCFS, captures strict majority demand","Strategic gaps in service order beat FCFS","Beat FCFS: leave gaps in your waitlist to win demand","Queue design trick beats FCFS and wins majority"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00056,"raw_usage":{"total_tokens":2632,"prompt_tokens":891,"completion_tokens":1741,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":507,"completion_tokens_details":{"reasoning_tokens":1673}},"tokens_in":507,"tokens_out":1741,"duration_ms":15753,"temperature":1.0,"reasoning_tokens":1673,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T00:32:59.756013+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"establishes positive recurrence of two parallel FCFS queues with shortest-queue routing, used as the baseline system in the coupling."},{"cited_title":", title =","cited_arxiv_id":null,"evidence_quote":"supplies the regenerative-structure result that lets the coupled Ledger-FCFS chain inherit positive recurrence from system 1."}],"review_version":1}