Queueing to learn

Margaria, Chiara Article Queueing to learn Theoretical Economics Provided in Cooperation with: The Econometric Society Suggested Citation: Margaria, Chiara (2025) : Queueing to learn, Theoretical Economics, ISSN 1555-7561, The Econometric Society, New Haven, CT, Vol. 20, Iss. 2, pp. 623-665, https://doi.org/10.3982/TE4814 This Version is available at: https://hdl.handle.net/10419/320295 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by-nc/4.0/ Theoretical Economics 20 (2025), 623–665 1555-7561/20250623 Queueing to learn Chiara Margaria Department of Economics, Boston University I study the efficient design of a queue to dynamically allocate a scarce resource to long-lived agents. Agents can be served multiple times, and their valuations fluctuate over time with some persistence. Each agent privately learns whether his prevailing valuation is high or low only when served. An agent can decide anytime whether to either join a queue of his choice or renege. I show that it is efficient to elicit agents’ private information by offering a simple binary menu (i.e., two customer classes): a first-come, first-served queue, to attract low-value agents, and one in random order, to attract high-value agents. When queueing is costly, offering a single queue may be optimal because of the tradeoff between allocative efficiency and the cost of screening. Keywords. Queues, experimentation, reneging, congestion, mechanism design. JEL classification. C73, D47, D82. 1. Introduction This paper studies the efficient design of a queue to allocate a resource flow. Examples of rationing by waiting are plentiful: the allocation of subsidized credit and public housing, assignment of homeless shelters, provision of health and sanitation services, allocation of donated organs, and sharing of processing power in a capacity-constrained computing system. I study the design of a queue to maximize efficiency when strategic agents require service repeatedly and learn their valuation only when served. Consider the following stylized examples of which the model is suggestive. A microfinance institution allocates short-term loans to entrepreneurs to fund small-scale projects, such as starting a business in a developing country or increasing crop production. The profitability of each entrepreneur’s project depends on market conditions and fluctuates over time. Each entrepreneur is uncertain about the prospects of his project and can assess its profitability only when allocated funds to invest; in this sense, agents learn their valuations when they are served. Because the loans are small and short-term, the same entrepreneur requests loans repeatedly to operate his business when it is profitable for him to do so. Chiara Margaria: [email protected] I am indebted to Johannes Hörner and Larry Samuelson for their invaluable help and support throughout this project. I would like to thank Dirk Bergemann, Eduardo Faingold, Mira Frick, Ryota Iijima, and Bart Lipman for their useful comments and suggestions, and Gad Allon, Barı¸s Ata, and Achal Bassamboo for insightful discussions. I benefited from many conversations with visitors at Yale, in particular V. Bhaskar, Laura Doval, Caroline Thomas, and Takuo Sugaya, and from excellent comments from Balazs Szentes, Nikhil Vellodi, Allen I. K. Vong, and various seminar participants. I am grateful to Beixi Zhou for excellent research assistance. ©2025 The Author. Licensed under the Creative Commons Attribution-NonCommercial License 4.0. Available at https://econtheory.org.https://doi.org/10.3982/TE4814 624 Chiara Margaria Theoretical Economics 20 (2025) Intuitively, the objective of the designer is twofold: maximizing allocative efficiency and minimizing congestion, that is, allocating the scarce resource to agents with the highest expected valuation (in the microfinance example, entrepreneurs with the most profitable investment opportunities) and reducing the queue length (the average time to obtain a loan). On the face of it, a single first-come first-served queue is inefficient because agents joining the queue impose a negative externality on future arrivals by increasing the time it takes for future agents to be served, and arriving agents may have a higher expected valuation. Serving agents in a single service-in-random-order queue deters agents from joining the queue when their prevailing expected valuation is low, alleviating the externality problem. In the microfinance example, if the expected net return from a loan is negative, an entrepreneur would postpone their application until prospects improve if there is a chance of receiving the loan without delay. More subtly, because agents are served repeatedly and learn about their valuation when they are served, the service discipline also affects the equilibrium length of the queue, or to put it differently, the proportion of time that agents allocate to costly queueing. If loans are granted to entrepreneurs who are on average more optimistic about their return prospects, a larger fraction of them are likely to resubmit an application right away, exacerbating future congestion. The contribution of this paper is to propose a parsimonious model to investigate these tradeoffs and to examine rationing by queueing in the absence of monetary transfers while considering the possibility of reneging.1The optimal queueing mechanism is remarkably simple and involves well-known queueing disciplines: it is a menu of at most two queues, service is rendered in a first-come, first-served manner in one queue and in random order in the other. In the model, a constant flow of a resource is to be allocated to a continuum of forward-looking agents. Capacity is limited: over any interval of time, only a fixed mass of agents can be served. At each moment in time, agents decide whether and when to engage in (possibly) costly queueing to be served, and each of them can be served multiple times. Valuations fluctuate independently across agents, and each agent faces an experimentation problem because the lump-sum payoff collected at each service reveals the prevailing valuation, which can be high or low. Rivalry generates an externality problem, because agents ignore the fact that their actions affect overall congestion. The setup presents a few methodological challenges. First, because of reneging, the revelation principle does not apply. Second, even if the underlying valuation is binary, because of learning, an agent’s type belongs to a continuum. Third, the lack of transfers prevents the use of standard methods based on the envelope theorem to elicit private information. I overcome these challenges by showing that without loss of generality, one can restrict attention to queues that provide the agents incentives not to renege. This observation, which may be useful in other contexts, relies solely on the assumption that agents 1Following the operations research terminology, I use the term reneging to describe the act of leaving a queue before being served. Theoretical Economics 20 (2025) Queueing to learn 625 acquire information about their valuation only when they are served. Further, I prove that as long as agents’ expected valuations evolve monotonically over time—a condition automatically satisfied in the case of binary underlying valuations—attention can be restricted to binary menus. I then show that as far as payoffs are concerned, each queue in the menu can be summarized by a pair of sufficient statistics. This pair determines whether a queueing discipline or menu of queueing disciplines is feasible, that is, whether the induced service rate does not exceed capacity. The idea is that both payoff and service rate depend only on the amount of time an agent expects to queue between two consecutive services and on the probability of having a high valuation when served. A version of the familiar single-crossing property of preferences holds. Specifically, the risk attitude of an agent (i.e., his preference towards a more or less risky queueing discipline) depends on his belief about his current valuation. Having characterized the optimal menu, I then derive a set of comparative statics results. When waiting is costless or the resource is relatively abundant, it is efficient to serve agents in two queues. In contrast, when waiting is particularly wasteful, it is optimal to offer a single first-come, first-served queue, because it minimizes queue length.2 Related literature This paper is related to several strands of literature. First, it belongs to the literature on strategic behavior in queues.3The idea that in a first-come, firstserved (FCFS) queue rational agents adopt suboptimal behavior dates back to Naor (1969). In that framework, Hassin (1985) shows that a last-come, first-served (LCFS) queueing discipline achieves the social optimum without the need for transfers (see also Scarsini and Shmaya (2024)). Platz and Østerdal (2017) find that in a concert queueing game, FCFS and LCFS achieve the minimal and maximal aggregate equilibrium payoff among all queueing disciplines, respectively. In their environment, as in mine, FCFS provides incentives to join the queue early, which in the end hurts all agents in equilibrium. The results in Hassin (1985)andPlatz and Østerdal (2017), however, rely on the designer’s ability to prevent restarting. In contrast, the designer in my model cannot detect or punish reneging and restarting, and LCFS cannot be part of an equilibrium. Second, the dynamic allocation of objects to agents arriving over time through waiting lists has been studied in the context of public housing and organ transplants. Both Leshno (2022)andBloch and Cantala (2017) consider the problem of allocating a sequence of heterogeneous items that are sequentially offered to agents on a waiting list. Both papers assume that the flow of agents joining the pool is exogenous, so maximizing welfare is equivalent to maximizing allocative efficiency; consequently, the tradeoff between allocative efficiency and congestion is absent in these models. Bloch and Cantala (2017) assume that agents’ valuations evolve over time independently across periods, 2The result resonates with the anecdotal evidence that inspired Milner and Olsen (2008). The authors report that a call center was offering differentiated services to its two types of customers (those with and without a service-level agreement requiring a given percentage of customers to be served within a given time) only in off-peak hours. 3The motivation and modeling choices of my paper are close to those of Bassamboo and Randhawa (2015), who study scheduling policies in a queueing system with reneging customers, abstracting from strategic considerations. 626 Chiara Margaria Theoretical Economics 20 (2025) and show that service in a first-come, first-served order always outperforms service in random order. Leshno (2022) assumes that agents’ valuations are constant over time and shows that service in random order increases welfare, as compared to first-come, firstserved order, by partially shielding agents from random fluctuations in waiting time. Recently, Che and Tercieux (2023) assume that the designer chooses both the queueing discipline and the information available to the agents,4and show that it is optimal to provide no information about queue length and serve agents according to a first-come, first-served rule. Third, the paper contributes to the literature on dynamic mechanism design with unobservable arrival. With the exception of a few papers—among others, in the context of dynamic mechanism design with transfers, Garrett (2016)andBergemann and Strack (2022)—most of the literature on dynamic mechanism design assumes that the designer observes agents’ arrival. The case of unobservable arrival is natural in the context of queues: while the designer observes agents joining the queue, she may be unable to detect when an agent has balked and rejoined the queue, presumably disguised as a new agent. Hence, the designer is unable to condition on an agent’s past history of allocation so that neither quota mechanisms as in Jackson and Sonnenschein (2007)nor a “quantified entitlement” mechanism as in Guo and Hörner (2020) is feasible. As a result, the designer elicits private information by leveraging agents’ preferences about the distribution of service time, that is, their intertemporal preferences. Last, the interaction between agents who engage in individual experimentation has been studied by the strategic experimentation literature. However, most of it has focused on information externalities, which are absent in my model. An exception is Thomas (2021), who analyzes congestion externalities. Cripps and Thomas (2019) investigate the interaction between information externalities and congestion externalities in a queueing model. Their paper is, however, only tangentially related to mine. In their model, agents arrive over time and there is a common source of uncertainty, the service rate of a server. Observational learning arises because queue length and other agents’ reneging decisions reveal the agents’ private information. The rest of the paper is organized as follows. Section 2introduces the model. Section 3sets up the designer’s problem and simplifies it in three steps. In Section 4,I solve the designer’s problem and characterize the optimal menu of queueing disciplines. Section 5concludes the paper. 2. Setup Time is continuous, indexed by t≥0, and the horizon is infinite. A designer (she) wishes to allocate a perishable and indivisible good to a unit mass of long-lived agents indexed by i∈[0, 1]. Units of the good arrive at rate λ,soamassλ(t −t)is to be assigned over any interval of time [t,t],t<t. 4In my model, information design would not help: because of the continuum of agents and the assumption that the queue is unobservable, agents do not need to infer the distribution of the residual waiting time from the amount they have been waiting. Theoretical Economics 20 (2025) Queueing to learn 627 Let Ni tdenote the total number of times agent i∈[0, 1]has been allocated the good in the time interval [0, t](formally, Ni tis a counting process); feasibility requires that for all t≥0andallt<t,5 1 0t tdNi tdi≤λt −t.(1) The designer aims to maximize aggregate payoffs in some equilibrium of the game, as defined below. Designer’s choice There are no transfers, and the good is allocated via a queueing system. Informally, the designer commits to a menu of queues; at all times, each agent chooses whether to queue and which queue to join. Queues may differ in their capacity, that is, in the amount of resource allocated to them, and in their queueing discipline. The discipline dictates how the good is allocated across the agents in the queue based on their individual waiting time. Common examples of queueing disciplines are firstcome, first-served (FCSF), last-come, first-served (LCFS), and service in random order (SIRO). A menu of queues defines an anonymous sequential game between agents (Jovanovic and Rosenthal (1988)). I focus on steady-state equilibria. Owing to the law of large numbers, in the steady state, each agent faces a single-agent decision problem. The behavior of the other agents is relevant only inasmuch as it affects the waiting time before service. Hence, I formalize the choice of the designer as a choice of a collection of (steady-state) waiting-time distributions. More precisely, a menu is a collection of queues Qwith generic element q.Atany time t, an agent can either be queueing or not; hence, I describe agent i’s action by qi t∈ˆ Q:=Q∪{∅}, with the interpretation that qi t=∅when the agent does not queue and qi t∈Qwhen he is waiting at some queue. In light of the discussion above, the designer chooses a collection of (steady-state) waiting-time distributions, {Hq}q∈Qfor each q∈Q,withHq∈H, as defined below.6 Definition 1. The set His the set of cumulative distribution functions, H:R+→[0, 1], such that H(0)=0andtdH(t)<∞. Each waiting-time distribution Hqis the distribution of the time an agent waits before being served, provided that he does not abandon the queue before service, in steady state. The requirement that Hqshould not have atoms at 0 guarantees that the allocation is well defined for all strategy profiles of the agents. As will become clear (see Lemma 1), there is no loss in restricting attention to distributions having finite mean. 5To deal with essentially pairwise independent processes (Ni t)t≥0, one needs to work with an enrichment of the usual product probability space (see Sun (2006)). While the explicit construction is omitted, I rely on Sun’s law of large numbers for a continuum of random variables. 6Formulating the designer’s problem as a choice of waiting-time distributions circumvents the need to formalize the anonymous sequential game and the issues arising from having a continuum of independent continuous-time Markov processes. As will become clear, it amounts to restating the designer’s problem as a static mechanism design problem. 628 Chiara Margaria Theoretical Economics 20 (2025) To understand the relationship between queueing disciplines and waiting-time distributions, note that if a queue operates in a first-come, first-served manner and agents do not renege, in steady state, all agents wait the same deterministic amount of time before being served. In other words, the waiting-time distribution is degenerate. Similarly, in a service-in-random-order queue, each agent in line, irrespectively of the amount of time he has been waiting, has the same probability of being served in the next instant. As a result, the waiting time is exponentially distributed. For ease of exposition, I restate the relationship between some waiting-time distributions and queueing disciplines in the following definitions. Definition 2. (i) Agents are served according to a first-come, first-served discipline if the waiting-time distribution His a degenerate distribution. (ii) Agents are served according to a service-in-random-order discipline if the waiting-time distribution His an exponential distribution with support [0, ∞). (iii) Agents are served according to a service-in-random-order discipline with a minimum waiting-time requirement if the waiting-time distribution has a constant hazard rate and support [t,∞),forsomet>0. Two remarks are in order. First, the designer’s choice is not restricted to the classes of waiting-time distributions in the definition above; see Definition 2.Second,while the service-in-random-order discipline with a minimum waiting-time requirement is a generalization of the service-in-random-order discipline, distinguishing between them is convenient because the latter plays a more crucial role in the optimal menu characterization. Agents’ actions Arriving agents do not observe agents already waiting (i.e., queue length). An agent’s strategy specifies when to join and leave a queue. Because time is continuous, the formal definition requires some care. In particular, an agent who leaves a queue at time t, either because he reneges or because he is served at t,maywantto restart queueing with no delay. Informally, if the agent is not queueing, a (pure) strategy dictates the time at which he joins a queue and which one. If the agent is queueing, a (pure) strategy specifies the time at which the agent reneges, that is, leaves the queue if by that time he has not been served. In this case, the strategy prescribes the action to be taken when reneging: rejoining a queue or not. Finally, a strategy also prescribes whether to rejoin a queue with no delay after being served. Let the time-in-queue process (wi t)t≥0describe the amount of time elapsed since the agent last joined the queue he is currently in whenever the agent is queueing; set the time-in-queue process equal to 0 when the agent is not queueing. An agent’s strategy is an impulse control for the processes (qi t)t≥0and (wi t)t≥0.7 If the agent does not intervene, the processes evolve exogenously as follows. While an agent is queueing, the time-in-queue grows linearly over time until the agent is 7The formal definition of strategies as impulse control policies is relegated to the Appendix. Theoretical Economics 20 (2025) Queueing to learn 629 served, when the time-in-queue jumps to 0. At any service time, the queue process jumps to ∅. In other words, unless the agent reneges, the agent leaves the queue as soon as he is served. At any time t, the agent can intervene and induce (qi t,wi t)to jump to either (∅,0 )or (q,0 ),forsomeq∈Q. Intuitively, if a queueing agent leaves a queue—either because he reneges or because he is served—and does not rejoin the queue immediately, the process (qi t,wi t)jumps to (∅,0 ). If the agent either joins a queue or jockeys between queues, the process (qi t,wi t)jumps to (q,0 ),forsomeq∈Q. Payoffs When allocated the good, agent ireceives a lump-sum payoff equal to some state θi, which can take two possible values, θ0and θ1,withθ0<0<θ 1.Agenti’s state evolves unbeknown to him according to a continuous-time Markov chain (θi t)t≥0,with state space {θ0,θ1}, transition matrix ((−ρ0,ρ0),(ρ1,−ρ1)), and initial probability of state θ1given by ρ0/(ρ0+ρ1). The individual state processes of any pair of agents is assumed to be independent. Given some integrable queue process (qi t)t≥0, the realization of the state process (θi t)t≥0, and the individual allocation process (Ni t)t≥0, the realized payoff of agent iis given by the long-run average, limsup T→∞ 1 TT 0 θi tdNi t−T 0 c1qi t=∅ dt. This payoff has two components: the sum of lump-sum payoffs collected at each consumption experience and the total cost borne by the agent while queueing. Note the absence of discounting. Strategies and equilibrium Given a menu, each agent faces a single-agent Markov decision problem. I introduce a state variable to describe an agent’s information about his current valuation. Let pi tbe the belief that agent iattaches to his valuation being equal to θ1. As long as the agent is not served, his belief about this valuation evolves according to (the first-order) dpi t=1−pi tρ0−pi tρ1dt. Specifically, for all t≥0andallt<t, such that no service occurs from tto t, pi t =e−(ρ0+ρ1)(t−t)pi t+1−e−(ρ0+ρ1)(t−t)ρ0 ρ0+ρ1 .(2) Equation (2) makes it plain that the belief of agent iis a convex combination of his past belief pi tand the invariant probability of θ1,ρ0/(ρ0+ρ1). Along the history with no service, the posterior belief that the state is θ1converges to ρ0/(ρ0+ρ1). As soon as the agent is served, his belief about his valuation jumps to 1 or 0. It is without loss of generality to assume that agents’ strategies are Markov in calendar time, posterior belief, current queue, and time-in-queue (t,pi t,qi t,wi t). Abusing notation, I denote by the set of stationary Markov strategies, which are those that do not condition on calendar time. 630 Chiara Margaria Theoretical Economics 20 (2025) As explained above, the agent’s problem is formalized as an impulse control: the agent chooses the (random) dates at which he intervenes and adjusts his action, that is, the dates at which he joins or leaves a queue, in addition to choosing whether to rejoin a queue immediately after reneging or being served. Notice that, given an initial state (p,q,w), unless the agent adjusts his action by joining or leaving a queue, the evolution of the belief pis a sufficient statistic for the time-in-queue evolution. Hence, there is no loss of generality in focusing on impulse-control policies that are Markov in the belief. I focus on symmetric steady-state equilibria. In a steady state, each agent i∈[0, 1] chooses his strategy σito maximize Vσi,{Hq}q∈Q:=Eσi,{Hq}q∈Qlimsup T→∞ 1 TT 0 θi tdNi t−T 0 c1qi t=∅ dt.(3) Definition 3. A symmetric steady-state equilibrium is a pair (σ,{Hq}q∈Q),σ∈such that the strategy σ∈Sigma is optimal given {Hq}q∈Q⊂H. The designer’s goal is to choose a queueing menu to maximize aggregate payoffs in some equilibrium of the game. More precisely, she chooses a symmetric steady-state equilibrium (σ,{Hq}q∈Q)to maximize aggregate payoffs. Because, by definition, the equilibrium is symmetric, each agent achieves the same realized payoff (3). Hence, the aggregate payoff equals the payoff of a representative agent, denoted by ihereafter. The designer faces the aggregate capacity constraint (1). In the spirit of the law of large numbers, I state the capacity constraint as a bound on the average (long-run) service rate,8 1 0Sσi,{Hq}q∈Qdi≤λ,whereSσi,{Hq}q∈Q:=1 tNi t where the limit inside the integrand is understood in the sense of almost sure convergence.910 For notational convenience, I drop the superscript ihereafter. 3. Designer’sproblem I simplify the designer’s problem in two steps. First, I show that even if an agent’s type (i.e., his belief at each point in time) belongs to a continuum, attention can be restricted to binary menus. Second, I show that the problem can be cast into a lower-dimensional space of sufficient statistics. 8Note that the law of the counting process Ni tis jointly determined by {Hq}q∈Qand σi, but for notational simplicity, I keep such dependence implicit. 9In Section A.2.1, I show that for any {Hq}q∈Qand any best reply σ, the long-run service rate converges to a constant almost surely. 10As I will show, the solution to the designer’s problem involves waiting-time distributions, which are easily implementable with well-known queueing disciplines. As a result, it is not necessary to argue that for any equilibrium (σ,{Hq}q∈Q)∈×HQsuch that S(σ,{Hq}q∈Q)≤λ, it is possible to find a collection of queueing disciplines implementing it. This is a collection of allocation rules such that the induced anonymous sequential game between agents has a symmetric equilibrium in which each player adopts the strategy σand the collection of waiting-time distributions is {Hq}q∈Q. Theoretical Economics 20 (2025) Queueing to learn 637 Figure 2. On the left panel, the sets and NBUE. On the right panel, summary statistics for the optimal menu {H∗ 0,H∗ 1}and for the best disciplines within the SIRO and FCFS classes. Solid lines depict the agent’s indifference curves; utility is increasing in the southeast direction. (θ1,θ0,c,ρ0,ρ1,λ)=(1, −3/4, 0, 1, 1, 2). generating function evaluated at −(ρ0+ρ1)and the expected waiting time. Because the function t→ e−(ρ0+ρ1)tis convex, the southwestern boundary of the sets corresponds to degenerate distributions, that is, those assigning probability 1 to some μ∈(0, ∞).The northeastern boundary of NBUE corresponds to the set of exponential distributions, which are, as mentioned above, “extreme” within the NBUE family. From the perspective of incentives, when the waiting time is exponentially distributed, the nonreneging constraint is binding at all times: agents are served at a constant rate, independent of their arrival time in the queue. A noteworthy consequence of Lemma 3is that the classes of waiting-time distributions corresponding to the three classes of queueing disciplines in Definition 2span the set NBUE. If agents are served according to a first-come, first-served discipline, the pair of summary statistics lies on the western boundary of NBUE. If agents are served according to a service-in-random-order discipline, the pair of summary statistics lies on the eastern boundary of NBUE. Finally, each point in the interior of NBUE is achieved by a shifted exponential distribution that can be generated by serving agents in random order with a minimum waiting-time requirement t>0. Notice, however, that the characterization in Lemma 3doesnotaccountforthecapacity constraint. On the one hand, if the designer offers a single queue and does not discard any of the available resource flow, the expected waiting time does not exceed 1/λ. On the other hand, as I shall explain in the next section, identifying the best feasible first-come-first-served queue, for example, is not merely a statistical problem as it requires analyzing the agent’s best reply. 4. Optimal menu Since the designer maximizes the aggregate payoff and each agent achieves the same payoff in equilibrium, the designer’s preferences coincide with each agent’s preferences. 638 Chiara Margaria Theoretical Economics 20 (2025) However, there is scope for the intervention by a designer because agents do not internalize the externality generated by their actions. To shed light on the problem faced by the designer, I now present a payoff decomposition that highlights the source of the externality. (The formal derivation can be found in the Appendix.) Fix a pair of waiting-time distributions {H0,H1}⊂Hand a strategy σ∈NR that satisfies (IC). The payoff can be written as Vσi,{H0,H1}=Sσi,{H0,H1}·mδH0,δH1,pσθ1−cμH1 +1−mδH0,δH1,pσθ0−cμH0,(9) where m(δH0,δH1,pσ)is the long-run frequency with which a service yields a lump sum θ1,and Sσi,{H0,H1}=1 mδH0,δH1,pσμ1+1−mδH0,δH1,pσμ0−lnpσ/(ρ0+ρ1) is the induced service rate. According to (9),thepayofffromthestrategyσis the product of the rate at which the agent is served and the expected total payoff he collects between service times. The latter is a function of m(δH0,δH1,pσ), the probability of being served when the state is θ1. The relationship between m(δH0,δH1,pσ)and S(σi,{H0,H1})is easy to understand. From the elementary renewal theorem, the expected service rate equals the inverse of the average time between services. When joining the queue, the agent expects to wait an amount of time equal to either μH0or μH1, depending on the payoff he realized at the last service. Moreover, after being served, he waits an amount of time −ln(pσ)/(ρ0+ρ1)before joining the queue whenever the realized payoff is θ0,which occurs a proportion 1 −m(δH0,δH1,pσ)of the time. The cutoff pσaffects the rate at which an agent is served. This is a manifestation of the congestion externality, reminiscent of a “tragedy of the commons.” The designer must guarantee through an appropriate choice of distributions that the service rate induced by the agents’ best reply does not exceed the capacity λ. Ideally, the designer would like to minimize wasteful wait and persuade the agents with a low belief to delay as long as possible before joining the queue. The cutoff pσalso affects the rate of arrival of the high types, or to put it differently, the representative agent’s probability of realizing a high lump-sum payoff when served. The longer the agent waits before joining the queue after realizing a lump sum payoff of θ0, the larger rate of arrival of the high types. At the same time, by Proposition 1,an agent rejoins the queue with no delay as soon as he collects a high lump-sum payoff, so a larger rate of arrival of the high types may increase the aggregate queueing cost. 4.1 A special case: Costless queueing I start by characterizing the optimal menu when queueing is costless, to highlight the tradeoff stemming from the dynamic externality problem. When queueing is costless, Theoretical Economics 20 (2025) Queueing to learn 639 the negative externality that an agent imposes on another agent is not related to the cost of queuing but rather to the rivalry between agents. Agents’ desire to be served can be due to an exploration or exploitation motive: agents who want to explore, because they are growing increasingly optimistic about their valuation, do not internalize the fact that they may curtail other agents’ ability to exploit, that is, to be served when their expected valuation is the highest. To develop some intuition regarding the optimal menu, notice that when queueing is costless, serving agents in a single service-in-random-order queue yields a higher payoff compared to serving them in a single first-come, first-served queue. When agents are served in random order, they may be served immediately after realizing a high lumpsum payoff when their expected valuation is the highest, which never happens when serving them in order of arrival. The right panel of Figure 2plots the summary statistics for the best feasible service-in-random-order queue and the best feasible first-come, first-served queue: serving agents in random order may involve a longer wait compared to serving them in order of arrival, but because queueing is costless, the former is welfare-improving. Now, observe that the designer could achieve the same payoff and service rate as a service in random order queue while having agents queue at all times by offering a binary menu consisting of a service-in-random-order queue and a service-in-randomorder queue with a minimum waiting-time requirement. To put it differently, when c=0, the designer does not need to try and persuade agents with a low belief to delay joining the queue, and without loss of generality, we can assume that in the optimal menu, agents queue at all times. Next, I argue that a version of the familiar single-crossing property of preferences holds: from the law of motion of beliefs (7), an agent’s attitude toward uncertainty in the service time—whether he is risk-seeking or risk-averse over time lotteries—depends on whether he is growing optimistic or pessimistic about his valuation. An agent with a belief below the invariant probability dislikes randomness in his service time, while the opposite is true for agents with a belief above the invariant probability. Naturally, one of the incentive constraints must bind; for otherwise, the designer could decrease the wait at the service-in-random-order queue and increase the wait at the first-come, first-served queue and increase payoffs, without violating any constraint. In the optimal menu, the incentive constraint of the agent joining with a low belief binds. As a result, the optimal menu is payoff-equivalent to serving agents in a single service-in-random-order queue. Of course, to achieve the same payoff with a single service-in-random-order queue, the designer would need a larger capacity than λ: the wait at the service-in-random-order queue in the menu is shorter than the wait at the best feasible service-in-random-order queue (see the right panel of Figure 2). Theorem 1. Suppose c=0. AnoptimalmenuisonesuchthatμH∗ 1≥μH∗ 0,δH∗ 0≥δH∗ 1, the capacity constraint (C) is binding, and: 640 Chiara Margaria Theoretical Economics 20 (2025) (i) (FCFS/SIRO menu) H∗ 0is degenerate and H∗ 1is exponential; (ii) (low-type IC binds) any best reply to {H∗ 1,H∗ 1}yields the same payoff as (σ,{H∗ 0, H∗ 1});and (iii) (agents queue at all times) pσ=0. Agents are offered a choice between two queues: one with a first-come, first-served discipline and the other with a random-order discipline. The agents joining the queue with a high belief, that is, immediately after receiving a positive lump-sum payoff, are served in random order, the “riskiest” discipline that provides incentives not to renege. The agents joining immediately after receiving a negative lump-sum payoff are served according to a first-come, first-served queueing discipline; hence, they are exposed to minimal risk. 4.2 The general case When c>0, considerations about queue length cannot be ignored. The trade-off between allocative efficiency and congestion is more subtle, and pooling different types of agents by offering a single queue is sometimes optimal. Theorem 2. There exists a solution (σ,{H∗ 0,H∗ 1})to the designer’s problem (M). It is such that μH∗ 1≥μH∗ 1,δH∗ 1≥δH∗ 1, the capacity constraint (C) is binding, and one of the following holds: (i) (pooling menu) H∗ 0=H∗ 1=H∗for some H∗∈HNBUE, (ii) (separating menu) H∗ 0= H∗ 1,and (a) (FCFS/SIRO menu) H∗ 0is degenerate and H∗ 1is exponential; (b) (low-type IC binds) any best reply to {H∗ 1,H∗ 1}yields the same payoff as (σ,{H∗ 0,H∗ 1});and (c) (agents queue at all times) pσ=0. The optimal menu can be of two types: pooling or separating. Intuitively, in the absence of monetary transfers, queueing is not only a byproduct of scarcity but also serves as a costly signaling device. A screening menu requires agents to engage in wasteful queueing to signal their type and allocates dedicated capacity to the “high types.” As in Condorelli (2012), sometimes the designer finds it optimal not to extract agents’ private information and instead offers a single queue. When the optimal menu is pooling, the optimal service discipline is either firstcome, first-served or service in random order with or without a minimum waiting-time requirement. As shown below, both first-come, first-served and service-in-randomorder (with an arbitrary waiting-time requirement t>0) disciplines can emerge as optimal for some sets of parameters (θ1,θ0,ρ0,ρ1,λ). Theoretical Economics 20 (2025) Queueing to learn 641 A separating optimal menu coincides with the one in Theorem 1. The value of the information acquired at each service is maximized: learning is so valuable that agents queue at all times, even if queueing is costly. From the perspective of the individual experimentation problem, this does not mean that exploring is valuable at every belief. Joining the queue has an option value: it guarantees the right to be served at some point in the future when the belief will be higher. An agent joins the queue at a belief of 0 because he is certain that he will not engage in exploration for some time. 4.3 Discussion: Comparative statics As mentioned before, when c>0, considerations about queue length cannot be ignored. In fact, the separating menu, if optimal, maximizes queue length. To the other extreme, if the waiting cost is high enough,16 the designer finds it optimal to offer a single firstcome, first-served queue, even if this implies forgoing the possibility to serve returning agents as soon as they rejoin the queue. Lemma 4. Fix any admissible set of parameters (θ1,θ0,ρ0,ρ1,λ). (i) There exists a csuch that for c>c, neither the separating menu nor the pooling service-in-random order queue is optimal. (ii) If offering a single first-come, first-served queue is optimal, then it minimizes the average waiting time μ(equivalently, the queue length) among all feasible disciplines. Part (i) formalizes the idea that the benefit from serving agents who are likely to have a high prevailing valuation does not pay off for the increased congestion when the queueing cost is high, while part (ii) lays bare the fact that the benefit from a first-come, first-served queueing discipline comes from shortening the queue. The comparative statics with respect to λare summarized in Lemma 5and Figure 3. When the resource is scarce, it is optimal to offer a single queue. A first-come, firstserved queue is suboptimal for a high enough λ. Lemma 5. Fix any admissible set of parameters (θ1,θ0,ρ0,ρ1). (i) There exists a λsuch that for λ<λ, the separating menu is not optimal. (ii) There exists a λsuch that offering a single first-come, first-served queue is suboptimal for any λ≥λ. The role of persistence is less clear-cut. On the one hand, the informational value from being served increases with persistence, making screening more valuable. On the other hand, the cost of not serving returning agents as soon as they join the queue decreases with persistence. In the extreme case, if the state becomes arbitrarily persistent, 16Because rescaling (θ1,θ0,c)amounts to rescaling payoffs but does not affect the implementable set , increasing cis equivalent to decreasing the gain from targeting the high types θ1−θ0. 642 Chiara Margaria Theoretical Economics 20 (2025) Figure 3. Comparative statics for (θ1,θ0,c)=(1, −3/4, 1/4)and ρ0=ρ1=ρ.Theshadingindicates the features of the optimal queueing discipline. all nonreneging single-queue service disciplines perform equally well. The ambiguous impact of persistence is shown in Figure 3, where for simplicity, I set ρ0=ρ1=ρ.As shown in the right panel, for some set of parameters, offering two queues is optimal only for an intermediate range of the persistence parameter ρ. While analytical results are difficult to obtain, numeral simulations suggest that the patterns identified in Figure 3 are the rule. Although the solution may be different for different objective functions, the analysis provides the tools to study the queueing discipline that minimizes waiting time or maximizes the expected return from service. In the working paper (Margaria (2021)), I show that the optimal menu can be virtually implemented, in the sense that it is possible to implement an outcome arbitrarily close to it with a single queueing discipline by taking advantage of reneging. 5. Concluding remarks I study the optimal design of a queue to allocate a resource to agents with heterogeneous preferences. In this setup, a menu to screen agents takes the form of multiple queues (or customer classes), with agents being served in a different order within each of them. The optimal menu is (at most) binary and has a simple structure. When it is optimal to offer two distinct queues, agents are served in a first-come, first-served manner in one queue and in random order in the other queue. When pooling is optimal, the single queue is either first-come, first-served or service in random order, possibly with a minimum waiting-time requirement. The analysis rests on three main assumptions: anonymity, no transfers, and learning. It can be shown that if any of the first two assumptions is dropped, it is possible to restore the first best, that is, to achieve a total payoff arbitrarily close to λθ1.17 If agents 17Each of these extensions is examined in the working paper, Margaria (2021). Theoretical Economics 20 (2025) Queueing to learn 643 observe the evolution of their state, the ranking of queueing disciplines is unambiguous: the service-in-random-order discipline dominates any other queueing discipline. If the designer is able to detect reneging, the optimal menu may involve a discipline that exposes the high-valuation agents to maximal variability in waiting time by serving at each point in time some of the newly arrived (as in a last-come, first-served queue) and some of the agents who have been waiting the longest (as in a first-come, first-served queue). The model is stylized in many respects. Some assumptions are for convenience. For instance, the optimal menu is binary even if the valuation takes more than two values, provided that the expected valuation E[θi t|θi t=θj]evolves monotonically over time. The assumption of a continuum of agents makes it possible to formulate the best-reply problem as a simple Markov decision problem. A model with a finite number of agents would allow for a finer analysis of the strategic interaction between them, beyond the general-equilibrium effect captured by the current model. However, to the extent that the problem reduces to a “two-level” optimization problem, I believe that the main insights would not be overturned in a setting with a large but finite number of agents. Allowing for variable capacity would be useful to study the welfare implications of congestion in an environment with fluctuations.18 More broadly, because of the stationarity of the environment and the independence assumption, important aspects of queueing and learning via experimentation are missing from the current model.19 For example, correlation in agents’ valuations would introduce the possibility of observational learning. Appendix A: Proofs A.1 Preliminaries This section contains the formal definition of strategies as impulse control policies. Fix amenu{Hq:q∈Q}and let (Fi t)t≥0be the filtration corresponding to the information of agent i. A strategy for agent i,i∈[0, 1], is a sequence of random times and random variables, (intervention times and impulses at these times, respectively), σ=(τk,ςk)∞ k=1, where: (i) 0 ≤τ1<τ 2<···, (ii) for any k∈N, τk=mint>τ k−1:dNi t>0,˜τk, 18Interestingly, the peer-to-peer lending platform Zopa, a two-tier queueing mechanism to allocate lenders’ funds to borrowing opportunities, prioritizes returning lenders. However, one may expect economic fluctuations to play a key role in this environment. 19Similarly, the assumption of a deterministic capacity, allows to abstract away from exogenous randomness in the service time, as would be the case if units of the good arrived stochastically. 644 Chiara Margaria Theoretical Economics 20 (2025) where ˜τkis a predictable stopping time adapted to the filtration (Fi t)t≥0(predictability enforces the informational restriction that, when queueing at t,an agent chooses the stopping time τat which he reneges conditional on the event {inf{t>t:dNi t>0}≥τ}), (iii) for any k∈N,ςk∈ˆ Qis a Fi τk-measurable random variables, and (iv) for any k∈N,ifςk=∅,thenςk+1= ∅ a.s. The strategy defines the action process (qi t,wi t)t≥0taking values in ˆ Q×R,where (qi t)t≥0is piecewise constant, qi τk=ςk,andwi t:=(t−supτk≤tτk)1qi t=∅. A.2 Proofs for Section 3 I first show that the payoff and the service rate from any stationary Markov strategy can be written as a function of a few sufficient statistics and prove the characterization of feasible statistics in Lemma 3, as stated in Section 3.3. Then I prove the results in Section 3.1 and Section 3.2. A.2.1 Proof of Lemma 2The transition matrix of the semi-Markov chain in Figure 1is ⎛ ⎜ ⎝ ρ1 ρ0+ρ1 +ρ0 ρ0+ρ1 ˆ δσ 0 ρ0 ρ0+ρ11−ˆ δσ 0 ρ1 ρ0+ρ11−ˆ δσ 1ρ1 ρ0+ρ1 +ρ0 ρ0+ρ1 ˆ δσ 1⎞ ⎟ ⎠. The chain is positive recurrent and irreducible. The unique stationary distribution is 1−m m:= ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ρ1 ρ0+ρ11−ˆ δσ 1 ρ1 ρ0+ρ11−ˆ δσ 1+ρ0 ρ0+ρ11−ˆ δσ 0 ρ0 ρ0+ρ11−ˆ δσ 0 ρ1 ρ0+ρ11−ˆ δσ 1+ρ0 ρ0+ρ11−ˆ δσ 0 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ . First, assume νσ s<∞,s=0, 1. Because any H∈Hhas no atoms at 0, there exist ε>0 and ε>0, such that Pr[Tn−Tn−1≤ε]≤1−ε. Moreover, the transition matrix is unichain. Consequently, the long-run average payoff can be computed using the evaluation equations (by Puterman (1994, Theorem 11.4.2, Chapter 11)). The long-run average payoff equals mθ1−cˆμσ 1+(1−m)θ0−cˆμσ 0 mνσ 1+(1−m)νσ 0 = ρ0 ρ0+ρ11−ˆ δσ 0θ1−cˆμσ 1+ρ1 ρ0+ρ11−ˆ δσ 1θ0−cˆμσ 0 ρ0 ρ0+ρ11−ˆ δσ 0νσ 1+ρ1 ρ0+ρ11−ˆ δσ 1νσ 0 . (10) Theoretical Economics 20 (2025) Queueing to learn 645 The time between Tnand Tn+1,forsomen∈N, is independent of n.Hence,the average number of upward jumps per unit of time converges almost surely to the inverse of the mean interarrival time (see, e.g., Asmussen (2003, Chapter V, Proposition 1.4)), that is, the service rate converges almost surely to a constant. From direct inspection of (10), the rate at which the agent collects lump sums converges almost surely to lim t→∞ 1 tNt=1 mνσ 1+(1−m)νσ 0 = ρ1 ρ0+ρ11−ˆ δσ 1+ρ0 ρ0+ρ11−ˆ δσ 0 ρ0 ρ0+ρ11−ˆ δσ 0νσ 1+ρ1 ρ0+ρ11−ˆ δσ 1νσ 0 . (11) Because the game is symmetric and I analyze the steady state, the long-run fraction of time for which the agent is queueing coincides with the length of the queue in steady state and is equal to mˆμσ,1 +(1−m)ˆμσ 0 mνσ 1+(1−m)νσ 0 = ρ0 ρ0+ρ11−ˆ δσ 0ˆμσ 1+ρ1 ρ0+ρ11−ˆ δσ 1ˆμσ 0 ρ0 ρ0+ρ11−ˆ δσ 0νσ 1+ρ1 ρ0+ρ11−ˆ δσ 1νσ 0 . Second, assume νσ s=∞for some s∈{0, 1}. In this case, the expected long-run average payoff is either −∞ or 0, depending on lim T→∞ Eσ,{Hq}q∈QT 0 1qt=∅ dt≧0. If the previous limit is 0, the long-run average payoff is 0; it diverges to −∞ otherwise. In both cases, the service rate converges almost surely to zero. A.2.2 Proof of Lemma 3Notice that the function x→ e−(ρ0+ρ1)xis convex. Thus, given a mean μ>0, the minimum value for the other statistics is achieved by the random variable that is degenerate at μ. This, together with e−(ρ0+ρ1)x<1, proves that for any H∈H, (δ,μ)∈. For the other direction, let (δ,μ)∈,δ= e−(ρ0+ρ1)μ. Consider a distribution Hthat randomizes between {ε/π,(μ−ε)/(1−π)}, with probability (π,1−π),where 0<ε<μand π>0 are chosen to satisfy πe−(ρ0+ρ1)ε/π +(1−π)e−(ρ0+ρ1)(μ−ε)/(1−π)=δ. If εwas 0, the previous equation would have a unique root π∈(0, 1). Because the left-hand side is continuous in ε,thereexistanε>0andaπ∈(0, 1)such that the equality is satisfied. Clearly, H∈H, and by construction, (δH,μH)=(δ,μ). If instead δ=e−(ρ0+ρ1)μ, the statistics of the random variable degenerate at μare (δ,μ). To show the other equivalence, let H∈HNBUE. Any NBUE random variable with mean μis smaller than Exp[μ]in the convex stochastic order,20 where Exp[μ]is the 20The random variable Xis said to be smaller than Yin the convex order if Eφ(X)≤Eφ(Y)for all convex functions φ:R→R, provided the expectation exists. 646 Chiara Margaria Theoretical Economics 20 (2025) exponential random variable with the mean μ(see Shaked and Shanthikumar (2007, Chapter 3, Theorem A.55)). Because the function x→ e−(ρ0+ρ1)xis convex, it follows that any H∈HNBUE satisfies δH≤Ee−(ρ0+ρ1)Exp(μ)=1 1+(ρ0+ρ1)μ. Consequently, any H∈HNBUE,(δH,μH)∈NBUE. To show the converse, let (δ,μ)∈ NBUE. Note that any degenerate distribution belongs to HNBUE.Forμ>0, let D(μ) denote the random variable degenerate at μ. Then, by the properties of the moment generating function, Ee−(ρ0+ρ1)(αD(μ)+(1−α)Exp(μ))=e−(ρ0+ρ1)αμ 1 1+(ρ0+ρ1)(1−α)μ. Let αbe such that e−(ρ0+ρ1)αμ 1 1+(ρ0+ρ1)(1−α)μ=δ. (12) Because δ∈[e−(ρ0+ρ1)μ,1 1+(ρ0+ρ1)μ]and the left-hand side is decreasing in α,forα∈ [0, 1], there exists a unique root αto (12)in[0, 1]. This shows that one can find a random variable Hthat is a convolution of a degenerate distribution and an exponential distribution such that (δ,μ)=(δH,μH). Because convolutions of IHR distributions are IHR, the random variable αD(μ)+(1−α)Exp(μ)is IHR, and hence it is an NBUE random variable. Because μ<∞, and neither D(μ),nor0<Exp(μ)have atoms at 0, H∈HNBUE. A.2.3 Proof of Proposition 1In the proof, I assume that {Hq}q∈Qis such that the agent has a best reply that yields strictly positive payoffs. (In light of Lemma 11, this assumption is without loss of generality.) As argued, a strategy σ∈can be described in terms of one state variable only, the posterior belief. I now introduce some notation to describe stationary Markov strategies in a way that exploits this recursivity. Fix a (pure) strategy σ∈.Foranyp∈[0, 1], define qσ:[0, 1]→ˆ Qto be such that, along the path induced by σ,qσ(pt)=qta.s. Additionally, define τσ:[0, 1]→R+so that, a.s, along the path induced by σ, τσ(p):=inf τ≥0|wt+τ−wt+τ−= 0orqt+τ= qt−|pt=p,dNt+τ=0. The maps τσand qσcompletely characterize the strategy σ∈: for any starting belief pand action (on the recurrent path induced by σ), the agent adjusts his action either after an interval of time τσ(p), or when his belief jumps, whichever occurs first. Note that, the time it takes for the belief to go from pto p, in the absence of jumps, whenever either p<p <ρ/ (ρ0+ρ1)or p>p >ρ/ (ρ0+ρ1)is ln(p)−ln p/(ρ0+ρ1) where the function :[0, 1]→Rwas defined in (8). Theoretical Economics 20 (2025) Queueing to learn 653 A.3 Proofs for Section 4 A.3.1 Preliminaries From the proof of Lemma 2(see Section A.2.1),thepayofffroma strategy σ∈satisfying the properties in Proposition 1equals (with abuse of notation) V(δˆ Hσ 0,μˆ Hσ 0,δˆ Hσ 1,μˆ Hσ 1,pσ),where V(δ0,μ0,δ1,μ1,p) :=(1−δ0)ρ0 ρ0+ρ1 +δ0p(θ1−μ1c)+(1−δ1)ρ1 ρ0+ρ1 (θ0−μ0c) (1−δ0)ρ0 ρ0+ρ1 +δ0pμ1+(1−δ1)ρ1 ρ0+ρ1μ0+1 ρ0+ρ1 lnρ0 (1−p)ρ0−pρ1, and the (a.s. limit of the) long-run service rate induced by σis equal to (with abuse of notation) limt→∞ 1 tNt=S(δˆ Hσ 0,μˆ Hσ 0,δˆ Hσ 1,μˆ Hσ 1,pσ),where S(δ0,μ0,δ1,μ1,p) := δ0p+(1−δ0)ρ0 ρ0+ρ1 +(1−δ1)ρ1 ρ0+ρ1 δ0p+(1−δ0)ρ0 ρ0+ρ1μ1+(1−δ1)ρ1 ρ0+ρ1μ0+1 ρ0+ρ1 lnρ0 (1−p)ρ0−pρ1. For later purposes, notice that the following identities hold (the decomposition in (9)is a special case of these identities): V(δ0,μ0,δ1,μ1,p) =S(δ0,μ0,δ1,μ1,p)m(δ0,δ1,p)(θ1−μ1c) +1−m(δ0,δ1,p)(θ0−μ0c), (18) S(δ0,μ0,δ1,μ1,p)=1 m(δ0,δ1,p)μ1+1−m(δ0,δ1,p)μ0+t(p), (19) where m(δ0,δ1,p):= (1−δ0)ρ0 ρ0+ρ1 +δ0p (1−δ0)ρ0 ρ0+ρ1 +δ0p+(1−δ1)ρ1 ρ1+ρ0 . (20) The next lemma shows that for any tuple of summary statistics, (δ0,μ0,δ1,μ1),there exists a unique optimal cutoff strategy within the class of nonreneging strategies. Let p∗:×→[0, ρ0/(ρ0+ρ1)] be defined as p∗(δ0,μ0,δ1,μ1) := ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ 0ifβ(δ0,μ0,δ1,μ1)≤α(μ0,μ1)−1<−1, ρ0 ρ0+ρ1 if β(δ0,μ0,δ1,μ1)≥0, or α(μ0,μ1)>0, ρ0 ρ0+ρ1 ×1−β(δ0,μ0,δ1,μ1) W−1e−1+α(μ0,μ1)β(δ0,μ0,δ1,μ1)otherwise, 654 Chiara Margaria Theoretical Economics 20 (2025) where W−1is the (negative branch of the) Lambert function and α(μ0,μ1)=− (ρ0+ρ1)θ1μ0−θ0μ1 θ1−cμ1 , β(δ0,μ0,δ1,μ1)=−ρ0(θ1−cμ1)+(1−δ1)ρ1(θ0−cμ0) δ0ρ0(θ1−cμ1). (21) The proof of Lemma 10 is a matter of tedious algebra and omitted. Lemma 10. Given (δ0,μ0,δ1,μ1)∈×, there exists a unique p∈[0, ρ0/(ρ0+ρ1)] that solves maxp∈[0,ρ0/(ρ0+ρ1)] V(δ0,μ0,δ1,μ1,p). It equals p∗(δ0,μ0,δ1,μ1). Let V∗(δ0,μ0,δ1,μ1):=V(δ0,μ0,δ1,μ1,p∗(δ0,μ0,δ1,μ1))and S∗(δ0,μ0,δ1,μ1):= S(δ0,μ0,δ1,μ1,p∗(δ0,μ0,δ1,μ1)). It is easy to see that the function V∗is Gateaux differentiable in (δ0,μ0,δ1,μ1)whenever V∗(δ0,μ0,δ1,μ1)is strictly positive. A similar remark holds for p∗(δ0,μ0,δ1,μ1)whenever interior, because it is a composition of Gateaux differentiable functions. The following fact assembles some technical results to be used later. Fact 1. Let (δ0,μ0,δ1,μ1)∈×and p∈[0, ρ0/(ρ0+ρ1))be such that V(δ0,μ0,δ1,μ1, p)>0. (i) V(δ0,μ0,δ1,μ1,p)is strictly decreasing in μ0,μ1,andδ0, and strictly increasing in δ1. (ii) p∗(δ0,μ0,δ1,μ1)is increasing in μ0and μ1, increasing in δ0(strictly if interior), and decreasing in δ1. Lemma 10 has an immediate important consequence: the designer can always guarantee that the aggregate payoff is strictly positive by offering a single service-in-randomorder queue. The result is formalized in the following lemma whose proof is omitted. Lemma 11. For any set of admissible parameters (θ1,θ0,c,ρ0,ρ1,λ)∈R++ ×R++ ×R+× R++ ×R++, there exists an equilibrium (σ,H)∈×Hthat yields a strictly positive payoff. A.3.2 Proof of Theorem 2Whenever the cutoff belief in Lemma 10 is interior, it satisfies the first-order condition V(δ0,μ0,δ1,μ1,p)=θ1−cμ1 μ1+ρ1 ρ0+ρ1 1−δ1 δ0 1 (1−p)ρ0−pρ1 . (22) For convenience, let κ(δ0,μ0,δ1,μ1) :=1−δ1 δ0 1 1−p∗(δ0,μ0,δ1,μ1)ρ0−p∗(δ0,μ0,δ1,μ1)ρ1 , (23) Theoretical Economics 20 (2025) Queueing to learn 655 so that, when the optimal cutoff is interior, the following identity holds: mδ0,δ1,p∗(δ0,μ0,δ1,μ1) = 1 1−δ1 ρ0 ρ0+ρ1 −1 (ρ0+ρ1)κ(δ0,μ0,δ1,μ1) 1 1−δ1 ρ0 ρ0+ρ1 +ρ1 ρ1+ρ0 −1 (ρ0+ρ1)κ(δ0,μ0,δ1,μ1) . (24) I shall refer to these three equalities several times in the remainder of the proof, in addition to the payoff decomposition in (18)andtoFact1. A.3.2.1 Relaxed problem I start by solving the relaxed program maxV∗δH0,μH0,δH1,μH1(RP) over (δH0,μH0)∈and (δH1,μH1)∈NBUE subject to V∗δH0,μH0,δH1,μH1≥V∗δH1,μH1,δH1,μH1,(IC-θ0) V∗δH0,μH0,δH1,μH1≥V∗δH0,μH0,δH0,μH0,(IC-θ1) S∗δH0,μH0,δH1,μH1≤λ.(C) I first state the solution of the program (RP), then conclude the proof of Theorem 2,and finally present the proof of the maximization. Lemma 12. There exists a solution to (RP). It is such that (C) binds and either of the following holds: (i) δH0=δH1and μH0=μH1; (ii) δH0=e−(ρ0+ρ1)μH0,μH0>μ H1,andδH1=1/(1+(ρ0+ρ1)μH1),and(IC-θ0)is binding. A.3.2.2 Conclusion of the proof of Theorem 2It remains to prove that in the case of a separating menu, agents have no incentives to renege. Since H0is degenerate, restarting is suboptimal. The distribution H1is memoryless; hence, no agent can strictly benefit from restarting. Because μH1≤μH1and δH0<δ H1, any agent with a belief above the invariant probability prefers H1to H0; thus, even along an arbitrarily long history with no service, the high type does not find it optimal to leave his queue and join the queue H0. A.3.2.3 Proof of Lemma 12 First, I formulate the domain restrictions (δH0,μH0)∈ and (δH1,μH1)∈NBUE as explicit constraints: e−(ρ0+ρ1)μH1−δH1≤0, (WB-1) e−(ρ0+ρ1)μH0−δH0≤0, (WB-0) δH1−1 1+(ρ0+ρ1)μH1≤0. (EB-1) 656 Chiara Margaria Theoretical Economics 20 (2025) Define the Lagrangian function as LδH0,μH0,δH1,μH1,η=V∗δH0,μH0,δH1,μH1+η1λ−S∗δH0,μH0,δH1,μH1 +η2V∗δH0,μH0,δH1,μH1−V∗δH1,μH1,δH1,μH1 +η3V∗δH0,μH0,δH1,μH1−V∗δH0,μH0,δH0,μH0 +η4δH0−e−(ρ0+ρ1)μH0+η51 1+(ρ0+ρ1)μH1−δH1 +η6δH1−e−(ρ0+ρ1)μH1, where η∈R6 +is a vector of multiplier. If (δ∗ 0,μ∗ 0,δ∗ 1,μ∗ 1)∈(0, 1)×(0, ∞)×(0, 1)×(0, ∞) and η∗≥0,η∗= 0are such that (i) the constraints (IC-θ1), (IC-θ0), (C), (WB-1), (WB-0), (EB-1), and the complementary slackness conditions are satisfied; (ii) L(δH0 ∗,μH0 ∗,δH1 ∗,μH1 ∗,η∗)≥L(δH0,μH0,δH1,μH1,η∗),forany(δH0,μH0,δH1, μH1)∈(0, 1)×(0, ∞)×(0, 1)×(0, ∞), then (δH0 ∗,μH0 ∗,δH1 ∗,μH1 ∗)is optimal. In the following, I first derive qualitative properties of any (δH0,μH0,δH1,μH1)∈(0, 1)×(0, ∞)×(0, 1)×(0, ∞)satisfying (i) and (ii). It is then easy to show that for any set of parameters, such a pair exists and the optimal (δH0,μH0,δH1,μH1)must satisfy the conditions in the statement of Lemma 12. First, assume, throughout the following claims, that (δH0,μH0,δH1,μH1)∈(0, 1)× (0, ∞)×(0, 1)×(0, ∞). Claim 1. If (δH0,μH0,δH1,μH1)satisfies (IC-θ0)and(IC-θ1), δH0≤δH1. Proof. By the average cost optimality equations, there exists a unique (up to an additive constant) map u:{0, 1}→Rand a unique V∗∈Rsuch that u(0)=max (δ,μ)−V∗μ−cμ +δp∗δH0,μH0,δH1,μH1+(1−δ)ρ0 ρ0+ρ1 ×θ1+u(1)−θ0−u(0) +θ0+u(0), u(1)=max (δ,μ)−V∗μ−cμ +δ+(1−δ)ρ0 ρ0+ρ1θ1+u(1)−θ0−u(0)+θ0+u(0), where the maxima are taken over (δ,μ)∈{(δH0,μH0),(δH1,μH1)}. Clearly, u(0)<u (1). It is easy to check that, for (IC-θ0)and(IC-θ1) to be satisfied, δH0≤δH1. Claim 2. If (δH0,μH0,δH1,μH1)satisfies (IC-θ0), δH0<δ H1,μH1≤μH0,andS∗(δH0, μH0,δH1,μH1)<S ∗(δH1,μH1,δH1,μH1),thenp∗(δH0,μH0,δH1,μH1)=0. Theoretical Economics 20 (2025) Queueing to learn 657 Proof. Proceeding by contradiction, assume that p∗(δH0,μH0,δH1,μH1)>0. First, I show that this implies p∗(δH1,μH1,δH1,μH1)>0. In fact, because the right-hand side of (22) is strictly increasing in δH0and strictly decreasing in p,foranyh=(hδH0,hμH0,0,0 ), hδH0>0andhμ0≤0suchthat∇V∗(δH0,μH0,δH1,μH1)·h≤0, ∇p∗(δH0,μH0,δH1,μH1)· h>0. As a result, (IC-θ0) implies that if p∗(δH0,μH0,δH1,μH1)>0, p∗(δH1,μH1,δH1, μH1)>0. Second, by (22), (IC-θ0)implies κδH0,μH0,δH1,μH1≤κδH1,μH1,δH1,μH1 mδH0,δH1,p∗δH0,μH0,δH1,μH1≤mδH1,δH1,p∗δH1,μH1,δH1,μH1. Since μH1≤μH0, it follows that S∗(δH1,μH1,δH1,μH1)≤S∗(δH0,μH0,δH1,μH1),acontradiction. Claim 3. If (δH0,μH0,δH1,μH1)solves (RP)andμH0<μ H1,thenp∗(δH0,μH0,δH1, μH1)=0. Proof. First, notice that μH0<μ H1and (IC-θ1) imply that (IC-θ0) is slack. Assume that p∗(δH0,μH0,δH1,μH1)>0, so that the first-order conditions hold. Consider a change along a direction h=(0, hμH0,0,hμH1),hμ0>0, hμ1<0suchthat mδH0,δH1,p∗δH0,μH0,δH1,μH1hμH1 +1−mδH0,δH1,p∗δH0,μH0,δ1,μH1hμH0=0 If ∇V∗(δH0,μH0,δH1,μH1)·h≤0, (22)implies∇κ(δH0,μH0,δH1,μH1)·h>0and ∇p(δH0,μH0,δH1,μH1)·h>0. Hence, ∇S∗(δH0,μH0,δH1,μH1)·h<0. As a result, one can find h μH1such that ∇S∗δH0,μH0,δH1,μH1·0, hμH0,0,h μH1=0, ∇V∗δH0,μH0,δH1,μH1·0, hμH0,0,h μH1>0. If instead ∇S∗(δH0,μH0,δH1,μH1)·h>0, let h μH0>h μH0be such that ∇S∗(δH0,μH0, δH1,μH1)·(0, h μH0,0,hμH1)=0.Bythefirstpartoftheproof,∇V∗(δH0,μH0,δH1,μH1)· h>0, contradicting the optimality of (δH0,μH0,δH1,μH1). Claim 4. If (δH0,μH0,δH1,μH1)solves (RP), (δH0,μH0)= (δH1,μH1),andp∗(δH0,μH0, δH1,μH1)=0,then(WB-0)and(EB-1)arebinding. Proof. Suppose first that (WB-0) is slack. In this case, ∂S∗δH0,μH0,δH1,μH1 ∂δ0 =− μH0−μH1ρ0 1−δH0ρ0+1−δH1ρ1 ∂S∗δH0,μH0,δH1,μH1 ∂μ0 , (25) 658 Chiara Margaria Theoretical Economics 20 (2025) and ∂V ∗δH0,μH0,δH1,μH1 ∂δ0 =− μH0θ1−μH1θ0ρ0 1−δH0ρ0θ1+1−δH1ρ1θ0 ∂V ∗δH0,μH0,δH1,μH1 ∂μ0 . (26) Because θ0<0<θ 1,21 μH0−μH1ρ0 1−δH0ρ0+1−δH1ρ1 <μH0θ1−μH1θ0ρ0 1−δH0ρ0θ1+1−δH1ρ1θ0 . (27) Since ∂V ∗δH0,μH0,δH1,μH1 ∂μ0 <0, ∂S∗δH0,μH0,δH1,μH1 ∂μ0 <0, there exists a direction h=(hδH0,hμH0,0,0 ),hδH0<0, hμ0>0, along which ∇S∗δH0,μH0,δH1,μH1·h≤0, ∇V∗δH0,μH0,δH1,μH1·h>0. Because along the direction hall other constraints are either unchanged or relaxed, at the optimum, (WB-0) must bind. Assume next that (EB-1)isslack.Since, ∂S∗δH0,μH0,δH1,μH1 ∂δ1 =μH0−μH1ρ1 1−δH0ρ0+1−δH1ρ1 ∂S∗δH0,μH0,δH1,μH1 ∂μ1 , ∂V ∗δH0,μH0,δH1,μH1 ∂δ1 =μH0θ1−μH1θ0ρ1 1−δH0ρ0θ1+1−δH1ρ1θ0 ∂V ∗δH0,μH0,δH1,μH1) ∂μ1 , by (27), there exists a direction h=(0, 0, hδH1,hμH1),hδH1>0andhμ1>0, along which all constraints are relaxed or unchanged and the objective function is increased. Hence, (EB-1) must bind at the optimum. Claim 5. If (δH0,μH0,δH1,μH1)solves (RP), p∗(δH0,μH0,δH1,μH1)=0,and(WB-1)is slack, (IC-θ0)binds. 21In light of the definition of G(δH0,μH0,δH1,μH1,p), for any candidate optimal tuple (δH0,μH0,δH1,μH1), the denominator of the term on the right-hand side of equation (27) is strictly positive. For otherwise, the aggregate payoffs would be strictly negative, for any strategy that prescribes queueing with positive probability. Theoretical Economics 20 (2025) Queueing to learn 659 Proof. Assume by contradiction that (IC-θ0)isslack.Leth=(hδH0,hμH0,0,0 ),hδH0< 0, hμ0>0beadirectionsuchthat 22 hδH0+(ρ0+ρ1)e−(ρ0+ρ1)μ0hμ0=0. (28) Assume first that ∇V∗(δH0,μH0,δH1,μH1)·h<0. Then, by (25)–(27), ∇S∗(δH0,μH0,δH1, μH1)·h<0. Let then hμH1<0besuchthat∇S∗(δH0,μH0,δH1,μH1)·(hδH0,hμH0,0, hμH1)=0. Because ∂m(δH0,δH1,p)/∂δH0<0, if ∇S∗(δH0,μH0,δH1,μH1)·h=0, ∇V∗(δH0,μH0,δH1,μH1)·h>0. As no constraint is violated along that direction, this contradicts the optimality of (δH0,μH0,δH1,μH1). Assume next that ∇V∗(δH0,μH0,δH1, μH1)·h>0. Again, by (25)–(27), it is possible to find a direction h=(h δH0,h μH0,0,0 ) that does not violate (WB-0)andsuchthat∇S∗(δH0,μH0,δH1,μH1)·h=0and∇V∗(δH0, μH0,δH1,μH1)·h>0. As no constraint is violated along that direction, this contradicts the optimality of (δH0,μH0,δH1,μH1). Claim 2and Claim 3implythatatanyoptimal(δH0,μH0,δH1,μH1),(δH0,μH0)= (δH1,μH1),p∗(δH0,μH0,δH1,μH1)=0. Hence, by Claim 4, at any optimal such a (δH0,μH0,δH1,μH1),(WB-0)and(EB-1) are binding. As when (EB-1) is binding, (WB-1) is slack, Claim 5implies that (IC-θ0) binds, which implies μH0>μ H1. It remains to prove that (C) binds at any such optimal (δH0,μH0,δH1,μH1). Claim 6. If (δH0,μH0,δH1,μH1)is optimal, p∗(δH0,μH0,δH1,μH1)=0,δH0<δ H1,and (IC-θ0) binds, the constraint (C)binds. Proof. Consider a direction h=(hδH0,hμH0,0,0 ),hδH0>0, and hμ0<0suchthat hδH0+(ρ0+ρ1)δH0hμ0=0. It can be checked that ∂V ∗δH0,μH0,δH1,μH1 ∂δ0 =μH0θ1−μH1θ0ρ0 1−δH0ρ0θ1+1−δH1ρ1θ0 ∂V ∗δH0,μH0,δH1,μH1 ∂μ0 <0. Since p∗(δH0,μH0,δH1,μH1)=0, μH0θ1−μH1θ0ρ0 1−δH0ρ0θ1+1−δH1ρ1θ0 <1 (ρ0+ρ1)δH0. As a result, ∇V∗(δH0,μH0,δH1,μH1)·h>0. If (C) does not bind, no constraint is violated along the direction h, contradicting the optimality of (δH0,μH0,δH1,δH1). Claim 7. If (δ,μ,δ,μ)is optimal, (C)binds. 22The restriction (28)takescareof(WB-0). 660 Chiara Margaria Theoretical Economics 20 (2025) Proof. Assume (C)doesnotbind.Ife−(ρ0+ρ1)μ<δ,sothat(WB-1)and(WB-0)areslack, consider a direction h=(0, hμ,0,hμ),hμ<0. The fact that ∇V∗(δ,μ,δ,μ)·h>0contradicts the optimality of (δ,μ,δ,μ). Consider next the case in which δ=e−(ρ0+ρ1)μand consider a direction h=(hδ,0,hδ,0 ),hδ>0. It is verified that ∂mδ,δ,p∗(δ,μ,δ,μ) ∂δ0 +∂mδ,δ,p∗(δ,μ,δ,μ) ∂δ1 >0 ∂δ,μ,δ,μ,p∗(δ,μ,δ,μ) ∂δ0 +∂δ,μ,δ,μ,p∗(δ,μ,δ,μ) ∂δ1 >0. Since the change p∗(δ,μ,δ,μ)can be neglected (as follows from the envelope theorem), ∇V∗(δ,μ,δ,μ)·h>0, yielding the desired contradiction. A.3.3 Proof of Theorem 1First, I show when c=0, service-in-random-order is the best discipline when the designer is constrained to offer a single nonreneging queueing discipline. Second, I show that there exist a menu that outperforms the best service-inrandom-order discipline. Let (δ,μ)∈NBUE and h=(hδ,hμ,hδ,hμ)∈R4 ++ be a direction such that ∇V∗(δ,μ, δ,μ)·h=0. There are two cases. If ρ0θ1+ρ1θ0>0, the optimal cutoff p(v,μ,δ,μ) is strictly increasing in δand μ. Since for fixed p,∇m(δ,δ,p)·h>0andm(δ,δ,p)is strictly increasing in p, ∇mδ,δ,p∗(δ,μ,δ,μ)·h+∂mδ,δ,p∗(δ,μ,δ,μ) ∂p ∇p∗(δ,μ,δ,μ)·h>0. (29) By (18), ∇V∗(δ,μ,δ,μ)·h=0onlyif∇S∗(δ,μ,δ,μ)·h<0. Next, I show that even if ρ0θ1+ρ1θ0≤0, (29) holds. To do so, I rewrite the agent’s best reply problem in Lemma 10 as a choice over minstead of a choice over optimal cutoffs p.Thatis,given (δ,μ)∈, there exists a unique m∈(0, 1)that solves max m∈[ρ0/(ρ0+ρ1),ρ0/(ρ0+(1−δ)ρ1)) mθ1+(1−m)θ0 μ+(1−m)1 ρ0+ρ1 ln(1−m)δρ0 (1−m)ρ0−(1−δ)mρ1 The first-order conditions read (1−δ)mθ1+(1−m)θ0ρ1 ρ0+ρ1 −(θ1−θ0)μ+θ1 ρ0+ρ1 ln(1−m)δρ0 (1−m)ρ0−(1−δ)mρ1(1−m)ρ0−(1−δ)mρ1=0. It can be shown that the left-hand side the equation above is decreasing in δand μ, and, using the assumption ρ0θ1+ρ1θ0≤0, it is increasing in m.Hence,bytheimplicit function theorem, along a direction h=(hδ,hμ,hδ,hμ)∈R4 ++,(29)musthold,and again, by (18), ∇V∗(δ,μ,δ,μ)·h=0onlyif∇S∗(δ,μ,δ,μ)·h<0. As a result, the optimal pair (δ,μ)∈NBUE must lie at the east boundary of the set NBUE. Otherwise, one could increase welfare by increasing δand μwithout violating the capacity constraint. Theoretical Economics 20 (2025) Queueing to learn 661 To find the first-come first-served/service-in-random-order menu that outperforms the best single service-in-random-order queue, I show that the following system, which identifies a candidate optimal menu, has a solution: (1−δ0)ρ0 ρ0+ρ1 θ1+(1−δ1)ρ1 ρ0+ρ1 θ0 (1−δ0)ρ0 ρ0+ρ1 1−δ1 (ρ0+ρ1)δ1 +(1−δ1)ρ1 ρ0+ρ1 ln(1/δ0) ρ0+ρ1 =δ1θ1 1−δ1 ρ0+ρ1 +ρ1 ρ0+ρ1 1−δ1 ρ0−(ρ0+ρ1)p∗1−δ1 (ρ0+ρ1)δ1 ,δ1,1−δ1 (ρ0+ρ1)δ1 ,δ1 , (30) (1−δ0)ρ0 ρ0+ρ1 +(1−δ1)ρ1 ρ0+ρ1 (1−δ0)ρ0 ρ0+ρ1 1−δ1 (ρ0+ρ1)δ1 +(1−δ1)ρ1 ρ0+ρ1 ln(1/δ0) ρ0+ρ1 =λ, (31) 0≤(1−δ0)ρ0 ρ0+ρ1 θ1+(1−δ1)ρ1 ρ0+ρ1 θ0−ρ0δ0θ1 ln(1/δ0) ρ0+ρ1 −θ0 1−δ1 (ρ0+ρ1)δ1. (32) For a fixed δ0∈(0, 1), the left-hand side of (31) is increasing in δ1, tends to infinity as δ1→1, and to 0 as δ1→0. As a result, there exists a continuous curve C⊂(0, 1)2,the first and second coordinates corresponding to δ0and δ1, respectively, that is a solution to (31). It is easy to see that {(0, 1),(1, 0)}⊂C. For a fixed δ1∈(0, 1), the left-hand side of (32) is decreasing in δ0;letD0∈(0, 1)2 be the set of points that satisfy (32)asequality. DenotebyD0the set of points lying on or above the curve D0. The left-hand side of (30) is increasing in δ0if and only if (δ0,δ1)∈D0. Hence, there exists a continuous curve D⊂D0that solves (30). Because {(0, 0),(1, 1)}⊂D, by the intermediate value theorem, the two curves Dand Ccross and (δ0,δ1)∈C∩D⊂D0solves the system of (30)–(32). Any solution to the system describes an incentive-compatible and feasible menu such that agents have incentive to join the first-come first-served queue as soon as their belief jumps to zero. By Lemma 13,forany(δ0,δ1)∈C∩D, mδ0,δ1,p∗δ1,1−δ1 (ρ0+ρ1)δ1 ,δ1,1−δ1 (ρ0+ρ1)δ1<m (δ0,δ1,0 ), which implies that S∗δ0,ln(1/δ0) ρ0+ρ1 ,δ1,1−δ1 (ρ0+ρ1)δ1<S ∗δ1,1−δ1 (ρ0+ρ1)δ1 ,δ1,1−δ1 (ρ0+ρ1)δ1. That is, the service-in-random-order discipline which yields the same payoff as a candidate menu is unfeasible. Consequently, the best feasible service-in-random-order discipline is outperformed by any candidate menu that solves (30)–(32). Lemma 13. Suppose δ0∈(0, 1)and δ1∈(0, 1)solves (30)–(32)andV∗(δ,ln(1/δ0)/(ρ0+ ρ1),δ1,1−δ1/((ρ0+ρ1)δ1)) >0.Then m∗δ1,δ1,p∗δ1,1−δ1 (ρ0+ρ1)δ1 ,δ1,1−δ1 (ρ0+ρ1)δ1<m (δ0,δ1,0 ). 662 Chiara Margaria Theoretical Economics 20 (2025) Proof. One can check that for any δ1∈(0, 1),p∗(δ1,1−δ1/((ρ0+ρ1)δ1),δ1,1−δ1/ ((ρ0+ρ1)δ1))>0 and, by assumption, p∗(1−δ1/((ρ0+ρ1)δ1),δ1,1−δ1/((ρ0+ρ1)δ1), δ1)<ρ 0/(ρ0+ρ1), so the first-order condition holds. Hence, δ0·ρ0 ρ0+ρ1 <δ 1ρ0 ρ0+ρ1 −p∗1−δ1 (ρ0+ρ1)δ1 ,δ1,1−δ1 (ρ0+ρ1)δ1 ,δ1 The result follows from the definition of m(δ0,δ1,p). A.3.4 Proof of Lemma 4 A.3.4.1 Proof of (i) First, when the candidate menu is optimal, the total payoff is bounded above by λθ1−c, which is negative for c>λθ 1. However, as shown after Fact 1, the designer can always guarantee that the aggregate payoff is strictly positive by offering a single service-in-random-order queue. Hence, the separating menu cannot be optimal for sufficiently high c. Second, I show that for sufficiently high c, service-in-random-order is not optimal even if the designer is constrained to a single nonreneging queue. Let (δSIRO c,μSIRO c)be the statistics of the best feasible service-in-random-order queue when the queueing cost is c.Thatis, S∗δSIRO c,μSIRO c,δSIRO c,μSIRO c=λ,μSIRO c=1−δSIRO c (ρ0+ρ1)δSIRO c . (By Lemma 11, this system has a solution for any c>0.) Claim 8. The following hold: (i) limc→∞ δSIRO c=1; (ii) limc→∞ p∗(δSIRO c,μSIRO c,δSIRO c,μSIRO c)=ρ0/(ρ0+ρ1). Proof.First,(δ,μ,δ,μ,p)is strictly decreasing in pwhen evaluated at p∗(δ,μ)and δ,(1−δ)/(ρ0+ρ1)δ,δ,(1−δ)/(ρ0+ρ1)δ,p is strictly increasing in δ. Second, for a fixed (δ,μ),thefunctionp∗(δ,μ,δ,μ)is increasing in cand p∗δ,(1−δ)/(ρ0+ρ1)δ,δ,(1−δ)/(ρ0+ρ1)δ is decreasing in δ, in both cases strictly if the cutoff belief is interior. Additionally, p∗(δSIRO c,μSIRO c,δSIRO c,μSIRO c)>0 (see proof of Lemma 11). Hence, (i) follows by the implicit function theorem. To show (ii), notice that as c→∞,S∗(δSIRO c,μSIRO c,δSIRO c,μSIRO c) is bounded only if −ln (p∗(δSIRO c,μSIRO c,δSIRO c,μSIRO c)) →∞,thatis,ifp∗(δSIRO c,μSIRO c, δSIRO c,μSIRO c)→ρ0/(ρ0+ρ1).