# Queueing games with an endogenous number of machines

Ata Atay and Christian Trudeau

###### Abstract.

This paper studies queueing problems with an endogenous number of machines
with and without an initial queue, the novelty being that coalitions not only
choose how to queue, but also on how many machines. For a given problem,
agents can (de)activate as many machines as they want, at a cost. After
minimizing the total cost (processing costs and machine costs), we use a game
theoretical approach to share to proceeds of this cooperation, and study the
existence of stable allocations. First, we study queueing problems with an
endogenous number of machines, and examine how to share the total cost. We
provide an upper bound and a lower bound on the cost of a machine to guarantee
the non-emptiness of the core (the set of stable allocations). Next, we study
requeueing problems with an endogenous number of machines, where there is an
existing queue. We examine how to share the cost savings compared to the
initial situation, when optimally requeueing/changing the number of machines.
Although, in general, stable allocation may not exist, we guarantee the
existence of stable allocations when all machines are considered public goods,
and we start with an initial schedule that might not have the optimal number
of machines, but in which agents with large waiting costs are processed first.

A. Atay is a Serra Húnter Fellow (Professor Lector Serra Húnter) under the
Serra Húnter Plan (Pla Serra Húnter). A. Atay gratefully acknowledges
financial support by the University of Barcelona through grant UB-AE-2022-TBA.
C.Trudeau gratefully acknowledges financial support by the Social Sciences and
Humanities Research Council of Canada [grant number 435-2019-0141].
Atay: Department of Mathematical Economics, Finance and Actuarial Sciences,
and Barcelona Economic Analysis Team (BEAT), University of Barcelona, Spain.
E-mail<EMAIL_ADDRESS>
Trudeau: Department of Economics, University of Windsor, Windsor, ON, Canada.
E-mail<EMAIL_ADDRESS>
Keywords: queueing problems $\cdot$ convexity $\cdot$ cost sharing $\cdot$
allocation problems
JEL Classification: C44 $\cdot$ C71 $\cdot$ D61 $\cdot$ D63
Mathematics Subject Classification (2010): 60K25 $\cdot$ 90B22 $\cdot$ 91A12

##  1\. Introduction

Consider a set of agents with jobs that have to be executed by a number of
machines in such a way that the aim is to minimize the total cost based on
some criterion. We observe such problems in many real-life applications such
as manufacturing, health care, logistics, etc. In this paper, we consider
queueing problems from two different perspectives; (i) queueing problems that
consider the problem of optimally queueing the agents before they arrive, (ii)
queueing problems that consider the problem of reorganizing (rescheduling) an
existing queue optimally. In both problems, a set of agents wait for their
jobs to be processed on machines. Each agent has a job that needs the same
amount of processing time with a different unit waiting cost. We refer to Chun
(2016) for a comprehensive survey on queueing theory.

This paper is the first one that allows for an endogeneous number of machines.
Maniquet (2003) studied one machine queueing problem from a cooperative game
theoretical perspective and showed that the rule assigning positions in the
queue and compensations is the Shapley (1953) value of the associated TU-game.
Chun (2006) introduced a pessimistic definition of the worth that can be
generated by a subset of agents. It is proved that different definitions lead
to very different rules. Towards a generalization to multiple machines, Chun
and Heo (2008) consider queueing problems with two parallel machines. Curiel
et al. (1989) are the first to study one-machine sequencing problems from a
cooperative game theoretical point of view. That is, queueing problems with an
initial queue where rescheduling is allowed to improve upon the initial
situation. The rescheduling of jobs is allowed to reduce weighted completion
time and the total savings by rescheduling can be shared by agents who own the
jobs. Hamers et al. (1999) (see also Slikker, 2006a) consider multiple
parallel sequencing situations where the number of machines is fixed. They
guarantee the non-emptiness of the core for one and two machine situations,
and moreover for two subclasses when there are at least three machines.

In this paper, we consider that the number of machines is endogenous. Each
machine has a cost to activate. Hence, in both types of problems, a subset of
agents can “buy” as many machines as they want to in exchange of its cost, and
under some constraints in problems with an existing initial order, might be
able to “sell” some of the existing machines. Moreover, each agent incurs some
waiting cost until her job is processed and she can leave the system. Then, we
take a game theoretical approach to address the question on how to distribute
among the players the proceeds of their cooperation, whenever they
(re)schedule their jobs to be processed in an optimal way, minimizing total
costs. Following the vast literature on different problems on rescheduling an
initial queue (see for instance Calleja et al., 2002; Musegaas et al., 2015;
Bahel and Trudeau, 2019; Atay et al., 2021), we examine conditions
guaranteeing the existence of stable allocations.

First, we examine queueing problems that consider the problem of optimally
queueing the agents before they arrive. Traditionally, queueing problems have
a fixed number of machines, and their cost is sunk and thus ignored. The
resulting cost game is then superadditive, as congestion implies that the
total waiting cost for two agents is larger than the sum of their waiting
costs if they are alone. With an endogeneous number of machines, the cost
function is always subadditive, as two agents can always each buy a machine,
generating costs equal to the sum of their individual stand-alone costs. This
allows a traditional definition of the core. We provide a lower bound and an
upper bound on the cost of a machine for the non-emptiness of the core of a
queueing problem with an endogenous number of machines (Theorems 1, 2). In the
second case, we provide a full description of the core (Theorem 2).

Next, we consider the problem of rescheduling an existing queue optimally with
an endogenous number of machines which we call the requeueing problem. While
the sequencing literature has crucially depended on the assumptions regarding
the admissible rearrangements of the initial queue by a coalition on a given
machine, our results depend mostly on the assumptions made on the adjustment
of the queue when new machines are added.

If we suppose that a coalition will be the sole users of a new machine it
adds, we see that the core of a requeueing game with an endogenous number of
machines may be empty (Example 2), and that under any assumptions on how a
coalition can reorganize its members on the existing machines. Nevertheless,
we provide sufficient conditions to guarantee the non-emptiness of the core
(Theorems 3, 4). We also obtain positive results if we suppose that machines
are public goods. That is, when we add machines, the whole queue moves up, and
not only the members of the coalition that paid for the extra machines. The
distinction is akin to establishing VIP machines and general-use machine. We
show that under the assumption of public machines, whenever the initial
schedule efficiently orders agents from high to low waiting costs but might
not have the optimal number of machines, the public requeueing games always
have a non-empty core (Theorem 5).

The paper is organized as follows. In Section 2 we present queueing problems
with an endogenous number of machines. In Section 3 we introduce the
associated TU-game for queueing problems with an endogenous number of
machines. We derive upper and lower bounds on the cost of a machine to
guarantee the existence of stable allocations as well as a full
characterization of the set of stable allocations. In Section 4 we introduce
two types of problems and their associated TU-games, the so-called private and
public requeueing problems (and games). For private requeuing games, although
stable allocations need not exist, we provide an upper-bound and a lower-bound
to guarantee their existence. For public requeuing games, we show that stable
allocations always exist if the initial schedule serves agents with larger
waiting costs first. Finally, we draw conclusions in Section 5.

##  2\. Queueing problems with an endogenous number of machines

We examine first the queueing problem. We have a set of agents
$N=\\{1,2,\ldots,n\\}$. When no confusion arises we denote by $|N|=n$ the
cardinality of the set of agents. Each agent has one job to be processed on a
machine. The agents have access to an unlimited number of machines, but they
must pay $b\in\mathbb{R}_{+}$ for each machine that they use. All jobs and all
machines are identical, and each machine can process one job per period. We
assume that each machine starts processing at time 0.

Every agent $i\in N$ has a waiting cost that is linear with respect to the
time it spends in the system. The waiting cost function of an agent $i\in N$
is $w_{i}t$ where $w_{i}>0$ is the waiting (weight) cost per unit time of
player $i$ and $t$ is the period at which the job has been processed. We refer
to the vector of weights by $w:=(w_{i})_{i\in N}$. Let $w^{S}_{k}$ be the
waiting cost of the $k^{th}$ agent (according to the order $N$) in $S$ and
$w^{-S}_{k}\equiv w^{N\setminus S}_{k}$ be the waiting cost of the $k^{th}$
agent outside the coalition $S$.

A _queueing problem with an endogenous number of machines_ can be described as
$(N,w,b)$ where $N$ is the set of agents, $w$ is the vector of unit waiting
costs and $b\in\mathbb{R}_{+}$ is the cost of a machine. We suppose that
$w_{1}\geq w_{2}\geq...\geq w_{n}$.

In a queueing problem, we examine the problem before agents arrive to queue:
we are looking for the optimal number of machines and the optimal queueing of
agents on those machines, the objective being the minimization of the total
cost, consisting of the agents’ waiting costs and the machine costs.

The solution consists in choosing a number of machines $m\in\\{1,...,n\\}$ and
a schedule $\sigma=(\varphi,s)$, where $\varphi:N\rightarrow\\{1,...,m\\}$
assigns agents to machines and $s:N\rightarrow\mathbb{N}\cup\\{0\\}$ assigns
to each agent a starting time. A schedule $\sigma=(\varphi,s)$ is admissible
if for all $i,j\in N$, $\varphi(i)=\varphi(j)\Rightarrow s(i)\neq s(j)$. In
words, if two agents are assigned to the same machine, they must have
different starting times. The set of all possible schedules with $m$ machines
is denoted by $\Sigma(m)$. A scheduling plan is $(m,\sigma)$, with
$\sigma\in\Sigma(m)$.

Let $N^{k}=\\{i\in N:\varphi(i)=k\\}$ be the set of agents assigned to machine
$k$. A schedule is a _semi-active schedule_ if there is no job which could be
started earlier without altering the processing schedule. This has two
implications for $\sigma$. First, we must have that if $\varphi(i)=k$ and
$s(i)=l>0$, there must be $j\in N^{k}$ such that $s(j)=l^{\prime}$ for all
$l^{\prime}\in\\{0,...,l-1\\}$. Second, we must have
$|N^{k}|-|N^{k^{\prime}}|<2$ for all $k,k^{\prime}\in\\{1,...,m\\}$. In words,
the first condition imposes that a schedule on a given machine has no
downtime, and processes a job at all periods until all agents assigned to that
machine have their job processed. The second condition imposes a difference in
the number of agents assigned to pairs of machines to be at most one;
otherwise, we could move the last agent on the first machine to the last
position on the second machine, reducing the processing time of that agent
without affecting the processing time of other agents.

Since no preemption is allowed, the completion time of the job of agent $i$
according to $\sigma=(\varphi,s)$ is $s(i)+1$. Hence, the waiting cost of an
agent $i\in N$ can be written as $c_{\sigma}(i)=w_{i}(s(i)+1)$.

We thus need to find $(m,\sigma)$ that optimizes the following objective
function:

$\min_{m\in\\{1,...,n\\}}\left(bm+\min_{\sigma\in\Sigma^{m}}\sum_{i\in
N}c_{\sigma}(i)\right).$

It is well-established in the literature that, for the one-machine case (with
equal processing times), the total cost is minimal if the players are arranged
according to their waiting costs in a decreasing order (see Smith, 1956;
Curiel et al., 1989). With multiple machines, it remains optimal to not
process jobs of agents with larger waiting costs after those of agents with
smaller waiting costs, i.e. $w_{i}<w_{j}\Rightarrow s(i)\leq s(j)$.

Given this result, if we install $m$ machines, it is optimal to schedule the
$m$ agents with the highest waiting costs (agents $\\{1,\ldots,m\\}$) at time
0, and it is irrelevant to which machine each agent is assigned to. The next
$m$ agents are then scheduled in the next period, and so on. Thus, the
queueing problem reduces to finding the number of machines that solves

$\min_{m\in\\{1,\ldots,n\\}}\left(bm+\sum\limits_{i\in
N}\left(\left\lceil\frac{i}{m}\right\rceil\right)w_{i}\right).$

We provide some initial results on the structure of the game. Let $m(S)$ be
the optimal number of machines for coalition $S\subseteq N$.222There might be
a tie, in which case pick the lowest number of machines among optimal ones.

######  Lemma 1.

Fix the set of agents $N$. For any weight vector $w$ there exists a non-
increasing function $r^{w}:\\{2,...,n\\}\to\mathbb{R}_{+}$ such that:

  1. (i)

if $b\geq r^{w}(2)$, then $m(N)=1$;

  2. (ii)

if $r^{w}(k)>b\geq r^{w}(k+1)$ for some $1<k<n$, then $m(N)=k$;

  3. (iii)

if $r^{w}(n)>b$ then $m(N)=n$.

###### Proof.

Fix $N$ and $w$. The total cost when $k$ machines are used would be cheaper
than when $k-1$ machines are used if

$bk+\sum_{i\in N}\left(\left\lceil\frac{i}{k}\right\rceil\right)w_{i}\leq
b(k-1)+\sum_{i\in N}\left(\left\lceil\frac{i}{k-1}\right\rceil\right)w_{i}$

which simplifies to

$\displaystyle b$ $\displaystyle\leq\sum_{i\in
N}\left(\left\lceil\frac{i}{k-1}\right\rceil-\left\lceil\frac{i}{k}\right\rceil\right)w_{i}$
(a)
$\displaystyle=w_{k}+\sum_{i=k+1}^{n}\left(\left\lceil\frac{i}{k-1}\right\rceil-\left\lceil\frac{i}{k}\right\rceil\right)w_{i}.$

The inequality (a) provides an upper-bound on the cost of a machine such that
we prefer to use $k$ machines to $k-1$ machines. Let us denote this number
obtained in (a) by $r^{w}(k)$. This defines a function
$r^{w}:\\{2,...,n\\}\to\mathbb{R}_{+}$.

We next show that this function is non-increasing. We show that $r^{w}(k)\leq
r^{w}(k-1),$ that is,

$w_{k}+\sum_{i=k+1}^{n}\left(\left\lceil\frac{i}{k-1}\right\rceil-\left\lceil\frac{i}{k}\right\rceil\right)w_{i}\leq
w_{k-1}+\sum_{i=k}^{n}\left(\left\lceil\frac{i}{k-2}\right\rceil-\left\lceil\frac{i}{k-1}\right\rceil\right)w_{i}.$

By assumption, $w_{k}\leq w_{k-1}.$ We will show that

$\sum_{i=k+1}^{n}\left(\left\lceil\frac{i}{k-1}\right\rceil-\left\lceil\frac{i}{k}\right\rceil\right)w_{i}\leq\sum_{i=k}^{n}\left(\left\lceil\frac{i}{k-2}\right\rceil-\left\lceil\frac{i}{k-1}\right\rceil\right)w_{i},$

which together with $w_{k}\leq w_{k-1}$ show that the inequality holds. To do
so, we compare the right-hand side and the left-hand side summands of the same
order in the inequality (2). We see that

$\displaystyle\left(\left\lceil\frac{k+1}{k-1}\right\rceil-\left\lceil\frac{k+1}{k}\right\rceil\right)w_{k+1}$
$\displaystyle\leq$
$\displaystyle\left(\left\lceil\frac{k}{k-2}\right\rceil-\left\lceil\frac{k}{k-1}\right\rceil\right)w_{k}$
$\displaystyle\left(\left\lceil\frac{k+2}{k-1}\right\rceil-\left\lceil\frac{k+2}{k}\right\rceil\right)w_{k+2}$
$\displaystyle\leq$
$\displaystyle\left(\left\lceil\frac{k+1}{k-2}\right\rceil-\left\lceil\frac{k+1}{k-1}\right\rceil\right)w_{k+1}$
$\displaystyle\vdots$
$\displaystyle\left(\left\lceil\frac{n-1}{k-1}\right\rceil-\left\lceil\frac{n-1}{k}\right\rceil\right)w_{n-1}$
$\displaystyle\leq$
$\displaystyle\left(\left\lceil\frac{n-2}{k-2}\right\rceil-\left\lceil\frac{n-2}{k-1}\right\rceil\right)w_{n-2}$
$\displaystyle\left(\left\lceil\frac{n}{k-1}\right\rceil-\left\lceil\frac{n}{k}\right\rceil\right)w_{n}$
$\displaystyle\leq$
$\displaystyle\left(\left\lceil\frac{n-1}{k-2}\right\rceil-\left\lceil\frac{n-1}{k-1}\right\rceil\right)w_{n-1}$
$\displaystyle 0$ $\displaystyle\leq$
$\displaystyle\left(\left\lceil\frac{k}{k-2}\right\rceil-\left\lceil\frac{k}{k-1}\right\rceil\right)w_{n},$

and we see that removing a machine is costlier in terms of waiting costs if
there are less machines in the initial problem. Applying the result
recursively, starting with $r^{w}(n)$, we obtain that $r^{w}$ is non-
increasing.

It remains to show that we can define $m$ using $r^{w}$. Let $C(N,k)$ be the
cost for coalition $N$ if it uses $k$ machines. Suppose that $b\geq r^{w}(2)$.
Then, since $r^{w}$ is non-increasing $b\geq r^{w}(k)$ for all
$k\in\\{2,...,n\\}.$ This implies that $C(N,k)\leq C(N,k+1)$ for all
$k=1,...,n-1.$ By transitivity, $C(N,1)\leq C(N,k)$ for all
$k\in\\{2,...,n\\}$ and thus $m(N)=1$.

Suppose next that $r^{w}(k)>b\geq r^{w}(k+1)$ for some $1<k<n$. By the same
argument as above, $b\geq r^{w}(k+1)$ implies that $C(N,k)\leq C(N,l)$ for all
$l\in\\{k+1,...,n\\}$. Since $r^{w}$ is non-increasing, $r^{w}(k)>b$ implies
that $r^{w}(l)>b$ for all $l=2,...,k$. This implies that $C(N,l)<C(N,l-1)$ for
all $l=2,...,k$. By transitivity, $C(N,k)<C(N,l)$ for all
$l\in\\{1,...,k-1\\}$. Combining with the previous result, we obtain $m(N)=k$.

Finally, suppose that $r^{w}(n)>b$. By the same argument as above, we have
that $C(N,n)<C(N,l)$ for all $l\in\\{1,...,n-1\\}$ and we obtain $m(N)=n$. ∎

We can similarly define a non-increasing function
$r^{w}_{S}:\\{2,...,|S|\\}\to\mathbb{R}_{+}$ for all $S\subset N$ such that
$|S|>1$ to determine $m(S)$. For singletons, it is always optimal to use a
single machine, and thus $m(\\{i\\})=1$ for all $i\in N$. Observing the
structure of these functions $r^{w}_{S}$, the following result follows:

######  Lemma 2.

For all values of $w$ and $b$, we have:

  1. (i)

$m(S)\leq m(T)$ for all $S\subset T\subseteq N$;

  2. (ii)

$m(S\cup\\{i\\})\leq m(S\cup\\{j\\})$ for all $S\subseteq
N\setminus\\{i,j\\}$, and $i>j$.

###### Proof.

Let $r_{S}^{w}(k)$ be the equivalent of $r^{w}(k)$ for coalition $S.$

(i) If $m(T)\geq\left|S\right|,$ the result is immediate. Thus, suppose that
$m(T)<\left|S\right|.$

We show that for any $S\subset T\subseteq N$ and $k=2,...,\left|S\right|,$ we
have that $r_{S}^{w}(k)\leq r_{T}^{w}(k).$ That is,

$\displaystyle r_{S}^{w}(k)$ $\displaystyle=$ $\displaystyle
w_{k}^{S}+\sum_{l=k+1}^{\left|S\right|}\left(\left\lceil\frac{l}{k-1}\right\rceil-\left\lceil\frac{l}{k}\right\rceil\right)w_{l}^{S}$
$\displaystyle\leq$ $\displaystyle
w_{k}^{T}+\sum_{l=k+1}^{\left|S\right|}\left(\left\lceil\frac{l}{k-1}\right\rceil-\left\lceil\frac{l}{k}\right\rceil\right)w_{l}^{T}$
$\displaystyle\leq$ $\displaystyle
w_{k}^{T}+\sum_{l=k+1}^{\left|T\right|}\left(\left\lceil\frac{l}{k-1}\right\rceil-\left\lceil\frac{l}{k}\right\rceil\right)w_{l}^{T}$
$\displaystyle=$ $\displaystyle r_{T}^{w}(k),$

where the first inequality comes from the fact that $w_{k}^{S}\leq w_{k}^{T}$
for all $k.$

Then, if $b\geq r_{T}^{w}(2),$ $b\geq r_{S}^{w}(2)$ and $m(S)=m(T)=1.$
Otherwise, $m(S)$ is the highest integer such that $b<r_{S}^{w}(m(S)).$ But
since $r_{S}^{w}(m(S))\leq r_{T}^{w}(m(S)),$ we have $b<r_{S}^{w}(m(T))$, and
thus $m(S)\leq m(T),$ as desired.

ii) The proof is identical to part i), replacing $S$ by $S\cup\\{i\\}$ and $T$
by $S\cup\\{j\\}$. ∎

In words, if we add agents to a coalition, it cannot be optimal to use less
machines. The strategy to add an additional machine can only become more
profitable (or less unprofitable) as the new agents might have higher waiting
costs, and the additional agents might lead to more saved waiting costs. The
same is true if we replace an agent by one with a larger waiting cost.

##  3\. Queueing games with an endogenous number of machines

A _cooperative transferable utility (TU) game_ is defined by the pair $(N,C)$
where $N$ is the set of the players and the coalitional function $C$ assigns
to each coalition $T\subseteq N$ its cost $C(T)\in\mathbb{R}$, with
$C(\emptyset)=0$.

Cooperative game theory aims to allocate the value of the grand coalition in
such a way that the cooperation is preserved among the agents. Given a
cooperative game $(N,C)$, a _cost allocation_ is $y\in\mathbb{R}^{N}$, where
$y_{i}$ stands for the cost paid by player $i\in N$. The total payment by a
coalition $S\subseteq N$ is denoted by $y(S)=\sum\limits_{i\in S}y_{i}$ with
$y(\emptyset)=0$.

In this section, we study the set of stable allocations of the total cost,
where no coalition of agents pays more than its stand-alone cost. To do so,
for any queueing problem with an endogenous number of machines, we will
introduce a TU-game and study the _core_ of the associated TU-game (Gillies,
1959).

Formally, let $(N,w,b)$ be a queueing problem with an endogenous number of
machines. Then, the corresponding _queueing game with an endogenous number of
machines_ is the pair $(N,C)$ where $N$ is the set of players, and $C$ is the
characteristic function that assigns the minimal cost $C(T)$ to each coalition
$T\subseteq N$ to queue its members, with $C(\emptyset)=0$. $C(T)$ includes
both the waiting costs and the cost of machines. The core of a cooperative
cost game $(N,C)$ is:

$Core(C)=\\{y\in\mathbb{R}^{N}\mid y(N)=C(N),\quad y(S)\leq C(S)\quad\text{for
all}\quad S\subset N\\}.$

A game is called _balanced_ if its core is non-empty.

Concave cost functions always have a non-empty core (Shapley, 1971). Formally,
a game $(N,C)$ is said to be _concave_ if for all $i\in N$ and all $S\subseteq
T\subseteq N\setminus\\{i\\}$, it holds $C(T\cup\\{i\\})-C(T)\leq
C(S\cup\\{i\\})-C(S)$.

###  3.1. On the non-emptiness of queueing games with an endogenous number of
machines

First, for queueing games with an endogenous number of machines, we provide an
upper bound on the cost of a machine to guarantee the non-emptiness of the
core.

For the sake of comprehensiveness, let us introduce some notation: Let
$\mu\equiv\left\lceil\frac{n}{2}\right\rceil$. If $n$ is even, then
$\\{1,...,\mu\\}$ and $\\{\mu+1,...,n\\}$ both contain $\mu$ agents, while if
$n$ is odd, then $\\{1,...,\mu\\}$ contains $\mu$ agents and
$\\{\mu+1,...,n\\}$ contains $\mu$-1 agents.

######  Theorem 1.

Let $(N,w,b)$ be a queueing problem with an endogenous number of machines, and
$(N,C)$ be the associated TU-game.

  1. (i)

If $b\leq w_{\mu}$ then $y=\left(\min\left(b+w_{i},2w_{i}\right)\right)_{i\in
N}\in Core(C)$;

  2. (ii)

If $b\leq w_{\left\lceil\frac{2n+1}{4}\right\rceil}$ then
$Core(C)=\left(\min\left(b+w_{i},2w_{i}\right)\right)_{i\in N}$.

###### Proof.

(i) We first show that the allocation
$y=\left(\min\left(b+w_{i},2w_{i}\right)\right)_{i\in N}$ is budget balanced.

First, notice that if we use $k\geq\mu$ machines, than agents wait at most 2
periods. Adding an additional machine allows to reduce the waiting cost of
agent $k+1$ from 2 to 1 period, with all other waiting costs remaining the
same. Thus, $r^{w}(k)=w_{k}$ for all $k>\mu$.

Notice also that when moving from $\mu-1$ to $\mu$ machines the cost savings
are larger: in addition to agent $\mu$ waiting for 1 period instead of 2, some
other agents will wait 2 periods instead of 3. Thus, $r^{w}(\mu)\geq w_{\mu}$.
Thus, given that $b\leq w_{\mu}\leq r^{w}(\mu)$ and by Lemma 1, $m(N)\geq\mu$.

Let $C(\cdot,k)$ be the cost function that assigns to each coalition the total
cost if it uses $k$ machines to process their jobs. For $k\geq\mu$,

$C(N,k)=kb+\sum_{i=1}^{k}w_{i}+\sum\limits_{i=k+1}^{n}2w_{i}.$

Thus,

$\displaystyle C(N)$ $\displaystyle=$
$\displaystyle\min_{k\in\left\\{\mu,...,n\right\\}}\left\\{kb+\sum_{i=1}^{k}w_{i}+\sum_{i=k+1}^{n}2w_{i}\right\\}$
$\displaystyle=$ $\displaystyle
b(\mu-1)+\sum_{i=1}^{\mu-1}w_{i}+\min_{k\in\left\\{\mu,...,n\right\\}}\left\\{b(k-\mu+1)+\sum_{i=\mu}^{k}w_{i}+\sum_{i=k+1}^{n}2w_{i}\right\\}$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{\mu-1}\left(b+w_{i}\right)+\sum_{i=\mu}^{n}\min\left(b+w_{i},2w_{i}\right)$
$\displaystyle=$ $\displaystyle\sum_{i\in N}\min\left(b+w_{i},2w_{i}\right)$
$\displaystyle=$ $\displaystyle\sum_{i\in N}y_{i}$

The third equality comes from the fact that for all $k>\mu$, $r^{w}(k)=w_{k}$,
implying that we use at least $k$ machines if and only $b+w_{k}\leq 2w_{k}$.
While $r^{w}(\mu)\geq w_{\mu}$, by assumption $b\leq w_{\mu}$. The fourth
equality also comes from the fact that by assumption, $b\leq w_{\mu}$.

It remains to prove that core constraints are satisfied, i.e., $y(T)\leq C(T)$
for all $T\subset N$. Fix $T\subset N$ and suppose that $\kappa$ is the
optimal number of machines for $T.$

We have that

$\displaystyle\sum_{i\in T}y_{i}$ $\displaystyle\leq$ $\displaystyle\kappa
b+\sum_{i=1}^{\kappa}w^{T}_{i}+\sum_{i=\kappa+1}^{\left|T\right|}2w_{i}^{T}$
$\displaystyle\leq$ $\displaystyle C(T),$

where the first inequality is obtained by assigning $b+w_{i}$ to the first
$\kappa$ agents in $T$ and $2w_{i}$ to others, regardless of which of these
two values is minimal, and the second inequality comes from the fact that the
expression is exactly the cost of coalition $T$ if $\kappa\geq\frac{|T|}{2}$,
with the cost no smaller otherwise. Thus the core constraint is satisfied.
Since $T$ is arbitrarily chosen, the proof is complete.

(ii) Notice first that if $n$ is odd,
$\left\lceil\frac{2n+1}{4}\right\rceil=\mu$, while if $n$ is even,
$\left\lceil\frac{2n+1}{4}\right\rceil=\mu+1$. In particular, for any $n$, we
have that $\left\lceil\frac{2n+1}{4}\right\rceil-1\geq\frac{n-1}{2}$.

If $b<w_{n}$, then $C(S)=|S|b+\sum_{i\in S}w_{i}$ for all $S\subseteq N$ and
the result is immediate. Thus, suppose that $b\geq w_{n}$.

Suppose that $w_{k+1}\leq b<w_{k}$ for
$k\in\left\\{\left\lceil\frac{2n+1}{4}\right\rceil,...,n-1\right\\}$. Then, by
Lemma 1, $C(N)=kb+\sum_{i=1}^{k}w_{i}+\sum_{i=k+1}^{n}2w_{i}$.

Consider coalition $N\setminus\\{i\\}$ for $i\in\left\\{1,...,k\right\\}$. If
they use $k$ machines, the cost is
$kb+\sum_{j=1}^{k}w_{i}+\sum_{j=k+1}^{n}2w_{i}-w_{i}-w_{k+1}$. If they use
$k-1$ machines, the cost is
$(k-1)b+\sum_{j=1}^{k}w_{i}+\sum_{j=k+1}^{n}2w_{i}-w_{i}$, as
$k-1\geq\left\lceil\frac{2n+1}{4}\right\rceil-1\geq\frac{n-1}{2}$. Thus, it
prefers to use $k-1$ machines if $b\geq w_{k+1}$, which is satisfied. If they
use $k-2$ machines, the cost is at least
$(k-2)b+\sum_{j=1}^{k}w_{i}+\sum_{j=k+1}^{n}2w_{i}-w_{i}+w_{k}$ (as some
agents might have to wait more than 2 periods now), and as $b\leq w_{k}$ it
prefers to use $k-1$ machines. Thus,
$C(N\setminus\\{i\\})=(k-1)b+\sum_{j=1}^{k}w_{i}+\sum_{j=k+1}^{n}2w_{i}-w_{i}$.

Notice that $C(N\setminus\\{i\\})+C(\\{i\\})=C(N)$, and thus in any core
allocation, we must have $y_{i}=C(\\{i\\})=b+w_{i}$ for all
$i\in\left\\{1,...,k\right\\}$.

Next, consider coalition $\\{i,j\\}$, with $i\in\left\\{1,...,k\right\\}$ and
$j\in\left\\{k+1,...,n\right\\}$. If it uses a single machine, the cost is
$b+w_{i}+2w_{j}$. If it uses 2 machines, the cost is $2b+w_{i}+w_{j}$. It
prefers to use a single machine as $b\geq w_{k+1}\geq w_{j}$. Thus,
$C(\\{i,j\\})=b+w_{i}+2w_{j}$. Since $y_{i}=b+w_{i}$, we obtain a core
constraint of $y_{j}\leq 2w_{j}$ for all $j\in\left\\{k+1,...,n\right\\}$.
Given the value of $C(N)$, our only core candidate is $y_{i}=b+w_{i}$ for all
$i\in\left\\{1,...,k\right\\}$ and $y_{j}=2w_{j}$ for all
$j\in\left\\{k+1,...,n\right\\}$. Given that we have shown in part i) that it
is a core allocation, our proof is complete. ∎

Following an upper-bound on the cost of a machine for the non-emptiness of the
core, we provide a full characterization of the core making use of a lower-
bound for the non-emptiness of the core.

######  Theorem 2.

Let $(N,w,b)$ be a queueing problem with an endogenous number of machines, and
$(N,C)$ be the associated TU-game. Then,

  1. (i)

if $b\geq\sum_{i=1}^{n}(i-1)w_{i}$, $Core(C)=Core(\hat{C})\neq\emptyset$ with
$\hat{C}(T):=C(T)-\sum\limits_{i=1}^{n-|T|-1}iw_{i+1}^{-T}$ for all
$\emptyset\neq T\subseteq N$. Moreover, $\hat{C}$ is concave.

  2. (ii)

if
$b\in\left[w_{2}+\sum\limits_{i=3}^{n}\left(i-\left\lceil\frac{i}{2}\right\rceil\right)w_{i},\sum_{i=1}^{n}(i-1)w_{i}\right)$,
then $Core(C)=\emptyset$.

###### Proof.

Notice that
$w_{2}+\sum\limits_{i=3}^{n}\left(i-\left\lceil\frac{i}{2}\right\rceil\right)w_{i}=r^{w}(2)$,
and thus by Lemma 1, $m(N)=1$. By Lemma 2, $m(S)=1$ for all $S\subseteq N$,
and thus all coalitions use a single machine.

i) Notice first that $\hat{C}(T)=C(T)$ if $\left|T\right|\geq n-1.$ Let
$j,k\in N$ and consider $N\backslash\left\\{j,k\right\\}.$ By the grand
coalition efficiency and individual rationality, if $y$ is a core allocation,
then $y(N\setminus\left\\{j,k\right\\})\leq
C(N\setminus\left\\{j\right\\})+C(N\setminus\left\\{k\right\\})-C(N).$

Suppose that we have shown that $y(T)\leq\hat{C}(T)$ in any core allocation if
$\left|T\right|>m.$ We need to show that it implies that $y(T)\leq\hat{C}(T)$
in any core allocation if $\left|T\right|=m.$

Fix $T$ such that $\left|T\right|=m.$ Following the grand coalition efficiency
and individual rationality, if $y$ is a core allocation, then
$y(T)\leq\hat{C}(T\cup\left\\{k\right\\})+\hat{C}(N\backslash\left\\{k\right\\})-\hat{C}(N).$

Now, consider the cost function
$\hat{C}(T)=C(T)-\sum_{i=1}^{n-\left|T\right|-1}iw_{i+1}^{-T},$ for all
$\emptyset\neq T\subseteq N.$ By definition, $\hat{C}\leq C$ and
$\hat{C}(N)=C(N).$ We will show that $\hat{C}$ is concave whenever the lower-
bound on the cost of a machine in (i) is satisfied.

First, notice that for all $k\in N$,
$\hat{C}(\left\\{k\right\\})=b+w_{k}-\sum_{i=1}^{n-2}iw_{i+1}^{-\left\\{k\right\\}}=b+w_{k}-\sum_{i<k}(i-1)w_{i}-\sum_{i>k}(i-2)w_{i}.$

Recall that $w^{T}_{k}$ denotes the waiting cost of the $k^{th}$ agent in $T$,
according to the order in $N$ and $w^{-T}_{k}\equiv w^{N\setminus T}_{k}$.
Next, fix $\emptyset\neq T\subseteq N\backslash\left\\{k\right\\}.$ Then, we
have that

$\displaystyle\hat{C}(T\cup\left\\{k\right\\})-\hat{C}(T)$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{\left|T\right|+1}iw_{i}^{T\cup\left\\{k\right\\}}-\sum_{i=1}^{\left|T\right|}iw_{i}^{T}-\sum_{i=1}^{n-\left|T\right|-2}iw_{i+1}^{-\left(T\cup\left\\{k\right\\}\right)}+\sum_{i=1}^{n-\left|T\right|-1}iw_{i+1}^{-T}$
$\displaystyle=$ $\displaystyle\sum_{i>k}w_{i}+kw_{k}$

The equality is based on the following observations: if $i<k$ and $i\in T$,
then its rank in $T\cup\left\\{k\right\\}$ is the same as in $T,$ and the
terms cancel out. The same is true if $i\in N\setminus T.$ If $i>k$ and $i\in
T,$ the rank of $i$ is one higher in $T\cup\left\\{k\right\\}$ than in $T.$ If
$i>k$ and $i\in N\backslash T$, the rank of $i$ is one smaller in
$N\setminus\left(T\cup\left\\{k\right\\}\right)$ than in $N\setminus T.$ In
all cases, the difference is $w_{i}.$ As for $k,$ it appears in the first and
fourth terms. The weight on its waiting cost is its rank in
$T\cup\left\\{k\right\\}$ plus its rank in $N\setminus T$ minus 1. For all
agents, that equals $k$.

This result is independent of $T,$ as long as $T\neq\emptyset.$ Making use of
this result, we proceed to show $y(T)\leq\hat{C}(T).$ We have seen that
$\hat{C}(T\cup\left\\{k\right\\})=b+\sum_{i=1}^{\left|T\right|+1}iw_{i}^{T\cup\left\\{k\right\\}}-\sum_{i=1}^{n-\left|T\right|-2}iw_{i+1}^{-(T\cup\left\\{k\right\\})}$
and
$\hat{C}(N\backslash\left\\{k\right\\})=b+\sum_{i=1}^{n-1}iw_{i}^{N\backslash\left\\{k\right\\}}$and
$\hat{C}(N)=b+\sum_{i=1}^{n}iw_{i}.$ Thus,

$\hat{C}(T\cup\\{k\\})+\hat{C}(N\setminus\left\\{k\right\\})-\hat{C}(N)=b+\sum\limits_{i=1}^{|T|+1}iw_{i}^{T\cup\left\\{k\right\\}}-\sum\limits_{i=1}^{n-|T|-2}iw_{i+1}^{-(T\cup\left\\{k\right\\})}+\sum\limits_{i=1}^{n-1}iw_{i}^{N\setminus\left\\{k\right\\}}-\sum\limits_{i=1}^{n}iw_{i}.$

Next, let us distinguish several cases.

Case 1: $i\in T$ such that $i<k$. Then, $i$ is the $i^{th}$ agent in
$N\backslash\left\\{k\right\\}$ and in $N.$ The agent $i$ has the same rank in
$T$ and in $T\cup\left\\{k\right\\}.$

Case 2: $i\in T$ such that $i>k.$ Then, $i$ is the $(i-1)^{th}$ agent in
$N\backslash\left\\{k\right\\}$ and $i^{th}$ in $N.$ The agent $i$ has the
same rank in $T$ is one lower than in $T\cup\left\\{k\right\\}.$

Case 3: $j\notin T$ such that $j<k.$ Then, $j$ is the $j^{th}$ agent in
$N\backslash\left\\{k\right\\}$ and in $N.$ The agent $j$ has the same rank in
$N\backslash T$ and in $N\backslash(T\cup\left\\{k\right\\}).$

Case 4: $j\notin T$ such that $j>k.$ Then, $j$ is the $(j-1)^{th}$ agent in
$N\backslash\left\\{k\right\\}$ and $j^{th}$ in $N.$ The rank of $j$ in
$N\setminus T$ is one higher than in $N\backslash(T\cup\left\\{k\right\\}).$

Note that in the second term agent $k$ his waiting cost gets assigned a weight
equal to his rank in $T\cup\\{k\\}$. In the fifth term, his waiting cost gets
assigned a weight equal to $k$, his rank in $N$. These cases imply that

$\displaystyle\hat{C}(T\cup\left\\{k\right\\})+\hat{C}(N\backslash\left\\{k\right\\})-\hat{C}(N)$
$\displaystyle=$ $\displaystyle
b+\sum_{i=1}^{\left|T\right|}iw_{i}^{T}-\sum_{i=1}^{n-\left|T\right|-1}iw_{i+1}^{-T}$
$\displaystyle=$ $\displaystyle\hat{C}\left(T\right).$

Thus, we have the core constraint $y(T)\leq\hat{C}(T)$. In order to finish the
proof of $(\emph{i})$, we will show that $\hat{C}$ is concave.

To verify concavity, it remains to check that
$\hat{C}(T\cup\left\\{k\right\\})-\hat{C}(T)\leq\hat{C}\left(\left\\{k\right\\}\right)-\hat{C}\left(\emptyset\right)=\hat{C}\left(\left\\{k\right\\}\right)$
or equivalently,

$\sum_{i>k}w_{i}+kw_{k}\leq b+w_{k}-\sum_{i<k}(i-1)w_{i}-\sum_{i>k}(i-2)w_{i}$

which simplifies to

$b\geq\sum_{i=1}^{n}(i-1)w_{i}$

which is satisfied by assumption. Thus, $\hat{C}$ is concave and hence
$Core(\hat{C})$ is non-empty which finishes the proof of (i).

To prove the statement (ii), recall that we have shown that
$C(N\backslash\left\\{l\right\\})=b+\sum_{i=1}^{n-1}iw_{i}^{N\backslash\left\\{l\right\\}}$
for $l\in N$ and $C(N)=b+\sum_{i=1}^{n}iw_{i}.$ Thus,

$\displaystyle\sum_{l\in N}C\left(N\backslash\left\\{l\right\\}\right)$
$\displaystyle=$ $\displaystyle\sum_{l\in
N}\left(b+\sum_{i=1}^{n-1}iw_{i}^{N\backslash\left\\{l\right\\}}\right)$
$\displaystyle=$ $\displaystyle nb+\sum_{l\in
N}\sum_{i=1}^{n-1}iw_{i}^{N\backslash\left\\{l\right\\}}$ $\displaystyle=$
$\displaystyle nb+\sum_{i\in N}\left(i\left(n-2\right)+1\right)w_{i}.$

The last equality is obtained as follows: agent $i$ does not appear in
$N\backslash\left\\{i\right\\},$ appears at rank $i$ in
$N\backslash\left\\{l\right\\}$ if $l>i,$ and appears at rank $i-1$ if $l<i.$
We have $n-i$ coalitions where $l>i$ and $i-1$ coalitions where $l<i.$ Thus,
the coefficient associated to $w_{i}$ is $(n-i)i+(i-1)(i-1)=i(n-2)+1.$

Then, we have that

$\displaystyle\sum_{l\in
N}C\left(N\backslash\left\\{l\right\\}\right)-(n-1)C(N)$ $\displaystyle=$
$\displaystyle nb+\sum_{i\in
N}\left(i\left(n-2\right)+1\right)w_{i}-\left(\left(n-1\right)b+\sum_{i\in
N}\left(n-1\right)iw_{i}\right)$ $\displaystyle=$ $\displaystyle b-\sum_{i\in
N}(i-1)w_{i}$ $\displaystyle<$ $\displaystyle 0,$

and thus $\sum_{l\in N}C\left(N\backslash\left\\{l\right\\}\right)<(n-1)C(N),$
by our assumption on $b.$ Thus, $Core(C)$ is empty.

∎

We provide an example that shows that the conditions in Theorems 1 and 2i) are
not necessary for the core to be non-empty.

######  Example 1.

Suppose that $N=\\{1,2,3,4\\}$ and that $w_{i}=25-5i$ for all $i\in N$. Then,
Theorem 1 tells us that the core is non-empty if $b\leq 15$ while Theorem 2
(_i_) guarantees non-emptiness of the core for $b\geq 50$. For
$b\in\left[35,50\right)$, by Theorem 2 (_ii_) the core is empty. We verify
what happens when $b\in(15,35)$.

For $b\in\left[20,35\right)$, coalitions $\left\\{1,2,3\right\\}$ and
$\left\\{1,2,3,4\right\\}$ use 2 machines, all others use a single one. Using
the fact that we must have $y\left(\\{i,j\\}\right)=b+w_{i}+2w_{j}$ for all
$i\in\\{1,2\\},j\in\\{3,4\\}$ in any core allocation, we obtain maximal
allocations of $(40,35,25,15)$. Using $C(N)-C(N\setminus\\{i\\})$, we obtain
minimal allocations of $(b+15,b+10,b,b-10)$. Immediately, the core is empty
for $b\in(25,35)$. For $b\in\left[20,25\right]$, we can verify that the
allocation $(b+15,b+10,25,15)$ is in the core.

For $b\in(15,20)$, coalition $\left\\{1,2,4\right\\}$ also uses 2 machines.
Using the same technique as above to obtain minimal and maximal allocations,
our only candidate for a core allocation is $(b+15,b+10,25,15)$. But then,
coalition $\\{3,4\\}$ pays 40, while its stand-alone cost is $b+20$, and thus
there are no core allocations.

For $b\in\left(10,15\right]$, all coalitions of 3 or more agents use 2
machines, as well as coalition $\left\\{1,2\right\\}$. In addition to
$\left(b+20,b+15,20,10\right)$, the allocation
$\left(\frac{b}{2}+25,\frac{b}{2}+20,\frac{b}{2}+15,\frac{b}{2}+5\right)$ is
also in the core.

bTheorem 1Theorem 2 part
---
i
part
---
ii
unique
---
core
all.
multiple
---
core
all.
core
---
is empty
(b+15,
---
(b+10,
25,15)
in Core
core
---
is empty
core
---
is empty
full core
---
characterization
$m(N)\geq\mu=3$ $m(\\{1,2,3\\}$
---
=$m(\\{1,2,3\\}$
$=m(N)=2$
$m(S)=1$ else
$m(\\{1,2,3\\}$
---
$=m(N)=2$
$m(S)=1$ else
$m(S)=1$ for all $S$0101520253550 Figure 1. Summary of Example 1.

The example is summarized in Figure 1, with the results on the core and the
description of $m$, the optimal number of machines, depending on machine cost
$b$. In order to provide a clear illustration, Figure 1 does not respect the
appropriate proportions.

When $b\leq w_{\mu}$, the game we obtain is reminiscent of assignments games:
we need to match agents with a machine (those with $b\leq w_{i}$) to those
without (with $b>w_{i})$, matching at most one agent from the second group to
each agent in the first group. An agent from the second group generates value
of $b-w_{i}$ when he matches with any agent from the second group. Notice that
the first group contains at least half of the agents. If it is strictly more,
the only core allocation allocates all gains to the short side of the market,
the agents with $b>w_{i}$. If it is exactly half, as in our example above with
$b\in\left(10,15\right]$, the core contains multiple allocations. This is
where the similarities with the assignment game ends, as members of the second
group do create value when matched together (they share a machine), which
constrains the allocation that is optimal for the first side (those with
$b\leq w_{i}$).

##  4\. Requeueing games with an endogenous number of machines

For the rest of the paper, we consider queueing problems with an existing
queue, which study the problem from a different perspective: while queueing
problems consider the minimal cost of organizing the queue for a set of
players, starting from scratch, in the following, we consider requeueing
problems where possible cost savings can be obtained when we reschedule a
given queue. In our study of the problem with an endogeneous number of
machines, this implies that we start with a given number of machines, and that
the reorganization can include adding or removing machines.333We use queueing
problems with an existing queue and requeuing problems interchangeably.

Then, a _requeueing problem with an endogenous number of machines_ can be
described by $(N,m_{0},\sigma_{0},w,b)$ where $m_{0}$ is the initial number of
machines and $\sigma_{0}$ is the initial (existing) queue. Our first aim is to
find an optimal schedule that minimizes the total costs, as in Section 2. As
for queueing games, we build a coalitional function from the requeueing games,
now associating to each coalition $T\subseteq N$ the maximum cost savings
$V(T)$ it can generate from the initially existing queue. We will distinguish
between two cases based on whether new machines are exclusive for a set of
agents (private) or available for all agents (public).

###  4.1. Private requeueing games

We consider requeueing problems in which if a coalition buys a new machine, it
gains exclusive use of that machine and if a coalition sells a machine it
recovers the full value of that machine. These two assumptions can be seen as
“exclusive” use of machines for a coalition and hence they are “private”
machines for a coalition.

In order to determine the maximal cost savings of a coalition $T\subseteq N$,
we have to define which rearrangements are admissible. Various assumptions
have been made on admissible rearrangements of the initial schedule, see
Curiel et al. (1993), Slikker (2006b), Musegaas et al. (2015), and Atay et al.
(2021), among others. Following the literature, we consider two approaches to
define admissible rearrangements to study the non-emptiness of the core for
requeuing games with an endogenous number of machines.

First, we do not allow agents in a coalition to jump over agents outside the
coalition. Then, we say that a scheduling plan $(m,\sigma$) is _admissible_
for a coalition $T$ with respect to $(m_{0},\sigma_{0})$ if for any agent
outside coalition $T$ there are no new agents in her set of predecessors. That
is, for all $i\in N\setminus T$ it holds that $\varphi(i)=\varphi_{0}(i)$ and

(1) $\\{l\in N^{\varphi(i)}:s(l)<s(i)\\}\subseteq\\{l\in
N^{\varphi_{0}(i)}:s_{0}(l)<s_{0}(i)\\}.$

Notice that we do not require equality, as a predecessor of $i$ might move to
a new machine. For short, we call this assumption the ”no swaps” assumption,
and the set of admissible schedules for coalition $T$ that satisfy (1) is
denoted by $\Sigma^{ns}_{T}$.

Second, we relax the condition by allowing agents in a coalition to jump over
agents outside the coalition. We say that a scheduling plan $(m,\sigma$) is
_admissible_ for a coalition $T$ with respect to $(m_{0},\sigma_{0})$ if the
starting time for all agents outside the coalition does not increase. That is,
for all $i\in N\setminus T$ it holds that $\varphi(i)=\varphi_{0}(i)$ and

(2) $s(i)\leq s_{0}(i).$

Once again, we do not have equality, as predecessors are allowed to move to a
new machine. By opposition, this is the ”swaps” assumption, and the set of
admissible schedules for coalition $T$ that satisfy (2) is denoted by
$\Sigma^{s}_{T}$.

In our setting, we also must consider the possibility for a coalition to sell
a machine. We suppose that a coalition $T$ can sell a machine only if all
users of that machine are members of $T$. We then suppose that the agents that
were on the removed machine move at the end of the queue on the remaining
machines, a condition that is already covered by both (1) and (2).

For a set of admissible schedules, we can associate the corresponding
cooperative TU-game called a private requeueing game with an endogenous number
of machines. A _private requeuing problem with an endogenous number of
machines_ is a 5–tuple $(N,m_{0},\sigma_{0},w,b)$.444Since population and
costs are fixed, with an abuse of notation, we denote a private requeuing
problem also by the initial number of machines and the initial queue,
$(m_{0},\sigma_{0})$. The corresponding _private requeueing game with an
endogenous number of machines_ $(N,V)$ is defined by

$V(T)=c_{\sigma_{0}}(T)-c_{\sigma}(T)-(m-m_{0})b,$

where $(m,\sigma)$ is an optimal admissible scheduling plan for coalition $T$.
Furthermore, admissible schedules with and without swaps lead to different
games. We denote private requeueing games with swaps by $V_{s}$ and private
requeueing games without swaps by $V_{ns}$.

While concavity of a cost game is a sufficient condition for its core to be
non-empty, for value games the corresponding concept is that of convexity. The
condition has been widely studied to prove balancedness of sequencing games
associated with different problems (see for instance Curiel et al., 1994;
Hamers et al., 2005; Musegaas et al., 2018). A game $(N,v)$ is said to be
_convex_ if for all $i\in N$ and all $S\subseteq T\subseteq
N\setminus\\{i\\}$, it holds $v(T\cup\\{i\\})-v(T)\geq v(S\cup\\{i\\})-v(S)$.

Unfortunately, Example 2 shows that the associated game need not be balanced,
regardless if admissible schedules allow or not to jump over players outside
the coalition.

######  Example 2.

Consider $(N,m_{0},\sigma_{0},w,b)$ with $N=\\{1,2,3,4,5\\}$. The waiting
costs per unit for agents are given by the weight vector $w=(w_{i})_{i\in
N}=(20,15,13,13,5)$, and the cost of a machine is $b=18$.

First, we suppose that $(m_{0},\sigma_{0})$ is such that we order agents in
the queue on one machine according to their weights, in decreasing order:

$m_{1}$ | 1 | 2 | 3 | 4 | 5
---|---|---|---|---|---

.

Notice that agent 1 is a dummy player since he is served first, moving to
another machine is strictly worse for her. Thus, we can focus on the game
$(N,V_{s})$ for the remaining agents. One can calculate that
$V_{s}(\\{2,3,4\\})=36$, $V_{s}(\\{2,3,5\\})=25$, $V_{s}(\\{3,4,5\\})=44$, and
$V_{s}(\\{2,3,4,5\\})=46$. Next, let us consider the coalition
$T=\\{2,4,5\\}$.

First, suppose that we allow players in the coalition to jump over players
outside the coalition when we define admissible rearrangements. Take the
coalition $T=\\{2,4,5\\}$. Then, an optimal scheduling plan for coalition $T$,
$(m_{T},\sigma_{T})$, is

$m_{1}$ | 1 | 4 | 3
---|---|---|---
$m_{2}$ | 2 | 5 |

,

and then the total waiting cost savings are 15+26+15=56, but the coalition
buys a machine at a cost 18, and hence the maximal total cost savings is
$38=V_{s}(\\{2,4,5\\})$. Then,
$V_{s}(\\{2,3,4\\})+V_{s}(\\{2,3,5\\})+V_{s}(\\{3,4,5\\}+V_{s}(\\{2,4,5\\})=143>138=3V_{s}(\\{2,3,4,5\\})$,
and hence the core is empty.

Second, suppose that we do not allow players in the coalition to jump over
players outside the coalition when we define admissible rearrangements. Take
the coalition $T=\\{2,4,5\\}$. Then, an optimal scheduling plan for coalition
$T$, $(m^{\prime}_{T},\sigma^{\prime}_{T})$, is

$m_{1}$ | 1 | 2 | 3
---|---|---|---
$m_{2}$ | 4 | 5 |

,

and then the total waiting cost savings are 39+15=54, but the coalition buys a
machine at a cost 18, and hence the maximal total cost savings is
$36=V_{ns}(\\{2,4,5\\})$. For all other coalitions $S$, we have
$V_{ns}(S)=V_{s}(S)$. Then,
$V_{ns}(\\{2,3,4\\})+V_{ns}(\\{2,3,5\\})+V_{ns}(\\{3,4,5\\}+V_{ns}(\\{2,4,5\\})=141>138=3V_{ns}(\\{2,3,4,5\\})$,
and hence the core is empty.

Although we have seen that the associated private requeueing game can have an
empty core, there are sufficient conditions to guarantee the non-vacuity of
the core. First, we provide a lower bound on the cost of a machine for the
non-emptiness of the core.

######  Theorem 3.

Let $(N,m_{0},\sigma_{0},w,b)$ be a private requeuing problem and let
$(N,V_{ns})$ be the associated private requeuing game without swaps, and
$(N,V_{s})$ be the associated private requeueing game with swaps. If $b\leq
w_{n}$, then $Core(V_{ns})\neq\emptyset$ and $Core(V_{s})\neq\emptyset$.

###### Proof.

Since the cost a machine is at most equal to the smallest unit waiting cost,
$b\leq w_{n}$, for any coalition $S\subseteq N$, it is optimal to have $|S|$
machines. Let $s_{0}(i)$ be the starting time of the job $i$ under the
schedule $\sigma_{0}$. The first agents at each machine in the initial
schedule, that is $i\in N$ such that $s_{0}(i)=0$, need not change their
position. For all $S\subseteq N$, let $S_{0}$ be the set of such agents. For
all other agents $i\in N\setminus N_{0}$ such that $s_{0}(i)\geq 1$, buying a
new machine is the option that maximizes the cost savings at any given
coalition since $b\leq w_{n}$. Thus there exists a unique core allocation
where $y_{i}=s_{0}(i)w_{i}-b$ for all $i\in N\setminus N_{0}$ and $y_{i}=0$
for $i\in N_{0}$. Then, $\sum\limits_{i\in N}y_{i}=\sum\limits_{i\in
N_{0}}0+\sum\limits_{i\in N\setminus N_{0}}(s_{0}(i)w_{i}-b)=\sum\limits_{i\in
N\setminus N_{0}}s_{0}(i)w_{i}-(n-m_{0})b=V_{s}(N)=V_{ns}(N)$, and efficiency
holds. For any coalition $S\subset N$, $y(S)=\sum\limits_{i\in S\setminus
S_{0}}(s_{0}(i)w_{i}-b)$. Since using a machine for each agent in the
coalition is the optimal schedule in both cases $y(S)=V_{s}(S)=V_{ns}(S)$.
Thus, $y$ also satisfies coalitional rationality and hence it is a core
allocation. ∎

Following a lower-bound on the cost of a machine to guarantee the non-
emptiness of the core, we provide an upper-bound on the cost of a machine for
the non-emptiness of the core when the initial number of machines is 1,
$m_{0}=1$. Intuitively, it consists in setting the machine cost so high that
no coalition wants to buy a second machine. The problem then becomes one or
reorganizing the queue on the existing machine, making the problem equivalent
to one with a single machine and no possibility to add more.

######  Theorem 4.

Let $(N,m_{0},\sigma_{0},w,b)$ be a private requeuing problem. If $m_{0}=1$
and $b\geq\max_{k=1}^{\mu}(n-k)w_{i}$, then $Core(V_{s})\neq\emptyset$ and
$Core(V_{ns})\neq\emptyset$.

###### Proof.

We will show that for the private sequencing game without swaps where the
agents are ordered in an increasing way with respect to their waiting costs at
the initial order, making use of the only machine is better than buying a new
machine for any coalition. Given that this is the worst case scenario in terms
of ordering, and we still do not want to buy more than one machine, the result
holds for all other orderings. Formally, we consider an initial schedule
$\sigma_{0}$ such that $s_{0}(i)=n-i$ for all $i\in N.$

First, consider the last agent in the order, agent 1, which by definition is
such that $w_{1}\geq(w_{i})_{i\in N\setminus\\{1\\}}$. If she buys a machine,
the total cost savings are $(n-1)w_{1}-b$. Since
$b\geq\max_{k=1}^{\mu}(n-k)w_{i}\geq(n-1)w_{1}$, the total cost savings
$(n-1)w_{1}-b\leq 0$. Hence, agent 1 is worse off by buying a new machine.
Note that for any other individual coalition $\\{i\\}$ such that $i\in
N\setminus\\{1\\}$, since the gain by buying a new machine is
$(n-i)w_{i}<(n-1)w_{1}$, the total cost savings $(n-i)w_{i}-b<(n-1)w_{1}-b\leq
0$. Thus, no individual coalition $\\{i\\}$ such that $i\in N$ has incentives
to buy a new machine.

We next show that it is true for a coalition containing $k\leq\mu$ agents.
Consider the coalition of the last $k$ agents in the order, agents 1 through
$k$. Recall that $w_{1}\geq\ldots\geq w_{k}\geq w_{i}$ for all other $i\in N$
such that $s(i)<n-k$. Then, the gain for coalition $\\{1,\ldots,k\\}$ is
$(n-1)w_{1}+\ldots+(n-k)w_{k}$. Since
$b\geq\max_{k=1}^{\mu}(n-k)w_{i}\geq(n-1)w_{1}+\ldots+(n-k)w_{k}$, the total
cost savings $\\{k-1,\ldots,1\\}$ is $(n-1)w_{1}+\ldots+(n-k)w_{k}-b\leq 0$,
and hence coalition $\\{1,\ldots,k\\}$ prefers to use one machine. Notice that
no other coalition $S$ with $|S|=k$ can achieve higher total cost savings than
coalition $\\{1,\ldots,k\\}$, hence no $k$-agent coalition has incentives to
buy a new machine.

Notice that for any coalition that consists of last $k$ agents where $k>\mu$,
only agents with a position in the initial order of more than $\mu$ get to use
the new machine. Hence, their gains are less than the last $\mu$ agents, and
they also prefer to use the only machine provided to them. Moreover, since we
compare all possible coalitions with the same size coalition that consists of
the last agents in the initial queue, our result under not allowing swaps
subsumes if we allow swaps. Then, we deal with a 1-machine problem with an
initial queue. Together with the result of Curiel et al. (1989) and Hamers et
al. (1999) stating that the core is always non-empty for 1-machine problem, we
guarantee the non-emptiness of the core whenever
$b\geq\max_{k=1}^{\mu}(n-k)w_{i}$ with $m_{0}=1$. ∎

Given that the previous result is obtained using the worst case scenario of a
completely inefficient initial ordering, for a random initial ordering a lower
bound guaranteeing a non-empty core could be found. However, a general
expression for such a bound is difficult to obtain.

###  4.2. Public requeueing games

Implicit in the previous subsection was the assumption that if a coalition
buys a new machine it would gain exclusive use of that machine. That does not
have to be the case. We consider here the opposite assumption, in which new
machines are available for all agents. To illustrate the differences between
the two assumptions, suppose that we have a long queue of agents waiting to go
through security/ticket control at a sporting event. If somehow agents waiting
got hold of an additional employee who could, given appropriate compensation,
open a new lane to speed up the process, who would have access to that lane?
Up to now, we had supposed that this new lane would be a VIP lane, accessible
only to agents who helped compensate this additional worker. But another
reasonable interpretation is that this new lane would be available to all,
making this new machine a public good.

More precisely, if a new line opens up, the initial schedule $\sigma_{0}$ is
split up in two: 1 and 2 are served first, 3 and 4 second, and 5 third and the
new scheduling plan $(m^{\prime},\sigma^{\prime})$ is

$m_{1}$ | 1 | 3 | 5
---|---|---|---
$m_{2}$ | 2 | 4 |

.

Then, we can calculate the worth of the coalition $T=\\{2,4,5\\}$, as the
waiting costs saved by its members only, net of the new machine cost. In other
words, when we add machines a coalition receives the gains its members make in
waiting costs, as the queue moves up, but must fully pay for the new machines.

To properly express how this requeueing occurs, we build from the initial
schedule $\sigma_{0}=(\varphi_{0},s_{0})$ a priority order $\pi$, which will
allow us to determine, which agent moves up when new machines becomes
available. Formally, for any $i,j\in N$

$\pi(i)<\pi(j)\Leftrightarrow\bigl{\\{}s_{0}(i)<s_{0}(j)\text{ or
}\\{s_{0}(i)=s_{0}(j)\text{ and }\varphi_{0}(i)<\varphi_{0}(j)\\}\bigr{\\}}.$

In words, to rank agents we first look at the period in which they are served,
and break ties by giving priority to agents served on machines identified with
lower numbers.

Notice that in a public requeueing game a coalition $T$ has much less ability
to choose an alternative schedule. Once it has chosen a new number of
machines, agents requeue automatically using the ordering $\pi$. Coalition $T$
however can still reorder its members, under constraint. We assume that they
can do so at two occasions, before and after adjusting the number of machines.
We define as $\hat{\Sigma}^{s}$ and $\hat{\Sigma}^{ns}$ the admissible
schedules under these constraints.

In a public requeuing game (public game for short), we suppose that a
coalition $T$ still can only sell a machine if only its members are using it,
but we now further suppose that the revenues from the sale must be split
equally among all agents in $N$, as the machines are public. Coalition $T$
thus receives a fraction $\frac{|T|}{n}$ of the proceeds.

Let $\widehat{V}_{s}(T,k)$ and $\widehat{V}_{ns}(T,k)$ be the functions giving
the value (possibly negative) that we obtain if we force coalition $T$ to use
$k$ machines, in the public game with and without swaps, respectively. We then
have that:

$\widehat{V}_{s}(T,k)=\left\\{\begin{array}[]{c}\max_{\sigma\in\hat{\Sigma}_{T}^{s}(k)}\left(\sum_{i\in
T}\left(s_{0}(i)\right)-s(i))w_{i}-(k-m_{0})b\right)\text{ if }k\geq m_{0}\\\
\max_{\sigma\in\hat{\Sigma}_{T}^{s}(k)}\left(\sum_{i\in
T}\left(s_{0}(i)\right)-s(i))w_{i}-\frac{\left|T\right|}{n}(k-m_{0})b\right)\text{
if }k<m_{0}\end{array}\right.$

It is possible for $\widehat{\Sigma}_{T}^{s}(k)$ to be empty if $k<m_{0}$, if
$T$ does not have exclusive use of $m_{0}-k$ machines, in which case we simply
let $\hat{V}_{s}(T,k)=0$. We define $\hat{V}_{ns}(T,k)$ in the same manner.

We obtain the optimal cost savings for a coalition by maximizing over the
number of machines:
$\widehat{V}_{s}(T)\equiv\max_{k\in\\{1,...,n\\}}\widehat{V}_{S}(T,k)$ and
$\widehat{V}_{ns}(T)\equiv\max_{k\in\\{1,...,n\\}}\widehat{V}_{ns}(T,k)$.

A _public requeueing problem_ is a requeueing problem
$(N,m_{0},\sigma_{0},w,b)$ with an endogenous number of machines where the
machines are public goods. If all machines are public goods, we call a
requeueing game with an endogenous number of machines a _public requeueing
game_ denoted by $(N,\widehat{V}_{s})$ or $(N,\widehat{V}_{ns})$, depending if
we allow swaps or not.

We guarantee the non-emptiness of the core for public requeueing games when
the initial queue is optimal.

######  Theorem 5.

Let $(N,m_{0},\sigma_{0},w,b)$ be a public requeueing problem such that the
ordering $\pi$ induced by $\sigma_{0}$ is the optimal queue $\\{1,2,...,n\\}$,
and let $(N,\widehat{V}_{s})$ be the associated public requeueing game with
swaps and $(N,\widehat{V}_{ns})$ be the associated public requeueing game
without swaps. Then, $Core(\widehat{V}_{s})\neq\emptyset$ and
$Core(\widehat{V}_{ns})\neq\emptyset$.

###### Proof.

Given that $\widehat{V}_{ns}(S)\leq\widehat{V}_{s}(S)$ for all $S\subset N$
and $\widehat{V}_{ns}(N)=\widehat{V}_{s}(N)$, it suffices to show that
$Core(\widehat{V}_{s})\neq\emptyset$. To ease on the notation in the proof, we
use $V$ for $\widehat{V}_{s}$.

Let $V(S,k)$ be the total gain (potentially negative) when we force coalition
$S$ to use $k$ machines. If $k>m_{0}$, we have $V(S,k)=\sum_{l\in
S}\left(\left\lceil\frac{l}{m_{0}}\right\rceil-\left\lceil\frac{l}{k}\right\rceil\right)w_{l}-b(k-m_{0})$.

For $m_{0}>k$, we have that $V(S,k)=\frac{|S|}{n}b(m_{0}-k)-\sum\limits_{l\in
S}\left(\left\lceil\frac{l}{k}\right\rceil-\left\lceil\frac{l}{m_{0}}\right\rceil\right)w_{l}$
which is only feasible if coalition $S$ contains all users of $m_{0}-k$
machines. We consider the value function $\overline{V}(S,k)$ which allows $S$
to sell any number of machines it wants and receive the full amount for it.
That is, $\overline{V}(S,k)=b(m_{0}-k)-\sum\limits_{l\in
S}\left(\left\lceil\frac{l}{k}\right\rceil-\left\lceil\frac{l}{m_{0}}\right\rceil\right)w_{l}$.
On the other hand, for $k>m_{0}$, we have $\overline{V}(S,k)=V(S,k)$.

Notice that for all $S$ and $k$, $\overline{V}(S,k)\geq V(S,k)$ and
$\overline{V}(N,k)=V(N,k)$. Let $\overline{V}$ be the maximum value function
over the number of machines, i.e.,
$\overline{V}(S):=\max\limits_{k\in\\{1,...,n\\}}\overline{V}(S,k)$. Then,
$\overline{V}(S)\geq V(S)$ and $\overline{V}(N)=V(N)$. Let $\overline{m}(S)$
be the optimal number of machines for $S$.555There could be many, in which
case we pick the lowest one. $\overline{m}(\cdot)$ has the same properties as
$m(\cdot)$.

Let $S\subseteq N\setminus\\{i,j\\}$ and suppose that $i>j$. By Lemma 2 we
have that $\overline{m}(S\cup\\{i\\})\leq\overline{m}(S\cup\\{j\\})$.

By definition,
$\overline{V}(S\cup\\{i,j\\})\geq\overline{V}(S\cup\\{i,j\\},\overline{m}(S\cup\\{j\\}))$,
and hence

$\displaystyle\overline{V}(S\cup\\{i,j\\})$ $\displaystyle\geq$
$\displaystyle\sum\limits_{l\in
S}\left(\left\lceil\frac{l}{m_{0}}\right\rceil-\left\lceil\frac{l}{\overline{m}(S\cup\\{j\\})}\right\rceil\right)w_{l}-b(\overline{m}(S\cup\\{j\\})-m_{0})$
$\displaystyle+$
$\displaystyle\left(\left\lceil\frac{i}{m_{0}}\right\rceil-\left\lceil\frac{i}{\overline{m}(S\cup\\{j\\})}\right\rceil\right)w_{i}+\left(\left\lceil\frac{j}{m_{0}}\right\rceil-\left\lceil\frac{j}{\overline{m}(S\cup\\{j\\})}\right\rceil\right)w_{j}$
$\displaystyle=$
$\displaystyle\overline{V}(S\cup\\{j\\})+\left(\left\lceil\frac{i}{m_{0}}\right\rceil-\left\lceil\frac{i}{\overline{m}(S\cup\\{j\\})}\right\rceil\right)w_{i}$

and thus

(3)
$\overline{V}(S\cup\\{i,j\\})-\overline{V}(S\cup\\{j\\})\geq\left(\left\lceil\frac{i}{m_{0}}\right\rceil-\left\lceil\frac{i}{\overline{m}(S\cup\\{j\\})}\right\rceil\right)w_{i}.$

Similarly, we have that
$\overline{V}(S)\geq\overline{V}(S,\overline{m}(S\cup\\{i\\}))$, and thus

$\overline{V}(S)\geq\sum\limits_{l\in
S}\left(\left\lceil\frac{l}{m_{0}}\right\rceil-\left\lceil\frac{l}{\overline{m}(S\cup\\{i\\})}\right\rceil\right)w_{l}-b(\overline{m}(S\cup\\{i\\})-m_{0})$

and

(4)
$\overline{V}(S\cup\\{i\\})-\overline{V}(S)\leq\left(\left\lceil\frac{i}{m_{0}}\right\rceil-\left\lceil\frac{i}{\overline{m}(S\cup\\{i\\})}\right\rceil\right)w_{i}.$

Combining (3) and (4), we get

$\displaystyle\overline{V}(S\cup\\{i,j\\})-\overline{V}(S\cup\\{j\\})$
$\displaystyle\geq\left(\left\lceil\frac{i}{m_{0}}\right\rceil-\left\lceil\frac{i}{\overline{m}(S\cup\\{j\\})}\right\rceil\right)w_{i}$
$\displaystyle\geq\left(\left\lceil\frac{i}{m_{0}}\right\rceil-\left\lceil\frac{i}{\overline{m}(S\cup\\{i\\})}\right\rceil\right)w_{i}$
$\displaystyle\geq\overline{V}(S\cup\\{i\\})-\overline{V}(S),$

where the second inequality follows from
$\overline{m}(S\cup\\{i\\})\leq\overline{m}(S\cup\\{j\\})$, proving that
$\overline{V}$ is convex and hence $Core(\overline{V})$ is non-empty. Then,
$\overline{V}(S)\geq V(S)$ and $\overline{V}(N)=V(N)$ imply that
$Core(\overline{V})\subseteq Core(V)$. Together with the non-emptiness of
$Core(\overline{V})$, it implies that $Core(V)$ is also non-empty which
completes the proof. ∎

Interestingly, while the concept of public sequencing games leads naturally to
the assumption that a coalition getting rid of machines would only collect
part of the value of that machine, and would be severely limited in when they
could sell a machine that is publicly owned, it turns out that these
assumptions are not necessary to obtain core allocations. We always have core
allocations, even if we eliminate all constraints on selling machines and
allow coalitions to pocket to full value of the machines it sells. Even more,
the game becomes convex with these assumptions.

The assumption that agents are ranked in an optimal way in the original
schedule is crucial in our proof, allowing us to obtain the same structure for
the optimal number of machines as when queueing without an initial allocation.
For instance, if agent 1 has a particularly large waiting cost and is
initially ranked last, when he is by himself he might prefer to buy many
machines to be served earlier, while with other agents it might not be
necessary, as switching spots with other members of the coalition might allow
him to be served early without buying as many machines.

An important consequence of Theorem 5 is that whenever each agents own a
machine at the initial schedule, then the core is always non-empty.

######  Corollary 1.

Given a public requeueing problem $(N,m_{0},\sigma_{0},w,b)$ such that
$m_{0}=|N|$, the associated public requeueing game without swaps
$(N,\widehat{V}_{ns})$, and with swaps $(N,\widehat{V}_{s})$, has a non-empty
core.

Theorem 5 establishes the non-emptiness of the core for public requeueing
games under the assumption that the initial schedule is optimal. The next
example shows that if we relax this assumption, the core of a public
requeueing game can be empty.

######  Example 3.

Consider $(N,m_{0},\sigma_{0},w,b)$ with $N=\\{1,2,3,4\\}$, $m_{0}=1$, and the
ordering induced by $\sigma_{0}$ being $\pi=(4,3,2,1)$. The waiting costs per
unit for agents are $w=(w_{i})_{i\in N}=(13,7,6,1)$, and the cost of a machine
is $b=15$.

Notice first that the initial queue $(4,3,2,1)$ is not optimal:

$m_{1}$ | 4 | 3 | 2 | 1
---|---|---|---|---

.

Suppose that we allow agents to jump over the agents not belonging to the
coalition. Let $(N,\widehat{V}_{s})$ be the associated public requeueing game.
Let us illustrate how to calculate the value of a coalition by doing it for
$\\{1,4\\}$. If agent 1 and agent 4 do not buy any machine, then they switch
their positions:

$m_{1}$ | 1 | 3 | 2 | 4
---|---|---|---|---

,

and hence the total savings for $\\{1,4\\}$ is $(13-1)\times 3=36$.

If they buy a new machine, since it is a public requeueing game, the queue
moves in a way such that agents 3, 4 are served first and agents 1, 2 are
served second. Then, agents 1 and 4 change positions:

$m_{1}$ | 3 | 2 |  |
---|---|---|---|---
$m_{2}$ | 1 | 4 |  |

,

and hence the total savings for $\\{1,4\\}$ is $13\times 3-15-1=23$.

If they buy two new machines, the queue moves in a way such that agents 2,3,4
are served in the first position of a machine while agent 1 is served in the
second position at a machine. Then, agents 1 and 4 switch positions:

$m_{1}$ | 1 | 4 |  |
---|---|---|---|---
$m_{2}$ | 3 |  |  |
$m_{3}$ | 2 |  |  |

,

and hence the total savings for $\\{1,4\\}$ is $13\times 3-15\times 2-1=8$.
Finally, if they buy three machines, all agents’ operations are processed at
the first position on each machine:

$m_{1}$ | 1 |  |  |
---|---|---|---|---
$m_{2}$ | 2 |  |  |
$m_{3}$ | 3 |  |  |
$m_{4}$ | 4 |  |  |

,

and hence the total savings is $13\times 3-15\times 3=-6$. Then, the maximum
of possible total cost savings for $\\{1,4\\}$ is achieved when they do not
buy any new machine, $\widehat{V}_{s}(\\{1,4\\})=\max\\{36,23,8,-6\\}=36$.

Consider now coalitions $\\{1,4\\}$, $\\{2,4\\}$, $\\{3,4\\}$, $\\{1,2,3\\}$,
and $\\{1,2,3,4\\}$. Following our illustration, one can check that
$\widehat{V}_{s}(\\{1,4\\})=36$, $\widehat{V}_{s}(\\{2,4\\})=12$,
$\widehat{V}_{s}(\\{3,4\\})=5$, $\widehat{V}_{s}(\\{1,2,3\\})=31$, and
$\widehat{V}_{s}(N)=37$. Now, suppose that there exists a core allocation
$(y_{1},y_{2},y_{3},y_{4})\in Core(\widehat{V}_{s})$. Then, it would satisfy
the core constraints $y_{1}+y_{4}\geq 36$, $y_{2}+y_{4}\geq 12$,
$y_{3}+y_{4}\geq 5$, $y_{1}+y_{2}+y_{3}\geq 31$. Nevertheless, such a payoff
vector $(y_{1},y_{2},y_{3},y_{4})$ is not in the core since the core
constraints
$(y_{1}+y_{4})+(y_{2}+y_{4})+(y_{3}+y_{4})+2(y_{1}+y_{2}+y_{3})=3(y_{1}+y_{2}+y_{3}+y_{4})\geq
115$ is not compatible with $3\widehat{V}_{s}(N)=111$, and hence
$Core(\widehat{V}_{s})=\emptyset$.

##  5\. Concluding remarks

This paper studies queueing problems from a game theoretical point of view.
The novelty of this paper is that the number of machines is endogenous. For a
given problem, agents are allowed to (de)activate as many machines they want,
at a cost. We have distinguished two types of queueing problems: without and
with an initial queue. For the first case, we have provided both a lower and
an upper bound on the cost of machine to guarantee the non-emptiness of the
core. Moreover, in some instances we have provided a full characterization of
the core by means of concavity. For the second case, although we have shown
that the core may be empty, we have guaranteed balancedness when all machines
are accessible to all agents and the initial ordering correctly ranks agents
in decreasing order of their waiting costs.

Compared to the earlier literature, our main innovations are (i) the existence
of an endogenous number of machines at a given queueing problem, (ii) the cost
associated with a machine to (de)activate it, (iii) the distinction between
private and public queueing problems with an initial queue.

An interesting direction for future research is to study the existence of an
allocation rule that always selects a stable allocation for balanced
requeueing games. Furthemore, although we have a counterexample when swaps are
allowed for public requeueing games with the non-optimal initial queue, it is
still an open question whether it is also the case when swaps are not allowed.

## References

  * Atay et al. (2021) Atay, A., P. Calleja, and S. Soteras (2021), “Open shop scheduling games.” _European Journal of Operational Research_ , 295, 12–21.
  * Bahel and Trudeau (2019) Bahel, E. and C. Trudeau (2019), “Stability and fairness in the job scheduling problem.” _Games and Economic Behavior_ , 117, 1–14.
  * Calleja et al. (2002) Calleja, P., P. Borm, H. Hamers, F. Klijn, and M. Slikker (2002), “On a new class of parallel sequencing situations and related games.” _Annals of Operations Research_ , 109, 265–277.
  * Chun (2006) Chun, Y. (2006), “No-envy in queueing problems.” _Economic Theory_ , 29, 151–162.
  * Chun (2016) Chun, Y. (2016), _Fair queueing_. Springer.
  * Chun and Heo (2008) Chun, Y. and E. J. Heo (2008), “Queueing problems with two parallel servers.” _International Journal of Economic Theory_ , 4, 299–315.
  * Curiel et al. (1989) Curiel, I., G. Pederzoli, and S. Tijs (1989), “Sequencing games.” _European Journal of Operational Research_ , 40, 344–351.
  * Curiel et al. (1993) Curiel, I., J. Potters, R. Prasad, S. Tijs, and B. Veltman (1993), “Cooperation in one machine scheduling.” _Zeitschrift für Operations Research_ , 38, 113–129.
  * Curiel et al. (1994) Curiel, I., J. Potters, R. Prasad, S. Tijs, and B. Veltman (1994), “Sequencing and cooperation.” _Operations Research_ , 42, 566–568.
  * Gillies (1959) Gillies, D. B. (1959), “Solutions to general non-zero-sum games.” In _Contributions to the Theory of Games IV_ (A. W. Tucker and R. D. Luce, eds.), 47–85, Princeton University Press.
  * Hamers et al. (1999) Hamers, H., F. Klijn, and J. Suijs (1999), “On the balancedness of multiple machine sequencing games.” _European Journal of Operational Research_ , 119, 678–691.
  * Hamers et al. (2005) Hamers, H., F. Klijn, and B. Van Velzen (2005), “On the convexity of precedence sequencing games.” _Annals of Operations Research_ , 137, 161–175.
  * Maniquet (2003) Maniquet, F. (2003), “A characterization of the shapley value in queueing problems.” _Journal of Economic Theory_ , 109, 90–103.
  * Musegaas et al. (2015) Musegaas, M., P. Borm, and M. Quant (2015), “Step out–Step in sequencing games.” _European Journal of Operational Research_ , 246, 894–906.
  * Musegaas et al. (2018) Musegaas, M., P. Borm, and M. Quant (2018), “On the convexity of step out–step in sequencing games.” _TOP_ , 26, 68–109.
  * Shapley (1953) Shapley, L. S. (1953), “A value for n-person games.” In _Contributions to the Theory of Games II_ (Kuhn. H. W. and A. W. Tucker, eds.), 307––317, Princeton University Press.
  * Shapley (1971) Shapley, L. S. (1971), “Cores of convex games.” _International Journal of Game Theory_ , 1, 11–26.
  * Slikker (2006a) Slikker, M. (2006a), “Balancedness of multiple machine sequencing games revisited.” _European Journal of Operational Research_ , 174, 1944–1949.
  * Slikker (2006b) Slikker, M. (2006b), “Relaxed sequencing games have a nonempty core.” _Naval Research Logistics_ , 53, 235–242.
  * Smith (1956) Smith, W. (1956), “Various optimizers for single-stage production.” _Naval Research Logistics Quarterly_ , 3, 59–66.