Pith. sign in

REVIEW 3 major objections 4 minor 23 references

Strategic Queues with Priority Classes

T0 review · 3 major / 4 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read In a strategic two-class priority queue, low-priority customers follow a single total-queue-length cutoff, and the cutoff has a closed form.

desk verdict The equilibrium characterization is solid and worth citing; the social-optimum section leans on an unproven extension of Hassin's LCFS argument and needs major revision. read the letter →

arxiv 2502.05906 v2 pith:GIPQH4NU submitted 2025-02-09 cs.GT math.PR

Maurizio D'Andrea , Marco Scarsini This is my paper · ORCID
classification cs.GTmath.PR MSC 60K2591A10
keywords M/M/1queuepriorityclassesbalkingrenegingthresholdstrategyMarkovperfectequilibriumsocialoptimumgambler'sruin
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

This paper studies an observable M/M/1 queue in which customers split into two classes, A and B, with A holding priority over B, and every customer may decide whether to join and later whether to renege. The central claim is that the equilibrium is unique and threshold-based: A-customers use the classic Naor threshold $M_A = \lfloor R_A \mu / C_A \rfloor$ and never renege, while B-customers join when the total number in the queue is below a cutoff and renege once that cutoff is exceeded. The B cutoff is either the lower value solving (4.3) or, when $R_B/C_B$ is large enough, $T_B = M_A + V_B$ with $V_B$ given by the closed formula (4.6). The argument works because the two-dimensional state $(n_A,n_B)$ ahead of a tagged B-customer reduces to a one-dimensional gambler's ruin, so service probability and expected waiting time have closed forms. The paper further claims a priority-free social optimum with Naor-style thresholds for both classes and gives a system for the two-planner case.

What carries the argument

The load-bearing object is a birth-and-death process $Y_t$ that counts the number of people ahead of a tagged B-customer, observed only at the epochs when either an A-customer arrives or a service completes. Each step thus rises with probability $\lambda_A/(\lambda_A+\mu)$ and falls with probability $\mu/(\lambda_A+\mu)$, which is exactly a gambler's ruin; because A's arrivals are capped at $M_A$ and B-customers cannot pass one another, the two-dimensional state $(n_A,n_B)$ collapses to the total queue length $n = n_A+n_B$. The gambler's-ruin probability (B.1) and expected duration (B.2) give the tagged customer's expected payoff, and the equilibrium threshold is the largest $n$ for which that payoff is nonnegative even in the worst case $(M_A, n_B)$. This reduction is what turns a dynamic game with balking and reneging into explicit algebraic cutoff formulas.

What would settle it

For the social-optimum claim, compute the truly optimal admission policy by dynamic programming on a small finite state space, for instance with $\mu=1$, $\lambda_A=0.3$, $\lambda_B=0.4$, and $R_A/C_A > R_B/C_B$, and compare it with equations (5.1)--(5.2); any instance where the planner optimally admits an A-customer beyond $M^*_A$ or violates the total-cutoff structure would settle that the LCFS-based optimum is not the true optimum.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is that the equilibrium of a fully strategic priority queue is completely described by three formulas. A-customers are oblivious to B-customers, so they inherit Naor's single-class threshold $M_A = \lfloor R_A \mu / C_A \rfloor$ and never renege. If a B-customer's reward-to-cost ratio is low ($R_B/C_B < E(M_A,0)$), B-customers join only while the total queue length is below the floor of the solution of equation (4.3). If $R_B/C_B \geq E(M_A,0)$, B-customers join whenever $n = n_A + n_B < T_B$ and renege when the total exceeds $T_B$, where $T_B = M_A + V_B$ and $V_B$ is the integer in (4.6). The same gambler's-ruin machinery yields the semi-strategic threshold (3.5), and the paper uses Hassin's last-come-first-served device to propose social-optimum thresholds (5.1)--(5.2) and a trapezoid first-exit system for the two-planner case.

Load-bearing premise

The social-optimum section's thresholds hold only if the last-come-first-served trick, which makes an individual's optimal decision socially optimal in a single class, still works when two classes with different rewards and costs share the queue; the paper asserts this extension rather than proving it.

Editorial extensions

If this is right

  • A-customers' equilibrium strategy is exactly Naor's single-class threshold, so adding a lower-priority class does not change high-priority admission or waiting behavior.
  • B-customers' equilibrium decisions depend on the total queue length $n = n_A + n_B$, not on how many of those customers are A or B; the cutoff is $T_B = M_A + V_B$ in the high-reward regime and the solution of (4.3) in the low-reward regime.
  • A B-customer who has joined reneges as soon as the total queue length exceeds the threshold, so abandonment is predictable from a single observable.
  • A social planner without priority constraints who values A more per unit cost will admit at most the Naor optimum $M^*_A$ A-customers and cap total admissions by the Naor threshold computed with combined traffic load $\rho=(\lambda_A+\lambda_B)/\mu$.
  • With one planner per class, the A-planner's threshold is again the Naor optimum, while the B-planner's problem becomes the first-exit problem of a genuinely two-dimensional random walk from a trapezoid.

Reading between the lines

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

  • The composition-insensitivity of B behavior is directly testable: in a laboratory or simulated queue, fixing total length and varying the A/B split should leave low-priority join and renege decisions unchanged.
  • Because the B threshold is driven only by $\rho_A$ and $M_A$, a queue manager could estimate admission cutoffs from high-priority traffic statistics without ever measuring the low-priority arrival process.
  • The same gambler's-ruin reduction is unlikely to survive three or more priority classes, since each additional class adds a boundary; the paper's own conclusion says this explicitly, so the closed-form equilibrium thresholds should be read as a two-class phenomenon.
  • The Section 5 planner formulas rest on the asserted LCFS equivalence; turning that assertion into a proof, or finding a counterexample, is the natural next step.
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

3 major / 4 minor

Summary. The paper studies an observable M/M/1 queue with two customer classes, A and B, where A-customers have priority over B-customers. Customers may balk upon arrival and may renege while waiting. The authors first analyze a semi-strategic model in which only B-customers are strategic, obtaining a threshold M_B^eq for B-customers. They then analyze the fully strategic model, claiming that A-customers follow the Naor threshold M_A = floor(R_A mu / C_A), while B-customers use a threshold T_B = M_A + V_B on the total number of customers in the system, with V_B given explicitly in Eq. (4.6). The paper then considers a globally optimizing social planner without priority constraints and derives thresholds given in Eqs. (5.1)-(5.2), and finally sketches a class-wise optimization problem in Section 6.

Significance. If the equilibrium characterization is fully correct, it is a valuable and elegant contribution: it reduces a seemingly two-dimensional strategic queueing problem to a one-dimensional random walk and gives closed-form equilibrium thresholds for both classes. The derivation is parameter-free in the sense that all quantities are expressed in terms of the primitives (arrival rates, rewards, costs, service rate). The semi-strategic and fully strategic B-threshold calculations are internally consistent, and the monotonicity claim in Claim 4.3 is checked. However, the social-optimum sections are not developed with the same rigor. The global-optimum result in Section 5 rests on an unproved extension of Hassin's LCFS equivalence to a heterogeneous two-class system, and Section 6 stops at a set of linear equations without proving the claimed optimal-strategy characterization. Since the abstract advertises a comparison of equilibrium and social optimum, this gap is load-bearing.

major comments (3)
  1. [Theorem 4.2, paragraphs after Eq. (4.6)] The proof establishes that B-customers join when n < T_B, but it does not prove that they balk when n >= T_B. The threshold V_B is derived from the worst-case state (M_A, n_B), and the text then asserts that 'the number of customers in the system cannot exceed M_A + V_B'. For a state with total n = T_B but n_A < M_A, the queue has more B-customers and fewer A-customers than the worst-case state, so the payoff comparison is not immediate; the assertion requires a monotonicity argument that is not supplied. This is a load-bearing step for the claimed unique threshold equilibrium.
  2. [Section 5, Eqs. (5.1)-(5.2)] The global social optimum is derived by asserting that the planner favors the class with higher R_theta / C_theta and then invoking Hassin's LCFS technique. The sentence 'This is the technique used by Hassin (1985)' is not a proof that the technique extends to a two-class system with different rewards and costs. In particular, Eq. (5.1) contains no B-dependent terms, yet admitting an A-customer can delay B-customers and thereby change the social cost of an A admission. The paper needs either a proof of the claimed extension or a statement of the additional assumptions under which Eqs. (5.1)-(5.2) are valid.
  3. [Section 6, first two paragraphs and Eqs. (6.4)-(6.6)] The claim that Belinda-Paris's optimal strategy 'coincides with the equilibrium strategy in a LCFS regime' is asserted without proof, and the claim that for R_B/C_B < R_A/C_A this strategy coincides with the global planner's strategy is also asserted without proof. The subsequent analysis stops at linear systems for the hitting probabilities eta(i,j) and expected times kappa(i,j); it does not solve these systems, does not give a threshold characterization, and does not state a theorem for the B-planner's optimum. As written, Section 6 does not deliver a complete result.
minor comments (4)
  1. [Abstract and Section 4.1] There are several typos: 'first-co me' in the abstract, 'equilibroium threshold' in Section 4.1, and 'does not case about B-customers' in Remark 4.4.
  2. [Theorem 3.2 proof] The proof states that the function gamma is 'unbounded and increasing' but does not show the monotonicity; a one-line difference argument would make this self-contained.
  3. [Section 5, paragraph after Eq. (5.2)] The sentence 'If n_A < M_A^*' should specify what happens when n_A >= M_A^*, since the planner's admission rule for A-customers is part of the claimed optimum.
  4. [Figures 1 and 2] The axes in the random-walk figures are not labeled; labeling n_A, n_B, M_A, and V_B directly in the figures would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the Section 4 equilibrium is derived from primitives; Section 5's LCFS step is an unproven extension, not a circular reduction.

full rationale

The paper's central equilibrium characterization is self-contained. Theorem 4.2 defines TB = MA + VB, with VB in Eq. (4.6) obtained by solving RB - CB E(MA,nB) >= 0 at the worst-case state (MA,nB), and then independently verified for all states n < TB through the ruin-probability formulas (4.17)-(4.20) and Claim 4.3; no parameter is fitted to a target quantity, and the threshold is not assumed rather than derived. Eq. (4.1) for A-customers is the classical Naor threshold, and the random-walk results in the appendices use standard external theorems (Ethier, Norris). The only potentially load-bearing external import is Hassin's LCFS argument used in Section 5 to assert that the global planner admits at most MA* A-customers satisfying the single-class equation (5.1), with the B-threshold given by (5.2) under aggregate rho. That step is asserted rather than proved for the heterogeneous two-class case, and it could be a soundness or correctness gap, but it is not a circular reduction: the paper does not define the social optimum in terms of those equations, nor does it fit parameters to make the conclusion come out. The self-citations (Scarsini and Shmaya 2024a,b) appear only in the literature review and are not load-bearing for any theorem. No quotation from the paper exhibits a derivation that reduces to its own inputs, so no specific circular step can be identified.

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

The central claims rest on standard queueing and Markov-chain tools plus a few modeling simplifications. The most fragile input is the unproven extension of Hassin's LCFS equivalence in Section 5. No new particles, forces, or entities are postulated.

assumptions (5)
  • domain assumption Reneging is allowed only for B-customers; A-customers never renege because A arrivals never worsen their position.
    Section 2.2 states 'only B-customers renege because, unlike A-customers, their position in the queue can get worse with the arrival of higher-priority customers.' This is a modeling restriction that simplifies the A-side to Naor's model.
  • domain assumption Hassin's LCFS equivalence applies to the two-class social planner problem without priority constraints.
    Section 5 invokes Hassin (1985) to justify the social-optimum thresholds (5.1)-(5.2); the extension to heterogeneous classes with different rewards and costs is asserted, not proved.
  • domain assumption The process of customers ahead of a tagged B-customer is a birth-death random walk with up-rate lambda_A and down-rate mu, independent of B arrivals.
    Section 2.3 models the queue as seen by a tagged B-customer; this ignores the effect of B arrivals on the tagged customer's position, which is valid only if new B's join behind the tagged customer and do not overtake.
  • standard math Standard gambler's ruin and Markov chain hitting-time results (Ethier 2010; Norris 1997) are used for all hitting probabilities and expected times.
    Appendix B and C rely on these external theorems.
  • domain assumption Stability: in the semi-strategic model, mu is greater than lambda_A; the fully strategic model has finite state space due to thresholds, so no stability condition is stated.
    Section 3 says 'to guarantee stability of the system, we assume that mu is greater than lambda_A'; the fully strategic model implicitly relies on finite thresholds MA and TB to bound the state space.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Strategic Queues with Priority Classes." pith.science (2026). https://pith.science/paper/GIPQH4NU

@misc{pith2026250205906,
  author       = {Pith},
  title        = {Pith review of: Strategic Queues with Priority Classes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GIPQH4NU}},
  note         = {Machine review of arXiv:2502.05906}
}
abstract

We consider a strategic M/M/1 queueing model under a first-come-first-served regime, where customers are split into two classes and class $A$ has priority over class $B$. Customers can decide whether to join the queue or balk, and, in case they have joined the queue, whether and when to renege. We study the equilibrium strategies and compare the equilibrium outcome and the social optimum in the two cases where the social optimum is or is not constrained by priority.

Figures

Figures reproduced from arXiv: 2502.05906 by the authors.

Figure 1
Figure 1. Random-walk representation of a B-customer strategy Then, by Theorem B.2, Eb(nA, nB) =    (n + 1 − VB) [PITH_FULL_IMAGE:figures/full_fig_p013_1.png] view at source ↗
Figure 2
Figure 2. Random-walk representation of a B-planner strategy As shown in [PITH_FULL_IMAGE:figures/full_fig_p017_2.png] view at source ↗
Figure 3
Figure 3. Random-walk in a rectangle Lemma C.2. Consider the random walk in [PITH_FULL_IMAGE:figures/full_fig_p023_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Bounded Random-walk Then, by Theorem C.1, we have: hi =    0 for i = 0, 1 + λA λA + µ hi+1 + µ λA + µ hi−1 for 0 < i < L, 1 + λA λA + µ hMA + µ λA + µ hMA−1 for i = L. (C.7) As a consequence, hL = λA + µ µ + hL−1 (C.8) and, for every 0 < i < L, hi − hi−1 = λ…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

  1. [1]

    and Yechiali, U

    Adiri, I. and Yechiali, U. (1974). Optimal priority-purcha sing and pricing decisions in nonmonopoly and monopoly queues. Oper. Res., 22(5):1051–1066. Afèche, P. and Sarhangian, V. (2015). Rational abandonment from priority queues: Equilibrium strategy and pricing implications. Technical report, Columbia Busi ness School Research Paper

    work page 1974

  2. [2]

    Optimal Queue Design

    Che, Y.-K. and Tercieux, O. (2024). Optimal queue design. Te chnical report, arXiv 2307.07746

    work page Pith review arXiv 2024

  3. [3]

    and Kulkarni, V

    Chen, F. and Kulkarni, V. G. (2006). Admission control in the presence of priorities: a sample path approach. In Stochastic Processes, Optimization, and Control Theory: Ap plications in Financial Engineering, Queueing Networks, and Manufacturing Systems , pages 73–95. Springer, New York

    work page 2006

  4. [4]

    and Kulkarni, V

    Chen, F. and Kulkarni, V. G. (2007). Individual, class-base d, and social optimal admission policies in two-priority queues. Stoch. Models, 23(1):97–127

    work page 2007

  5. [5]

    Cripps, M. W. and Thomas, C. D. (2019). Strategic experiment ation in queues. Theor. Econ., 14(2):647–708

    work page 2019

  6. [6]

    Ethier, S. N. (2010). The Doctrine of Chances: Probabilistic Aspects of Gambling . Probability and Its Applications. Springer

    work page 2010

  7. [7]

    Hassin, R. (1985). On the optimality of first come last served queues. Econometrica, 53(1):201–202

    work page 1985

  8. [8]

    Hassin, R. (2016). Rational Queueing . CRC Press, Boca Raton, FL

    work page 2016

Show all 23 references
  1. [9]

    and Haviv, M

    Hassin, R. and Haviv, M. (1997). Equilibrium threshold stra tegies: The case of queues with priorities. Oper. Res., 45(6):966–973

    1997

  2. [10]

    and Haviv, M

    Hassin, R. and Haviv, M. (2003). To Queue or Not to Queue: Equilibrium Behavior in Queueing Sys tems. Kluwer Academic Publishers, Boston, MA

    2003

  3. [11]

    and Haviv, M

    Hassin, R. and Haviv, M. (2006). Who should be given priority in a queue? Oper. Res. Lett., 34(2):191–198. 28

    2006

  4. [12]

    and Oz, B

    Haviv, M. and Oz, B. (2016). Regulating an observable M/M/1 q ueue. Oper. Res. Lett. , 44(2):196–198

    2016

  5. [13]

    and Oz, B

    Haviv, M. and Oz, B. (2018). Social cost of deviation: new and old results on optimal customer behavior in queues. Queueing Models Service Management , 1(2):31–58

    2018

  6. [14]

    and Ravner, L

    Haviv, M. and Ravner, L. (2016). Strategic bidding in an accu mulating priority queue: equilibrium analysis. Ann. Oper. Res. , 244(2):505–523

    2016

  7. [15]

    Margaria, C. (2024). Queueing to learn. Theor. Econ., page forthcoming

    2024

  8. [16]

    Naor, P. (1969). The regulation of queue size by levying toll s. Econometrica, 37(1):15–24

    1969

  9. [17]

    Norris, J. R. (1997). Markov Chains . Cambridge Series in Statistical and Probabilistic Mathem atics. Cam- bridge University Press

    1997

  10. [18]

    Rastpour, A., Ingolfsson, A., and Sandı kçı, B. (2022). Algo rithms for queueing systems with reneging and priorities modeled as quasi-birth-death processes. INFORMS J. Comput. , 34(3):1693–1710

    2022

  11. [19]

    and Shmaya, E

    Scarsini, M. and Shmaya, E. (2024a). A characterization of o ptimal queueing regimes. Technical report, arXiv 2401.13812

    2024 arXiv

  12. [20]

    Wang, C.-L. (2016). On socially optimal queue length. Management Sci. , 62(3):899–903

    2016

  13. [21]

    Wang, J., Baron, O., and Scheller-Wolf, A. (2015). M/M/c queue with two priority classes. Oper. Res. , 63(3):733–749

    2015

  14. [22]

    Xu, B., Xu, X., and Wang, X. (2016). Optimal balking strategi es for high-priority customers in M/G/1 queues with 2 classes of customers. J. Appl. Math. Comput. , 51(1-2):623–642

    2016

  15. [23]

    Xu, B., Xu, X., and Yao, Z. (2019). Equilibrium and optimal ba lking strategies for low-priority customers in the M/G/1 queue with two classes of customers and preemptive priority . J. Ind. Manag. Optim. , 15(4):1599–1615. 29

    2019

Pith tools

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