# Resource-Aware Cost-Sharing Mechanisms with Priors

Vasilis Gkatzelis<EMAIL_ADDRESS>Drexel University  Emmanouil Pountourakis
<EMAIL_ADDRESS>Drexel University  Alkmini Sgouritsa<EMAIL_ADDRESS>University of Liverpool

###### Abstract

In a decentralized system with $m$ machines, we study the selfish scheduling
problem where each user strategically chooses which machine to use. Each
machine incurs a cost, which is a function of the total load assigned to it,
and some cost-sharing mechanism distributes this cost among the machine’s
users. The users choose a machine aiming to minimize their own share of the
cost, so the cost-sharing mechanism induces a game among them. We approach
this problem from the perspective of a designer who can select which cost-
sharing mechanism to use, aiming to minimize the price of anarchy (PoA) of the
induced games.

Recent work introduced the class of _resource-aware_ cost-sharing mechanisms,
whose decisions can depend on the set of machines in the system, but are
oblivious to the total number of users. These mechanisms can guarantee low PoA
bounds for instances where the cost functions of the machines are all convex
or concave, but can suffer from very high PoA for cost functions that deviate
from these families.

In this paper we show that if we enhance the class of resource-aware
mechanisms with some prior information regarding the users, then they can
achieve low PoA for a much more general family of cost functions. We first
show that, as long as the mechanism knows just two of the participating users,
then it can assign special roles to them and ensure a constant PoA. We then
extend this idea to settings where the mechanism has access to the probability
with which each user is present in the system. For all these instances, we
provide a mechanism that achieves an expected PoA that is logarithmic in the
expected number of users.

##  1 Introduction

In this paper we revisit a classic selfish scheduling problem: in a large
decentralized system with a set $M$ of machines and a set $\mathcal{N}$ of
registered users, each day some subset of these users enter the system seeking
to process some task. Each user assigns their task to one of the machines,
generating a cost that depends on the machine’s total load, and the cost of
each machine is then charged to its users, through some cost-sharing
mechanism. The users’ goal is to minimize their own share of the cost, so they
strategically assign their task to the machine that would yield the smallest
cost share. However, their cost share depends on the congestion of each
machine, and thus on the strategic choices of all the other users currently in
the system, giving rise to a game.

The need to better understand these games and to evaluate the efficiency of
their outcomes lies at the heart of Algorithmic Game Theory, and some of the
first seminal papers in this literature analyzed the _price of anarchy_ (PoA)
of such games, i.e., the extent to which the performance of their Nash
equilibria approximates the optimal performance. Much of this work, e.g., in
congestion games and network formation games, assumed that the users share the
cost _equally_ , in accordance with the Shapley value cost-sharing mechanism
(e,g., see Chapters 18 and 19, respectively, from Nisan et al. (2007)).
However, it soon became clear that the equal-sharing policy can lead to highly
inefficient outcomes, even in very simple instances Anshelevich et al. (2008).
As a result, subsequent work focused on the design of alternative, more
sophisticated, cost-sharing mechanisms, with the goal of reducing the PoA.

The first to study the extent to which a designer can reduce the PoA using
improved cost-sharing mechanisms were Chen et al. (2010). One of their main
goals was to analyze mechanisms that are _stable_ (i.e., guarantee the
existence of pure Nash equilibria in the games they induce) and
_decentralized_ (i.e., have limited information regarding the overall state of
the system). Taking the need for decentralization to an extreme, they focused
on the class of _oblivious_ cost-sharing mechanisms111Also known as _uniform_
mechanisms., which decide how to share the cost of each machine among its
users without using _any_ information regarding the set of other users or
machines that are present in the system. After providing a precise
characterization of stable mechanisms for network formation games (where the
resources that the agents use have _constant_ cost-functions), they
systematically analyzed their performance. Building on this work, von
Falkenhausen and Harks (2013) and then Christodoulou et al. (2017) considered
more general classes of cost functions. Among other results, von Falkenhausen
and Harks (2013) showed that no oblivious cost-sharing mechanism can guarantee
a PoA bound better than linear function in the number of agents, even for
instances with concave cost functions. Motivated by this limitation of
oblivious mechanisms, subsequent work introduced the model of _resource-aware
mechanisms_ Christodoulou and Sgouritsa (2019); Christodoulou et al. (2017).
Compared to oblivious mechanisms, resource-aware ones are more informed: their
decision regarding how to share the cost of a machine can also depend on the
set of other machines that are available in the system. Using this additional
information, Christodoulou et al. (2017) managed to overcome the limitations
of oblivious mechanisms and design resource-aware mechanisms that achieve a
constant PoA for convex and concave cost functions. On the negative side, they
showed that there exists a class of seemingly simple cost functions for which
no resource-aware cost-sharing mechanism can achieve a PoA better than
$O(\sqrt{n})$.

These negative results suggest that it may be impossible for resource-aware
mechanisms to achieve a constant PoA for interesting cost functions beyond
convex and concave. However, although resource-aware mechanisms are more
informed than oblivious ones, they are still severely limited in terms of what
they know about the users in the system. In this paper we enhance resource-
aware mechanisms with some prior information regarding the users in the
system, and we show that this is sufficient for us to design cost-sharing
mechanisms that achieve low PoA for a very broad class of cost functions.

###  1.1 Our Results

Our main results show that, using only a limited amount of prior information
regarding the set of users in the system, resource-aware cost-sharing
mechanisms can guarantee a low price of anarchy for a very wide class of
selfish scheduling problems.

##### Cost functions.

In contrast to prior work in cost-sharing mechanisms, which was mostly
restricted to either convex or concave cost functions, our positive result
applies to a much larger class of functions. Specifically, we consider any
instance where the cost functions of the machines satisfy a mild condition
regarding how fast they can grow. We call a cost function _bounded_ if it
satisfies the condition that $c(\ell+1)/c(\ell)=O(1)$ for all $\ell>0$, i.e.,
that the relative jump in the cost function can be upper bounded by some
constant. Although the class of bounded functions does not capture extreme
examples of cost functions such as $c(\ell)=\ell^{\ell}$, where
$c(\ell+1)/c(\ell)>\ell$, it captures the vast majority of functions that may
characterize the cost incurred by some machine as a function of its load. For
example, it includes all polynomial and even exponential cost functions. Note
that this class also contains highly complicated functions that may not have a
closed-form expression.

##### Games with two known users

We first consider resource-aware mechanisms that are oblivious to the set of
users in the system, with the exception of just two users. The main idea
behind our proposed mechanism is to assign special roles to these two users,
referred to as _enforcers_ , and carefully incentivize them to enforce an
approximately efficient assignment in equilibrium. Using this approach we
manage to guarantee a constant PoA for instances with any combination of
bounded cost functions.

Theorem: For any class of scheduling games with two known users and bounded
cost functions, there exists a stable resource-aware cost-sharing mechanism
that achieves a constant PoA.

##### Games with stochastic user arrivals.

We then extend this idea to the case where each user enters the system with
some probability $p$, and the mechanism knows $p$ but not the realization. To
achieve a good PoA bound for this class of instances we assign the role of the
enforcer to more users, depending on the value of $p$, and guarantee an
expected PoA that is at most logarithmic in the expected number of users.

Theorem: For any class of scheduling games with i.i.d. arrivals222We also
extend this result to hold even if each bidder $i$ arrives with a different
probability, $p_{i}$. and bounded cost functions, there exists a stable
resource-aware cost-sharing mechanism that achieves an expected PoA of
$O(\log(\tilde{n}))$, where $\tilde{n}=p|\mathcal{N}|$ is the expected number
of users.

##### Technical obstacles

Designing efficient cost-sharing mechanisms for such a wide family of
instances is quite demanding: the structure of the optimal assignment can
change, depending on the actual number, $n$, of users in the system, but the
mechanism is oblivious to this number. So, how can the mechanism approximate
the optimal solution without knowing $n$? Prior work focused on the case of
concave or convex cost functions, and designed mechanisms leveraging the fact
that the corresponding optimal assignments are reasonably “well behaved”: for
concave costs there always exists an optimal solution where all the jobs are
assigned to a _single_ machine, and for convex costs an optimal assignment can
be reached using a simple _greedy_ solution (e.g., Christodoulou et al. (2017,
2020)). However, we cannot expect to find such convenient structural
properties when dealing with the vast family of bounded functions, because the
optimal assignment can change radically as a function of $n$.

To deal with this fundamental obstacle, we propose a novel solution: rather
than trying to implement the optimal assignment in equilibrium, we instead
seek to implement a “well behaved” alternative assignment implied by an
_online algorithm_. This algorithm assigns jobs to machines using a
predetermined assignment sequence which is _independent of the total number of
jobs, $n$_. We prove that this algorithm has a constant competitive ratio and
then carefully design our cost-sharing mechanisms aiming to implement the
outcome of this algorithm in equilibrium, thus inheriting a good approximation
guarantee. We believe this technique may be of independent interest.

###  1.2 Related Work

Our work extends the recent literature that uses resource-aware cost-sharing
mechanisms to achieve low PoA in different classes of games. Christodoulou and
Sgouritsa (2019) were the first to study this family of mechanisms333In their
paper, Christodoulou and Sgouritsa (2019) refer to these mechanisms as
_universal_ instead of resource-aware., focusing on the class of network
formation games (like Chen et al. (2010) did for the family of oblivious
mechanisms). Unlike the scheduling games that we study in this paper, network
formation games take place over a graph: each agent is associated with a
vertex of the graph and needs to use a path connecting that vertex to a
designated sink-vertex, and each edge of the graph corresponds to a resource
with a constant cost function. One can think of the games in our paper as the
special case where the graph has just two vertices (a source and a sink) and
several parallel edges: each edge corresponds to one of the machines, and
every agent needs to choose one of these edges in order to get from the source
to the sink. From this perspective, our games are more restricted in terms of
the users’ strategy space, but quite more general in terms of the classes of
cost functions. Christodoulou and Sgouritsa (2019) showed that when the graph
is outerplanar, then resource-aware mechanisms can outperform oblivious ones,
but they also proved that an analogous separation is not possible for general
graphs. In subsequent work, Christodoulou et al. (2017) designed resource-
aware mechanisms for the same class of scheduling games that we study in this
paper, and were able to achieve a constant PoA for instances with convex and
concave cost functions. In a recent paper, Christodoulou et al. (2020)
extended many of these results to more general graphs, beyond parallel links,
including directed acyclic or series parallel graphs with convex or concave
cost functions on the edges.

The assumption that the cost-sharing mechanism may have additional prior
information regarding the users was also part of the model studied by
Christodoulou and Sgouritsa (2019) for the case of network formation games.
Specifically, rather than assuming that the source vertex of each agent is
chosen adversarially, they assumed that it is drawn from a distribution over
all vertices. The cost-sharing mechanism is aware of this stochastic process,
so they designed a mechanism that leverages this information to achieve a
constant PoA. Following-up on this work Christodoulou et al. (2019) extended
the constant PoA to also include Bayesian Nash equilibria.

Ensuring that a cost-sharing mechanism is stable can be quite demanding, so
characterizations of stable mechanisms can be very useful. Building on the
impressive characterization of stable oblivious mechanisms by Chen et al.
(2010), Gopalakrishnan et al. (2014) provided a characterization for the set
of stable oblivious cost-sharing mechanisms. They proved that these mechanisms
correspondend to the class of generalized weighted Shapley values. Leveraging
this characterization, Gkatzelis et al. (2016) analyzed this family of cost-
sharing protocols and showed that the unweighted Shapley value achieves the
optimal price of anarchy guarantees for a large family of network cost-sharing
games.

Other papers on the design and analysis of cost-sharing protocols include
Harks and von Falkenhausen (2014), who focused on capacitated facility
location games, Marden and Wierman (2013) who considered a utility
maximization model, and Harks et al. (2021), who considered a model that
imposes some constraints over the portions of the cost that can be shared
among the agents. Also, Harks and Miller (2011) studied the performance of
several cost-sharing protocols in a setting, where each player can declare a
different demand for each resource.

Finally, there are several other models in which cost-sharing has played a
central role. For example, Moulin and Shenker (2001) focused on participation
games, while Moulin (2008) and Mosk-Aoyama and Roughgarden (2009) studied
queueing games. Caragiannis et al. (2017) recently also pointed out some
connections between cost-sharing mechanisms and the literature on coordination
mechanisms, which started with the work of Christodoulou et al. (2009) and led
to several papers focusing on decentralized scheduling policies for machine
scheduling games Immorlica et al. (2009); Azar et al. (2015); Caragiannis
(2013); Abed and Huang (2012); Kollias (2013); Cole et al. (2015);
Christodoulou et al. (2014); Bhattacharya et al. (2014). Just like the
research on cost-sharing mechanisms, most of the work in coordination
mechanisms studies how the price of anarchy varies with the choice of local
scheduling policies on each machine (i.e., the order in which to process jobs
assigned to the same machine).

##  2 Preliminaries

We analyze the scheduling games that arise in a decentralized system with a
set $M=\\{1,2,\dots,m\\}$ of $m$ machines and a set $N=\\{1,2,\dots,n\\}$ of
$n$ users. Each user owns a job and needs to schedule it on one of the
machines. Each machine $j\in M$ is characterized by a cost function
$c_{j}:\mathbb{N}\to\mathbb{R}$, where $c_{j}(\ell)$ is the cost that the
machine would incur for processing a total of $\ell$ jobs. The cost function
satisfies $c_{j}(0)=0$ and it is non-decreasing.

The strategy profile, $\mathbf{s}=(s_{1},s_{2},\dots,s_{n})$, of a scheduling
game is a schedule, where $s_{i}$ corresponds to the machine that player $i$
chooses for her job. We use $S_{j}(\mathbf{s})=\\{i\in N:s_{i}=j\\}$ to denote
the set of players who scheduled their jobs on machine $j$ in profile
$\mathbf{s}$, and $\ell_{j}(\mathbf{s})=|S_{j}(\mathbf{s})|$ to denote the
load on machine $j$ in $\mathbf{s}$. Therefore, the cost of machine $j$ in
this schedule is $c_{j}(\ell_{j}(\mathbf{s}))$, and the overall generated cost
is $C(\mathbf{s})=\sum_{j\in M}c_{j}(\ell_{j}(\mathbf{s}))$. For notational
simplicity, apart from $c_{j}(\ell_{j}(\mathbf{s}))$, we also use
$c_{j}(\mathbf{s})$ to denote the cost of machine $j$ in $\mathbf{s}$, since
$j$’s load is directly implied by $\mathbf{s}$.

Cost-Sharing Mechanisms. A _cost-sharing mechanism_ is a protocol that
determines the cost of each agent using a machine. Formally, a cost-sharing
mechanism $\Xi$ defines at each schedule $\mathbf{s}$ a nonnegative cost share
$\xi_{ij}(\mathbf{s})$ for each $j\in M$ and $i\in S_{j}(\mathbf{s})$. Since
the machine that $i$ uses, i.e., $s_{i}$, is implied by $\mathbf{s}$, we also
denote this cost share as $\xi_{i}(\mathbf{s})$. In any schedule $\mathbf{s}$,
the cost of each machine $j$ must be fully covered by the agents using it, so
$\sum_{i\in S_{j}(\mathbf{s})}\xi_{i}(\mathbf{s})\geq
c_{j}(\ell_{j}(\mathbf{s}))$. We use $\hat{C}(\mathbf{s})=\sum_{j\in
M}\sum_{i\in S_{j}(\mathbf{s})}\xi_{i}(\mathbf{s})$ to denote the overall cost
suffered by the users in $\mathbf{s}$. Since the agents pay at least the cost
they generate, we have $\hat{C}(\mathbf{s})\geq C(\mathbf{s})$ for every
profile $\mathbf{s}$. If there exists some profile for which this inequality
is strict, i.e., the cost suffered by the users is greater than the cost that
they generated, then we say that the cost-sharing mechanism uses
_overcharging_.

Resource-Aware Mechanisms. In the class of _resource-aware_ cost-sharing
mechanisms, the value of the cost-share $\xi_{ij}(\mathbf{s})$ for each $i\in
S_{j}(\mathbf{s})$ can depend on the set $S_{j}(\mathbf{s})$ of agents using
that machine, on the set of machines $M$, and their cost functions, but not on
the set $N\setminus S_{j}(\mathbf{s})$ of agents using other machines. In this
paper we enhance this class of mechanisms with some prior stochastic
information regarding the set $N\setminus S_{j}(\mathbf{s})$, which enriches
the set of cost-sharing functions that we can implement, allowing us to
achieve improved performance guarantees.

Pure Nash Equilibrium (PNE). A tuple $(N,M,\mathbf{c},\Xi)$ of a set of
agents, a set of machines and their cost functions $\mathbf{c}=(c_{j})_{j\in
M}$, and a cost-sharing mechanism, defines a scheduling game $G$. The goal of
every user in this game is to choose a machine that minimizes her own share of
the cost, determined by $\Xi$. A strategy profile $\mathbf{s}$ is a _pure Nash
equilibrium_ (PNE) of this game $G$ if for every player $i\in N$, and every
strategy $s^{\prime}_{i}\in M$

$\xi_{i}(\mathbf{s})~{}=~{}\xi_{i}(s_{i},\mathbf{s}_{-i})~{}~{}\leq~{}~{}\xi_{i}(s^{\prime}_{i},\mathbf{s}_{-i}),$

where $\mathbf{s}_{-i}$ denotes the profile of strategies for all agents other
than $i$. In other words, in a PNE $\mathbf{s}$ no agent can decrease her cost
share by unilaterally deviating from machine $s_{i}$ to $s^{\prime}_{i}$ if
all the other agents’ choices remain fixed.

Stability. In accordance with prior work, we restrict our attention to
_stable_ cost-sharing mechanisms, i.e., ones that induce games possessing at
least one PNE.

Price of Anarchy (PoA). To measure the performance of a cost-sharing mechanism
in a given game, $G$, we evaluate the total cost $\hat{C}(\mathbf{s})$
suffered by the users in the worst equilibrium $\mathbf{s}$, and compare it to
the minimum total cost they could suffer. If we let $Eq(G)$ be the set of all
PNE of $G$ and $F(G)$ denote the set of all its feasible schedules, then the
_price of anarchy_ (PoA) of game $G$ is

$\text{PoA}(G)=\frac{\max_{\mathbf{s}\in\textrm{Eq($G$)}}\hat{C}(\mathbf{s})}{\min_{\mathbf{s}^{*}\in
F(G)}C(\mathbf{s}^{*})}\,.$

Rather than evaluating the performance of cost-sharing mechanisms on a single
game, we evaluate them on large classes of games. A class of scheduling games,
$\mathcal{G}$, is defined by a tuple $({\mathcal{N}},{\mathcal{C}},\Xi)$,
which comprises a universe of players $\mathcal{N}$, a universe of cost
functions $\mathcal{C}$, and a cost sharing mechanism $\Xi$. An instance of a
scheduling game $G\in\mathcal{G}$ consists of some subset of users
$S\subseteq\mathcal{N}$, a set $M$ of machines with cost functions from
$\mathcal{C}$, and the cost sharing mechanism $\Xi$. The _worst-case price of
anarchy_ of mechanism $\Xi$ for a class of games $\mathcal{G}$ is then defined
as $\text{PoA}(\mathcal{G})=\sup_{G\in\mathcal{G}}\text{PoA}(G)$. We also
consider settings where the subset of agents, $S$, is drawn from $\mathcal{N}$
based on some distribution $P$. In that case, we evaluate the _expected price
of anarchy_ of $\Xi$ as

$\text{ExpectedPoA}(\mathcal{G})=\sup_{M,\mathbf{c}\in\mathcal{C}^{|M|}}\left\\{\operatorname*{\mathbb{E}}_{S\sim
P}[\text{PoA}((S,M,\mathbf{c},\Xi))]\,\right\\}.$

In other words, given an adversarial choice of machines $M$ using cost
functions from $\mathcal{C}$, we evaluate the expected PoA over the randomness
of $P$ in defining the subset of agents $S$.

Classes of Cost Functions. We say that a cost function is _bounded_ if
$c(\ell+1)/c(\ell)=O(1)$ for all $\ell>0$. Another class of functions that
plays an important role in prior work is that of _capacitated constant_ cost
functions. That is, functions such that $c(\ell)=c$ when $\ell\leq t$ and
$c(\ell)=\infty$ when $\ell>t$, for some positive constants $c$ and $t$. Note
that, although these cost functions are not bounded, one of our first results
shows that we can achieve a small PoA for them as well, as long as their
capacity, $t$, is at least 4. Finally, a _4-step_ function is a step function
whose segments have length at least 4. In other words, the value of a 4-step
function does not change more than once within any interval of length 4 in its
domain. Note that capacitated constant functions with capacity at least 4 are
a special case of a 4-step function. Also, it is easy to verify that for any
bounded cost function $c^{\prime}$, there exists a 4-step function $c$ such
that $c(\ell)\geq c^{\prime}(\ell)$ and $c(\ell)/c^{\prime}(\ell)=O(1)$ for
all $\ell>0$444To verify this fact, note that given a bounded function
$c^{\prime}$, we can define a 4-step function $c$ such that for every
$k\in\mathbb{N}$, if $\ell\in[4k-3,4k]$ then $c(\ell)=c^{\prime}(4k)$.
Clearly, $c(\ell)\geq c^{\prime}(\ell)$ for all $\ell>0$. Also, since
$c^{\prime}$ is bounded, this means that for every $\ell$ we have
$c(\ell)/c^{\prime}(\ell)\leq c^{\prime}(\ell+4)/c^{\prime}(\ell)=O(1)$.. This
means that we can always approximate a bounded cost function using a 4-step
function, so in the rest of the paper we assume that the cost functions are
all 4-step functions.

Global Ordering. Our mechanisms, as well as many mechanisms in the related
work (e.g. Moulin (1999); Christodoulou et al. (2017, 2020)), use a global
ordering $\pi$ over the universe $\mathcal{N}$ of players in deciding how to
distribute the cost. Although the externality of the users in the games that
we study is symmetric (e.g., they all cause the same marginal increase in the
cost of a machine), the mechanism needs to share the cost unevenly among them
to achieve a good PoA555It is well known that the PoA is linear in the number
of agents if we share the cost equally Anshelevich et al. (2008).. The global
ordering provides a consistent way for the mechanism to differentiate between
these users. To ensure that no fairness concerns arise from the asymmetry
introduced by these mechanisms, we assume that this global ordering can change
periodically in a predetermined way, thus providing a symmetric treatment of
the users over time.

##  3 Online Scheduling Algorithm

The main obstacle that resource-aware mechanisms face in approximating the
optimal solution is that they do not know the number $n$ of agents that are
present in the system. Since the optimal solution can change radically as a
function of $n$, how can the cost-sharing mechanism try to approximate it
without knowing the value of $n$?

Rather than trying to implement the optimal assignment as an equilibrium, the
main idea behind our solution is to instead implement a much more “well
behaved” allocation that, in turn, closely approximates the cost of the
optimal assignment. Specifically, we define an online algorithm, called
Delayed-OPT, which sequentially assigns jobs to machines using a predetermined
order, without knowing the value of $n$. We show that this algorithm has a
constant competitive ratio and then we design cost-sharing mechanisms aiming
to implement the outcome of this algorithm in equilibrium.

If $A(n)$ is the outcome of the online algorithm and $\text{OPT}(n)$ is the
optimal allocation (i.e. the feasible schedule with the minimum social cost)
when the total number of jobs is $n$, then the competitive ratio is equal to
$\max_{n}\\{C(A(n))/C(\text{OPT}(n))\\}$. To simplify the description of the
Delayed-OPT online algorithm, without loss of generality we normalize the
costs functions. That is, all costs are multiplied by the same constant such
that the minimum non-zero cost is equal to $1$.For each $k\in\mathbb{N}$, let
$a_{k}=\max\\{q\in\mathbb{N}:~{}C(\text{OPT}(q))<2^{k}\\}$ be the largest
number of jobs such that the optimal social cost for scheduling these jobs
remains less than $2^{k}$ (Figure 1 shows two examples for capacitated
constant cost functions). Using this definition, let $\ell_{jk}^{*}$ denote
the number of jobs assigned to machine $j$ in the optimal allocation when the
total number of jobs is $a_{k}$.

When the $q^{\text{th}}$ job arrives, the Delayed-OPT finds the smallest value
of $k$ such that for some machine $j\in M$ the number of jobs, $\ell_{j}$,
assigned to it so far is less than $\ell_{jk}^{*}$. Then, among all such
machines, the algorithm assigns this job to the one that has the smallest
index666We assume that the machines have some arbitrary, but fixed, ordering
indicated by their indices.. The algorithm then increments the value of
$\ell_{j}$ by one and moves on to the next job. A formal description of the
Delayed-OPT algorithm is provided as Algorithm 1, below, and two examples of
the induced assignment are provided in Figure 1.

$c_{1}=1$$1$$c_{2}=2$$2$$3$$4$$c_{3}=15$$5$$6$$7$$8$$9$$10$$a_{0}=0$$a_{1}=1$$a_{2}=4$$a_{3}=4$$a_{4}=6$$a_{5}=10$(a)$c_{1}=1$$1$$c_{2}=2$$2$$3$$c_{3}=2$$12$$13$$c_{4}=2$$14$$15$$c_{5}=7$$4$$5$$6$$7$$8$$9$$10$$11$$a_{0}=0$$a_{1}=1$$a_{2}=3$$a_{3}=8$$a_{4}=15$(b)
Figure 1: These figures depict machines with capacitated constant cost
functions. Figure (a) shows three machines whose cost is $1$, $2$, and $15$
for any load up to $1$, $3$, and $6$, respectively (and the cost becomes
infinite for any load beyond that). Similarly, Figure (b) shows five machines
whose cost is $1,2,2,2$, and $7$ for any load up to $1,2,2,2$, and $8$,
respectively. In both figures, the $a_{k}$ values are given on the right, and
each number inside the machines represents a job with the number indicating
the order of their arrival. The figures show how the Delayed-OPT algorithm
assigns the jobs to the machines, e.g. the first job is assigned to the first
machine in both cases.

1$q\leftarrow 0$ // Initialize counter for the number of jobs

2 $\ell_{j}\leftarrow 0$ for each $j\in M$ // Initialize all loads to zero

3 while  _there exist more jobs_ do

4 $q\leftarrow q+1$

5 $k\leftarrow\min\\{k\in\mathbb{N}~{}|~{}\exists j\in
M:\ell_{j}<\ell_{jk}^{*}\\}$

6 $j\leftarrow\arg\min\\{j\in M~{}|~{}\ell_{j}<\ell_{jk}^{*}\\}$

7 $\ell_{j}\leftarrow\ell_{j}+1$ // Assign job to first machine that has not
reached target load

ALGORITHM 1 Delayed-OPT Online Algorithm

######  Lemma 1.

If $q\leq a_{k^{\prime}}$ for some $k^{\prime}\in\mathbb{N}$, then the value
of $k$ computed by the algorithm in the iteration corresponding to the
$q^{\text{th}}$ job satisfies $k\leq k^{\prime}$.

###### Proof.

Assume that this is not the case. This would mean that in that iteration of
the algorithm, for every machine $j\in M$ we have
$\ell_{j}\geq\ell_{jk^{\prime}}^{*}$. Summing over all $j\in M$, this would
yield

$\sum_{j\in M}\ell_{j}~{}\geq~{}\sum_{j\in
M}\ell_{jk^{\prime}}^{*}~{}=~{}a_{k^{\prime}}.$

But, since $q=\sum_{j\in M}\ell_{j}+1$, this contradicts the fact that $q\leq
a_{k^{\prime}}$. ∎

We now proceed to show that the competitive ratio of this algorithm is less
than 4.

######  Theorem 2.

The competitive ratio of the Delayed-OPT algorithm is less than 4.

###### Proof.

Let $k\in\mathbb{N}$ be the minimum value such that $n\leq a_{k}$. The load
that the algorithm assigns on any machine $j$ is no more than
$\max_{k^{\prime}\leq k}\\{\ell_{jk^{\prime}}^{*}\\}$. As a result, the cost
of the Delayed-OPT algorithm for $n$ jobs is

$C(A(n))\leq\sum_{k^{\prime}\leq
k}C(\text{OPT}(a_{k^{\prime}}))<\sum_{k^{\prime}\leq
k}2^{k^{\prime}}<2^{k+1},$

while the optimal cost is $C(\text{OPT}(n))\geq C(\text{OPT}(a_{k-1}+1))\geq
2^{k-1}$, leading to a competitive ratio of less than $2^{k+1}/2^{k-1}=4$. ∎

The following lemma will be useful in the next sections.

######  Lemma 3.

If $c_{j}(\ell)=c_{j}(\ell+\ell^{\prime})$ for some machine $j$ and some loads
$\ell,\ell^{\prime}>0$, then right after the iteration that the Delayed-OPT
algorithm assigns the $\ell^{\text{th}}$ job at machine $j$, it assigns the
next $\ell^{\prime}$ jobs at the same machine.

###### Proof.

Suppose that in the iteration that the Delayed-OPT algorithm assigns the
$\ell^{\text{th}}$ job at machine $j$ it computes $k$ to be the smallest value
such that there exists a machine $j^{\prime}$ with
$\ell_{j^{\prime}}<\ell_{j^{\prime}k}^{*}$. Since the algorithm assigns the
current job to machine $j$, at this iteration $\ell_{j}<\ell_{jk}^{*}$ and $j$
has the smallest index among machines that satisfy this inequality.

Moreover, since the cost functions are all non-decreasing, the cost of machine
$j$ is the same for all loads between $\ell$ and $\ell+\ell^{\prime}$, which
means that $\ell_{jk}^{*}\geq\ell+\ell^{\prime}$. To better see this suppose
on the contrary that $\ell_{jk}^{*}<\ell+\ell^{\prime}$. The allocation that
assigns another job to machine $j$ has the same cost with current optimal
allocation, i.e. $C(\text{OPT}(a_{k}))=C(\text{OPT}(a_{k}+1))$. This is a
contradiction to the definition of $a_{k}$ that needs to satisfy that
$C(\text{OPT}(a_{k}))<C(\text{OPT}(a_{k}+1))$.

Overall, in the next iteration, $\ell_{j}<\ell_{jk}^{*}$ and $j$ should be the
smallest index that satisfies this inequality, otherwise this wouldn’t be true
in the previous iteration. Therefore, the Delayed-OPT algorithm assigns the
next job to machine $j$ and by induction it should assign all the following
jobs until the load of machine $j$ becomes $\ell+\ell^{\prime}$. Figure 1
shows such examples. ∎

##  4 Resource-Aware Mechanism for Games with Two Known Users

In this section we consider resource-aware mechanisms that are oblivious to
the set of users in the system, with the exception of just two users.
Formally, we consider classes of games such that for every game $G$ in this
class, the set of agents, $S$, always contains two known agents. Note that the
set $S$ is otherwise totally unrestricted and can also contain an
adversarially chosen subset of the agents from ${\mathcal{N}}$, so this class
of games is quite general. In fact, since the optimal allocation may very
heavily depend on the total number of agents that participate in the game, the
aforementioned restriction is seemingly benign. In what follows, we propose a
resource-aware mechanism that assigns a special role to the two known agents,
leading to very efficient equilibria for any bounded cost function. In fact we
show that the assignment of every Nash equilibrium in the induced game is the
same as the outcome of the Delayed-OPT algorithm when scheduling $|S|$ jobs.

As a warm-up, we first consider the games whose cost functions are drawn from
the class of capacitated cost functions, and then we go on to extend our
result beyond this class.

###  4.1 Warm-up: A Class of Capacitated Constant Functions

In order to more clearly capture the intuition behind how our proposed
mechanism works, we first focus on games whose cost functions are capacitated
constant, with a capacity of at least 4. That is, for every machine $j$ we
have $c_{j}(\ell)=c_{j}$ when $\ell\leq t_{j}$ and $c_{j}(\ell)=\infty$
otherwise, where $c_{j}>0$ and $t_{j}\geq 4$ are constants777The assumption of
$c_{j}>0$ for all $j$ is w.l.o.g. because if there are machines with zero
cost, we may charge everybody with $0$, unless the machine load exceeds its
capacity, in which case everybody is charged with infinity. In both the
Delayed-OPT algorithm and any Nash equilibrium those machines are firstly
occupied up to their capacity and then other machines are used resulting in a
PoA equal to the one that ignores those machines.. Note that these cost
functions are actually not bounded, since they jump from some constant to
infinity when their capacity is exceeded, so this section also shows that our
positive results can even be extended to cost functions beyond the class of
bounded ones.

Before presenting our protocol, we make an important observation, that can be
derived directly from Lemma 3, regarding the allocation of the Delayed-OPT
algorithm when the machines have capacitated constant cost functions.

######  Observation 1.

For any instance involving a set $M$ of machines with capacitated constant
cost functions, there exists an ordering of the machines in $M$ such that the
Delayed-OPT algorithm fills up machine $j$ up to its capacity before assigning
any job to any machine $j^{\prime}$ that is later in the ordering.

Let $D=\\{1,2\\}$ be the set of the two agents, called enforcers, who are
guaranteed to participate, and let $R=S\setminus D$ be the rest of the agents,
which we call regular agents. Also, given some set of agents $S^{\prime}$, let
$h(S^{\prime})$ be the first (highest priority) agent in $S^{\prime}$
according to a global ordering $\pi$. For simplicity we assume that the
machines are renamed according to the ordering implied by the Delayed-OPT
algorithm (Observation 1), and let $Z_{j}=\sum_{k\leq j}c_{k}$ be the sum of
the costs of the first $j$ machines in this ordering. Note that the value of
$Z_{j}$ is strictly increasing with $j$ by our convention that $c_{j}>0$ for
all $j$. Finally, to define the protocol we also use an arbitrarily small
positive value $\varepsilon_{j}$ for each machine $j$ to be used as a special
charge for enforcers in some cases; $\varepsilon_{j}$ values are strictly
decreasing values, i.e. $\varepsilon_{j}>\varepsilon_{j+1}$.

Brief description of the protocol. The enforcers are charged with the small
value $\varepsilon_{j}$ for using machine $j$ only in two cases: i) if they
are together in $j$ along with at least one regular agent (if there were no
regular agent, the enforcers should cover the cost of the machine) and the
load of machine $j$ doesn’t exceed its capacity $t_{j}$, ii) if the enforcer
is alone in $j$ and the load of machine $j$ exceeds its capacity $t_{j}$. In
any other case they pay $Z_{j}$. Regarding the regular agents, the highest
priority regular agent always pays a non-zero charge. More specifically, if
machine $j$’s load doesn’t exceed $t_{j}$, the highest priority regular agent
pays the cost of $j$, $c_{j}$, if the machine is full (i.e. its load equals
$t_{j}$) and there is no enforcer in $j$; otherwise, meaning when $j$’s load
is less than $t_{j}$ or there is an enforcer in $j$, the highest priority
regular agent pays $Z_{j}$. The rest of the regular agents are charged with
$0$ if $j$’s load doesn’t exceed $t_{j}$. If $j$’s load exceeds $t_{j}$, then
everybody is charged with infinity.

##### Protocol.

Given a strategy profile $\mathbf{s}$, the cost share of any enforcer $i\in D$
for using machine $j$ is

$\xi_{i}(\mathbf{s})=\begin{cases}\varepsilon_{j}&\text{if
}\ell_{j}(\mathbf{s})\leq t_{j}\mbox{ and }D\subset S_{j}(\mathbf{s})\\\
\varepsilon_{j}&\text{if }\ell_{j}(\mathbf{s})>t_{j}\mbox{ and }D\cap
S_{j}(\mathbf{s})=\\{i\\}\\\ Z_{j}&\text{otherwise.}\end{cases}\,$

The cost share of any regular agent $i\in R$ for using machine $j$ is

$\xi_{i}(\mathbf{s})=\begin{cases}0&\text{if }\ell_{j}(\mathbf{s})\leq
t_{j}\mbox{ and }i\neq h(S_{j}(\mathbf{s})\cap R)\\\ c_{j}&\text{if
}\ell_{j}(\mathbf{s})=t_{j},D\cap S_{j}(\mathbf{s})=\emptyset\mbox{ and
}i=h(S_{j}(\mathbf{s})\cap R)\\\ Z_{j}&\text{if
}\ell_{j}(\mathbf{s})=t_{j},D\cap S_{j}(\mathbf{s})\neq\emptyset\mbox{ and
}i=h(S_{j}(\mathbf{s})\cap R)\\\ Z_{j}&\text{if
}\ell_{j}(\mathbf{s})<t_{j}\mbox{ and }i=h(S_{j}(\mathbf{s})\cap R)\\\
\infty&\text{otherwise.}\end{cases}\,$

The main idea behind this protocol is that in the equilibrium if agents use
some machine, all machines with lower indices should be full (i.e. its load
equals its capacity). As we mentioned above, $Z_{j}$ values are strictly
increasing. As a result if some agent is charged $Z_{j}$ in machine $j$, she
prefers to deviate to a non-full machine (non-full means that its load is less
that its capacity) with smaller index. Such an agent exists when the machine
is not full or when an enforcer is using it. However, there is no such agent
when the machine is full with only regular agents, where the importance of
enforcers comes in place as we explain next. We note here that it is crucial
to keep the budget balance in full machines without enforcers so that we do
not lose in efficiency too much.

If a machine that is not used by the Delayed-OPT algorithm is full with only
regular agents, enforcers are going to disrupt them and push them to machines
with lower indices. The reason is because $\varepsilon_{j}$ values are
decreasing, so enforcers prefer to occupy machines with higher indices. So, if
an enforcer deviates to a full machine $j$, the load of that machine will
exceed capacity and the enforcer will be charged $\varepsilon_{j}$.

The cases where the charges of the enforcers are high ($Z_{j}$) are crucial in
order to guarantee stability as we show in Theorem 5.

######  Theorem 4.

The PoA for the class of capacitated constant cost functions, assuming two
enforcers, is constant.

###### Proof.

It is sufficient to show that the social cost of any Nash equilibrium is
constant away from the cost induced by the Delayed-OPT algorithm, which in
turn is constant away from the cost of the optimal allocation.

In fact we show that under any pure Nash equilibrium, the allocation is the
same with the outcome of the Delayed-OPT algorithm; that is for any used
machine $r$, all prior machines $j<r$ are fully used. Then, it is easy to
check that, regarding the overcharging, each enforcer may ”cause” some regular
agent to pay at most the cost of the outcome of the Delayed-OPT algorithm and
each enforcer itself may pay some arbitrarily small value
$\varepsilon_{j}$.888There is no Nash equilibrium where the enforcers are
charged more than some $\varepsilon_{j}$, unless there is no regular agent
where we again have the same overcharging.

For the sake of contradiction suppose that in some Nash equilibrium there
exist machines $j<r$ such that machine $r$ is used and machine $j$ is not
full. Let $r$ be the largest possible such index.

  * •

If $r$ is not full, or if it is full and has at least one enforcer, there
exists an agent paying $Z_{r}$ and if he deviates to $j$ he should pay at most
$Z_{j}<Z_{r}$, so he has an incentive to deviate (Figure 2).

  * •

If $r$ is full with only regular agents, there exists an enforcer in an
earlier machine $j^{\prime}<r$ paying at least $\varepsilon_{j^{\prime}}$.
That enforcer has an incentive to deviate to $r$ where he will pay
$\varepsilon_{r}<\varepsilon_{j^{\prime}}$ (Figure 3).

$c_{1}$$1$$c_{j}$$j$$c_{r}$$r$highest priorityregular
agentdeviates(a)$c_{j}$$j$$c_{r}$$r$highest priorityregular
agentdeviatesenforcer(b) Figure 2: In this figure we assume that machine $j$
is not full and there exists a non empty machine $r$, with $r>j$ (where $r$ is
the maximum such index). If machine $r$ is either not full (a) or has an
enforcer (b), then there is always a regular agent from $r$ that prefers to
deviate to $j$.
$c_{1}$$1$$c_{j}$$j$$c_{j^{\prime}}$$j^{\prime}$enforcer$c_{r}$$r$deviates
Figure 3: In this figure we assume that machine $j$ is not full and there
exists a non empty machine $r$, with $r>j$ (where $r$ is the maximum such
index). If machine $r$ is full with only regular agents, then any enforcer
prefers to deviate to $r$.

In both cases there exists an agent with an incentive to deviate to another
machine which is a contradiction to our assumption that this is a Nash
equilibrium. ∎

######  Theorem 5.

The protocol for the class of capacitated constant cost functions, assuming
two enforcers, is stable.

###### Proof.

In order to show stability, we create a strategy profile that is an
equilibrium for any set of agents $S\subseteq\mathcal{N}$ as long as
$D\subseteq S$.

Let $n$ be the number of agents in the system, where $n-2$ of them are regular
agents, since there exist two enforcers. Suppose that $r$ machines are
occupied based on the Delayed-OPT algorithm, with the first $r-1$ machines
being fully occupied and machine $r$ having $n_{r}\leq t_{r}$ agents. The
strategy profile we create depends on the value of $n_{r}$.

##### Case of $n_{r}\leq 2$.

In this case, we create a strategy profile where the enforcers use the last
full machine $r-1$ (unless $r=1$, meaning that there is no regular agent, and
the enforcers use machine $1$ which is a Nash equilibrium). The regular agents
are placed according to the outcome of the Delayed-OPT algorithm such that in
the last machine $r$ the lowest priority agents are placed (Figure 4 (a)).
Next we show that nobody has an incentive to deviate from this strategy
profile and therefore it is stable.

The enforcers are currently charged with $\varepsilon_{r-1}$ and if they
deviate to any previous machine $j$ with $j<r-1$ they will be charged with
$\varepsilon_{j}>\varepsilon_{r-1}$. Moreover, if they unilaterally deviate to
$r$ they will be charged $Z_{r}>\varepsilon_{r-1}$ because they will be the
only enforcer there. Deviating to any other machine $j$ with $j>r$ will result
in an even higher charge, since the enforcer will be alone there. Overall,
enforcers have no incentive to deviate.

From the regular agents’ perspective, nobody has an incentive to deviate to a
full machine $j^{\prime}<r$ because its load then will exceed its capacity
resulting in infinity charges. Additionally, no agent currently located to
some machine $j\leq r$ has an incentive to deviate to an empty machine
$j^{\prime}>r$, because he is currently charged at most $Z_{j}$ and if he
deviates to $j^{\prime}$, he will be charged $Z_{j^{\prime}}>Z_{j}$. The last
case to check is if an agent currently located to some machine $j<r$, has an
incentive to deviate to $r$. Note that if he deviates to $r$, the machine will
still not be full and he will be the highest priority agent, as in $r$ we
allocated the lowest priority agents; therefore, he will be charged
$Z_{r}>Z_{j}$, where $Z_{j}$ is the maximum he may currently be charged.

##### Case of $n_{r}>2$.

In this case, we create a strategy profile where the enforcers use that last
machine $r$. The regular agents are placed according to the outcome of the
Delayed-OPT algorithm such that in the last machine $r$ the lowest priority
agents are placed (Figure 4 (b)). Similar arguments hold in this case in order
to show that nobody has an incentive to deviate from this strategy profile.

More specifically the enforcers are currently charged with $\varepsilon_{r}$
and any deviation will result in a charge of either $\varepsilon_{j}$ with
$j<r$ or $Z_{j}$ with $j>r$, which are both strictly greater than
$\varepsilon_{r}$.

Regarding the regular agents, as before, nobody wants to deviate to a full
machine or to a machine $j>r$. Any agent currently using some machine $j<r$ is
charged with at most $Z_{j}$ and if he deviated to machine $r$ he would pay at
least $Z_{r}>Z_{j}$ because he would be the highest priority agent in $r$. ∎

$c_{1}$$1$$c_{r-1}$$r-1$enforcers$c_{r}$$r$lowest priorityregular
agents(a)$c_{1}$$1$$c_{r}$$r$lowest priorityregular agentsenforcers(b) Figure
4: This figure shows the stable outcomes when the Delayed-OPT algorithm
allocates in the last machine (a) at most two agents and (b) more than two
agents.

In Appendix A we give some intuition on why we may need of at least two
enforcers and the capacities to be at least $4$. Both restrictions are
important in order to guarantee stability.

###  4.2 Bounded Cost Functions

We now extend the result of Section 4.1 to the class of bounded cost
functions. For simplicity, we focus on the class of 4-step cost functions
which naturally generalize the capacitated cost functions considered above; as
we discussed in Section 2, any bounded cost function can be approximated by a
4-step cost function, so our results directly extend to bounded cost functions
as well.

A key difference between the segments of 4-step functions and the capacitated
constant functions is that having a single job in a segment may have two
meanings in the respective machines with capacitated constant functions: it
may be considered as i) having a single job in the machine with capacitated
constant function corresponding to that segment or ii) having an overload in
the machine with capacitated constant function corresponding to the previous
segment of the step function. In order to overcome this ambiguity we slightly
change our protocol in order to handle those two cases consistently and get
the same results.

Let agents $D=\\{1,2\\}$ be the two agents/enforcers who are guaranteed to
participate, and let $R=S\setminus D$ be the regular agents. Before describing
the protocol we need to give some further definitions; Figure 5 gives some
intuition for some of the following definitions.

####  4.2.1 Preliminaries

We first provide an alternative definition of a 4-step function. In the rest
of the paper, we will be assuming that all the machine cost functions are
4-step functions.

######  Definition 6.

A function $c$ is called 4-step function if the following are true: there are
steps of lengths $t(1),t(2),\dots\geq 4$ such that for all $k$ and all
$x\in[1+\sum_{k^{\prime}=1}^{k-1}t({k^{\prime}}),\sum_{k^{\prime}=1}^{k}t({k^{\prime}})]$
we have that

$c(x)=c\left(\sum^{k}_{k^{\prime}=1}t({k^{\prime}})\right)=\tilde{c}(k).$

That is, the cost function increases only when an extra step needs to be used.
If any number of jobs between one and $t(1)$ are undertaken by this machine,
the cost is $\tilde{c}(1)$. Then if one more job is added the cost jumps to
$\tilde{c}(2)$ and then the cost for $t(1)+1$ up to $t(1)+t(2)$ jobs remains
$\tilde{c}(2)$, and so forth. Note that trivially all functions on natural
numbers are 1-step functions.

Length and cost of a segment. According to Definition 6, we define segment $k$
of machine $j$ to be the $k^{th}$ step of machine $j$’s cost function $c_{j}$
and has length $t_{j}(k)$ and cost $\tilde{c}_{j}(k)$.

Last used segment
$\varkappa_{j}(\ell_{j}(\mathbf{s}))=\varkappa_{j}(\mathbf{s})$. For each
machine $j$ and profile $\mathbf{s}$, we denote by $\varkappa_{j}(\mathbf{s})$
the last segment that is used in machine $j$ under $\mathbf{s}$. It holds that
$c_{j}(\mathbf{s})=\tilde{c}_{j}(\varkappa_{j}(\mathbf{s}))$.

Machine’s excess $w_{j}(\ell_{j}(\mathbf{s}))=w_{j}(\mathbf{s})$. For each
machine $j$ and profile $\mathbf{s}$, we denote by $w_{j}(\mathbf{s})$ the
number of jobs occupying the last segment of machine $j$ under $\mathbf{s}$ if
that segment is not filled to capacity. If the number of jobs fill the last
segment to capacity then we set $w_{j}(\mathbf{s})$ to $0$. More formally,

$w_{j}(\mathbf{s})=\begin{cases}\ell_{j}(\mathbf{s})-\sum^{\varkappa_{j}(\mathbf{s})-1}_{k=1}t_{j}(k)&\text{
if }\ell_{j}(\mathbf{s})>\sum^{\varkappa_{j}(\mathbf{s})-1}_{k=1}t_{j}(k)\\\
0&\text{ otherwise}\end{cases}\,$

Segment order $\phi$. Lemma 3 implies that the Delayed-OPT algorithm fills up
a segment up to its capacity before assigning any job to any other segment.
Therefore, a priority order on the segments can be derived according to the
Delayed-OPT algorithm that assigns for every machine $j$ and segment $k$ a
number $\phi_{j}(k)$. The function $\phi$ respects the order of the machine
step costs, i.e. it is strictly monotone.

Definition of $Z_{j}(k)$. Similarly to the case of capacitated constant
functions, we define

$Z_{j}(k)=\sum_{j^{\prime}}\max_{k^{\prime}:\phi_{j^{\prime}}(k^{\prime})\leq\phi_{j}(k)}\tilde{c}_{j^{\prime}}(k^{\prime}),$

which is the aggregate cost of all machines if all segments up to
$\phi_{j}(k)$ in the priority order are occupied. W.l.o.g. the $Z_{j}(k)$
values are strictly increasing according to the order defined by $\phi$. This
is by assuming non-zero costs which is w.l.o.g. according to footnote 7, and
additionally if two consecutive segments have the same cost, we may assume
that they are merged into a single segment.

Definition of $\varepsilon_{j}(k)$. We also use an arbitrarily small positive
value $\varepsilon_{j}(k)$ for each segment $k$ of machine $j$ to be used as a
special charge for enforcers in some cases; $\varepsilon_{j}(k)$ values are
strictly decreasing values according to the order $\phi$, i.e. if
$\phi_{j}(k)>\phi_{j^{\prime}}(k^{\prime})$ then
$\varepsilon_{j}(k)<\varepsilon_{j^{\prime}}(k^{\prime})$.

First two machines. We further distinguish two machines $1$ and $2$ to be the
first and the second machines, respectively, to be used by the Delayed-OPT
algorithm.

Highest priority agents $h(S^{\prime})$. Given some set of agents
$S^{\prime}$, $h_{i}(S^{\prime})$ is the $i^{th}$ agent in $S^{\prime}$
according to the global ordering $\pi$.

##### Protocol.

Given a strategy profile $\mathbf{s}$ we next define the cost shares of the
agents. For simplicity, we drop the dependency on the load and on $\mathbf{s}$
since there is no ambiguity. The cost share of any enforcer $i\in D$ using
machine $j$ is

$\xi_{i}(\mathbf{s})=\begin{cases}\varepsilon_{j}(\varkappa_{j})&\text{if
}w_{j}\neq 1\mbox{ and }D\subset S_{j}\\\
\varepsilon_{j}(\varkappa_{j}-1)&\text{if }w_{j}=1,D\cap S_{j}=\\{i\\}\mbox{
and }\varkappa_{j}>1\\\ Z_{j}(\varkappa_{j})&\text{otherwise.}\end{cases}\,$

The cost share of any regular agent $i\in R$ using machine $j$ is

$\xi_{i}(\mathbf{s})=\begin{cases}c_{j}&\text{if }w_{j}=0,D\cap
S_{j}=\emptyset\mbox{ and }i=h_{1}(S_{j}\cap R)\\\
Z_{j}(\varkappa_{j})&\text{if }w_{j}=0,D\cap S_{j}\neq\emptyset\mbox{ and
}i=h_{1}(S_{j}\cap R)\\\ Z_{j}(\varkappa_{j})&\text{if }w_{j}=1\mbox{ and
}i\in\\{h_{1}(S_{j}\cap R),h_{2}(S_{j}\cap R)\\}\\\
Z_{j}(\varkappa_{j})&\text{if }w_{j}\notin\\{0,1\\}\mbox{ and
}i=h_{1}(S_{j}\cap R)\\\ 0&\text{otherwise.}\end{cases}\,$

$w_{1}(A)=0$$\tilde{c}_{1}(1)$$\phi_{1}(1)=1$$\tilde{c}_{1}(2)$$\phi_{1}(2)=5$$\tilde{c}_{1}(3)$$\phi_{1}(3)=11$$w_{2}(A)=0$$\phi_{2}(1)=2$$\phi_{2}(2)=3$$\phi_{2}(3)=6$$\phi_{2}(4)=9$$w_{3}(A)>0$$\phi_{3}(1)=4$$\phi_{3}(2)=7$$\phi_{3}(3)=10$$w_{4}(A)=0$$\phi_{4}(1)=8$$\phi_{4}(2)=12$$t_{4}(1)$$t_{4}(2)$$1$$2$$3$$4$
Figure 5: This figure shows an example of the first four machines in the order
that are used by the Delayed-OPT algorithm. The cost functions belong to the
class of 4-step functions. In the figure, $\tilde{c}_{1}(k)$ is the cost of
machine $1$ when the $k^{th}$ step/segment is used but not the $(k+1)^{th}$,
and $t_{4}(k)$ is the length of the $k^{th}$ step/segment of machine $4$. The
$\phi_{j}(k)$ values show the order that the Delayed-OPT algorithm fills the
segments. In this example, the allocation $A$ of the Delayed-OPT algorithm
fully uses the first $6$ segments and also part of the $7^{th}$ segment. The
excess of all machines but the third are $0$ and machine $3$ has positive
excess since its $2^{nd}$ segment is not fully used.

######  Theorem 7.

The PoA for the class of 4-step cost functions, assuming two enforcers, is
constant.

###### Proof.

We will show that the total cost of any induced pure Nash equilibrium,
assuming two enforcers, is constant away the total cost induced by the
Delayed-OPT algorithm which in turns is a constant approximation to the cost
of the optimal allocation. In order to show this, we will show that any pure
Nash equilibrium $\mathbf{s}$ has the same allocation with the Delayed-OPT
algorithm allocation $A$. This means that for any machine $j$ the load in
$\mathbf{s}$ and $A$ are the same, i.e. $\ell_{j}(\mathbf{s})=\ell_{j}(A)$.

######  Claim 1.

For any Nash equilibrium $\mathbf{s}$, $\ell_{j}(\mathbf{s})=\ell_{j}(A)$ for
all $j$.

###### Proof.

For the sake of contradiction suppose that there exists some Nash equilibrium
$\mathbf{s}$ with different allocation than $A$. Then there should be a
machine $r$ with $\ell_{r}(\mathbf{s})>\ell_{r}(A)$. If there are many
machines with more load in $\mathbf{s}$ than in $A$, we choose $r$ to be the
one with the maximum $\phi_{r}(\varkappa_{r}(\mathbf{s}))$.

For any machine $j$, with $\ell_{j}(\mathbf{s})\leq\ell_{j}(A)$, it holds that
the last segment of machine $j$ under $A$ precedes the last segment of machine
$r$ under $\mathbf{s}$ according to segment order $\phi$, i.e.
$\phi_{j}(\varkappa_{j}(A))<\phi_{r}(\varkappa_{r}(\mathbf{s}))$, meaning that
overall $\phi_{r}(\varkappa_{r}(\mathbf{s}))$ is the maximum among used
segments under $\mathbf{s}$. The reason is that, if $l$ is the last machine
used by the Delayed-OPT algorithm, the excess of all other machines different
than $l$ is $0$ under $A$, and therefore if $r\neq l$,
$\varkappa_{r}(\mathbf{s})$ is not used in $A$; by the definition of $\phi$
order,
$\phi_{j}(\varkappa_{j}(A))<\phi_{r}(\varkappa_{r}(A)+1)\leq\phi_{r}(\varkappa_{r}(\mathbf{s}))$.
If $r=l$, it trivially holds that
$\phi_{j}(\varkappa_{j}(A))<\phi_{r}(\varkappa_{r}(A))\leq\phi_{r}(\varkappa_{r}(\mathbf{s}))$.

Next we show that under $\mathbf{s}$ either a regular agent or an enforcer has
an incentive to deviate leading to a contradiction.

  * •

If there is at least one enforcer in machine $r$, or
$\varkappa_{r}(\mathbf{s})$ is not full, i.e. $w_{r}(\mathbf{s})\neq 0$, the
highest priority regular agent in $r$, $h_{1}(S_{r}(\mathbf{s})\cap R)$, is
paying $Z_{r}(\varkappa_{r}(\mathbf{s}))$. If this agent deviated to any
machine $j$, with $\ell_{j}(\mathbf{s})<\ell_{j}(A)$ (there exists at least
one because $\ell_{r}(\mathbf{s})>\ell_{r}(A)$), the total load on that
machine would be at most $\ell_{j}(A)$ and therefore the agent’s payment would
be at most $Z_{j}(\varkappa_{j}(A))<Z_{r}(\varkappa_{r}(\mathbf{s}))$.

  * •

If machine $r$ has only regular agents and $0$ excess, i.e.
$w_{r}(\mathbf{s})=0$, there exists an enforcer in some machine
$j^{\prime}\neq r$ that is charged with at least
$\varepsilon_{j^{\prime}}(\varkappa_{j^{\prime}}(\mathbf{s}))$. If he deviated
to machine $r$, the excess of that machine would become $1$ and he would be
the only enforcer in machine $r$, therefore, he would be charged with
$\varepsilon_{r}(\varkappa_{r}(\mathbf{s}))<\varepsilon_{j^{\prime}}(\varkappa_{j^{\prime}}(\mathbf{s}))$,
where the inequality holds because $\phi_{r}(\varkappa_{r}(\mathbf{s}))$ is
the maximum among used segments under $\mathbf{s}$.

∎

∎

######  Theorem 8.

The protocol for the class of 4-step cost functions, assuming two enforcers,
is stable.

Due to space limitations we refer the reader to the appendix for the proof of
the theorem.

##  5 Resource-Aware Mechanism for Games with Stochastic Arrivals

In this section we study the case of stochastic arrivals, where each agent $i$
appears in the system with probability $p_{i}$ and the mechanism has access to
$\mathbf{p}=(p_{1},p_{2},\dots,p_{|\mathcal{N}|})$. Let $S$ be the random set
of the arriving agents and $M$ be a set of machines whose cost functions are
from the class of 4-step functions. We design a cost sharing scheme with the
goal of minimizing the expected price of anarchy defined as follows:

$\text{ExpectedPoA}(\mathcal{G})=\sup_{M,\mathbf{c}\in\mathcal{C}^{|M|}}\left\\{\operatorname*{\mathbb{E}}_{S\sim
P}[\text{PoA}((S,M,\mathbf{c},\Xi))]\,\right\\}.$

Our main theorem (Theorem 12) bounds the expected price of anarchy of our
protocol in relation to the expected number of arriving agents
$\tilde{n}=\operatorname*{\mathbb{E}}_{S\sim\mathbf{p}}[|S|]$. For the sake of
simplicity in this section we prove the case of identical agents that is
$p_{i}=p$ for all $i$. The proof for the general case (Theorem 14) can be
found in the appendix. We show that for the case of independently arriving
agents there exists a protocol using $3+\lfloor
3\frac{\log({p|\mathcal{N}|})}{-\log(1-p)}\rfloor$ enforcers that achieves an
expected price of anarchy of at least

$\text{ExpectedPoA}(\mathcal{G})=O\left(\log\left(\operatorname*{\mathbb{E}}_{S\sim\mathbf{p}}[|S|]\right)\right)=O(\log\tilde{n})\,.$

##### Protocol.

The protocol is similar to the one we defined with the guaranteed enforcers.
However rather than using the two guaranteed agents as the enforcers we choose
an appropriate set of enforcers using the distributional information we have.
In order to guarantee stability for any number of enforcers we adjust the cost
sharing protocol by adding two rest points for enforcers where they pay $0$
share; we further slightly modify the cost shares of enforcers to include
cases where many enforcers use the same machine.

Given the set of arriving agents $S$ and a strategy profile $\mathbf{s}$ we
next define the cost shares of the agents. Let $D\subseteq S$ be the set of
enforcers in $S$ and $R=S\setminus D$ be the set of regular agents in $S$. For
simplicity, we drop the dependency on the load and on $\mathbf{s}$ since there
is no ambiguity. The cost share of any enforcer $i\in D$ using machine $j$ is

$\xi_{i}(\mathbf{s})=\begin{cases}0&\text{if
}j\in\\{1,2\\},w_{j}\in\\{0,t_{j}(\varkappa_{j})-1\\}\mbox{ and }D\cap
S_{j}=\\{i\\}\\\ \varepsilon_{j}(\varkappa_{j})&\text{if }w_{j}\neq 1,D\cap
S_{j}\supset\\{i\\},R\cap S_{j}\neq\emptyset\mbox{ and }i\in\\{h_{1}(S_{j}\cap
D),h_{2}(S_{j}\cap D)\\}\\\ \varepsilon_{j}(\varkappa_{j}-1)&\text{if
}w_{j}=1,D\cap S_{j}=\\{i\\}\mbox{ and }\varkappa_{j}>1\\\
Z_{j}(\varkappa_{j})&\text{otherwise.}\end{cases}\,$

The cost share of any regular agent $i\in R$ using machine $j$ is (the same as
in Section 4.2)

$\xi_{i}(\mathbf{s})=\begin{cases}c_{j}&\text{if }w_{j}=0,D\cap
S_{j}=\emptyset\mbox{ and }i=h_{1}(S_{j}\cap R)\\\
Z_{j}(\varkappa_{j})&\text{if }w_{j}=0,D\cap S_{j}\neq\emptyset\mbox{ and
}i=h_{1}(S_{j}\cap R)\\\ Z_{j}(\varkappa_{j})&\text{if }w_{j}=1\mbox{ and
}i\in\\{h_{1}(S_{j}\cap R),h_{2}(S_{j}\cap R)\\}\\\
Z_{j}(\varkappa_{j})&\text{if }w_{j}\notin\\{0,1\\}\mbox{ and
}i=h_{1}(S_{j}\cap R)\\\ 0&\text{otherwise.}\end{cases}\,$

We refer the reader to the appendix for the proof of the following theorem.

######  Theorem 9.

The protocol for the class of 4-step cost functions is stable for any number
of enforcers.

Next we continue with upper bounding the expected price of anarchy of our
protocol. First we prove two important lemmas on how far the cost of any Nash
equilibrium may be from the cost of the allocation $A$ of the Delayed-OPT
algorithm, conditioned on the number of enforcers in the system. We
distinguish two cases of having at least three enforcers or at most two
enforcers in the system. In the first case, the proof is similar to the one of
Theorem 7, but we now need at least three enforcers because based on the
protocol at most two enforcers may pay $0$ cost shares; those enforcers have
no incentive to deviate to machines that are not used in $A$ and are full with
regular agents.

######  Lemma 10.

If $d\geq 3$ enforcers arrive then the cost of the Nash equilibrium is no more
than $d+3$ times the cost of the allocation $A$ of the Delayed-OPT algorithm,
by ignoring the arbitrarily small charges of $\varepsilon_{j}(k)$ values.

###### Proof.

Since we have two rest points for the enforcers (first case of the cost
shares), meaning that at most two enforcers may pay $0$ in any Nash
equilibrium $\mathbf{s}$, if $d\geq 3$ enforcers appear in the system, then at
least one of them must pay a non-zero share. Following the proof of Theorem 7
we can easily infer that $\mathbf{s}$ uses the exact same allocation as the
Delayed-OPT algorithm (Claim 1). Next we need to bound the overcharging cost.
Note that any cost share $Z_{j}(\varkappa_{j}(A))$ for some $j$ is no more
than the cost of $A$. As a result we simply need to bound the number of agents
charged with such a cost share. Let $d_{j}$ be the number of enforcers in
machine $j$.

First, we examine the machines other than the last machine used by the
Delayed-OPT algorithm. By definition, such machine $j$ will have zero excess,
$w_{j}(A)=0$. Therefore, if there are only regular agents there will be no
overcharging. If there are only enforcers the overcharging is
$d_{j}Z_{j}(\varkappa_{j}(A))$ which is at most $d_{j}$ times the total cost
of $A$. If there is at least one enforcer and at least one regular agent, then
we have at most one regular agent paying $Z_{j}(\varkappa_{j}(A))$ and either
one enforcer is paying $0$ or two enforcers are paying the arbitrarily small
value $\varepsilon_{j}(\varkappa_{j}(A))$. In any case, the overcharging is at
most $d_{j}$ times the total cost of $A$, by ignoring the
$\varepsilon_{j}(\varkappa_{j}(A))$ values.

Second, let’s consider the last machine $r$ used by the Delayed-OPT algorithm.
At most two regular agents are charged with $Z_{r}(\varkappa_{r}(A))$ (if
$w_{r}(A)=1$). It is also possible that all the enforcers are charged with
$Z_{r}(\varkappa_{r}(A))$ and therefore, the total overcharging in machine $r$
is at most $d_{r}+2$ times the total cost of $A$, by ignoring again the
$\varepsilon_{r}(\varkappa_{r}(A))$ values.

Overall, the overcharging is at most $d+2$ times the total cost of $A$ and as
a result, the total cost of $\mathbf{s}$ is no more than $d+3$ times the total
cost of $A$. ∎

######  Lemma 11.

If $r$ regular agents and $d\leq 2$ enforcers arrive then the cost of the Nash
equilibrium $\mathbf{s}$ is no more than $r+d$ times the cost of the
allocation $A$ of the Delayed-OPT algorithm, by ignoring the arbitrarily small
charges of $\varepsilon_{j}(k)$ values.

###### Proof.

If the allocation of $\mathbf{s}$ is not the same as $A$, there must be some
machine $j$ such that $\ell_{j}(\mathbf{s})<\ell_{j}(A)$. This implies that
any agent can deviate to this machine and pay at most
$Z_{j}(\varkappa_{j}(A))$. As a result the cost of any agent (enforcer or
regular) under $\mathbf{s}$ is no more than $Z_{j}(\varkappa_{j}(A))$ which is
upper bounded by the total cost of $A$. Therefore, the total cost of
$\mathbf{s}$ is no more than $r+d$ times the total cost of $A$. ∎

Next we upper bound the price of anarchy in the special case where the agents
arrival probabilities are identical, that is $p_{i}=p$ for all
$i\in\mathcal{N}$. Note that in this case the expected number of agents is
$\tilde{n}=E_{S\sim\mathbf{p}}[|S|]=p|\mathcal{N}|$.

######  Theorem 12.

For independently arriving agents with identical probabilities $p$ and for the
class of 4-step cost functions, there exists a protocol using $|D|=3+\lfloor
3\frac{\log({p|\mathcal{N}|})}{-\log(1-p)}\rfloor$ enforcers that achieves an
expected price of anarchy of

$\text{ExpectedPoA}(\mathcal{G})=O(\log(\operatorname*{\mathbb{E}}_{S\sim\mathbf{p}}[|S|]))=O(\log\tilde{n})\,.$

Before proceeding with the proof of Theorem 12, we state the following lemma.
The proof of the lemma is in the appendix.

######  Lemma 13.

If we choose a set of enforcers $D$ such that $|D|=3+\lfloor
3\frac{\log({p|\mathcal{N}|})}{-\log(1-p)}\rfloor$ then

$\mathbb{P}[d\leq 2]\operatorname*{\mathbb{E}}_{S\sim\mathbf{p}}[|S|\mid d\leq
2]\leq 9\,,$

where $\mathbb{P}$ is the probability symbol and $d=|S\cap D|$ is a random
variable depending on $\mathbf{p}.$

###### Proof.

(Theorem 12) Let $S$ be a random set of arriving agents, $G$ be the
corresponding game, $Eq(G)$ be the set of Nash equilibria for $G$ and $A$ be
the allocation of the Delayed-OPT algorithm for the set $S$. Moreover, let
$d=|S\cap D|$ be a random variable depending on $\mathbf{p}$. Combining both
Lemmas 10 and 11 we get that the expected ratio of the cost of the worst case
equilibrium to the cost of the allocation of the Delayed-OPT algorithm is

$\operatorname*{\mathbb{E}}_{S\sim\mathbf{p}}\left[\frac{\max_{\mathbf{s}\in\textrm{Eq($G$)}}\hat{C}(\mathbf{s})}{C(A)}\right]=\mathbb{P}[d\leq
2]\operatorname*{\mathbb{E}}_{S\sim\mathbf{p}}[|S|\mid d\leq
2]+\mathbb{P}[d\geq 3]\operatorname*{\mathbb{E}}_{S\sim\mathbf{p}}[d+3\mid
d\geq 3]\,.$ (1)

We can bound the second summand of Equation (1) as

$\displaystyle\mathbb{P}[d\geq
3]\operatorname*{\mathbb{E}}_{S\sim\mathbf{p}}[d+3\mid d\geq 3]$
$\displaystyle\leq$
$\displaystyle\operatorname*{\mathbb{E}}_{S\sim\mathbf{p}}[d+3\mid d\geq 3]$
(2) $\displaystyle\leq$
$\displaystyle\operatorname*{\mathbb{E}}_{S\sim\mathbf{p}}[d\mid d\geq
0]+6=p|D|+6\,.$

Combining Lemma 13, Equation (1) and Equation (2) we get that

$\displaystyle\operatorname*{\mathbb{E}}_{S\sim\mathbf{p}}\left[\frac{\max_{\mathbf{s}\in\textrm{E($G$)}}\hat{C}(\mathbf{s})}{C(A)}\right]$
$\displaystyle\leq$ $\displaystyle p|D|+15\leq\lfloor
3\log(p|\mathcal{N}|)\left(\frac{p}{-\log(1-p)}\right)\rfloor+18$ (3)
$\displaystyle\leq$ $\displaystyle
3\log(p|\mathcal{N}|)\left(\frac{p}{-\log(1-p)}\right)+18$ $\displaystyle\leq$
$\displaystyle 3\log(p|\mathcal{N}|)+18=3\log\tilde{n}+18\,,$

where the last inequality is due to $(\frac{p}{-\log(1-p)})\leq 1$ for $p\geq
0$. The fact that the cost of the Delayed-OPT algorithm outcome is a constant
approximation to the optimum cost completes the proof. ∎

Next we upper bound the price of anarchy when the agents arrival probabilities
are not necessarily identical. For $p_{i}$ being the probability that agent
$i$ arrives,
$\tilde{n}=E_{S\sim\mathbf{p}}[|S|]=\sum_{i=1}^{|\mathcal{N}|}p_{i}$ is the
expected number of agents. The proof of the theorem is in the appendix.

######  Theorem 14.

For independently arriving agents with not necessarily identical probabilities
and for the class of 4-step cost functions, there exists a protocol that
achieves an expected price of anarchy of

$\text{ExpectedPoA}(\mathcal{G})=O(\log(\operatorname*{\mathbb{E}}_{S\sim\mathbf{p}}[|S|]))=O(\log\tilde{n})\,.$

### Acknowledgments

The authors would like to thank Giorgos Christodoulou for helpful discussions
during the initial stages of this project. The work of the first author was
partially supported by NSF CAREER award CCF-2047907.

## References

  * Abed and Huang [2012] F. Abed and C.-C. Huang.  Preemptive coordination mechanisms for unrelated machines.  In _European Symposium on Algorithms_ , pages 12–23. Springer, 2012\.
  * Anshelevich et al. [2008] E. Anshelevich, A. Dasgupta, J. M. Kleinberg, É. Tardos, T. Wexler, and T. Roughgarden.  The price of stability for network design with fair cost allocation.  _SIAM J. Comput._ , 38(4):1602–1623, 2008.
  * Azar et al. [2015] Y. Azar, L. Fleischer, K. Jain, V. S. Mirrokni, and Z. Svitkina.  Optimal coordination mechanisms for unrelated machine scheduling.  _Operations Research_ , 63(3):489–500, 2015.
  * Bhattacharya et al. [2014] S. Bhattacharya, S. Im, J. Kulkarni, and K. Munagala.  Coordination mechanisms from (almost) all scheduling policies.  In _5th conference on Innovations in theoretical computer science_ , pages 121–134. ACM, 2014.
  * Caragiannis [2013] I. Caragiannis.  Efficient coordination mechanisms for unrelated machine scheduling.  _Algorithmica_ , 66(3):512–540, 2013.
  * Caragiannis et al. [2017] I. Caragiannis, V. Gkatzelis, and C. Vinci.  Coordination mechanisms, cost-sharing, and approximation algorithms for scheduling.  In N. R. Devanur and P. Lu, editors, _Web and Internet Economics \- 13th International Conference, WINE 2017, Bangalore, India, December 17-20, 2017, Proceedings_ , volume 10660 of _Lecture Notes in Computer Science_ , pages 74–87. Springer, 2017.
  * Chen et al. [2010] H.-L. Chen, T. Roughgarden, and G. Valiant.  Designing network protocols for good equilibria.  _SIAM Journal on Computing_ , 39(5):1799–1832, 2010.
  * Christodoulou and Sgouritsa [2019] G. Christodoulou and A. Sgouritsa.  Designing networks with good equilibria under uncertainty.  _SIAM J. Comput._ , 48(4):1364–1396, 2019.
  * Christodoulou et al. [2009] G. Christodoulou, E. Koutsoupias, and A. Nanavati.  Coordination mechanisms.  _Theor. Comput. Sci._ , 410(36):3327–3336, 2009\.
  * Christodoulou et al. [2014] G. Christodoulou, K. Mehlhorn, and E. Pyrga.  Improving the price of anarchy for selfish routing via coordination mechanisms.  _Algorithmica_ , 69(3):619–640, 2014.
  * Christodoulou et al. [2017] G. Christodoulou, V. Gkatzelis, and A. Sgouritsa.  Cost-sharing methods for scheduling games under uncertainty.  In _Proceedings of the 2017 ACM Conference on Economics and Computation, EC ’17, Cambridge, MA, USA, June 26-30, 2017_ , pages 441–458, 2017\.
  * Christodoulou et al. [2019] G. Christodoulou, S. Leonardi, and A. Sgouritsa.  Designing cost-sharing methods for bayesian games.  _Theory of computing systems_ , 63(1):4–25, 2019\.
  * Christodoulou et al. [2020] G. Christodoulou, V. Gkatzelis, M. Latifian, and A. Sgouritsa.  Resource-aware protocols for network cost-sharing games.  In P. Biró, J. D. Hartline, M. Ostrovsky, and A. D. Procaccia, editors, _EC ’20: The 21st ACM Conference on Economics and Computation, Virtual Event, Hungary, July 13-17, 2020_ , pages 81–107. ACM, 2020\.
  * Cole et al. [2015] R. Cole, J. R. Correa, V. Gkatzelis, V. S. Mirrokni, and N. Olver.  Decentralized utilitarian mechanisms for scheduling games.  _Games and Economic Behavior_ , 92:306–326, 2015.
  * Gkatzelis et al. [2016] V. Gkatzelis, K. Kollias, and T. Roughgarden.  Optimal cost-sharing in general resource selection games.  _Operations Research_ , 64(6):1230–1238, 2016\.
  * Gopalakrishnan et al. [2014] R. Gopalakrishnan, J. R. Marden, and A. Wierman.  Potential games are necessary to ensure pure nash equilibria in cost sharing games.  _Mathematics of Operations Research_ , 2014.
  * Harks and Miller [2011] T. Harks and K. Miller.  The worst-case efficiency of cost sharing methods in resource allocation games.  _Operations Research_ , 59(6):1491–1503, 2011\.
  * Harks and von Falkenhausen [2014] T. Harks and P. von Falkenhausen.  Optimal cost sharing for capacitated facility location games.  _Eur. J. Oper. Res._ , 239(1):187–198, 2014.
  * Harks et al. [2021] T. Harks, M. Hoefer, A. Schedel, and M. Surek.  Efficient black-box reductions for separable cost sharing.  _Mathematics of Operations Research_ , 46(1):134–158, 2021.
  * Immorlica et al. [2009] N. Immorlica, L. E. Li, V. S. Mirrokni, and A. S. Schulz.  Coordination mechanisms for selfish scheduling.  _Theoretical Computer Science_ , 410(17):1589–1598, 2009.
  * Kollias [2013] K. Kollias.  Nonpreemptive coordination mechanisms for identical machines.  _Theory of Computing Systems_ , 53(3):424–440, 2013.
  * Marden and Wierman [2013] J. R. Marden and A. Wierman.  Distributed welfare games.  _Operations Research_ , 61(1):155–168, 2013.
  * Mosk-Aoyama and Roughgarden [2009] D. Mosk-Aoyama and T. Roughgarden.  Worst-case efficiency analysis of queueing disciplines.  In _International Colloquium on Automata, Languages and Programming_ , pages 546–557. Springer, 2009.
  * Moulin [1999] H. Moulin.  Incremental cost sharing: Characterization by coalition strategy-proofness.  _Social Choice and Welfare_ , 16(2):279–320, 1999\.  ISSN 1432-217X.
  * Moulin [2008] H. Moulin.  The price of anarchy of serial, average and incremental cost sharing.  _Economic Theory_ , 36(3):379–405, 2008.
  * Moulin and Shenker [2001] H. Moulin and S. J. Shenker.  Strategyproof sharing of submodular costs: budget balance versus efficiency.  _Economic Theory_ , 18(3):511–533, 2001.
  * Nisan et al. [2007] N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani, editors.  _Algorithmic Game Theory_.  Cambridge University Press, 2007.
  * von Falkenhausen and Harks [2013] P. von Falkenhausen and T. Harks.  Optimal cost sharing for resource selection games.  _Mathematics of Operations Research_ , 38(1):184–208, 2013.

##  Appendix A Additional Discussion Regarding our Results

In this section we briefly address some more technical aspects regarding our
results and its comparison to prior work. We first discuss the type of
overcharging that we use in our mechanisms, and compare it to the types of
overcharging that has been used in prior work. We then provide some (partial)
justification and intuition behind some limits that we require on the number
of enforcers, and the capacities of the capacitated constant cost functions.

##### Power of overcharging.

At the core of our cost-sharing mechanism lies the ability of enforcers to
penalize other agents through overcharging. In fact, the total amount of
overcharging that our mechanism enforces can depend not only on the number of
agents using a machine, but also on the actual set of agents (e.g., on whether
one of them is an enforcer or not). This is in contrast to the way that some
prior cost-sharing mechanisms have used overcharging, e.g., in Christodoulou
et al. [2017, 2020]. In fact, the result of Christodoulou et al. [2017],
showing that no resource-aware mechanism can achieve a PoA better than
$O(\sqrt{n})$, even if it uses overcharging, assumes that the amount of
overcharging would depend only on the number of users, not the set of users of
the corresponding machine. In light of this observation, one could argue that
our mechanisms in this paper do not only leverage the additional information
that they have, relative to prior-free resource-aware mechanisms; they
actually also leverage the ability to introduce overcharging in a more
flexible way.

##### Restriction on the number of enforcers.

Assume that there was only one enforcer appearing in the system. Consider a
number of agents such that in the allocation of the Delayed-OPT algorithm the
last machine $r$ is fully used, i.e., $n_{r}=t_{r}$ agents are allocated in
machine $r$. The enforcer should not have an incentive to deviate to machines
full of regular agents and therefore, he should pay at most
$\varepsilon_{r-1}$. Moreover, he should pay more than $\varepsilon_{r+1}$ so
he deviates to machine $r+1$ if it is full of regular agents. This is the
reason we assume the monotonicity on the $\varepsilon_{j}$ values and we
allocate the enforcer in machine $r$.

Consider now a number of agents such that in the allocation of the Delayed-OPT
algorithm machine $r$ is used by $n_{r}=t_{r}-1$ agents. In the stable
outcome, if we allocate the enforcer to any full machine $j$, he has an
incentive to deviate to the last machine, make it full and pay
$\varepsilon_{r}<\varepsilon_{j}$. Therefore, the only option is to allocate
the enforcer to the last machine $r$. In order for such allocation to be an
equilibrium, he should be charged with some
$\varepsilon^{\prime}_{r}<\varepsilon_{r-1}$ so he has no incentive to deviate
to prior machines full of regular agents. By considering now $n_{r}=t_{r}-2$
and using the same arguments we can show that if the enforcer uses machine
$r$, he should be charged with something strictly less than
$\varepsilon_{r-1}$. Similarly, for any $n_{r}$ we can show that the enforcer
should be charged with an amount strictly less than $\varepsilon_{r-1}$, and
therefore the same should hold for $n_{r}=1$. But for $n_{r}=1$ the enforcer
would be alone in $r$ and hence, he should pay at least $c_{r}$ which leads to
a contradiction. Considering enforcers in pairs resolves this issue and
results in the existence of stable outcomes.

##### Restriction on the capacities.

This was derived from the need to distinguish between the two cases in the
proof of Lemma 5. First notice that the two enforcers should be together,
otherwise they have an incentive to deviate to a machine full of regular
agents. Suppose now that $n_{r}=2$ agents use the last machine $r$ based on
the allocation of the Delayed-OPT algorithm. If both enforcers were placed in
machine $r$, one of them should be charged with at least $c_{r}/2$ and still
have an incentive to deviate to a full machine. Therefore, for $n_{r}\leq 2$,
in any equilibrium the enforcers do not use $r$.

One the other hand, in the case that $n_{r}=t_{r}-1$, if no enforcer was
placed in machine $r$, the lowest priority agent $i$ in machine $j$ that the
enforcers use, may have an incentive to deviate to machine $r$. This could be
the case because agent $i$ is currently charged with $Z_{j}$, which could
possibly be greater than $c_{r}$, where $c_{r}$ would be the maximum charge of
agent $i$ if he deviated to machine $r$; the reason is that $r$ would become
full. This means that for $n_{r}=t_{r}-1$, in any equilibrium at least one
enforcer should use machine $r$ (this automatically means that $t_{r}$ should
be different than $1$).

Overall, the above two points indicate the restriction of $t_{r}-1>2$, which
results in the requirement of $t_{j}\geq 4$ for all machines $j$.

##  Appendix B Missing Proofs from Section 4

###  B.1 Proof of Theorem 8

We next show how we construct a strategy profile that is a Nash equilibrium.
Let $A$ be the allocation according to the Delayed-OPT algorithm and let $r$
be the last machine used by the Delayed-OPT algorithm. We will consider cases
based on the excess of that machine, $w_{r}(A)$, and its load, $\ell_{r}(A)$.
For any other machine $j\neq r$ note that $j$ has $0$ excess, i.e.
$w_{j}(A)=0$.

For the construction of the Nash equilibrium we allocate the agents the same
way as the Delayed-OPT algorithm does, but we need to carefully assign the
enforcers and regular agents to the appropriate machines in order to ensure
stability. The following assignment guarantees stability.

  * •

If only one machine is used by the Delayed-OPT algorithm, then simply
allocating any agent to this machine would be Nash equilibrium.

  * •

If more than one machine is used by the Delayed-OPT algorithm, we distinguish
between two cases based on the values of $w_{r}(A)$ and $\ell_{r}(A)$.

    * –

$w_{r}(A)\neq 1$ and $\ell_{r}(A)>2$: We allocate the two enforcers to machine
$r$ and the regular agents in a way such that the allocation coincides with
$A$ by ensuring that agents paying non-zero cost shares are the highest
priority agents, with the lowest among them to be allocated to machine $r$.

Obviously, regular agents paying $0$ have no incentive to deviate. If an
enforcer from machine $r$ deviated to another machine $j$ then the excess
would increase to $1$ and the enforcer would pay
$\varepsilon_{j}(\varkappa_{j}(A))$, but ,by the definition of the
$\varepsilon_{j}(k)$ values, this is higher than his current payment of
$\varepsilon_{r}(\varkappa_{r}(A))$. Finally, regarding regular agents with
non-zero cost shares, if they deviated to machine $r$ they would have the
highest priority and pay at least $Z_{r}(\varkappa_{r}(A))$ which is more than
their current charge. If they deviated to any machine $j\neq r$, they would
increase the excess to $1$ and pay
$Z_{j}((\varkappa_{j}(A)+1))>Z_{r}(\varkappa_{r}(A))$.

    * –

$w_{r}(A)=1$ or $\ell_{r}(A)=2$: We allocate the two enforcers to machine
$r^{\prime}\neq r$ that is the last machine used by the Delayed-OPT algorithm
before $r$.999We do not assign the enforcers to machine $r$, because in the
cases that the excess is $1$ and there are two enforcers or there is no
regular agents, the enforcers pay a high cost. We allocate the regular agents
in a way such that the allocation coincides with $A$ by ensuring that agents
paying non-zero cost shares are the highest priority agents with the two
lowest among them (or the one lowest, if $\ell_{r}(A)=1$) to be allocated to
machine $r$.

Similarly, regular agents paying $0$ have no incentive to deviate. If an
enforcer from machine $r^{\prime}$ deviated to another machine $j\neq r$ the
same argument as before holds. If he deviated to machine $r$, he would be the
only enforcer and the excess of $r$ would become either $2$ or $3$, meaning
that his charge would be $Z_{r}(\varkappa_{r}(A))$. Finally, regarding regular
agents with non-zero cost shares, the same arguments as before hold.

##  Appendix C Missing Proofs from Section 5

###  C.1 Proof of Theorem 9

We show how we construct a strategy profile that is a Nash equilibrium
similarly to Theorem 8. Let $A$ be the allocation according to the Delayed-OPT
algorithm and let $r$ be the last machine used by the Delayed-OPT algorithm.
We will consider cases based on the excess of that machine, $w_{r}(A)$ and its
load, $\ell_{r}(A)$.

If only one machine is used in the Delayed-OPT algorithm then simply
allocating any agent to this machine would be Nash equilibrium. Next we
consider separately the cases of no enforcer, one enforcer and at least two
enforcers.

  * •

Only regular agents

    * –

If $w_{r}(A)\neq t_{r}(\varkappa_{r}(A))-1$, we assign agents according to $A$
making sure that the highest priority agents are responsible for non-zero
costs, i.e. if an agent has a cost share of $0$ then all lower priority agents
have a cost share of $0$. Additionally we ensure that among the agents paying
non-zero cost, the lowest priority agents are allocated to machine $r$; in
other words, if $w_{r}(A)=1$ we ensure that the two highest priority agents in
machine $r$ have the lowest priority among agents with non-zero cost shares
and if $w_{r}(A)\neq 1$ we ensure that the one highest priority agent in
machine $r$ has the lowest priority among agents with non-zero cost shares.

Every agent with $0$ cost share has no incentive to deviate. Consider some
agent with non-zero cost share. Deviating to some machine $j\neq r$ would
increase the excess to $1$ causing the two highest priority agents to pay a
non-zero cost share equal to
$Z_{r}(\varkappa_{r}(A)+1)>Z_{r}(\varkappa_{r}(A))$. Currently there is only
one agent charged with non-zero cost share in machine $j$, and therefore the
deviating agent would have one of the two highest priorities which means that
the deviation is not profitable. If the agent deviated to $r$, since
$w_{r}(A)\neq t_{r}(\varkappa_{r}(A))-1$ and the agent has higher priority
than any agent in machine $r$, he would pay either
$Z_{r}((\varkappa_{r}(A)+1))$ if $w_{r}(A)=0$ or $Z_{r}(\varkappa_{r}(A))$
otherwise. In either case this is not a desirable deviation.

    * –

If $w_{r}=t_{r}(\varkappa_{r}(A))-1$ then we may need to alter the allocation
$A$ as follows. Let $j$ be the machine with the highest total cost $c_{j}(A)$
according to $A$. We move one agent from machine $j$ to machine $r$ (or do
nothing if $j=r$). Similarly as above, we make sure that the highest priority
agents are responsible for non-zero costs and the lowest priority of those are
placed in machine $j$.

We claim that this assignment is a Nash equilibrium. Naturally agents that
have $0$ cost share have no incentive to deviate. If an agent with non-zero
cost deviates to some machine $j^{\prime}\neq j$ will result in excess of $1$
and will pay
$Z_{j^{\prime}}(\varkappa_{j^{\prime}}(A)+1)>Z_{r}(\varkappa_{r}(A))$.
Deviating to machine $j$ will result in $0$ excess and since the agent has the
highest priority will pay the total cost of the machine. But since this agent
was already paying the total cost of another machine and the cost of machine
$j$ is the highest the deviation is not profitable.

  * •

Exactly one enforcer

    * –

If $w_{r}(A)\neq t_{r}(\varkappa_{r}(A))-1$, we put the enforcer to either
machine $1$ or $2$ depending on which of them has excess of $0$ (always one of
them has) so that the enforcer pays $0$. We allocate arbitrarily the rest of
the agents according to $A$ making sure that the highest priority agents are
responsible for non-zero costs, ensuring that the lowest priority agents among
them are allocated to machine $r$.

Since the machine that the enforcer occupies (machine $1$ or $2$) has excess
$0$ the enforcer pays $0$ and has no incentive to deviate. The same arguments
as in the case of only regular agents can be used here in order to show that
no regular agent has an incentive to deviate.

    * –

If $w_{r}(A)=t_{r}(\varkappa_{r}(A))-1$ then we allocate the enforcer to
either machine $1$ or $2$ depending on which of them has excess of $0$; let
$f$ be that machine. We first assign the regular agents according to $A$ and
then adjust the assignment as follows. Let $j$ be the machine with the maximum
total cost $c_{j}(A)$ according to $A$. If $Z_{f}(\varkappa_{f}(A))>c_{j}(A)$
we change $j$ to be $f$. Then we move one agent from machine $j$ to machine
$r$, unless $j=r$, and similarly as above, we make sure that the highest
priority agents are responsible for non-zero costs and the lowest priority
among them are placed in machine $j$.

The enforcer pays $0$ since machine $f$ has either excess $0$ or excess
$t_{f}(\varkappa_{f}(A)-1)$ and therefore the enforcer has no incentive to
deviate. If any agent deviated to some machine $j^{\prime}\neq j$ would result
in a cost
$Z_{j^{\prime}}(\varkappa_{j^{\prime}}(A)+1)>Z_{r}(\varkappa_{r}(A))$.
Deviating to machine $j$ would result in a cost share equal to either
$Z_{f}(\varkappa_{f}(A))$ if $j=f$ or $c_{j}(A)$ otherwise. Since we picked
$j$ such that the cost share of deviating to be the maximum, the deviation is
not profitable.

  * •

At least two enforcers
Let $d$ be the number of enforcers that arrive and $f$ be either machine $1$
or $2$ as long as it is different from $r$; $f$ has excess of $0$. We allocate
the agents according to $A$ and we assign the spots to enforcers and regular
agents as follows:

    * –

$w_{r}(A)\neq 1$ and $\ell_{r}(A)>2$
We allocate the enforcers in pairs, following their priority order from high
to low, to machines with increasing $\varepsilon_{j}(\varkappa_{j}(A))$,
starting from machine $r$; in the case that $d$ is odd, we assign only one
enforcer to machine $f$. If there are more enforcers, we allocate one more
enforcer based on the priority order to machine $f$ in the case that $d$ is
odd and the rest of the enforcers are allocated arbitrarily.

    * –

$\ell_{r}(A)\leq 2$
Similarly as above, we allocate the enforcers in pairs as above but by
ignoring machine $r$. If there are more enforcers we allocate the next
pair101010Note that there would be a pair of enforcers because if $d$ is odd,
we would have allocated odd number of enforcers so far and if $d$ is even we
would have allocated even number of enforcers so far. to machine $r$ if
$\ell_{r}(A)=2$ or the next enforcer to machine $r$ if $\ell_{r}(A)=1$. If
there are more enforcers we allocate the next one to machine $f$ if it has
only one enforcer and the rest arbitrarily.

    * –

$w_{r}(A)=1$ and $\ell_{r}(A)>2$
We start allocating the enforcers as in the second case with the only
difference that we if we allocate a pair of enforcers in machine $r$, we make
sure that the highest priority pair of enforcers is allocated in $r$.

We allocate the regular agents arbitrarily making sure that the highest
priority regular agents are charged with non-zero cost shares, ensuring that
machine $r$ has the lowest priority among them.

Obviously, agents paying $0$ have no incentive to deviate.

If an enforcer deviated to machine $r$ and the first case applies where
$w_{r}(A)\neq 1$ and $\ell_{r}(A)>2$, then machine $r$ has already the two
highest priority enforcers and therefore the deviating enforcer would pay
either $Z_{r}(\varkappa_{r}(A)+1)$ or $Z_{r}(\varkappa_{r}(A))$ both of which
are not profitable. If an enforcer deviated to $r$ and $\ell_{r}(A)\leq 2$
then either he would be the only enforcer or $r$ had no regular agent; in both
cases the deviating enforcer would pay $Z_{r}(\varkappa_{r}(A))$. If an
enforcer deviated to $r$ and $\ell_{r}(A)>2$ but $w_{r}(A)=1$, the excess of
$r$ would become $2$ and machine either $r$ has already the two highest
priority enforcers or it has no enforcer, meaning in both cases that the
deviating enforcer would pay $Z_{r}(\varkappa_{r}(A))$.

If an enforcer deviated to another machine $j$ then the excess increases to
$1$. If there was already at least one enforcer then the deviating enforcer
would pay $Z_{j}(\varkappa_{j}(A)+1)>Z_{r}(\varkappa_{r}(A))$. If there was no
other enforcer then the deviating enforcer would pay
$\varepsilon_{j}(\varkappa_{j}(A))$ but by our assignment this must be higher
than the current payment of the enforcer.

Finally if any regular agent with non-zero cost share deviated to $r$, he
would be the highest priority agent and pay $Z_{r}(\varkappa_{r}(A)+1)$ or
$Z_{r}(\varkappa_{r}(A))$ and if he deviated to $j\neq r$ he would increase
the excess to $1$ and pay $Z_{j}(\varkappa_{j}(A)+1)>Z_{r}(\varkappa_{r}(A))$.

###  C.2 Proof of Lemma 13

We consider two cases with respect to the expected number of agents.

If $p|\mathcal{N}|\leq 1$,

$\mathbb{P}[d\leq 2]\operatorname*{\mathbb{E}}_{S\sim\mathbf{p}}[|S|\mid d\leq
2]\leq\operatorname*{\mathbb{E}}_{S\sim\mathbf{p}}[|S|\mid d\leq 2]\leq
p|\mathcal{N}\setminus D|+2\leq p|\mathcal{N}|+2\leq 3\,.$

If $p|\mathcal{N}|>1$,

$\displaystyle\mathbb{P}[d\leq
2]\operatorname*{\mathbb{E}}_{S\sim\mathbf{p}}[|S|\mid d\leq 2]]$
$\displaystyle\leq$
$\displaystyle(\mathbb{P}[d=0]+\mathbb{P}[d=1]+\mathbb{P}[d=2])(p|\mathcal{N}\setminus
D|+2)$ $\displaystyle\leq$
$\displaystyle((1-p)^{|D|}+(1-p)^{|D|-1}p|D|+(1-p)^{|D|-2}p^{2}|D|^{2})(p|\mathcal{N}|+2)$
$\displaystyle\leq$
$\displaystyle(1+p|D|+p^{2}|D|^{2})(1-p)^{|D|-2}(p|\mathcal{N}|+2)$
$\displaystyle\leq$ $\displaystyle
3(p|\mathcal{N}|)^{2}(1-p)^{|D|-2}(p|\mathcal{N}|+2)$ $\displaystyle\leq$
$\displaystyle 9(p|\mathcal{N}|)^{3}(1-p)^{|D|-2}$ $\displaystyle\leq$
$\displaystyle
9(p|\mathcal{N}|)^{3}(1-p)^{\frac{\log\left(\frac{1}{(|\mathcal{N}|p)^{3}}\right)}{\log(1-p)}}$
$\displaystyle=$ $\displaystyle
9(p|\mathcal{N}|)^{3}\frac{1}{(p|\mathcal{N}|)^{3}}=9.$

where the last inequality comes from the fact that
$|D|-2=1+\lfloor\frac{\log\left(\frac{1}{(|\mathcal{N}|p)^{3}}\right)}{\log(1-p)}\rfloor\geq\frac{\log\left(\frac{1}{(|\mathcal{N}|p)^{3}}\right)}{\log(1-p)}$

###  C.3 Proof of Theorem 14

Let $S$ be a random set of arriving agents, $G$ be the corresponding game,
$Eq(G)$ be the set of Nash equilibria for $G$ and $A$ be the allocation of the
Delayed-OPT algorithm for the set $S$. Moreover, let $d=|S\cap D|$ be a random
variable depending on $\mathbf{p}=(p_{1},p_{2},\ldots,p_{|\mathcal{N}|})$.
Similarly to the proof of Theorem 12, combining both Lemmas 10 and 11 we get
that the expected ratio of the cost of the worst case equilibrium to the cost
of the allocation of the Delayed-OPT algorithm is

$\operatorname*{\mathbb{E}}_{S\sim\mathbf{p}}\left[\frac{\max_{\mathbf{s}\in\textrm{Eq($G$)}}\hat{C}(\mathbf{s})}{C(A)}\right]=\mathbb{P}[d\leq
2]\operatorname*{\mathbb{E}}_{S\sim\mathbf{p}}[|S|\mid d\leq
2]+\mathbb{P}[d\geq 3]\operatorname*{\mathbb{E}}_{S\sim\mathbf{p}}[d+3\mid
d\geq 3]\,.$ (4)

W.l.o.g. assume $p_{1}\geq p_{2}\geq\dots\geq p_{|\mathcal{N}|}$. Then we
designate the set of enforcers $D$ to be the agents associated with the
highest probabilities such that $\sum_{i=3}^{|D|}p_{i}=3\log\tilde{n}$ (we
always designate as enforcers the two agents with the highest probability). We
first bound the probability $\mathbb{P}[d\leq 2]$ for the case that
$\tilde{n}>1$ as follows.

$\displaystyle\mathbb{P}[d\leq 2]$ $\displaystyle=$
$\displaystyle\mathbb{P}[d=0]+\mathbb{P}[d=1]+\mathbb{P}[d=2]$
$\displaystyle=$
$\displaystyle\prod_{i=1}^{|D|}(1-p_{i})+\sum_{j=1}^{|D|}p_{j}\cdot\prod_{i=1,i\neq
j}^{|D|}(1-p_{i})+\sum_{k=1}^{|D|}p_{k}\cdot\sum_{j=1,j\neq
k}^{|D|}p_{j}\cdot\prod_{i=1,i\notin\\{j,k\\}}^{|D|}(1-p_{i})$
$\displaystyle\leq$
$\displaystyle\prod_{i=3}^{|D|}(1-p_{i})\left(1+\sum_{j=1}^{|D|}p_{j}+\sum_{k=1}^{|D|}p_{k}\cdot\sum_{j=1,j\neq
k}^{|D|}p_{j}\right)$ $\displaystyle\leq$
$\displaystyle\left(\frac{\sum_{i=3}^{|D|}(1-p_{i})}{|D|-2}\right)^{|D|-2}\left(1+\sum_{j=1}^{|\mathcal{N}|}p_{j}+\sum_{k=1}^{|\mathcal{N}|}p_{k}\cdot\sum_{j=1}^{|\mathcal{N}|}p_{j}\right)$
$\displaystyle\leq$
$\displaystyle\left(1-\frac{\sum_{i=3}^{|D|}p_{i}}{|D|-2}\right)^{|D|-2}\cdot
3\tilde{n}^{2}=3\tilde{n}^{2}\left(1-\frac{3\log\tilde{n}}{|D|-2}\right)^{|D|-2}$
$\displaystyle\leq$ $\displaystyle
3\tilde{n}^{2}e^{-3\log\tilde{n}}=3\tilde{n}^{2}\frac{1}{\tilde{n}^{3}}=\frac{3}{\tilde{n}}\,,$

where the second inequality comes from the AM/GM inequality:
$\left(\prod_{i=1}^{k}x_{i}\right)^{1/k}\leq 1/k\sum_{i=1}^{k}x_{i}$, and the
final inequality follows from the fact that $(1-x/k)^{k}\leq e^{-x}$. As a
result, we can bound the first summand of (4) by $9$ as follows.

If $\tilde{n}\leq 1$, then

$\mathbb{P}[d\leq 2]\operatorname*{\mathbb{E}}[|S|\mid d\leq
2]\leq\operatorname*{\mathbb{E}}[|S|\mid d\leq 2]\leq\tilde{n}+2\leq 3\,,$ (5)

otherwise,

$\mathbb{P}[d\leq 2]\operatorname*{\mathbb{E}}[|S|\mid d\leq
2]\leq\frac{3}{\tilde{n}}(\tilde{n}+2)\leq 9\,.$ (6)

Similarly to Equation (2) we can bound the second summand of (4) as

$\mathbb{P}[d\geq 3]\operatorname*{\mathbb{E}}[d+3\mid d\geq
3]\leq\operatorname*{\mathbb{E}}[d\mid d\geq
0]+6\leq\sum_{i=1}^{|D|}p_{i}+6\leq\sum_{i=3}^{|D|}p_{i}+8=3\log\tilde{n}+8$
(7)

Combining Equations (4), (5), (6) and (7) completes the proof of the theorem.