The concert queueing game: to wait or to be late

Abstract

We introduce the concert (or cafeteria) queueing problem: A finite but large number of customers arrive into a queueing system that starts service at a specified opening time. Each customer is free to choose her arrival time (before or after opening time), and is interested in early service completion with minimal wait. These goals are captured by a cost function which is additive and linear in the waiting time and service completion time, with coefficients that may be class dependent. We consider a fluid model of this system, which is motivated as the fluid-scale limit of the stochastic system. In the fluid setting, we explicitly identify the unique Nash-equilibrium arrival profile for each class of customers. Our structural results imply that, in equilibrium, the arrival rate is increasing up until the closing time where all customers are served. Furthermore, the waiting queue is maximal at the opening time, and monotonically decreases thereafter. In the simple single class setting, we show that the price of anarchy (PoA, the efficiency loss relative to the socially optimal solution) is exactly two, while in the multi-class setting we develop tight upper and lower bounds on the PoA. In addition, we consider several mechanisms that may be used to reduce the PoA. The proposed model may explain queueing phenomena in diverse settings that involve a pre-assigned opening time.

Appendix A

Here we first present proofs for some propositions stated above, and then discuss some supplementary results to Section 6.3 related to reduction in PoA through charging tariffs.

1.1 Proofs for Sections 4.2 and 6.1

A.1 Proof of Proposition 2

Recall that the social cost is defined as the sum of costs of all customers, at a given arrival profile. Consider the equilibrium arrival profile that was computed in Section 4.1. Since the equilibrium cost C _i (t) is the same for all members of each class, say C _i , we obtain

$$ \label{Jeq1} J_{\rm eq} = \sum\limits_i \Lambda_i C_i \,. $$

(29)

The cost C _i may be computed in any point in [T _i − 1,T _i ]. Picking T _i , we get

$$ C_i=C_i(T_i) = (\alpha_i+\beta_i)\frac{F(T_i)}{\mu} - \alpha_i T_i \,. $$

It will be convenient to express this as

$$ \mu C_i = \beta_i F(T_i) +\alpha_i(F(T_i) -\mu T_i) \,. $$

Substituting T _i and F(T _i ) from Eqs. 11 and 12, we get

$$ \mu C_i = \beta_i \sum\limits_{j=1}^{i} \Lambda_j +\alpha_i \left(\Lambda - \sum\limits_{j=i+1}^{n} \Lambda_j -\Lambda + \sum_{j=i+1}^{n}\Lambda_j \frac{\alpha_j+\beta_j}{\alpha_j}\right) $$

(30)

$$ = \beta_i \sum\limits_{j=1}^{i} \Lambda_j +\alpha_i \sum\limits_{j=i+1}^{n}\Lambda_j \frac{\beta_j}{\alpha_j} \,. $$

(31)

Note that we can observe three distinct components in this expression. The right most sum is the influence of later arrivals (customer classes with j > i) on class i. The influence of customer classes that arrive earlier (j < i) is summarized by the preceding term, summed up to i − 1. The remaining term β _i Λ _i expresses the effect of competition within class i customers.

Substituting the last expression in Eq. 29, we obtain

$$ \label{eq_cost} J_{\rm eq} = \sum\limits_i \Lambda_i C_i = \sum\limits_i \frac{\Lambda_i}{\mu} \left(\beta_i \sum\limits_{j=1}^{i} \Lambda_j + \alpha_i \sum\limits_{j=i+1}^{n}\Lambda_j \frac{\beta_j}{\alpha_j} \right)\,. $$

(32)

To obtain the required (more symmetric) form of J _eq, note that the ratio $\frac{\beta_i}{\alpha_i}$ is decreasing in i (since the opposite holds for m _i by assumption). Therefore,

$$\begin{array}{rll} J_{\rm eq} &=& \frac{1}{\mu} \sum\limits_{i=1}^I \Lambda_i\Lambda_j \alpha_i\left( \sum\limits_{j=1}^i \frac{\beta_i}{\alpha_i} + \sum\limits_{j=i+1}^I \frac{\beta_j}{\alpha_j}\right) \\ &=& \frac{1}{\mu} \sum\limits_{i,j=1}^I \Lambda_i\Lambda_j \alpha_i \min\left\{\frac{\beta_i}{\alpha_i},\frac{\beta_j}{\alpha_j}\right\} \,, \end{array} $$

(33)

as claimed. We observe that the latter expression is independent of ordering of the classes.

We next turn to the optimal social cost J _opt, which is obtained by optimizing the arrival times and server allocation for all customers. Here there would be no queues, as each customer can arrive exactly when her turn to be served arrives. It may then be seen through a simple interchange argument that the optimal ordering of arrivals between classes is in decreasing order of β _i . Let σ(i) be an index permutation so that β _σ(1) ≥ ... ≥ β _σ(n). Then, class σ(i) customers arrive uniformly with rate μ between τ _i − 1 and τ _i , where $\tau_i=\mu^{-1}\sum_{j=1}^{i} \Lambda_{\sigma(j)}$. The overall cost for this class becomes

$$ J_i = \Lambda_{\sigma(i)} \beta_{\sigma(i)} \frac{T_{i-1}+T_i}{2} = \frac{\Lambda_{\sigma(i)}}{\mu} \beta_{\sigma(i)} \left(\sum\limits_{j=1}^{i-1} \Lambda_{\sigma(j)}+\frac{1}{2}\Lambda_{\sigma(i)}\right) $$

so that

$$ \label{opt_cost} J_{\rm opt} = \sum\limits_i J_i = \sum\limits_{i=1}^I \frac{\Lambda_{\sigma(i)}}{\mu} \beta_{\sigma(i)} \left(\sum\limits_{j=1}^{i-1} \Lambda_{\sigma(j)}+\frac{1}{2}\Lambda_{\sigma(i)} \right). $$

(34)

Again, we can express J _opt in a more symmetric form. Indeed,

$$ J_{\rm opt} = \frac{1}{2\mu} \sum\limits_{i=1}^I \Lambda_{\sigma(i)} \left(\sum\limits_{j=1}^{i-1} \Lambda_{\sigma(j)} \beta_{\sigma(i)} + \Lambda_{\sigma(i)} \beta_{\sigma(i)} +\sum_{j=i+1}^{I}\Lambda_{\sigma(j)} \beta_{\sigma(j)} \right) $$

(35)

$$ = \frac{1}{2\mu} \sum\limits_{i,j=1}^I \Lambda_{\sigma(i)}\Lambda_{\sigma(j)} \min\{\beta_{\sigma(i)},\beta_{\sigma(j)}\} $$

(36)

where the first equality follows by splitting the last sum in Eq. 34 into two equal terms and changing order of summation in one of them, and the second equality follows since β _σ(i) is decreasing in i. Now, it may be seen that the last expression does not depend on the permutation σ, hence we can remove the permutation and finally obtain Eq. 14. □

Proof of Proposition 3

Item (i) is immediate from Eq. 17. As for (ii), from the same equation we obtain the upper bound

$$ {\rm PoA} = 2 \frac{\sum_{i,j=1}^I \Lambda_i\Lambda_j \min\big\{1,\frac{\alpha_i}{\alpha_j}\big\}}{\sum_{i,j=1}^I \Lambda_i\Lambda_j } \, \leq 2. $$

(37)

On the other hand, proceeding from the last expression and recalling that α _i  ≤ α _j for i < j,

$$ {\rm PoA} = 2 - \frac{2 \sum_{i,j=1}^I \Lambda_i\Lambda_j \big(1-\min\big\{1,\frac{\alpha_i}{\alpha_j}\big\}\big)}{\sum_{i,j=1}^I \Lambda_i\Lambda_j } $$

(38)

$$ = 2 - \frac{2 \sum_{i<j} \Lambda_i\Lambda_j \big(1-\frac{\alpha_i}{\alpha_j}\big)}{\sum_{i,j=1}^I \Lambda_i\Lambda_j } $$

(39)

$$ \geq 2 - \frac{\max_{i,j} \big(1-\frac{\alpha_i}{\alpha_j}\big)\cdot 2\sum_{i<j} \Lambda_i\Lambda_j }{\sum_{i,j=1}^I \Lambda_i\Lambda_j } $$

(40)

$$ =2 - \left(1-\frac{\alpha_{\min}}{\alpha_{\max}}\right)\frac{ \sum_{i\not=j}\Lambda_i\Lambda_j} {\big(\sum_{i}^I \Lambda_i\big)^2 }. $$

(41)

It is easily verified that the last fraction is maximized when all the Λ _i ’s are equal, and in that case it equals (I − 1)/I. Hence follows the lower bound in Eq. 19. □

Proof of Proposition 4

The bounds in Eq. 20 follow immediately after noting that, by collecting terms, Eq. 17 may be written as:

$$ {\rm PoA} = 2 \frac{\sum_{i} \beta_i\Lambda_i^2+\sum_{i<j} \Lambda_i\Lambda_j (\alpha_i+\alpha_j) \min\big\{\frac{\beta_i}{\alpha_i},\frac{\beta_j}{\alpha_j}\big\}} {\sum_{i}\beta_i \Lambda_i^2 +\sum_{i<j} \Lambda_i\Lambda_j 2\min\{\beta_i,\beta_j\}} $$

so that H(i,j) is the ratio of the coefficients of the i,j terms. The remaining bounds follow by appropriately bounding H(i,j). As for Eq. 21, assuming that β _i  ≤ β _j we get

$$ 2H(i,j) = \frac{(\alpha_i+\alpha_j)\min\big\{\frac{\beta_i}{\alpha_i},\frac{\beta_j}{\alpha_j}\big\}} {\beta_i} \leq \frac{(\alpha_i+\alpha_j)\frac{\beta_i}{\alpha_i}}{\beta_i} = 1+\frac{\alpha_j}{\alpha_j} \leq 1+ \frac{\alpha_{\max}}{\alpha_{\min}} $$

(the case β _i  > β _j is symmetric since H(i,j) = H(j,i)). As for Eq. 22, supposing that $\frac{\beta_i}{\alpha_i}\leq \frac{\beta_j}{\alpha_j}$, we get

$$ 2H(i,j) = \frac{\alpha_i\frac{\beta_i}{\alpha_i}+\min\big\{\frac{\alpha_j \beta_i}{\alpha_i},{\beta_j}\big\}} {\min\{\beta_i,\beta_j\}} \leq \frac{\beta_i+\beta_j}{\min\{\beta_i,\beta_j\}} \leq 1+ \frac{\beta_{\max}}{\beta_{\min}}. $$

Finally, to establish Eq. 23, consider again that β _i  ≤ β _j so that

$$ \begin{array}{rll} 2H(i,j) &=& (\alpha_i+\alpha_j)\min\left\{\frac{1}{\alpha_i},\frac{1}{\alpha_j}\frac{\beta_j}{\beta_i}\right\} \\ &=& \min\left\{1+\frac{\alpha_j}{\alpha_i},\left(1+\frac{\alpha_i}{\alpha_j}\right)\frac{\beta_j}{\beta_i}\right\} \geq \left(1+\frac{\alpha_{\min}}{\alpha_{\max}}\right)\frac{\beta_{\min}}{\beta_{\max}}. \end{array} $$

□

Proof of Proposition 5

From Eqs. 14 and. 15, we have

$$ \label{toBound} {\rm PoA} \leq \frac{2\sum_{i,j=1}^I \Lambda_i\Lambda_j \beta_i} {\sum_{i,j=1}^I \Lambda_i\Lambda_j \min\{\beta_i,\beta_j\}}. $$

(42)

We proceed to bound he last expression, by computing its maximum over $\boldsymbol{\Lambda}\geq 0$, where $\boldsymbol{\Lambda}=(\Lambda_1,\dots,\Lambda_I)$.

Let us reorder the class indices so that β ₁ < β ₂ < ... < β _I (in case there are equal coefficients we can collapse them into a single class). Denote the right-hand side of Eq. 42 by Λ, and let Λ and Λ denote the nominator and denominator of that expression. We will show that the maximum of F is attained when Λ₂ = ... = Λ_I − 1 = 0 and $\Lambda_1/\Lambda_I=\sqrt{\beta_I}/\sqrt{b1}$. The required bound is then the value of F at this point.

A maximizer Λ of F must satisfy

$$ F^{\prime}_k({\mathbf \Lambda})\stackrel{\triangle}{=} \frac{\partial F({\mathbf \Lambda})}{\partial \lambda_k} \leq 0,\quad k=1,\dots,I $$

with equality if Λ _k  > 0. Since F = N/D, we get

$$ \frac{N_k' D - D_k^{\prime} N}{D^2} \leq 0 $$

or equivalently

$$ \label{cond1} \frac{N_k^{\prime}}{D_k^{\prime}} \leq \frac{N}{D} $$

(43)

with equality if Λ _k  > 0.

Consider three consecutive coordinates (Λ_k − 1,Λ _k ,Λ_k + 1) of the maximizer Λ, with 2 ≤ k < I − 1, and suppose that Λ _k  > 0. We will show that this is impossible. Since the right hand side of Eq. 43 is independent of k, we get at this point

$$ \frac{N_{k-1}^{\prime}}{D_{k-1}^{\prime}} \leq \frac{N_k^{\prime}}{D_k^{\prime}} \geq \frac{N_{k+1}^{\prime}}{D_{k+1}^{\prime}} $$

which implies that

$$ \label{ineq2} \frac{N_k^{\prime} - N_{k-1}^{\prime}}{D_k^{\prime} - D_{k-1}^{\prime}} \geq \frac{N_{k+1}^{\prime}-N_k^{\prime}}{D_{k+1}^{\prime}-N_k^{\prime}}. $$

(44)

Now, direct computation of the relevant derivatives gives

$$ \begin{array}{rll} N^{\prime}_k &\stackrel{\triangle}{=}& \frac{\partial N({\mathbf \Lambda})}{\partial \Lambda_k} = \sum\limits_i \beta_i \Lambda_i + \beta_k \sum\limits_i \Lambda_i \\ D^{\prime}_k &\stackrel{\triangle}{=}& \frac{\partial D({\mathbf \Lambda})}{\partial \Lambda_k} = 2 \sum\limits_i \Lambda_i \min\{\beta_i,\beta_k\} \end{array} $$

so that

$$ \frac{N_k^{\prime} - N_{k-1}^{\prime}}{D_k^{\prime} - D_{k-1}^{\prime}} = \frac{(\beta_k - \beta_{k-1})\sum_i \Lambda_i }{2(\beta_k-\beta_{k-1}) \sum_{i\geq k} \Lambda_i } = \frac{\sum_i \Lambda_i}{2 \sum_{i\geq k}\Lambda_i} $$

and similarly

$$ \frac{N_{k+1}^{\prime} - N_{k}^{\prime}}{D_{k+1}^{\prime} - D_{k}^{\prime}} = \frac{\sum_i \Lambda_i}{2 \sum_{i\geq k+1}\Lambda_i}. $$

Comparing the last two expressions, it is evident that Eq. 44 can hold only if Λ _k  = 0.

It follows that any maximizer Λ of F must have Λ₂ = ...Λ_I − 1 = 0. To determine Λ₁ and Λ _I , observe that F now reduces to

$$ \begin{array}{rll} F({\mathbf \Lambda}) &=& 2 \frac{\beta_1\Lambda_1^2 + (\beta_1+\beta_2)\Lambda_1\Lambda_2 + \beta_2\Lambda_2^2} {\beta_1\Lambda_1^2 + 2\beta_1\Lambda_1\Lambda_2 + \beta_2\Lambda_2^2} \\ &=& 2+\frac{2(\beta_2-\beta_1)\Lambda_1\Lambda_2} {\beta_1\Lambda_1^2 + 2\beta_1\Lambda_1\Lambda_2 + \beta_2\Lambda_2^2} =2+\frac{2(\beta_2-\beta_1)}{\beta_1 \lambda + 2\beta_1 + \beta_2/\lambda} \end{array} $$

where $\lambda\stackrel{\triangle}{=} \Lambda_1/\Lambda_2$. Minimizing the last denominator over λ (which is equivalent to maximizing F) gives $\beta_1 - \beta_2/\lambda^2=0$, or $\lambda=\sqrt{\beta_2/\beta_1}$. Substituting this maximizing value back in F gives the upper bound $F({\mathbf \Lambda}) = 1+\sqrt{\beta_I/\beta_1}$. Recalling that the β _i ’s were arranged in increasing order, this establishes the claimed upper bound. □

Proof of Proposition 6

First consider $\tau_0 < \hat{\tau} < \frac{a}{\mu}$. As argued before, under any equilibrium, the server will serve at a full rate till time 1/μ. Clearly, the last customer to be served in equilibrium will arrive at time 1/μ and incur the cost $c_2\stackrel{\triangle}{=} \beta/\mu$. Note also that any customer from population 1 has the option of arriving at time $\hat{\tau}$ and be served by at most time a/μ, resulting in an upper bound on her cost $c_1\stackrel{\triangle}{=}\alpha\big(\frac{a}{\mu} - \hat{\tau}\big) + \beta \frac{a}{\mu}$. Therefore, the equilibrium cost for population 1 is upper bounded by c ₁. It is easy to verify that c ₁ < c ₂ (using $\tau_0 < \hat{\tau}$), which implies that population 1 customers will not be the last to arrive.

Hence, some member of population 2 is the last to arrive, and in equilibrium the cost incurred by each customer of population 2 equals c ₂. Clearly, population 1 cannot arrive after time $\hat{\tau}$ and incur cost less than c ₂, as then a customer from population 2 can replicate this to lower her own cost. Hence, since all customers in population 1 have a constant cost, this population arrives uniformly in an interval $\big[\tau-\frac{a}{\mu m},\tau\big]$ at rate μm for some $\tau \leq \hat{\tau}$. Again, if $\tau < \hat{\tau}$, the last customer of this population can improve her cost by arriving at $\hat{\tau}$, so $\tau = \hat{\tau}$. In particular, the cost incurred by population 1 customers equals c ₁, and they are served uninterruptedly till time a/μ, which results in the stated arrival profile. From population 2’s viewpoint, then, in equilibrium the service opens at time a/μ, and hence in equilibrium it must follow the profile specified in the proposition.

It is straightforward to compute the PoA for the specified equilibrium, we omit the details.

Now consider the case $\hat{\tau} < \tau_0$. Let c ₁ and c ₂ be defined as above, and note that now c ₁ > c ₂. As before, we argue that no customer can have cost more than c ₂, while population 2’s cost will equal c ₂. If all of population 1 arrives by time $\hat{\tau}$, the cost incurred by its last customer (who will be served at time a/μ and will need to wait at least $a/\mu - \hat{\tau}$) is not less than c ₁. Hence, this cannot hold in equilibrium and some customers from population 1 must arrive after time $\hat{\tau}$. But these must have the same cost c ₂ as population 2 customers in equilibrium (as any arrival of population 2 at that time will incur the same cost). Thus, equilibrium cost for each customer must equal c ₂, and the joint arrival profile must be as stated. Finally, population 2 customers cannot come before $\hat{\tau}$ in equilibrium, since then a customer from population 1 that arrives at $\hat{\tau}$ will have priority over them and thereby achieve better cost than c ₂. However, beyond $\hat{\tau}$ arrivals from both populations have similar status, so that any order of arrival that keeps the joint uniform distribution (hence cost c ₂) would complete an equilibrium profile. The PoA clearly equals 2 since the joint arrival distribution is the same as in the single-class case.

The case of $\hat{\tau} = \tau_0$ is borderline between the above two and can be treated by either argument, we omit further details. □

1.2 A.2 Reducing the PoA through tariffs: supplements

This discussion supplements Section 6.3. We state two propositions: Proposition 7 specifies the equilibrium profile for $p=(1+c)\frac{\beta}{2 \mu}$, c > 0. Proposition 8 does this for $p=(1-c)\frac{\beta}{2 \mu}$, c > 0. The arrival profiles in the two cases are illustrated in Fig. 6. The proofs of these propositions are straightforward. They rely on the fact that the two populations: One that pays an additional tariff p and the other that doesn’t each arrive over their respective arrival intervals at a constant rate μm in such a way that the cost incurred by a customer in either population is the same. For brevity we omit the proofs.

Fig. 6

The dotted line in both the figures denotes the queue profile before differential pricing. The darkened line in the top figure denotes the queue profile of population 1 that pays β(1 + c)/(2μ) more than population 2 whose queue profile is shown using the lighter line. Here the population 1 is served till $\tilde{\tau}_1 = \frac{1}{ 2\mu} - \frac{c}{ 4\mu}$ and population 2 is served till $\tilde{\tau}_3 = \frac{1}{ \mu} + \frac{c}{ 4\mu}$. The cost to customer joining either of the two populations equals $\frac{\beta}{\mu}(1 + \frac{c}{4})$. In the bottom figure, the darkened line denotes the queue profile of population 1 that pays β(1 − c)/(2μ) more than population 2 whose queue profile is shown using the lighter line. Here the population 1 is served till $\breve{\tau}_1 = \frac{1}{2 \mu} + \frac{\beta c}{2\mu(\alpha+\beta)}$. The cost to customer joining either of the two populations equals $\frac{\beta}{\mu}$

Proposition 7

For $p=(1+c)\frac{\beta}{2 \mu}$, c > 0:

• 1. In unique equilibrium, $\big(\frac{1}{2}- \frac{c}{ 4}\big)$ proportion of customers arrive as population 1, for c ≤ 2, at rate μm, uniformly over

  $$ \left [ -\frac{\beta}{\alpha \mu}\left(\frac{1}{2}- \frac{c}{ 4}\right) , \frac{1}{\mu}\left(\frac{1}{ 2} - \frac{c}{ 4}\right) \right ], $$

  and $\big(\frac{1}{2}+ \frac{c}{ 4}\big)$ proportion arrive as population 2 at rate μm uniformly over

  $$ \left [ \frac{1}{2 \mu }- \frac{\beta}{2\alpha \mu}\left({1} + \frac{c}{ 2}\right), \frac{1}{ \mu} + \frac{c}{ 4\mu} \right]. $$

  For c ≥ 2, all customers come as population 2 as for c = 2.

• 2. Furthermore, for c ≤ 2, the PoA equals

  $$ \label{eqn:poa} =\frac{3}{2}+ \frac{c(1+c)}{4}. $$

  (45)

  For c > 2 it equals 3.

Proposition 8

For $p=(1-c)\frac{\beta}{2 \mu}$, c ∈ (0,1):

• 1. In unique equilibrium, proportion $\frac{1}{2} + \frac{\beta c}{2(\alpha+\beta)}$ of customers arrive as population 1 at rate μm, uniformly over

  $$ \left [-\frac{\beta}{2 \alpha \mu}(1+c), \frac{1}{2 \mu} \right]. $$

  In addition, proportion $\frac{1}{2} - \frac{\beta c}{2(\alpha+\beta)}$ of customers arrive as population 2 at rate μm, uniformly over

  $$ \left [\frac{1}{2\mu}- \frac{\beta}{2 \alpha \mu}(1-c), \frac{1}{\mu} \right]. $$

• 2. Furthermore,

  $$ \label{eqn:poa100} PoA = \frac{3}{2} + \frac{c(\alpha + \beta c)}{2(\alpha + \beta)}. $$

  (46)

  This equals 3/2 at c = 0 and 2 at c = 1.

Note that for tariff $0 \leq p \leq \frac{\beta}{2 \mu}$, the cost to each customer remains fixed at $\frac{\beta}{\mu}$ while this had increased for $p > \frac{\beta}{2 \mu}$.