{"id":"8c819e8e-d0fc-4d76-a051-27ab74d7669f","arxiv_id":"2502.08898","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"With a one-packet buffer at each server, no-regret learning queues keep a strategic queueing system stable when total service capacity exceeds three times total arrival rate, and at least double capacity is necessary.","lead":"This paper proves that in a queueing network where routers learn which servers to use, giving each server a one-packet buffer lets the network stay stable with only about three times the capacity needed under central coordination. It also shows by example that at least double capacity is necessary, and it presents simulations of the learning dynamics.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3's clearing bound ignores the model's uniform tie-breaking: with multiple queues sending to an empty server each is accepted with probability 1/n, so no-regret does not force a (1/2−δ)T decrease and Theorem 1's proof collapses.","rationale":"Reader and I concur. I read the model carefully: Step 2(ii) says the server accepts one packet chosen uniformly at random among all received packets. This is the exact point where the proof of Lemma 3 overcounts. The no-regret condition is a lower bound on the learner's cumulative reward relative to the best fixed action's cumulative reward in the realized environment. If several queues target the same empty server, the best fixed action's reward is not 1 per empty step; it is the queue's probability of being selected among all packets that arrive. The proof never upper-bounds the number of contenders, and the theorem's assumptions do not control it. The potential proof needs a linear decrease in every case: Lemma 2 covers the all-buffers-full case, Lemma 3 covers the open-server case. With Lemma 3's bound wrong, the factor-three capacity condition has no role in the open-server case, so the theorem is unsupported. This is internal inconsistency with the model, not a disagreement with outside consensus. The simulations are not affected by the proof gap, but they do not establish the uniform-in-time expected bound claimed in Theorem 1. A repaired proof would need either a contention-aware no-regret benchmark or a much stronger per-queue arrival condition; neither appears in the manuscript. I therefore keep the reader's rejection unchanged.","tokens_in":12045,"tokens_out":10514,"duration_ms":119370,"concrete_test":"Analytic re-derivation: in Lemma 3, replace the sentence 'by no-regret Condition 3 it clears at least (1/2−δ)T' with the model's actual reward rule: if k_t queues send to the empty server at step t, the reward for choosing it is 1/k_t. Check whether the proof still yields a lower bound of (1/2 − λ_i − 2δ)T. If the correct worst-case bound is instead (1/n − λ_i − 2δ)T, then for n≥3 and λ_i=0.4 the claimed decrease becomes negative and Lemma 3 fails. This can be verified by a 3-queue/1-contended-server experiment with all queues using EXP3: record the empty-server acceptance rate when the queue sends; unless it equals 1 in every contended step, the contention term is real and the lemma's accounting is wrong.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The main theorem rests on the potential argument in the proof of Theorem 1. The second case ('some server's buffer is empty more than half the period') uses Lemma 3 to conclude that a large queue i clears at least (1/2−δ)T packets in a T-period, giving the needed Ω(T) potential drop. The first paragraph of Lemma 3 says: 'If the queue has packets in every step in the window, by the no-regret Condition 3, it clears at least (1/2−δ)T.' This is the load-bearing step. Condition 3 only bounds regret with respect to the best fixed server's realized reward. Under the model's step 2(ii), a server with an empty buffer does not accept every packet sent to it: it chooses uniformly among all packets that arrive at that server. If n queues send to the same empty server, each has reward 1/n in that step. Therefore the benchmark reward for 'always send to the empty server' is at most (number of empty steps)/(number of competing queues), not the number of empty steps. No-regret then only implies a clearing rate of about 1/n times the empty-server steps, not 1/2 per step. The theorem's assumptions only require λ_i<1/2; when n≥3 a queue with λ_i between 1/(2n) and 1/2 can have negative drift even if the lemma's premise holds. The factor 3 in total capacity is independent of n and never compensates for this per-queue contention factor. Because the open-server case supplies one of only two sources of Ω(T) potential decrease, the proof of Theorem 1 is incomplete; the central stability claim is not established by the submitted argument.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies a repeated game between learning queues and servers with single-packet buffers. In each step, each nonempty queue sends one packet to a server; each server with an empty buffer accepts one of the packets arriving at it, chosen uniformly at random, and then attempts service. The main result (Theorem 1) claims that if each queue's arrival rate is below 1/2, the total arrival rate is below one third of the total service rate, and every queue uses a learning algorithm with high-probability sublinear regret, then the expected total number of packets in the system is uniformly bounded in time. The proof uses a potential function over T-step periods, with two cases: all servers busy more than half the period, or some server empty more than half the period. The paper also gives a lower-bound example requiring a factor-2 capacity margin (Theorem 3) and presents EXP3 simulations suggesting that systems remain stable at capacity ratios above 1/2.","tokens_in":12379,"tokens_out":16712,"duration_ms":168625,"significance":"If the main theorem were correct, it would be a substantial advance over the buffer-free model of Gaitonde and Tardos: a single-slot server buffer would remove the need for timestamps and priorities and reduce the required capacity over-coordination factor from 'hugely increased' to 3. The lower-bound example and the simulation study are useful first steps and give the reader a concrete picture of the threshold behavior. However, the central proof rests on a misapplication of the no-regret condition, so the theoretical contribution is not established in the present form.","major_comments":[{"comment":"The first paragraph of Lemma 3 states that if a queue has packets in every step of the window, Condition 3 implies it clears at least (1/2 - δ)T packets whenever some server's buffer is empty more than half the period. This ignores the model's step 2(ii): an empty server accepts one packet uniformly at random among all packets that arrive at it. If n queues send to that server on an empty step, each queue's expected reward for that step is 1/n, not 1. Consequently, the realized reward of the benchmark action 'always send to this server' is at most (#empty steps)/(#contending queues), not #empty steps, and no-regret only forces a clearing rate of roughly 1/n of the empty-server steps. The theorem's assumptions allow λ_i between 1/(2n) and 1/2, so the claimed (1/2 - λ_i - 2δ)T decrease can be negative even when the lemma's premise holds. Since the open-server case is one of only two sources of the Ω(T) potential drop in the proof of Theorem 1, this invalidates the main stability proof.","section":"Lemma 3"},{"comment":"Condition 3 and Lemma 5 presuppose a well-defined notion of regret with a high-probability guarantee, but the paper never specifies the counterfactual rewards of actions not chosen. In this model, if a queue had played a different action in earlier steps, the servers' buffer states would have evolved differently, so the reward of an unchosen server is not defined by the observed history. Standard bandit algorithms such as EXP3.P.1 guarantee regret only when rewards are independent of the player's own actions; that assumption is violated here because a queue's past choices determine whether a server is busy when the queue returns to it. Until a precise regret benchmark is given and an algorithm satisfying Condition 3 is exhibited under that benchmark, Lemma 5 is an assumption rather than a proved statement, and the theorem's hypothesis 'low regret with high probability' is not known to be instantiable.","section":"Condition 3 / Lemma 5"},{"comment":"The second half of Lemma 3 uses the quantity I, 'the number of steps queue i and the server were empty,' but Lemma 3's premise only asserts existence of some server that is empty more than half the steps; the proof does not show that this server is the one queue i sends to, nor that queue i's sends are the only ones contending for it. The inequality N'_i ≤ ... and the resulting potential decrease for queues with at least T packets therefore inherit the same unsupported clearing bound as the first paragraph. The proof would need an aggregate argument over all queues' no-regret guarantees rather than a per-queue bound against an unspecified empty server.","section":"Lemma 3, second case"}],"minor_comments":[{"comment":"In the paragraph after Theorem 2, 'the change in this potential satisfies the conditions of Theorem 1' should refer to Theorem 2.","section":"Section 3"},{"comment":"The line 'F or any constants δ >0 and η >0' has a missing space: it should read 'For any constants...'.","section":"Section 3, Lemma 4"},{"comment":"The sentence 'Assume that the server chooses a uniform random server at each step' should read 'the queue chooses a uniform random server at each step'.","section":"Theorem 3 proof"},{"comment":"The quantity 23/24 is an upper bound on the expected number of packets accepted per step, but the text calls it 'maximum expected service rate'; please clarify the distinction between acceptance into a buffer and service completion.","section":"Lemma 1 proof"},{"comment":"The two entries for Auer, Cesa-Bianchi, Freund, and Schapire (2002) are the same paper listed twice; please consolidate them.","section":"References"},{"comment":"The claim that dynamics 'converge in last iterate (up to a small noise level)' is informal; please state the convergence notion precisely and quantify the noise level.","section":"Section 4.3"}],"recommendation":"reject","confidential_remarks":"The flaw in Lemma 3 is not a minor gap: the clearing bound is false under the model's uniform tie-breaking rule, so the main theorem is unproven as written. I recommend rejection, although a substantially reworked proof that handles contention among queues in the open-server case, together with a precise regret benchmark, could change my view. The experimental and lower-bound parts are not enough to rescue the central claim in its current form."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nI read the queuing paper. The buffer-of-one extension is a natural and well-motivated variant of the Gaitonde-Tardos model, and the paper does two useful things: it identifies a new stability question and proves a factor-2 lower bound. The lower-bound example is neat, and the simulations are informative even if they don't substitute for theory.\n\nThe problem is the proof of Theorem 1. The argument splits into two cases; the second case, where some server's buffer is empty more than half the time, relies on Lemma 3. That lemma claims that a queue with packets throughout the window clears at least (1/2−δ)T packets by no-regret. But the model's step 2(ii) says that when several packets arrive at an empty server, the server accepts one uniformly at random. So a queue sending to an empty server is not guaranteed acceptance; its reward is 1/(number of competing senders). No-regret only forces the queue to match the best fixed server's realized reward, which is far below 1/2 per step under contention. The lemma effectively assumes the queue is the only one sending to that server. Since Theorem 1's stability bound depends on this Ω(T) drop, the main result is not established as written.\n\nI don't see an easy patch within the present framework. The per-queue condition λ_i < 1/2 would need to be strengthened, perhaps by a factor involving n, and it's unclear whether the factor-3 capacity condition can be preserved. The lower bound remains intact, and the theorem may be true with a different constant, but the current manuscript doesn't prove it.\n\nWho is this for? People working on learning in games with carryover effects and on queueing games. It deserves a serious referee: the model is worth discussing, the lower bound is interesting, and the flaw is a specific technical point that might be repairable. I would not cite it in its present form. For a reading group, it could be a good case study in how contention breaks no-regret arguments.\n\nMy recommendation: send it to peer review with a clear request to fix Lemma 3 or restructure the proof. The authors are honest about the gap between the factor of 3 and the lower bound of 2, but the current proof does not close that gap.","headline":"Original buffer-of-one model with an interesting lower bound, but the main proof of stability has a load-bearing gap in Lemma 3 that ignores contention at empty servers.","tokens_in":12915,"tokens_out":2491,"would_cite":false,"duration_ms":26011,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68M20","91A26","60K25"],"pacs":[],"model":"deepseek-v4-flash","headline":"A one-packet server buffer keeps no-regret learning queues stable under a constant-factor capacity margin.","keywords":["strategic queuing systems","no-regret learning","small buffers","stability","carryover effects","multi-agent learning","queueing games"],"falsifier":"Run 1,000 simulations of, say, n = 10 queues with arrival rates near 1/2 sending to a single server of capacity μ near 1 with a one-packet buffer, under EXP3, and record the maximum queue length over T = 50,000. If any queue's length grows linearly in T even though total arrivals are below (1/3)μ, Lemma 3's clearing-rate assumption is violated; conversely, if all queues stay bounded in that regime, the contention concern does not bite. The same experiment with n = 2 and n = 100 isolates whether the gap is due to contention.","tokens_in":11855,"feed_emoji":"📦","tokens_out":6159,"duration_ms":57473,"temperature":0.7,"pith_summary":"This paper asks whether a network of selfish routers, each running a simple no-regret learning rule, can keep packet queues bounded when servers have tiny buffers. Its main result is that it can: if every arrival rate is below 1/2 and the total arrival rate is below one-third of the total service capacity, then with a single-packet buffer at each server the expected number of packets in the system stays bounded by a time-independent constant, and no timestamps or priority rules are needed. A lower-bound example shows that a factor of 2 in capacity is necessary for such a guarantee, leaving a gap between 2 and 3. Simulations indicate that in typical randomized systems the practical transition from stable to unstable behavior occurs above 1/2 and below 1, better than the worst-case factor of 3.","feed_headline":"Small server buffers make learning routers stable at 3x capacity","feed_subtitle":"No-regret queues with one-packet server buffers keep the network bounded, with no timestamps needed.","key_machinery":"The load-bearing object is a potential function over T-step periods, Φ = Σ_i (N_i − (1/2 λ_i + 2δ)T)_+, where N_i is queue i's packet count at the start of the period and x_+ = max(x, 0). The proof shows that when Φ is large, a good period (empirical arrivals, service completions, and regrets all within δT of their expectations) makes Φ decrease by Ω(T), while a bad period can only increase it by nT and has probability at most η(m+2n). A stochastic drift theorem for sequences with bounded moments then converts the negative drift of Φ into a uniform-in-time bound on its moments. Within a good period, the argument splits into two cases: all servers busy more than half the time (total clearing dominates total arrivals), or some server empty more than half the time (no-regret learning forces a long queue to shrink). The one-packet server buffer is what lets a queue exploit low-capacity servers by sending to them rarely.","core_discovery":"The central claim is Theorem 1: in a repeated game with n queues and m servers, if each queue uses any learning rule with sublinear regret that holds with high probability, if λ_i < 1/2 for every queue, and if Σ_i λ_i < (1/3) Σ_j μ_j, then the expected total number of packets waiting in the system is bounded by a constant at all times, despite uncoordinated selfish choices and servers that pick uniformly among simultaneously arriving packets. The same conclusion does not require timestamps or priority for older packets, which the prior no-buffer model needed. The proof works period by period: with a long enough window, either every server is busy more than half the time, in which case total service exceeds total arrivals, or some server's buffer is empty more than half the time, in which case the no-regret guarantee forces any queue with many packets to clear packets at a positive linear rate. A constructed example with one queue and many low-capacity servers shows that a total capacity of at least twice the arrival rate is necessary for a no-regret outcome to be stable, so the sufficient factor of 3 is not tight.","pith_inferences":["If the factor-3 bound is not tight, a natural next step is to construct no-regret systems stable at every capacity ratio in (2,3); the paper's lower-bound technique with round-robin sending to equal low-capacity servers is a starting point.","The proof's 'empty server' case implicitly treats a queue's packet as accepted whenever it reaches an empty buffer; in systems where n queues all target the same empty server, each attempt succeeds with probability 1/n, so the per-queue clearing rate underlying Lemma 3 may need a contention-aware version.","The buffer-as-smoothing idea suggests a testable hypothesis for other carryover games: mechanisms that let an agent commit a resource now and receive the outcome later should improve the stability of no-regret learning dynamics in budgeted auctions and investment settings.","One could extend simulations to buffer sizes b > 1; if stability thresholds fall monotonically with b, the single-packet result is just the endpoint of a continuum."],"forward_implications":["Small, realistic buffers (one packet per server) turn a system that previously needed timestamps and large capacity reserves into one stable under a constant-factor capacity margin.","Any queue learning algorithm with high-probability sublinear regret, bandit or full information, inherits the stability guarantee; EXP3.P is an explicit example.","A capacity ratio of at least 2 is necessary in the worst case, so there is a concrete gap between the necessary lower bound and the sufficient factor of 3.","In randomized simulations of 5-queue, 6-server systems, the stable-to-unstable transition occurs above arriving-load 1/2 and below 1, suggesting typical systems clear packets much better than the worst-case bound.","Because buffers smooth the payoff stream across rounds, stability can be achieved without priority to older packets, which the no-buffer model could not avoid."],"supporting_citations":[{"why":"Defines the no-buffer strategic queueing model and shows that timestamps plus large capacity are needed there; this paper's buffer model is the direct extension.","marker":"Gaitonde and Tardos [2020, 2023]"},{"why":"Supplies the moment-condition drift theorem that converts expected negative drift of the potential into a uniform bound on moments.","marker":"Pemantle and Rosenthal [1999]"},{"why":"Provides EXP3.P, the concrete bandit algorithm used to instantiate the high-probability no-regret condition required by Theorem 1.","marker":"Auer et al. [2002a]"},{"why":"Gives the textbook stability condition for a single queue and server that frames the capacity comparison.","marker":"Shortle et al. [2018]"}],"fun_headline_variants":["Tiny buffers stabilize selfish routing at 3x capacity","Learning routers stable with just small server buffers","One-packet buffers make queuing games stable","Small buffers cut capacity waste in learning queues","No-regret queues stay bounded with small buffers"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof leans on a step where a queue that keeps sending to a server whose buffer is empty is assumed to clear about half its packets, even though if many queues target that same server each individual attempt is accepted with probability 1/n.","fun_headline_variants_meta":{"raw":{"variants":["Tiny buffers stabilize selfish routing at 3x capacity","Learning routers stable with just small server buffers","One-packet buffers make queuing games stable","Small buffers cut capacity waste in learning queues","No-regret queues stay bounded with small buffers"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000205,"raw_usage":{"total_tokens":1475,"prompt_tokens":1108,"completion_tokens":367,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":724,"completion_tokens_details":{"reasoning_tokens":296}},"tokens_in":724,"tokens_out":367,"duration_ms":4312,"temperature":1.0,"reasoning_tokens":296,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T23:19:00.024265+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run 1,000 simulations of, say, n = 10 queues with arrival rates near 1/2 sending to a single server of capacity μ near 1 with a one-packet buffer, under EXP3, and record the maximum queue length over T = 50,000. If any queue's length grows linearly in T even though total arrivals are below (1/3)μ, Lemma 3's clearing-rate assumption is violated; conversely, if all queues stay bounded in that regime, the contention concern does not bite. The same experiment with n = 2 and n = 100 isolates whether the gap is due to contention.","supporting_citations":[{"cited_title":"Stability and learning in strategic queuing systems","cited_arxiv_id":null,"evidence_quote":"Defines the no-buffer strategic queueing model and shows that timestamps plus large capacity are needed there; this paper's buffer model is the direct extension."},{"cited_title":"Moment conditions for a sequence with negative drift to be uniformly bounded in L ^r","cited_arxiv_id":null,"evidence_quote":"Supplies the moment-condition drift theorem that converts expected negative drift of the potential into a uniform bound on moments."},{"cited_title":"Fundamentals of Queueing Theory","cited_arxiv_id":null,"evidence_quote":"Gives the textbook stability condition for a single queue and server that frames the capacity comparison."}],"review_version":1}