Pith. sign in

REVIEW 2 major objections 5 minor 26 references

Strategic arrivals to a queue with service rate uncertainty

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

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

Pith's one-line read In a queue game, beliefs split arrivals into separate time windows.

desk verdict Genuine first step on heterogeneous-belief arrival games with a solid fluid classification and a clear but incompletely proven discrete-time existence story; the ABM/FR comparison in Section 6.2 is not actually computing a two-type equilibrium. read the letter →

arxiv 1908.08322 v3 pith:7GMN2RWV submitted 2019-08-22 math.PR cs.GT

Liron Ravner , Yutaka Sakuma This is my paper · ORCID
classification math.PRcs.GT MSC 60K2591A1091A80
keywords bottleneckqueuestrategicarrivalsNashequilibriumheterogeneousbeliefsservicerateuncertaintyfluidapproximationdiscrete-timeagent-basedlearning
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 when customers choose to arrive at a single-server queue when pessimistic and optimistic customers disagree about the service speed. It tries to establish that, in Nash equilibrium, the two belief types generically arrive during different—often disjoint—time intervals, rather than mixing together. The argument is carried by an explicit fluid-model solution for large systems and by a discrete-time best-response algorithm for general service-time distributions. If the paper is right, bottlenecks with heterogeneous beliefs produce predictable arrival segregation, and mean waiting time grows with the variability of service times.

What carries the argument

The machinery is a pair of equilibrium arrival distributions $(F_a,F_b)$ whose supports must satisfy equal-expected-waiting conditions, together with two calculation engines: the fluid-model queue length $q_i(t)=\sum_j\lambda_jF_j(t)-\mu_it$ that yields the explicit Theorem 2 solutions, and the discrete-time mean-workload recursion of Lemma 4, which produces the fixed-point equation (21) that Algorithm 2 solves by iterated best response. The separation of types follows from comparing the two beliefs' expected queue lengths: type-a (pessimistic) customers always face a longer queue than type-b customers for the same arrival profile.

What would settle it

Search the continuous-time exponential model for an equilibrium in which both types' arrival densities are positive on the same interval of times; finding one refutes Conjecture 1 and the uniqueness consequence drawn from it.

Watch

Extended reading notes

Core claim

The central claim is that the bottleneck arrival game with a Poisson population and two belief types—one expecting slow service, one fast—has symmetric Nash equilibria in which the types' arrival distributions are separated in time. For exponential service times the paper characterizes equilibrium structure (Theorem 1) and conjectures no interior overlap (Conjecture 1). In the fluid limit, Theorem 2 gives explicit equilibrium densities for all parameter regimes, including cases where optimistic customers expect zero delay while pessimistic ones face a queue, and cases with multiple equilibria. For general service times, Lemma 5 reduces equilibrium to a system of fixed-point equations, and Algorithm 2 computes equilibria by iterated best response; numerical results show the same separated pattern as the fluid solution. The paper also shows that mean waiting time increases with the coefficient of variation of service time, and that a learning agent-based model approximates the fully informed equilibrium better than the bounded-rationality equilibrium.

Load-bearing premise

The argument that an equilibrium always exists rests on the best-response map being continuous and single-valued—if at some parameter values the best response to the other type's distribution jumps or fails to be a well-defined distribution, the existence proof and the algorithm's usefulness collapse.

Editorial extensions

If this is right

  • In equilibrium, pessimistic and optimistic customers arrive at different, often disjoint, time intervals; in the fluid model this is proven as Lemma 3, and in the discrete-time numerics it persists.
  • The fluid model gives explicit arrival densities for every parameter regime, so a planner can predict arrival patterns from the arrival rates, service rates, and acceptance-period length alone.
  • Mean waiting time increases with the coefficient of variation of service times, so reducing service-time variability lowers average delay in equilibrium.
  • Customers who only learn from past experience end up with arrival distributions close to the fully rational equilibrium, and can sometimes have lower average waiting times than bounded-rational customers who compute the wrong equilibrium.
  • Multiple equilibria exist in some fluid parameter regimes, so the arrival game does not always have a unique prediction.

Reading between the lines

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

  • The signaling mechanism implies that what looks like irrational heterogeneous beliefs can arise from Bayesian updating with noisy signals, so the heterogeneous-belief game can also model a homogeneous Bayesian population; the paper's fully-informed comparison shows this matters for predictions.
  • If the separation result is robust, a system designer could influence arrival order by strategically releasing information about service speed, steering optimistic customers toward off-peak slots.
  • The discrete-time algorithm could likely be extended to more than two belief types, but the existence proof via the best-response map would need more care because the continuity assumption may fail in larger type spaces.
  • The learning-agent comparison suggests that simple reinforcement learning can approximate Nash equilibrium without knowing system parameters, which is a testable hypothesis in controlled queueing experiments.
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 a bottleneck arrival game in which a Poisson population of customers chooses arrival times to a single-server queue with an acceptance period, and where two customer types hold different beliefs about the service-time distribution. The authors present: (i) a partial characterization of Nash equilibria for exponential service times (Theorem 1 plus a conjecture), (ii) an explicit fluid-limit equilibrium construction (Theorem 2), (iii) a discrete-time formulation with general service times, a best-response characterization (Lemma 5), an iterative algorithm (Algorithm 2) and a Kakutani-based existence claim (Proposition 1), and (iv) an agent-based learning model whose long-run arrival distributions are numerically compared with bounded-rationality and fully-rational equilibria. The paper claims to be the first equilibrium analysis of a bottleneck arrival game with a discrete population and heterogeneous beliefs, and reports that in equilibrium optimistic and pessimistic customers often arrive during disjoint time intervals.

Significance. If the results are correct, the paper makes a useful contribution to strategic queueing by moving beyond homogeneous beliefs: the fluid equilibria of Theorem 2 are given in closed form and provide qualitative insight; Lemma 5 gives a clean fixed-point condition for the discrete game; and the ABM comparison addresses an interesting behavioral question. The authors are also transparent about the main unresolved points, namely Conjecture 1 in the exponential case and the absence of a convergence proof for Algorithm 2. However, the two load-bearing issues described below—the unsupported existence proof in Section 5.2 and the incorrect computation of the fully-rational equilibrium in Section 6.2—currently prevent the paper's central numerical and theoretical claims from being fully established.

major comments (2)
  1. [Section 5.2, Proposition 1 and Algorithm 2] The existence proof for the discrete two-type game is not supported. The proposition asserts that the best-response map BR is single-valued and has a closed graph, but neither property is proved. Single-valuedness is not established: uniqueness is only conjectured even in the single-type model of [23], and a fixed-point argument cannot simply assume that the algorithm's output is the unique best response. The claim that 'BR has a closed graph because solutions of (21) are continuous' does not follow, because BR is defined through Algorithm 1, which involves a bisection search with an endogenous support start θ and an endogenous equilibrium payoff w_i; no continuity argument is given for this selection. Since Proposition 1 is the only existence result for the discrete game, the statement that an equilibrium 'exists for any game parameters' is currently unproved. In addition, Algorithm 2 is presented as a method for computing equilibria for general service times, but no convergence guarantee is provided (as Remark 2 acknowledges). This limitation should be stated explicitly in the abstract and in the contributions, rather than presenting the algorithm as a general equilibrium-computation method.
  2. [Section 6.2, Eq. (32)] The 'fully rational' equilibrium used for the ABM comparison is not actually computed. In Eq. (32), the authors run Algorithm 2 twice with different rate vectors, taking the first component from the run with νa and the second component from the run with νb. But the FR game is a single coupled fixed-point problem: a pair (F_a,F_b) must satisfy F_a ∈ BR_a(F_b; νa, z_a) and F_b ∈ BR_b(F_a; νb, z_b). The first run computes a Nash equilibrium of an artificial game in which both types have arrival rates νa and service distribution z_a; its second component is not the type-b strategy of the original FR game. Similarly, the second run computes an equilibrium of a different artificial game with rates νb. The spliced pair is not checked for consistency, so it need not be a Nash equilibrium of the two-type FR game. Consequently, the claim that the ABM outcomes are close to the FR equilibrium (Figures 10–12) is unsupported by the computation presented.
minor comments (5)
  1. [Abstract and Section 3] The abstract and introduction say the paper 'characterizes' the Nash equilibrium dynamics for exponential service times, but Theorem 1 is only a partial characterization and the simultaneous-arrival case is left open by Conjecture 1. Please phrase this as a partial characterization or explicitly state that the full characterization depends on an unproved conjecture.
  2. [Section 3, Theorem 1(i)] In the statement of Theorem 1(i), the expression "∫_{t_b}^{T} f_b(t) dt = 1−F_b(t)" appears to contain a typo: the right-hand side should be 1−F_b(0) or 1−F_b(t_b), not 1−F_b(t).
  3. [Section 6, Eq. (27)] The formula for the exploration probability θ(x) is malformed as printed: with c_2>0, the expression 1−e^{c_2 x} is negative for x>0, so it cannot define a probability. Please provide the correct formula (likely involving 1+e^{c_2 x}) and specify the parameter values used in the simulations.
  4. [Section 2] The notation T is used both for the acceptance period and for its right endpoint (e.g., "T ⊆ [0,T]"), which is confusing. Please use a different symbol for one of the two objects.
  5. [Appendix B, Algorithm 1-1] In the bisection step, when ||p^{(M)}_i|| > 1, the code updates p^{(R)}_{i,θ} := p^{(M)}_{i,θ} but then writes p^{(M)}_{i,θ} := (p^{(L)}_{i,θ} + p^{(R)}_i)/2, where the subscript θ is missing from p^{(R)}_i. Please correct this typo.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the equilibrium construction is a fixed-point derivation, not a fit or a renamed input.

full rationale

The derivation chain is not circular. Lemma 4 computes mean unfinished workload by a direct Lindley-type recursion (20); Lemma 5 derives the algebraic equilibrium condition (21) from Definition 2 and (24); and Algorithm 2 is explicitly an iterated best-response search whose convergence point satisfies (21) and hence Definition 2. Theorem 2 is an explicit construction from the fluid queue equations (12) and Lemma 3, not a fit of the claimed equilibria. The only external load-bearing citations are [18] (homogeneous continuous-time equilibrium, uniqueness) and [23] (discrete-time single-type existence/algorithm), the latter co-authored by Sakuma; that is a normal, published predecessor, and the two-type equations do not reduce to the single-type theorem, because Equation (21) is a genuinely coupled two-type fixed point and no parameter in it is fitted to the target output. The paper itself flags its incomplete parts: Conjecture 1 is unproved, Remark 2 concedes no convergence proof for Algorithm 2, and Proposition 1's closed-graph claim is asserted rather than proved. The Section 6.2 computation of the fully rational equilibrium by splicing two separate Alg.2 runs is also questionable as a solution of the coupled FR game, but that is a correctness/support limitation, not circularity: the spliced quantities are not obtained by renaming a known result or by fitting the claimed conclusion into the premises. Hence the circularity score is 0.

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

The central claim rests on the belief-based queueing model (Definition 1), the Poisson population assumption, the fluid limit as a proxy for the stochastic game, and the borrowed single-type existence result of [23]. No data were fitted; lambda, mu_i, chi_i, p, q, T, tau are inputs. The unproven Conjecture 1 is explicitly not used in Theorem 1 but is used to motivate the qualitative 'disjoint arrival' claim.

assumptions (5)
  • domain assumption Customers of each type i evaluate waiting times as if all jobs have iid service times X_i, regardless of the other customers' actual types (Definition 1).
    This defines the belief structure; the whole paper's heterogeneous-belief equilibrium rests on it.
  • domain assumption The total number of customers each day is Poisson(lambda), and simultaneous arrivals are ordered uniformly at random.
    Used in Eqs. (4), (7), (24) to compute expected queue lengths; inherited from Glazer-Hassin models.
  • domain assumption The fluid model (Section 4) is a valid approximation for large populations and small service times.
    Stated in text: 'We refer the reader to [18] for rigorous justification'; the explicit fluid equilibria are used to infer qualitative behavior of the stochastic game.
  • domain assumption Existence result for the single-type discrete-time game of [23] is valid and applicable to the two-type best-response computation.
    Used in Proposition 1 to claim Algorithm 1 always returns a valid distribution; [23] is by co-author Sakuma and others.
  • standard math Kakutani's fixed point theorem is applied to a single-valued (or convex-valued) best-response map with closed graph.
    Used in Proposition 1; but continuity/closed graph is asserted, not proven, so the axiom's premises may not hold.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Strategic arrivals to a queue with service rate uncertainty." pith.science (2026). https://pith.science/paper/7GMN2RWV

@misc{pith2026190808322,
  author       = {Pith},
  title        = {Pith review of: Strategic arrivals to a queue with service rate uncertainty},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7GMN2RWV}},
  note         = {Machine review of arXiv:1908.08322}
}
read the original abstract

We study the problem of strategic choice of arrival time to a single-server queue with opening and closing times when there is uncertainty regarding service speed. A Poisson population of customers choose their arrival time with the goal of minimizing their expected waiting times and are served on a first-come first-served basis. There are two types of customers that differ in their beliefs regarding the service time distribution. The inconsistent beliefs may arise from randomness in the server state along with noisy signals that customers observe. Customers are aware of the two types of populations with differing beliefs. We characterize the Nash equilibrium dynamics for exponentially distributed service times and show how they substantially differ from the model with homogeneous customers. We further provide an explicit solution for a fluid approximation of the game. For general service time distributions we provide an algorithm for computing the equilibrium in a discrete time setting. We find that in equilibrium customers with different beliefs arrive during different (and often disjoint) time intervals. Numerical analysis further shows that the mean waiting time increases with the coefficient of variation of the service time. Furthermore, we present a learning agent based model (ABM) in which customers make joining decisions based solely on their signals and past experience. We numerically compare the long-term average outcome of the ABM with that of the equilibrium and find that the arrival distributions are quite close if we assume (for the equilibrium solution) that customers are fully rational and have knowledge of the system parameters, while they may greatly differ if customers have limited information or computing abilities.

Figures

Figures reproduced from arXiv: 1908.08322 by the authors.

Figure 1
Figure 1. Equilibrium arrival distributions (solid red for type [PITH_FULL_IMAGE:figures/full_fig_p017_1.png] view at source ↗
Figure 2
Figure 2. A sample path of the unfinished workload corresponding to a belief of type [PITH_FULL_IMAGE:figures/full_fig_p019_2.png] view at source ↗
Figure 3
Figure 3. An example for the best response of type [PITH_FULL_IMAGE:figures/full_fig_p022_3.png] view at source ↗
Figures from the paper (9 more)
Figure 4
Figure 4. Figure 4: cdfs of the equilibrium arrival distributions computed by (26), where the service time [PITH_FULL_IMAGE:figures/full_fig_p024_4.png]
Figure 5
Figure 5. Figure 5: cdfs of the equilibrium arrival distributions computed by (26), where the service time [PITH_FULL_IMAGE:figures/full_fig_p024_5.png]
Figure 6
Figure 6. Figure 6: cdfs of the equilibrium arrival distributions computed by (26), where the service time [PITH_FULL_IMAGE:figures/full_fig_p025_6.png]
Figure 7
Figure 7. Figure 7: Comparison between cdfs of the equilibrium arrival distributions calculated by (26) and [PITH_FULL_IMAGE:figures/full_fig_p027_7.png]
Figure 8
Figure 8. Figure 8: Comparison between cdfs of the equilibrium arrival distributions calculated by (26) and [PITH_FULL_IMAGE:figures/full_fig_p028_8.png]
Figure 9
Figure 9. Figure 9: Comparison between cdfs of the equilibrium arrival distributions calculated by (26) and [PITH_FULL_IMAGE:figures/full_fig_p028_9.png]
Figure 10
Figure 10. Figure 10: Comparison between cdfs of the equilibrium arrival distributions calculated by (32) [PITH_FULL_IMAGE:figures/full_fig_p030_10.png]
Figure 11
Figure 11. Figure 11: Comparison between cdfs of the equilibrium arrival distributions calculated by (32) [PITH_FULL_IMAGE:figures/full_fig_p030_11.png]
Figure 12
Figure 12. Figure 12: Comparison between cdfs of the equilibrium arrival distributions calculated by (32) [PITH_FULL_IMAGE:figures/full_fig_p031_12.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages

  1. [23]

    Sakuma, H

    Y. Sakuma, H. Masuyama, and E. Fukuda. Equilibrium arrival distributions in a discrete- time single-server queueing game with an acceptance period for a poissonian population of customers. European Journal of Operational Research, 283(1):253–264”, 2020

    work page 2020

  2. [1]

    Breinbjerg

    J. Breinbjerg. Equilibrium arrival times to queues with general service times and non-linear utility functions. European Journal of Operational Research, 261(2):595 – 605, 2017

    work page 2017

  3. [2]

    Bruneel and B

    H. Bruneel and B. G. Kim. Discrete-time models for communication systems including ATM , Springer Science & Business Media, 1993

    work page 1993

  4. [3]

    Chen and A

    H. Chen and A. Mandelbaum. Discrete flow networks: bottleneck analysis and fluid approxi- mation. Mathematics of operations research, 16(2), 408-446, 1991

    work page 1991

  5. [4]

    Cui and S

    S. Cui and S. Veeraraghavan. Blind queues: The impact of consumer beliefs on revenues and congestion. Management Science, 62(12):3656–3672, 2016

    work page 2016

  6. [5]

    Daley and D

    D.J. Daley and D. Vere-Jones. An Introduction to the Theory of Point Processes. Volume I: Elementary Theory and Methods , Springer, 2003

    work page 2003

  7. [6]

    Debo and S

    L. Debo and S. Veeraraghavan. Equilibrium in queues under unknown service times and service value. Operations Research, 62(1):38–57, 2014

    work page 2014

  8. [7]

    Economou and A

    A. Economou and A. Manou. Strategic behavior in an observable fluid queue with an alter- nating service process. European Journal of Operational Research, 254(1):148–160, 2016

    work page 2016

Show all 26 references
  1. [8]

    Glazer and R

    A. Glazer and R. Hassin. ?/M/ 1: On the equilibrium distribution of customer arrivals. Euro- pean Journal of Operational Research, 13(2):146–150, 1983

    1983

  2. [9]

    R. Hassin. Rational Queueing. CRC Press, 2016

    2016

  3. [10]

    Hassin and M

    R. Hassin and M. Haviv. To Queue or Not to Queue: Equilibrium Behavior in Queueing Systems, Springer, 2003

    2003

  4. [11]

    Hassin and Y

    R. Hassin and Y. Kleiner. Equilibrium and optimal arrival patterns to a server with opening and closing times. IIE Transactions, 43(3):164–175, 2011

    2011

  5. [12]

    M. Haviv. When to arrive at a queue with tardiness costs? Performance Evaluation, 70(6):387– 399, 2013

    2013

  6. [13]

    Haviv and I

    M. Haviv and I. Milchtaich. Auctions with a random number of identical bidders. Economics Letters, 114(2):143–146, 2012

    2012

  7. [14]

    Haviv and L

    M. Haviv and L. Ravner. Strategic timing of arrivals to a finite queue multi-server loss system. Queueing Systems, 81(1):71–96, 2015

    2015

  8. [15]

    Honnappa and R

    H. Honnappa and R. Jain. Strategic arrivals into queueing networks: the network concert queueing game. Operations Research, 63(1):247–259, 2015

    2015

  9. [16]

    Huang, and Y

    T. Huang, and Y. J. Chen. Service systems with experience-based anecdotal reasoning cus- tomers. Production and Operations Management, 24(5):778–790, 2015

    2015

  10. [17]

    R. Ibrahim. Managing queueing systems where capacity is random and customers are impa- tient. Production and Operations Management, 27(2):234–250, 2018

    2018

  11. [18]

    Juneja and N

    S. Juneja and N. Shimkin. The concert queueing game: strategic arrivals with waiting and tardiness costs. Queueing Systems, 74(4):369–402, 2013. 35

    2013

  12. [19]

    Juneja and N

    S. Juneja and N. Shimkin. On the computation of dynamic user equilibrium in the multiclass transient fluid queue. ACM SIGMETRICS Performance Evaluation Review , 45(3):137–142, Mar. 2018

    2018

  13. [20]

    Monderer and L

    D. Monderer and L. S. Shapley. Potential games. Games and Economic Behavior , 14(1):124 – 143, 1996

    1996

  14. [21]

    M. J. Osborne and A. Rubinstein. A Course in Game Theory . MIT press, 1994

    1994

  15. [22]

    L. Ravner. Equilibrium arrival times to a queue with order penalties. European Journal of Operational Research, 239(2):456–468, 2014

    2014

  16. [24]

    D. M. Topkis. Equilibrium points in nonzero-sum n-person submodular games. SIAM Journal on Control and Optimization , 17(6):773–787, 1979

    1979

  17. [25]

    Veeraraghavan and L

    S. Veeraraghavan and L. Debo. Joining longer queues: Information externalities in queue choice. Manufacturing & Service Operations Management , 11(4):543–562, 2009

    2009

  18. [26]

    Zhang and B

    H. Zhang and B. Li. Characterizations of discrete compound Poisson distributions. Commu- nications in Statistics-Theory and Methods , 45(22):6789–6802, 2016. 36

    2016

Pith tools

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