[1]Gennaro Auricchio

1]Department of Mathematics, Università di Padova, Padua, Italy

2]Department of Computer Science, University of Bath, Bath, UK

# Mechanism Design for Locating Facilities with Capacities with Insufficient
Resources222A previous version of this paper appeared in the proceedings of
UAI24, [1]. In this improved version, we study the problem in higher dimension
and enhance our numerical results.

<EMAIL_ADDRESS>Harry J. Clough<EMAIL_ADDRESS>Jie Zhang
<EMAIL_ADDRESS>[  [

###### Abstract

This paper explores the Mechanism Design aspects of the $m$-Capacitated
Facility Location Problem where the total facility capacity is less than the
number of agents. Following the framework outlined in [2], the Social Welfare
of the facility location is determined through a First-Come-First-Served
(FCFS) game, in which agents compete once the facility positions are
established. When the number of facilities is $m>1$, the Nash Equilibrium (NE)
of the FCFS game is not unique, making the utility of the agents and the
concept of truthfulness unclear. To tackle these issues, we consider
absolutely truthful mechanisms—mechanisms that prevent agents from
misreporting regardless of the strategies used during the FCFS game. We
combine this stricter truthfulness requirement with the notion of Equilibrium
Stable (ES) mechanisms, which are mechanisms whose Social Welfare does not
depend on the NE of the FCFS game. We demonstrate that the class of percentile
mechanisms is absolutely truthful and identify the conditions under which they
are ES. We also show that the approximation ratio of each ES percentile
mechanism is bounded and determine its value. Notably, when all the facilities
have the same capacity and the number of agents is sufficiently large, it is
possible to achieve an approximation ratio smaller than $1+\frac{1}{2m-1}$.
Finally, we extend our study to encompass higher-dimensional problems. Within
this framework, we demonstrate that the class of ES percentile mechanisms is
even more restricted and characterize the mechanisms that are both ES and
absolutely truthful. We further support our findings by empirically evaluating
the performance of the mechanisms when the agents are the samples of a
distribution.

###### keywords:

Facility Location, Mechanism Design, Game Theory, Nash Equilibrium

##  1 Introduction

The $m$-Capacitated Facility Location Problem ($m$-CFLP) extends the
$m$-Facility Location Problem ($m$-FLP) by introducing a constraint that
bounds the number of clients the facility can accommodate [3, 4, 5]. Both the
$m$-FLP and the $m$-CFLP are essential subproblems in various applications
within social choice theory. These include areas such as disaster relief [6],
where efficient allocation of resources is of critical importance; supply
chain management [7], which focuses on optimizing logistics and distribution
networks; healthcare systems [8], aiming to improve service delivery and
accessibility; clustering techniques [9, 10], used in data analysis and
machine learning; and public facility accessibility [11], which enhances
community services by effectively placing facilities to serve the population.
In its fundamental guise, the $m$-CFLP consists of determining the location of
$m$ facilities starting from the positions of $n$ agents. Each facility has a
capacity limit, which describes the maximum amount of agents it can serve.
While the algorithmic aspects of this problem have been extensively studied in
the literature (see [3]), the mechanism design aspects of the problem have
only recently started to garner the attention of the scientific community. In
mechanism design, the Facility Location Problem and the $m$-CFLP are studied
under the assumption that each agent incurs a cost to access the facilities.
This cost is usually equal to the distance between the agent and the nearest
facility. Consequently, every agent prefers to have a facility located as
close to them as possible. In this case, if each agent is in charge of
reporting its own position on the line, optimizing a communal goal is subject
to manipulation driven by the agents’ self-interested behaviour. For this
reason, a key property that a mechanism should possess is truthfulness, which
ensures that no agent can gain an advantage by misrepresenting their private
information. This stringent property, however, forces the mechanism to produce
suboptimal locations, leading to an efficiency loss which is quantified by the
approximation ratio – that is the worst-case ratio between the objective
achieved by the mechanism and the optimal objective attainable [12]. Defining
efficient routines that forbid agents from manipulating is the defining issue
of mechanism design.

In this paper, we study the mechanism design aspects of the $m$-CFLP. In
particular, we focus on the framework presented in [2], and extend it to the
case in which we have $m$ facilities whose total capacity is lower than the
number of agents needing accommodation. In this framework, the mechanism
designer cannot force agents to use a specific facility, therefore the agents
compete in a First-Come-First-Served (FCFS) game to determine who is
accommodated by the facilities. The overall process therefore consists of two
parts. First, the agents report their position to a mechanism, which locates
the facilities. Second, the agents compete in the FCFS game to determine their
utilities. Notice that the Social Welfare achieved by the mechanism and the
utilities of the agents depend on the Nash Equilibria (NE) of the FCFS game
induced by the facilities’ placements. When we need to place a single
facility, that is $m=1$, the FCFS game has always a unique NE. When $m\geq 2$,
however, the NE of the FCFS game is no longer unique, posing a series of
challenges: if the NE is not unique, the agents’ utilities and thus the Social
Welfare achieved by a facility placement have different values depending on
the equilibrium of the FCFS game. As a consequence, the approximation ratio
also depends on the specific NE. Furthermore, the classic definition of the
truthful mechanism is no longer suitable for this problem as it does not
consider the different strategies that the agents may adopt during the FCFS
game. Addressing these issues are a major challenge for this problem, and thus
they were left as an open problem in [2].

A previous version of this paper appeared in the proceedings of UAI 2024. In
this improved version, we fully characterize the set of feasible percentile
mechanisms by studying the All-In-One and Side-By-Side mechanism and extend
our study to higher dimensional problems. Furthermore, we enhance our
numerical results by adding new metrics to study how well the best percentile
mechanisms perform when the agents are assumed to be sampled from a
probability distribution.

### Our Contribution

In this paper, we study the mechanism design aspects of the $m$-CFLP when the
total capacity of the facilities is less than the number of agents. In
particular, we extend the framework presented in [2] to encompass problems in
which there is more than one capacitated facility to locate. First, we show
that, regardless of how we locate the facilities, the FCFS game induced by the
location has at least one pure NE. We then present a notion of truthfulness
that accounts for the different strategies the agents can adopt during the
FCFS game, which we name absolute truthfulness. Finally, we introduce the
class of Equilibrium Stable (ES) mechanisms, i.e. mechanisms whose output
induces a FCFS game in which every NE achieves the same Social Welfare. Within
this framework, we study the percentile mechanisms [13]. We show that every
percentile mechanism is absolutely truthful and then fully characterize the
set of conditions under which a percentile mechanism is ES and compute its
approximation ratio.

First, we consider the case $m=2$ and show that an absolutely truthful and ES
percentile mechanism exists. In particular, we show that there are three
categories of ES percentile mechanisms:  (i) the All-In-One (AIO) mechanisms,
which place all the facilities at the same position, i.e. $y_{1}=y_{2}=x_{i}$;
(ii) the Side-By-Side (SBS) mechanisms, which places all the facilities at two
consecutive agents’ positions, i.e. $y_{1}=x_{i}$ and $y_{2}=x_{i+1}$; and
(iii) the Wide-Gap (WG) mechanisms, which places the facilities at two well-
separated positions, i.e. $y_{1}=x_{i}$ and $y_{2}=x_{j}$ where $i+1<j$.  We
then characterize the approximation ratio of a percentile mechanism as a
function of the facilities’ capacities and the vector inducing the percentile
mechanism. Consequentially, we determine the best percentile mechanism
tailored to the number of agents $n$ and the capacities of the facilities
$k_{1}$ and $k_{2}$. We show that the best approximation ratio that an ES
percentile mechanism placing two facilities can achieve is $\frac{4}{3}$,
which occurs when $k_{1}=k_{2}=k$ and $n\geq 3k$. We then consider the case in
which $m>2$. In this framework, a percentile mechanism that is ES and places
the facilities at more than two different locations might not exist. However,
when all the facilities have the same capacity and $n\geq(2k-1)m$ holds, there
exists a percentile mechanism whose approximation ratio is less than
$1+\frac{1}{m-1}$. This result has two interesting consequences:  (i) it shows
that, under suitable assumptions, the percentile mechanisms are asymptotically
optimal with respect to $m$ and  (ii) it highlights the differences between
the $m$-CFLP and the $m$-FLP. Indeed, in the classic framework, any percentile
mechanism has unbounded approximation ratio whenever $m>2$, [14, 15].  We then
extend our study to higher-dimensional problems. We demonstrate that when
agents are supported in a space that has two or more dimensions, the set ES
percentile mechanisms becomes even more restricted. Specifically, a percentile
mechanism is ES if and only if it places all the facilities at the same
location or distributes all the facilities between two different points.
Despite their differences, the worst-case analysis of these two types of
percentile mechanisms yield similar worst-case guarantees.

Lastly, we empirically study the behaviour of the best percentile mechanisms
under the assumption that the agents are distributed according to a
distribution $\mu$. We focus on the case in which we have two facilities,
since it is the case in which the gap between $1$ and the approximation ratio
of the best possible percentile mechanism is largest. We conduct our analysis
using two different metrics: the Bayesian approximation ratio, which compares
the expected cost of the mechanism and the expected optimal cost [16] and the
average-case ratio, which measures the average ratio between the mechanism
cost and the optimal cost [17]. From our analysis, we observe that, regardless
of the metric, when the agents follow a distribution, the performances of the
ES mechanism are close to optimal, regardless of the distribution.

### Related Work

The Mechanism Design aspects of the $m$-FLP were firstly studied in [18],
where the authors studied the problem of placing a set of facilities amongst
$n$ self-interested agents who want to a facility located as close as possible
to their real position. In this pioneering work, the authors studied the
problem of placing a facility that minimizes the sum of all the agents costs.
Following this seminal work, various mechanisms with constant approximation
ratios for placing one or two facilities on lines [19], trees [20, 21],
circles [22, 23], general graphs [24, 25], and metric spaces [26, 27] were
introduced. Crucially, all these positive results are limited to scenarios
where the number of agents is restricted or the number of facilities is either
$1$ or $2$ and the objective is to minimize the total agents costs. For a
comprehensive survey of the mechanism design aspects of the FLP, we refer to
[28].

The $m$-Capacitated Facility Location Problem ($m$-CFLP) is a variation of the
$m$-FLP in which each facility has a capacity limit. The first game
theoretical framework for the $m$-CFLP was presented in [29]. In this paper,
the authors studied the case in which there are at least two facilities whose
total capacity is enough to accommodate all the agents and the mechanism
designer has to decide where to place the facilities and which agent can use
them, so that the mechanism must elicit the positions and the agent-to-
facility matching. Following this initial study, in [30] the authors proposed
a more theoretical analysis of the problem, while in [31] it was shown that it
is possible to define deterministic mechanisms with bounded approximation
ratio when all the facilities have the same capacities and the number of
agents is equal to the total capacities of the facilities. Lastly, the
$m$-CFLP has been studied from a Bayesian mechanism design perspective in
[32].

In this paper, we consider an alternative game theoretical framework for the
$m$-CFLP, firstly introduced in [2]. This framework differs from the one
proposed in [29] for two main reasons:  (i) the total capacity of the
facilities is lower than the total number of agents, thus part of the agents
cannot be accommodated and  (ii) the mechanism designer does not enforce an
agent-to-facility assignment. Thus, after the positions of the facilities are
elicited, the agents compete in a First-Come-First-Served (FCFS) game to
access the facilities.  When $m=1$, the FCFS game is trivial as the agents
accommodated by the facility are the ones that are closer to the facility.
When $m>1$, designing mechanisms becomes much more complicated as, for
example, the Nash Equilibrium (NE) of the FCFS game is no longer unique. As a
consequence the utility of every agent depends on the specific NE of the game,
making the classic notion of trustfulness unfit for this framework.

##  2 Setting Statement

Let $\vec{x}\in[0,1]^{n}$ be the position of $n$ agents in the interval
$[0,1]$. We denote with $\vec{k}=(k_{1},\dots,k_{m})$ the $m$-dimensional
vector containing all the capacities of the $m$ facilities, so that $k_{j}$ is
the maximum number of agents that the $j$-th facility can accommodate. We
assume that the total capacity of the facilities is less than the number of
agents, hence $\sum_{j\in[m]}k_{j}<n$. In this case, a mechanism is a function
$M:[0,1]^{n}\to\mathbb{R}^{m}$ that maps a vector containing the agents’
reports to a facility location $\vec{y}=(y_{1},\dots,y_{m})$, where $y_{j}$ is
the position of the facility with capacity $k_{j}$. After the mechanism places
the facilities, agents compete in a First-Come-First-Served (FCFS) game to
access the facilities.

###  2.1 First-Come-First-Served Game

Let $\vec{y}=(y_{1},\dots,y_{m})$ be a vector containing the position of the
facilities to locate, that is the facility with capacity $k_{j}$ is located at
$y_{j}$. In what follows, we implicitly assume that there is an internal
ordering of the agents to break ties. Then, given $\vec{x}\in[0,1]^{n}$ the
vector containing the positions of the $n$ agents on the interval $[0,1]$, the
FCFS game induced by the facility location $\vec{y}$ is as follows:

  1. (i)

Each agent selects one of the facilities, so that the set of strategies of
each agent is the set $[m]:=\\{1,2,\dots,m\\}$. We denote with
$\vec{s}\in[m]^{n}$ the vector containing a set of pure strategies. For every
$\vec{s}$, we denote with $\mathcal{S}_{j}\subset[n]$ the set of agents that
selected strategy $j$.

  2. (ii)

Denoted with $d_{i,j}=|x_{i}-y_{j}|$ the distance of the agent $i$ from the
location of the facility they selected, we define
$T_{j}\subset\mathcal{S}_{j}$ as the set containing the agents in
$\mathcal{S}_{j}$ whose value $d_{i,j}$ is in among the $k_{j}$ lowest values.
Break ties according to the prefixed priority rule.

  3. (iii)

Finally, the utility of agent $i$ is defined as follows

$u_{i}(\vec{x},\vec{y};\vec{s})=\begin{cases}1-|x_{i}-y_{j}|\quad\quad\text{if}\quad
i\in T_{j}\\\
0\quad\quad\quad\quad\quad\quad\quad\text{otherwise}\end{cases}.$

First, we show that every FCFS game has at least one pure Nash Equilibrium
(NE).

######  Theorem 1.

For every $\vec{x}\in[0,1]^{n}$, every $\vec{y}\in[0,1]^{m}$, and every
capacity vector $\vec{k}$, the FCFS game associated with $\vec{x}$, $\vec{y}$,
and $\vec{k}$ admits at least one pure Nash Equilibrium.

######  Proof 2.2.

Let $\vec{x}$ be the vector containing the position of the agents and let
$\vec{y}$ be the position of the facilities. We denote with $k_{j}$ the
capacity of the facility located at $y_{j}$ for every $j\in[m]$. In what
follows, we assume that the set of agents has an inner ordering that decides
how to break ties. Let us define $\mathcal{D}$ the set containing all the
distances agents to facility, that is
$\mathcal{D}=\\{|x_{i}-y_{j}|\\}_{i\in[n],j\in[m]}$.

Let $\vec{c},\vec{s}\in\mathbb{R}^{m}$ be two null vectors, that is
$c_{j}=s_{j}=0$ for every $j\in[m]$. We now construct a Nash Equilibrium
through the following iterative routine.

  1. 1.

Let $d$ be the minimum of the elements in $\mathcal{D}$. Up to a tie, there
exist a couple $(i_{1},j_{1})\in[n]\times[m]$ such that
$d=|x_{i_{1}}-y_{j_{1}}|$. We set $c_{j_{1}}=c_{j_{1}}+1$, $s_{i_{1}}=j_{1}$,
and remove all the elements of the form $|x_{i_{1}}-y_{j}|$ from
$\mathcal{D}$. Then, if $c_{j_{1}}=k_{j_{1}}$, we remove from $\mathcal{D}$
all the elements of the form $|x_{i}-y_{j_{1}}|$.

  2. 2.

We repeat the routine of point $(1)$ until $\mathcal{D}$ becomes empty.

  3. 3.

If $s_{i}=0$ for some $i\in[n]$, we set them to be equal to $1$.

Since $\mathcal{D}$ is discrete, the routine terminates in finite number of
iterations and the output is a vector containing a set of agents’ pure
strategies.

We now show that the output of the routine $\vec{s}$ is a Nash Equilibrium by
proving that no agent $i$ can increase its utility by deviating from playing
$s_{i}$. Toward a contradiction, assume that an agent $i$ can increase its
utility by playing $s_{i}^{\prime}$ rather than $s_{i}$. By definition of
$s_{i}$, we have that if $|x_{i}-y_{s_{i}^{\prime}}|<|x_{i}-y_{s_{i}}|$, then
there are at least $k_{s_{i}^{\prime}}$ agents that are closer to
$y_{s_{i}^{\prime}}$ or that have a higher priority order than agent $i$ and
play strategy $s_{i}^{\prime}$. Thus the agent cannot gain a benefit from
deviating from $s_{i}$, which proves that $\vec{s}$ is a pure Nash
Equilibrium.

When the vector $\vec{k}$ is clear from the context, we denote the set of all
the pure Nash Equilibria with $NE(\vec{x},\vec{y})$. The Social Welfare (SW)
of the facility location $\vec{y}$ according to $\gamma\in
NE(\vec{x},\vec{y})$ is defined as the sum of all the agents’ utilities, that
is $SW_{\gamma}(\vec{x},\vec{y})=\sum_{i\in[n]}u_{i}(\vec{x},\vec{y};\gamma)$.
Notice that when $m=1$, the Nash Equilibrium of the FCFS game is unique, since
every agent can play only one strategy, hence the SW of the game is well
defined. This is no longer true when we need to place more than one facility.
In this case, the SW of the game changes depending on the specific Nash
Equilibrium.

######  Example 2.3.

Let us consider the case in which we have 5 agents and need to place two
facilities with $k_{1}=k_{2}=2$. Let
$\vec{x}:=(0,0.3,0.4,0.5,0.9)\in[0,1]^{5}$ be the vector containing the
agents’ positions. If $\vec{y}=(0.3,0.5)$, both $\gamma_{1}=(1,1,2,2,2)$ and
$\gamma_{2}=(1,1,1,2,2)$ are pure NE of the FCFS game. However, the SW of the
FCFS game depends on the specific NE, indeed
$SW_{\gamma_{1}}(\vec{x},\vec{y})=3.6>3.5=SW_{\gamma_{2}}(\vec{x},\vec{y})$.
Moreover, the utility the agent located at $0.9$ is zero or $0.6$ depending on
the equilibrium.

(a) The Nash Equilibrium $\gamma_{1}$ from Example 2.3.

(b) The Nash Equilibrium $\gamma_{2}$ from Example 2.3.

Figure 1: The two Nash Equilibria described in Example 2.3. The circles
represents the agents, the green squares the facilities and the red arrows the
strategies played by the agents getting a non-null utility.

Lastly, we define the optimal SW achievable on the instance $\vec{x}$ as

$SW_{opt}(\vec{x})=\sup_{\vec{y}\in[0,1]^{m}}\sup_{\gamma\in
NE(\vec{x},\vec{y})}SW_{\gamma}(\vec{x},\vec{y}).$ (1)

###  2.2 Mechanism Design Aspects of the problem

A key property that a mechanism $M$ must possess is truthfulness, which
ensures that no agent can increase their utility by misreporting their
position. As shown in Example 2.3, the utility of an agent depends on the
other agents’ strategies. For this reason, we employ a stronger notion of
truthfulness that keeps track of the different strategies that agents can play
in the FCFS game.

######  Definition 2.4.

A mechanism $M$ is absolutely truthful if no agent increases its utility by
misreporting, regardless of the strategies played by other agents. More
formally, for every agent $i\in[n]$, $\vec{x}\in[0,1]^{n}$, and
$\vec{s}_{-i}\in[m]^{n-1}$, we have

$\max_{s_{i}\in[m]}u_{i}(\vec{x},M(\vec{x});s_{i},\vec{s}_{-i})\geq\max_{s_{i}^{\prime}\in[m]}u_{i}(\vec{x},M(\vec{x}^{\prime});s_{i}^{\prime},\vec{s}_{-i}),$

where  (i) $\vec{x}^{\prime}=(x_{i}^{\prime},\vec{x}_{-i})$for every
$x_{i}^{\prime}\in[0,1]$,  (ii) $\vec{x}_{-i}$and $\vec{s}_{-i}$, are the
vectors containing the positions and strategies of the other $n-1$ agents,
respectively.

In general, the FCFS game induced by the output of a mechanism has multiple
NE, hence the SW of the mechanism is not unique. For this reason, we introduce
the notion of Equilibrium Stable mechanism.

######  Definition 2.5.

An absolutely truthful mechanism $M$ is said Equilibrium Stable (ES) if, for
every $\vec{x}$, we have that

$SW(\vec{x},M(\vec{x});\gamma)=SW(\vec{x},M(\vec{x});\gamma^{\prime})$

for every Nash Equilibria $\gamma,\gamma^{\prime}\in NE(\vec{x},M(\vec{x}))$.

An absolutely truthful mechanism is not necessarily ES. For example, consider
the mechanism that places the facilities at $(0.3,0.5)$ regardless of the
agents’ reports. No agent can manipulate the outcome of the mechanism by
changing their reports, however, going back to Example 2.3, we have that the
mechanism induces two NE with different SW on the instance
$(0,0.3,0.4,0.5,0.9)$. Finally, since we are considering the utilities of the
agents, we define the approximation ratio of an ES mechanism as the worst-case
ratio of the optimal SW and the SW achieved by the mechanism.

######  Definition 2.6.

Let $M$ be an absolutely truthful and ES mechanism. We define the
approximation ratio of $M$ as

$ar(M)=\sup_{\vec{x}\in[0,1]^{n}}\frac{SW_{opt}(\vec{x})}{SW_{M}(\vec{x})},$

where $SW_{M}$ is the SW value achieved by $M$ on any of the NE in
$NE(\vec{x},M(\vec{x}))$ and $SW_{opt}$ is defined in (1).

##  3 Absolutely Truthful and Equilibrium Stable Mechanisms to place more than
one facility

In this section, we study the class of percentile mechanisms and characterize
under which conditions a percentile mechanism is absolutely truthful and ES.

######  Definition 3.7 (Percentile Mechanism, [13]).

Given a percentile vector $\vec{v}\in[0,1]^{m}$, the routine of the percentile
vector associated with $\vec{v}$, namely $\mathcal{PM}_{\vec{v}}$, is as
follows:  (i) The mechanism designer collects all the reports of the agents
$\\{x_{1},x_{2},\dots,x_{n}\\}$ and sorts them in non-decreasing order, so
that $x_{i}\leq x_{i+1}$.  (ii) The mechanism then places the $m$ facilities
at the positions $y_{j}=x_{i_{j}}$, where $i_{j}=\lfloor(n-1)v_{j}\rfloor+1$
for every $j\in[m]$.

All percentile mechanisms are absolutely truthful.

######  Theorem 3.8.

$\mathcal{PM}_{\vec{v}}$ is absolutely truthful for every $\vec{v}$.

######  Proof 3.9.

Toward a contradiction, let $\mathcal{PM}_{\vec{v}}$ be a percentile vector
such that, on instance $\vec{x}\in[0,1]^{m}$, the agent whose real position is
$x_{i}$ can manipulate by reporting $x_{i}^{\prime}\in[0,1]$. Let $\vec{y}$ be
the output of $\mathcal{PM}_{\vec{v}}$ in the truthful input and let
$\vec{y}\,^{\prime}$ be the output of $\mathcal{PM}_{\vec{v}}$ after the agent
manipulation. If $x_{i}^{\prime}\leq x_{i}$, we have that the position of the
facilities that $\mathcal{PM}_{\vec{v}}$ places on the left of $x_{i}$ move
further to the left of $x_{i}$. Each facility that was placed by
$\mathcal{PM}_{\vec{v}}$ on the right of $x_{i}$ does not change position.
Thus it holds $|x_{i}-y_{j}|\leq|x_{i}-y_{j}^{\prime}|$ for every $j\in[m]$.
Finally, let $\vec{s}_{-i}\in[m]^{n-1}$ be a vector containing the strategies
of the other agents and let us define with $F_{i}(\vec{z})\subset[m]$ the set
of strategies that give a non-null utility to the agent at $x_{i}$ when the
facilities are located at $\vec{z}$. Since
$|x_{i}-y_{j}|\leq|x_{i}-y_{j}^{\prime}|$ for every $j\in[m]$, we have that
$F_{i}(\vec{y}^{\prime})\subset F_{i}(\vec{y})$. To conclude, notice that for
every $s_{i}\in F_{i}(\vec{y}^{\prime})$ the utility of the manipulative agent
decreases, as all the distances from the facilities have increased after the
manipulation, which concludes the proof.

Unfortunately, not every percentile mechanism is ES: consider the situation
represented in Example 2.3: the position of the facilities are the output of
the $\mathcal{PM}_{\vec{v}}$ with $\vec{v}=(0.25,0.75)$, however, different NE
induce different SW values. In what follows, we characterize the set of
percentile mechanisms that are ES and study their approximation ratio. Owing
to this characterization, we identify the ES percentile mechanism with the
lowest approximation ratio. For the sake of simplicity, we start our
discussion from the case in which $m=2$.

###  3.1 Mechanisms to Place Two Facilities

First, we study the case in which we place two facilities. We denote with
$k_{1}$ and $k_{2}$ the capacities of the two facilities and assume that
$k_{1}+k_{2}<n$. Without loss of generality, let $k_{1}\geq k_{2}$. We show
that each ES percentile mechanism belong to one of the following three
categories:  (i) the All-In-One (AIO) mechanisms, that place all the
facilities at the same spot, that is $y_{1}=y_{2}$;  (ii) the Side-By-Side
(SBS) mechanisms, that places the facilities at two adjacent positions, that
is $y_{1}=x_{i}$ and $y_{2}=x_{i+1}$ where $i\in[n-1]$; and  (iii) the Wide-
Gap (WG) mechanism, which places the facilities at two agents positions that
are well-separated, i.e. $y_{1}=x_{i}$ and $y_{2}=x_{j}$ where $i+1<j$.
Notice that each percentile mechanism belongs to exactly one of these three
sub-classes, making the partition complete.

We start from the Wide-Gap mechanisms, as they are the more interesting class
of ES percentile mechanisms.

####  3.1.1 Wide-Gap mechanisms

First, we show that for every $k_{1}$ and $k_{2}$, there exists at least a WG
percentile mechanism that is ES. Moreover, for every $k_{1}$ and $k_{2}$, we
compute the approximation ratio of every ES percentile mechanism and
characterize the mechanism achieving the lowest approximation ratio. Notice
that by definition of WG mechanisms, and without loss of generality, we assume
that $v_{1}<v_{2}$. Thus the facility with the highest capacity is always
located on the left of the less capacious facility. The case in which
$v_{2}<v_{1}$ is symmetric and thus it does not need to be considered.

######  Theorem 3.10.

Let $\vec{v}=(v_{1},v_{2})\in[0,1]^{2}$ be a percentile vector and let
$\mathcal{PM}_{\vec{v}}$ be its associated percentile mechanism. Let
$k_{1},k_{2}\in\mathbb{N}$ and let $n\in\mathbb{N}$ be such that
$k_{1}+k_{2}<n$ and $\lfloor v_{2}(n-1)\rfloor-\lfloor v_{1}(n-1)\rfloor>1$.
Then, we have that $\mathcal{PM}_{\vec{v}}$ is ES if and only if

$\lfloor v_{2}(n-1)\rfloor-\lfloor v_{1}(n-1)\rfloor\geq k_{2}+k_{1}-1.$ (2)

######  Proof 3.11.

First, we show that condition (2) is sufficient to make a percentile mechanism
ES. If $\vec{v}$ satisfies (2), there are always $k_{1}+k_{2}$ agents such
that $y_{1}\leq x_{i}\leq y_{2}$, where $y_{1}$ and $y_{2}$ are the two
facility locations returned by the mechanism. Notice that if $y_{1}=y_{2}$,
then the two facilities share the position with $k_{1}+k_{2}$ agents, hence
the SW of any NE is equal to $k_{1}+k_{2}$. Assume now that $y_{1}<y_{2}$. Let
us then define $r_{j}$ the minimal values such that
$B_{r_{j}}(y_{j})\cap\\{x_{i}\\}_{i\in[n]}$ has cardinality larger or equal to
$k_{j}$111Here $B_{r}(y)$ denotes the ball centered in $y$ of radius $r$..
Since there are at least $k_{1}+k_{2}$ agents in $[y_{1},y_{2}]$, we have that
$r_{1}+r_{2}\leq|y_{1}-y_{2}|$. According to every NE, agents that do not
belong to either $B_{r_{1}}(y_{1})$ or $B_{r_{2}}(y_{2})$ have utility equal
to $0$. Indeed, if $\vec{s}\in NE(\vec{x},\mathcal{PM}_{\vec{v}}(\vec{c}))$ is
such that $x_{i}\notin B_{r_{1}}(y_{1})\cap B_{r_{2}}(y_{2})$ gets
accommodated by $y_{1}$, we would have that at least one agent $x_{j}\in
B_{r_{1}}(y_{1})$ has null utility, hence $s_{j}=2$. However, if agent $x_{j}$
can increase its utility by changing its strategy to $s_{j}=1$, hence
$\vec{s}\notin NE(\vec{x},\mathcal{PM}_{\vec{v}}(\vec{x}))$, which is a
contradiction. By the same argument, we infer that every agent
$x_{i}\in(y_{j}-r_{j},y_{j}+r_{j})$ attains utility $1-|x_{i}-y_{j}|$
according to every NE. Finally, we observe that the set of agents such that
$|x_{i}-y_{j}|=r_{j}$ that have non null utility may change according to the
specific NE, but the total utility of these agents does not change. Thus
condition (2) is sufficient to ensure $\mathcal{PM}_{\vec{v}}$ is ES.

Lastly, we show that the condition is necessary. Let us assume that $\vec{v}$
does not satisfy the condition (2). For the sake of simplicity, let us denote
with $i_{1}=\lfloor v_{1}(n-1)\rfloor+1$ and $i_{2}=\lfloor
v_{2}(n-1)\rfloor+1$. Let us consider the following instance
$x_{1}=\dots=x_{i_{1}-1}=0$, $x_{i_{1}}=0.4$,
$x_{i_{1}+1}=\dots=x_{i_{2}-1}=0.5$, $x_{i_{2}}=0.6$ and $x_{j}=0.9$ for all
the other indexes $j>i_{2}$. Notice that, since $\lfloor
v_{2}(n-1)\rfloor-\lfloor v_{1}(n-1)\rfloor>1$, there is at least one agent
located at $0.5$. Following the same argument used in Example 2.3, we can show
that, depending on the strategy played by the agents at $0.5$, the Social
Welfare of the mechanism changes.

Next, we characterize the approximation ratio of every WG percentile
mechanism. Given a percentile vector $\vec{v}\in[0,1]^{2}$ that satisfies
condition (2), we denote with $i_{1}=\lfloor v_{1}(n-1)\rfloor+1$ and
$i_{2}=\lfloor v_{2}(n-1)\rfloor+1$. Therefore that the mechanism places the
facility with capacity $k_{1}$ at $x_{i_{1}}$ and the facility with capacity
$k_{2}$ at $x_{i_{2}}$.

######  Theorem 3.12.

Given $n$, $k_{1}$, and $k_{2}$, let $\mathcal{PM}_{\vec{v}}$ an ES percentile
mechanism. Then, if $i_{1}\geq\lfloor\frac{k_{1}+1}{2}\rfloor$, we have that

$ar(\mathcal{PM}_{\vec{v}})=\frac{k_{1}+k_{2}}{\min\\{k_{1}+(n-i_{2})+1,\frac{k_{1}+1}{2}+k_{2}\\}}$
(3)

If $i_{1}<\lfloor\frac{k_{1}+1}{2}\rfloor$ and
$i_{2}<n-\lfloor\frac{k_{2}+1}{2}\rfloor$, we have

$ar(\mathcal{PM}_{\vec{v}})=\frac{k_{1}+k_{2}}{\min\\{k_{1}+(n-i_{2})+1,i_{1}+k_{2}\\}}.$

Otherwise, we have

$ar(\mathcal{PM}_{\vec{v}})=\frac{k_{1}+k_{2}}{\min\\{k_{1}+\frac{k_{2}+1}{2},k_{2}+i_{1}\\}}.$

######  Proof 3.13.

Our argument is as follows: we show that the worst instance for the mechanism
is either  (i) $x_{i}=0$if $i\in\\{1,\dots,i_{1}-1\\}$,
$x_{i_{1}}=\frac{1}{2}$, and $x_{i}=1$ otherwise, or  (ii) $x_{i}=0$if
$i\in\\{1,\dots,i_{2}-1\\}$ and $x_{i}=1$ otherwise.  Notice that in both
cases, the optimal SW is equal to $k_{1}+k_{2}$, which is the maximum SW
attainable. Let us show that the worst-case instance has the form described in
(i) or (ii). Owing to Theorem 3.10, we have that there are at least
$k_{1}+k_{2}$ agents in the interval $[y_{1},y_{2}]$, hence the agents that
are accommodated by the facility at $y_{j}$ are, up to ties, the $k_{j}$
agents that are closer to $y_{j}$. Since
$i_{1}\geq\lfloor\frac{k_{1}+1}{2}\rfloor$, the total utility of the agent
accommodated by the facility at $y_{1}$ is minimized when all the agents
accommodated by $y_{1}$ are all at the same distance from $y_{1}$, that is
$|x_{i_{1}-1}-y_{1}|=|x_{i_{1}+1}-y_{1}|$. Given $\lambda\in[0,\frac{1}{2}]$,
let us consider the following instance: $x_{1}=\dots=x_{i_{1}-1}=0$,
$x_{i_{1}}=\lambda$, $x_{i_{1}+1}=\dots=x_{i_{2}-1}=2\lambda$. Let us now
consider the facility located at $y_{2}$. By the same argument, we have that
if $n-i_{2}$ is larger than $\lfloor\frac{k_{2}+1}{2}\rfloor$, then, for every
$\lambda$, the position $y_{2}$ that minimizes the utility is
$\frac{1}{2}+\lambda$. In this case, the cost of the mechanism is
$2+(1-\lambda)(k_{1}-1)+(\frac{1}{2}+\lambda)(k_{2}-1)$. Since $k_{1}\geq
k_{2}$, we have that the minimum SW is achieved when $\lambda=\frac{1}{2}$,
thus all the agents on the right of $x_{i_{1}}$ are located at $1$, all the
agents on the left are located at $0$ and $x_{i_{1}}=\frac{1}{2}$. In this
case $SW_{\mathcal{PM}_{\vec{v}}}(\vec{x})=\frac{k_{1}+1}{2}+k_{2}$, while
$SW_{opt}(\vec{x})=k_{1}+k_{2}$, which is the maximum utility achievable and
is attained by placing both facilities at $1$. Consider now the case
$n-i_{2}<\lfloor\frac{k_{2}+1}{2}\rfloor$. In this case, for every $\lambda$,
the worst position for $y_{2}$ is $1$, hence the SW of the mechanism is
$n-i_{2}+2+(1-\lambda)(k_{1}-1)+2\lambda(k_{2}-n+i_{2}-1)$, therefore the SW
is minimized when $\lambda=0$ or $\lambda=\frac{1}{2}$. In particular, we have
that worst Social Welfare attainable by the mechanism is

$\min\\{n-i_{2}+k_{1}+1),\frac{1}{2}(k_{1}+1)+k_{2})\\}.$

Since $SW_{opt}(\vec{x})=k_{1}+k_{2}$, we conclude the first part of the
proof.

We now consider the case in which $i_{1}<\lfloor\frac{k_{1}+1}{2}\rfloor$.
First, we consider the case in which
$i_{2}<n-\lfloor\frac{k_{2}+1}{2}\rfloor$. By the same argument used to prove
the case in which $i_{1}\geq\lfloor\frac{k_{1}+1}{2}\rfloor$, we have that the
worst-case instance in this case is

$x_{i}=\begin{cases}x_{i}=0\quad\quad\text{if}\quad i=1,\dots,i_{1},\\\
x_{i}=\lambda\quad\quad\text{if}\quad i=i_{1}+1,\dots,i_{2}-1,\\\
x_{i}=1\quad\quad\text{otherwise.}\end{cases}$

for some $\lambda\in[0,1]$, since the SW of the mechanism is minimized when
the $i_{1}$-th and $i_{2}$-th agents are at the extremes of the interval. For
any value of $\lambda$, the SW of the mechanism is

$SW(\vec{x})=i_{1}+(n-i_{2})+(1-\lambda)(k_{1}-i_{1})+\lambda(k_{2}-(n-i_{2})).$

Since $SW(\vec{x})$ is linear in $\lambda$, we have that the minimum is
achieved at either $\lambda=0$ or $\lambda=1$. Thus the minimal SW achievable
is

$\min\\{k_{1}+(n-i_{2}),k_{2}+i_{1}\\}.$

Since in both cases we have that the optimal SW is $k_{1}+k_{2}$, we conclude
the thesis.

Lastly, we consider the case in which
$n-i_{2}\geq\lfloor\frac{k_{2}+1}{2}\rfloor$ and
$i_{1}<\lfloor\frac{k_{1}+1}{2}\rfloor$. In this case, the worst-case instance
places the first $i_{1}$ agents at $0$, therefore the instances we need to
consider are

$x_{i}=\begin{cases}x_{i}=0\quad\quad\text{if}\quad i=1,\dots,i_{1},\\\
x_{i}=\lambda\quad\quad\text{if}\quad i=i_{1}+1,\dots,i_{2}-1,\\\
x_{i_{2}}=\frac{\lambda+1}{2}\\\
x_{i}=1\quad\quad\text{otherwise.}\end{cases}$

The SW induced by the mechanism is then

$SW(\vec{x})=i_{1}+1+(1-\lambda)(k_{1}-i_{1})+\frac{1+\lambda}{2}(k_{2}-1).$

Again, since the SW is linear in $\lambda$, we have that the minimium is
attained at either $\lambda=0$ or $\lambda=1$. Then the minimum SW achievable
by the mechanism is

$\min\Big{\\{}k_{1}+\frac{(k_{2}+1)}{2},k_{2}+i_{1}\Big{\\}}.$

To conclude notice that in both cases, the SW attained by the optimal solution
is $k_{1}+k_{2}$.

Consequentially, we characterize the best ES percentile mechanisms given any
$2$-dimensional vector $\vec{k}$. In particular, we show that the
approximation of the best percentile mechanism decreases as
$\Delta:=n-(k_{1}+k_{2})$ increases.

######  Theorem 3.14.

Given $n$ and $\vec{k}$, let us define $\Delta=n-(k_{1}+k_{2})$, then we have
that the ES WG percentile mechanism that achieves the lowest approximation
ratio is induced by the percentile vector
$\vec{v}=(\frac{i_{1}}{n},\frac{i_{2}}{n})$, where $i_{1}$ and $i_{2}$ are as
follows

  1. (i)

$i_{1}=\lceil\frac{k_{1}}{2}\rceil$ and
$i_{2}=n-\lfloor\frac{k_{2}}{2}\rfloor$ if
$\Delta\geq\lceil\frac{k_{1}+k_{2}}{2}\rceil$, in which case
$ar(\mathcal{PM}_{\vec{v}})=\frac{k_{1}+k_{2}}{\frac{k_{1}+1}{2}+k_{2}}$,

  2. (ii)

$i_{1}=k_{1}-k_{2}+\alpha$ and $i_{2}=n-\alpha$, where
$\alpha=\lceil\frac{\Delta-(k_{1}-k_{2})}{2}\rceil$, if
$k_{1}-k_{2}\leq\Delta\leq\lfloor\frac{k_{1}+k_{2}}{2}\rfloor+1$, in which
case $ar(\mathcal{PM}_{\vec{v}})=\frac{k_{1}+k_{2}}{i_{1}+k_{2}}$, and

  3. (iii)

$i_{1}=\Delta+1$ and $i_{2}=n$ otherwise, in which case
$ar(\mathcal{PM}_{\vec{v}})=\frac{k_{1}+k_{2}}{\Delta+k_{2}+1}$.

######  Proof 3.15.

When $\Delta\geq\lceil\frac{k_{1}+k_{2}}{2}\rceil$, the indexes
$i_{1}=\lceil\frac{k_{1}}{2}\rceil$ and
$i_{2}=n-\lfloor\frac{k_{2}}{2}\rfloor$ are well defined. Owing to Theorem
3.10 and by definition of $\Delta$, we have that $\mathcal{PM}_{\vec{v}}$ is
ES. Finally, from Theorem 3.12, we infer that

$ar(\mathcal{PM}_{\vec{v}})=\frac{k_{1}+k_{2}}{\frac{k_{1}+1}{2}+k_{2}},$

which is the smallest approximation ratio achievable by an ES WG percentile
mechanism.

Let us consider the case (ii), that is
$k_{1}-k_{2}\leq\Delta\leq\lfloor\frac{k_{1}+k_{2}}{2}\rfloor+1$. Owing to
Theorem 3.12, we retrieve the best values $i_{1}$ and $i_{2}$ by maximizing
the quantity

$\min\\{k_{1}+(n-i_{2}),i_{1}+k_{2}\\}.$

Thus, we look for $i_{1}$ and $i_{2}$ such that

$k_{1}+(n-i_{2})=i_{1}+k_{2},$

subject to the constraint

$n-i_{2}+i_{1}=\Delta,$

since, owing to Theorem 2, $k_{1}+k_{2}$ agents must lay between $x_{i_{1}}$
and $x_{i_{2}}$. By a simple computation, we have that

$n-i_{2}=\frac{k_{2}-k_{1}+\Delta}{2},$

thus
$i_{1}=\frac{\Delta-(k_{2}-k_{1})}{2}=k_{1}-k_{2}+\frac{\Delta-(k_{2}-k_{1})}{2}$
and $i_{2}=n-\frac{k_{2}-k_{1}+\Delta}{2}$, which concludes the proof of case
(ii).

Lastly, we consider case (iii). In this case, we have that
$\Delta<k_{1}-k_{2}$, thus we have

$k_{2}+i_{1}-k_{1}-(n-i_{2})=i_{2}-n+i_{1}+k_{2}-k_{1}\leq\Delta+k_{2}-k_{1}<0,$

since $i_{2}-n+i_{1}<n-i_{2}+i_{1}\leq\Delta$. Thus the minimum SW attainable
by the mechanism is $i_{1}+k_{2}$, therefore, to maximize the minimum
achievable SW, we need to set $i_{1}=\Delta$ and $i_{2}=n$, which concludes
the proof.

Notice that the lowest approximation ratio is achieved when
$\Delta\geq\lceil\frac{k_{1}+k_{2}}{2}\rceil$. Moreover, notice that the
smaller the gap between $k_{1}$ and $k_{2}$, that is $k_{1}-k_{2}$, the lower
the approximation ratio of the best percentile mechanism. In particular, the
lowest approximation ratio is attained when $k_{1}=k_{2}$ and $n\geq 3k$, in
which case there exists a percentile mechanism whose approximation ratio is
$\frac{4}{3+\frac{1}{k}}\sim\frac{4}{3}$.

####  3.1.2 The All-In-One and Side-By-Side mechanisms

We conclude our study by considering the AIO and the SBS mechanisms. Unlike
the WG mechanisms, each AIO and SBS is ES. We consider the AIO mechanisms
first. Since all the AIO mechanisms place the facilities at the same position,
every Nash Equilibrium induced by the facility placement achieves the same
Social Welfare. Moreover, it is easy to see that the best AIO mechanism places
the both the facilities at the median agent. Indeed, we have the following.

######  Theorem 3.16.

The best AIO mechanism places all the facilities at the median agent.
Moreover, denoted with $M$ the mechanism that places both facility at the
median agent, we have that

$ar(M)=\begin{cases}\frac{2k_{2}+2\lfloor\frac{n}{2}\rfloor+1}{k_{1}+k_{2}+1}\quad\quad\text{if}\;\;k_{1}\geq\lceil\frac{n}{2}\rceil\\\
\\\
\frac{2(k_{2}+k_{1})}{k_{1}+k_{2}+1}\quad\quad\quad\>\;\text{otherwise}.\end{cases}$
(4)

######  Proof 3.17.

We prove this theorem as it follows: first, we compute the approximation ratio
of a generic AIO mechanism and then show that the approximation ratio is
minimized when the AIO mechanism places both facility at a median agent. Let
then $M$ be an AIO mechanism such that $y_{1}=y_{2}=x_{r}$ where $r\in[n]$.
Without loss of generality, we assume $r\leq\lfloor\frac{n+1}{2}\rfloor$.

We notice that, given an instance $\vec{x}$, it is possible to increase the
optimal Social Welfare and decrease the Social Welfare of the mechanism by
moving all the agents that are not the $r$-th agent to either $0$ or $1$. We
therefore restrict our attention to instances such that
$x_{1}=\dots=x_{r-1}=0$, $x_{r}=\lambda\in[0,1]$, and $x_{j}=1$ otherwise.
Since we have that $r\leq\lfloor\frac{n}{2}\rfloor$, we have that the worst-
case instance happens when $\lambda\in[0,\frac{1}{2}]$, thus the Social
Welfare achieved by the mechanism can be computed explicitly

$SW_{M}(\vec{x})=1+(1-\lambda)\min\\{r-1,k_{1}+k_{2}-1\\}+\lambda(k_{1}+k_{2}-\min\\{k_{1}+k_{2},r\\}).$

To complete the proof we need to compute the optimal SW achievable on these
instances. Since $r\leq\lfloor\frac{n}{2}\rfloor$ and $k_{1}\geq k_{2}$, we
have that the optimal solution either places the two facilities at $1$, in
which case the SW is equal to

$SW_{opt,1}=\min\\{n-r+\lambda,k_{1}+k_{2}\\},$

or places the facility with capacity $k_{2}$ at $0$ and the facility with
capacity $k_{1}$ at $1$, in which case the optimal SW is equal to

$SW_{opt,2}=\min\\{r-\lambda,k_{2}\\}+\min\\{n-r+\lambda,k_{1}\\}.$

So that $SW_{opt}=\max\\{SW_{opt,1},SW_{opt,2}\\}$ and hence

$ar(M)=\max_{\lambda\in[0,\frac{1}{2}]}\Bigg{\\{}\frac{\max\big{\\{}\min\\{n-r+\lambda,k_{1}+k_{2}\\},\min\\{r-\lambda,k_{2}\\}+\min\\{n-r+\lambda,k_{1}\\}\big{\\}}}{1+(1-\lambda)\min\\{r-1,k_{1}+k_{2}-1\\}+\lambda(k_{1}+k_{2}-\min\\{k_{1}+k_{2},r\\})}\Bigg{\\}}.$

We notice that this quantity is minimized when $r=\lceil\frac{n}{2}\rceil$,
which proves that the best AIO mechanism is the one placing all the facilities
at the median agent.

Let us now compute the approximation ratio of the median mechanism, that is
$r=\lceil\frac{n}{2}\rceil$. Moreover, since $SW_{opt}\geq SW_{M}$, $k_{1}\geq
k_{1}$, and both $SW_{M}$ and $SW_{opt}$ are piecewise linear functions with
respect to $\lambda$, we have that the maximum defining $ar(M)$ is attained
when wither $\lambda=0$ or $\frac{1}{2}$. We then conclude that

$ar(M)=\max_{\lambda\in\\{0,\frac{1}{2}\\}}\Bigg{\\{}\frac{\max\big{\\{}\min\\{\lfloor\frac{n}{2}\rfloor+\lambda,k_{1}+k_{2}\\},k_{2}+\min\\{\lfloor\frac{n}{2}\rfloor+\lambda,k_{1}\\}\big{\\}}}{\lambda+(1-\lambda)\min\\{\lfloor\frac{n}{2}\rfloor,k_{1}+k_{2}\\}+\lambda(k_{1}+k_{2}-\min\\{k_{1}+k_{2},\lceil\frac{n}{2}\rceil\\})}\Bigg{\\}},$

where we used the fact that $k_{2}\leq\lceil\frac{n}{2}\rceil$. Which allows
us to conclude (4) and thus the proof.

We then consider the SBS mechanisms. As for the AIO mechanisms, every SBS
mechanism is ES.

######  Theorem 3.18.

Each SBS mechanism is ES.

######  Proof 3.19.

Let $PM$ be an SBS percentile mechanism and let $i$ be the parameter such that
$y_{1}=x_{i}$ and $y_{2}=x_{i+1}$. Without loss of generality, we assume that
the facility at $y_{1}$ has capacity $k_{1}$ and that the facility at $y_{2}$
has capacity $k_{2}$. Let $\vec{x}$ be the vector containing the reports of
$n$ agents, we now show that every NE equilibrium induced by placing the
facilities at $y_{1}=x_{i}$ and $y_{2}=x_{i+1}$ achieves the same SW. Notice
that if $y_{1}=y_{2}$, there is nothing to prove, we then consider the case in
which $y_{1}<y_{2}$.

Let us now define

$A_{1}:=\\{x_{i}\leq y_{1}\\}\quad\quad\text{and}\quad\quad
A_{1}:=\\{x_{i}\geq y_{2}\\}.$ (5)

Notice that $A_{1}\cup A_{2}=\\{x_{i}\\}_{i\in[n]}$ and $A_{1}\cap
A_{2}=\emptyset$. By definition, every agent in $A_{1}$ is strictly closer to
$y_{1}$ and every agent in $A_{2}$ is strictly closer in $y_{2}$. We have
three cases:  (i) $|A_{1}|\leq k_{1}$and $|A_{2}|\leq k_{2}$;  (ii)
$|A_{1}|>k_{1}$and $|A_{2}|\leq k_{2}$; and  (iii) $|A_{1}|\leq k_{1}$and
$|A_{2}|>k_{2}$.

Case (i): In this case, we have that in every NE, the agents getting access to
the facilities are, up to breaking ties, the $k_{1}$ rightmost agents in
$A_{1}$ and the $k_{2}$ leftmost agents in $A_{2}$. In particular the SW
remains constant across all the possible Nash Equilibria.

Case (ii): In this case, we have that in every NE, the agents getting access
to the facilities are, up to breaking ties, the $a_{1}:=|A_{1}|$ agents in
$A_{1}$ and the $k_{2}+k_{1}-a_{1}$ leftmost agents in $A_{2}$. Notice that,
up to ties, the $k_{2}$ leftmost agents in $A_{2}$ are served by the facility
at $y_{2}$, while the other $k_{1}-a_{2}$ are served by the facility $y_{1}$.
In particular the SW remains constant across all the possible Nash Equilibria.

Case (iii): This case follows from an argument similar to the one used to
handle Case (ii). Thus we conclude the proof.

Lastly, we notice that the approximation ratio of any SBS mechanism can be
obtained by following the same argument used to prove Theorem 3.16. Indeed, it
is easy to see that the worst-case instance of the SBS places the two
facilities at the same position, i.e. $y_{1}=y_{2}$, as otherwise it would be
possible to increase the ratio by overlapping the two facilities. For this
reason, the worst-case guarantees of the SBS mechanisms are similar to the
worst-case guarantees of the AIO mechanisms, hence the SBS mechanism that
achieves the lowest approximation ratio is the one placing facilities at
$x_{\lfloor\frac{n}{2}\rfloor}$ and $x_{\lfloor\frac{n+1}{2}\rfloor}$.

###  3.2 Beyond two facilities

We now extend our study to the case in which we want to place $m>2$
facilities. For the sake of simplicity, we consider $m$ facilities that have
the same capacity $k$. The techniques used in this section can be easily
extended to the case in which facilities have different capacities. Notice
that, in this case, any percentile mechanism needs to be endowed with a
permutation to specify how to assign the different capacities to the positions
returned by the mechanism [29, 32].

First, we extend Theorem 3.10 to this framework.

######  Theorem 3.20.

Let $k$ be the capacity of $m$ facilities. Moreover, let $\vec{v}$ be a
percentile vector such that $v_{1}<v_{2}<\dots<v_{m}$ so that $\vec{v}$ does
not possess two equal entries and let $\mathcal{PM}_{\vec{v}}$ be its
associated percentile mechanism. Assume that $\lfloor
v_{j+1}(n-1)\rfloor-\lfloor v_{j}(n-1)\rfloor>1$ for every $j\in[m-1]$. Then
$\mathcal{PM}_{\vec{v}}$ is ES if and only if the following system of
inequalities is satisfied

$\displaystyle\begin{cases}&\lfloor v_{2}(n-1)\rfloor-\lfloor
v_{1}(n-1)\rfloor\geq 2k-1\\\ &\dots\\\ &\lfloor v_{m}(n-1)\rfloor-\lfloor
v_{m-1}(n-1)\rfloor\geq 2k-1\end{cases}.$ (6)

######  Proof 3.21.

The proof follows by the same argument used to prove Theorem 3.10. Indeed, by
condition (6) for every $j\in[m]$ we have that at least $2k$ agents are
located between $y_{j}$ and $y_{j+1}$, thus the Social Welfare generated by
the facilities at $y_{j}$ and $y_{j+1}$ does not depend on the specific Nash
Equilibrium. To conclude the proof, it suffices to apply this argument to each
couple of facilities $(y_{j},y_{j+1})$.

The set of inequalities (6) allows us to characterize the vectors $\vec{v}$
that induces an ES percentile mechanism $\mathcal{PM}_{\vec{v}}$ depending on
the capacity $k$. Notice that system (6) does not admit any solution when
$k>\frac{n+m}{2m}$ or, equivalently, $n<(2k-1)m$. Indeed, by summing all the
inequalities in (6), we have that

$\lfloor v_{m}(n-1)\rfloor-\lfloor v_{1}(n-1)\rfloor\geq(2k-1)m.$

Since $n\geq\lfloor v_{m}(n-1)\rfloor-\lfloor v_{1}(n-1)\rfloor$, we must have
that $n\geq(2k-1)m$. Although when $n<(2k-1)m$ it is impossible to define an
ES percentile mechanism that places $m$ facilities at $m$ different locations,
it is possible to define an ES percentile mechanism that places all the
facilities at one or two different locations. To keep the discussion on track,
we first study the case in which system (6) admits a solution and defer the
pathological case to a dedicated section.

###  3.3 Case $n\geq(2k-1)m$.

In this case, it is possible to select an ES and absolutely truthful
percentile mechanism that places the $m$ facilities at $m$ different positions
among the agents’ reports.

######  Theorem 3.22.

If $k<\frac{n+m}{2m}$, then given an ES $\mathcal{PM}_{\vec{v}}$, we have

$ar(\mathcal{PM}_{\vec{v}})=\begin{cases}\frac{mk}{(m-\frac{1}{2})k+\frac{1}{2}}\quad\quad\quad\text{if}\;i_{1},n-i_{m}\geq\lfloor\frac{k+1}{2}\rfloor\\\
\frac{mk}{(m-1)k+\min\\{i_{1},n-i_{m}\\}}\quad\text{otherwise}\end{cases}$

where $i_{1}=\lfloor v_{1}(n-1)\rfloor+1$ and $i_{m}=\lfloor
v_{m}(n-1)\rfloor+1$.

######  Proof 3.23.

The case in which $i_{1},n-i_{m}\geq\lfloor\frac{k+1}{2}\rfloor$ follows by
the same argument adopted in the proof of Theorem 3.12. Indeed, by definition
of the mechanism, the SW of the mechanism is minimized when each facility
$y_{j}=x_{\lfloor v_{j}(n-1)\rfloor+1}$ is such that $|y_{j}-x_{\lfloor
v_{j}(n-1)\rfloor}|=|y_{j}-x_{\lfloor v_{j}(n-1)\rfloor+2}|$. Hence the
mechanism achieves the minimal SW when $x_{\lfloor
v_{j}(n-1)\rfloor+1}=\frac{2j-1}{2m}$ for every $j\in[m]$ and
$x_{i}=\frac{l}{m}$ if $\lfloor v_{l}(n-1)\rfloor+1<i<\lfloor
v_{l+1}(n-1)\rfloor+1$ where $l=0,1,\dots,m$, $v_{0}=0$ and $v_{m+1}=1$. On
such instance the SW of the mechanism is $(m-\frac{1}{2})k+\frac{1}{2}$.
Notice the mechanism achieves the same SW on the instance $\vec{x}_{O}$
defined as $(x_{O})_{i}=0$ for every $i\leq\lfloor v_{1}(n-1)\rfloor+1$, and
$(x_{O})_{i}=1$ otherwise. To conclude, we observe that the optimal SW on
instance $\vec{x}_{O}$ is $mk$.

To conclude the proof, we need to consider the case in which either $i_{1}$ or
$n-i_{m}$ are lower than $\lfloor\frac{k+1}{2}\rfloor$.

Since the other case is symmetric, we restrict our analysis to the case in
which $i_{1}\leq n-i_{2}$. Again, since
$i_{1},n-i_{m}\leq\lfloor\frac{k+1}{2}\rfloor$, we have that the worst-case
instance places the first $i_{1}$ agents at $0$ and the last $n-i_{m}+1$ at
$1$. Since every facility has the same capacity, we have that the worst-case
instance has the following form

$x_{i}=\begin{cases}0\quad\quad\quad\quad\quad\quad\;\text{if}\quad
i=1,\dots,i_{1},\\\ \delta_{1}\quad\quad\quad\quad\;\;\;\quad\text{if}\quad
i=i_{1}+1,\dots,i_{2}-1,\\\
\delta_{1}+\frac{1-\delta_{1}-\delta_{2}}{2(m-2)}\quad\;\text{if}\quad
i=i_{2},\\\
\delta_{1}+2\frac{1-\delta_{1}-\delta_{2}}{2(m-2)}\quad\text{if}\quad
i=i_{2}+1,\dots,i_{3}-1,\\\
\delta_{1}+3\frac{1-\delta_{1}-\delta_{2}}{2(m-2)}\quad\text{if}\quad
i=i_{3},\\\
\delta_{1}+4\frac{1-\delta_{1}-\delta_{2}}{2(m-2)}\quad\text{if}\quad
i=i_{3}+1,\dots,i_{4}-1,\\\ \dots\\\
1-\delta_{2}\quad\quad\quad\quad\text{if}\quad i=i_{m-1}+1,\dots,i_{m}-1,\\\
1\quad\quad\quad\quad\quad\quad\text{otherwise}\end{cases}$

where $\delta_{1},\delta_{2}\geq 0$ and such that $\delta_{1}+\delta_{2}\leq
1$. The SW of the mechanism on this instance is

$\displaystyle SW(\vec{x})$
$\displaystyle=i_{1}+(n-i_{2})+m-2+(k-i_{1})(1-\delta_{1})+\sum_{i=2}^{m-2}\bigg{(}(k-1)\Big{(}\frac{m-3+\delta_{1}+\delta_{2}}{m-2}\Big{)}\bigg{)}$
$\displaystyle\quad+(k-(n-i_{m}))(1-\delta_{2}).$

Again, this quantity is linear in $\delta_{1}$ and $\delta_{2}$, thus it is
minimized when $\delta_{1},\delta_{2}\in\\{0,1\\}$ By plugging in the possible
combinations, we infer that the minimum is achieved when $\delta_{1}=1$ and
$\delta_{2}=0$ since $i_{1}\leq n-i_{m}$.

In particular, for every given the capacity $k$ and number of facility $m$, it
is possible to detect the best possible ES and absolutely truthful percentile
mechanism.

######  Theorem 3.24.

Given $k$, $m$, and $n$, let us define
$\alpha=\lfloor\frac{(n-2k(m-1)+1)}{2}\rfloor$. The vector $\vec{v}$ where
$v_{j}=\frac{\alpha+(2k-1)(j-1)}{n}$ for $j\in[m]$ induces the ES percentile
mechanism with the lowest approximation ratio. In particular, if $n\geq 2km$,
the approximation ratio of $\mathcal{PM}_{\vec{v}}$ is less than
$1+\frac{1}{2m-1}$.

######  Proof 3.25.

Owing to Theorem 3.22, the approximation ratio is lower when
$\min\\{i_{1},n-i_{m}\\}$ is maximized, thus when $i_{1}=n-i_{m}$. Thus the
best mechanism places the first and last facility at $x_{\ell}$ and
$x_{n-\ell}$, where $\ell$ is a suitable integer. Since
$i_{1}+n-i_{m}=n-2k(m-1)+1$, we complete the first half of the proof.

Notice that, if $i_{1}$ or $i_{m}$ is less than $\lfloor\frac{k+1}{2}\rfloor$,
then we have that $\min\\{i_{1},i_{m}\\}\leq\lfloor\frac{k+1}{2}\rfloor$. By
comparing the Social Welfare computed in the Theorem 3.22, we have that
$\Big{(}m-\frac{1}{2}\Big{)}k+\frac{1}{2}\geq(m-1)k+\min\\{i_{1},i_{m}\\}$,
indeed

$\Big{(}m-\frac{1}{2}\Big{)}k+\frac{1}{2}-(m-1)k-\min\\{i_{1},i_{m}\\}\geq\frac{k}{2}+\frac{1}{2}-\lfloor\frac{k+1}{2}\rfloor\geq
0,$

thus the approximation ratio of the mechanism is smaller when
$i_{1},i_{m}\geq\lfloor\frac{k+1}{2}\rfloor$. Moreover, in this case, the
approximation ratio does not depend on the specific $\vec{v}$, thus any ES
percentile mechanism whose $\vec{v}$ is such that
$i_{1},i_{m}\geq\lfloor\frac{k+1}{2}\rfloor$ achieves the minimum
approximation ratio. Notice that, by definition, the vector $\vec{v}$ where
$v_{j}=\frac{\alpha+(2k-1)(j-1)}{n}$ for $j\in[m]$ where
$\alpha=\lfloor\frac{(n-2k(m-1)+1)}{2}\rfloor$ is such that
$i_{1},i_{m}\geq\lfloor\frac{k+1}{2}\rfloor$. Moreover, owing to Theorem 2, it
is also ES, hence it achieves the minimal approximation ratio.

Lastly, notice that

$\frac{mk}{(m-\frac{1}{2})k+\frac{1}{2}}\leq\frac{mk}{(m-\frac{1}{2})k}=\frac{(m-\frac{1}{2})k+\frac{k}{2}}{(m-\frac{1}{2})k}=1+\frac{1}{2m-1},$

which concludes the proof.

Notice that, if $n\geq 2km$, the approximation ratio of the best percentile
mechanism decreases as the number of facilities increases. Noticeably, when
$m$ goes to infinity, the approximation ratio goes to $1$.

###  3.4 Case $n<(2k-1)m$.

We now consider the case in which the number of agent is too small and thus
Theorem 3.20 does not hold. In this case, it is possible to circumvent Theorem
3.20, by considering an percentile mechanism that places all the facilities at
either one or two locations, that is the percentile mechanisms whose
associated vector $\vec{v}$ has at most two different entries. When more than
one facility is placed at the same location, we considered them as a unique
facility whose capacity is the sum of all the facilities placed at the common
location. Notice that it is sufficient to consider the case in which
facilities are divided between at most two points. Indeed, splitting the
facilities between three or more positions leads to another unfeasible system
of the form (6).

Owing to the results of Section 3.1, we have that there are only three ways in
which the facilities can be grouped.

####  3.4.1 The All-aside mechanisms

When the mechanism places the facilities at two different locations, we can
use the results proposed in Section 3.1. Indeed, owing to Theorem 3.14, we
know that the approximation ratio becomes lower as the difference in capacity
between facilities is smaller. For this reason, we consider a mechanism that
splits the facilities as evenly as possible.

######  Mechanism 1 (All-aside mechanism).

Let $k$ be the capacity of $m$ facilities and let $a,b\in\mathbb{N}$ be such
that $a+2mk\leq b\leq n$. Given in input a vector $\vec{x}\in[0,1]^{n}$, the
All-aside mechanism associated with $a$ and $b$, namely $AS_{a,b}$, places
$\lceil\frac{m}{2}\rceil$ facilities at $x_{a}$ and
$\lfloor\frac{m}{2}\rfloor$ facilities at $x_{b}$.

Owing to Theorem 3.10, the All-aside mechanism is absolutely truthful and ES.
Moreover, we can extend Theorem 3.12 to this case.

######  Theorem 3.26.

The approximation ratio of every $AS_{a,b}$ is determined by Theorem 3.12 by
setting $k_{1}=\lceil\frac{m}{2}\rceil k$, $k_{2}=\lfloor\frac{m}{2}\rfloor
k$, $i_{1}=a$, and $i_{2}=b$.

######  Proof 3.27.

It follows directly from Theorem 3.12. Indeed, it suffices to prove that even
if we have $m$ facilities to locate, the optimal SW we can obtain by locating
$m$ facilities with capacity $l$ is the same as locating two facilities with
capacity $\lceil\frac{m}{2}\rceil k$ and $\lfloor\frac{m}{2}\rfloor k$. Since
the worst-case instance of any $\mathcal{PM}_{\vec{v}}$ with
$\vec{v}\in[0,1]^{2}$ places $i_{1}$ agents $0$ and the others at $1$, the
optimal SW remains $mk$ even though we locate $m$ facilities separately.

####  3.4.2 The AIO and SBS mechanisms

Lastly, we consider the case in which the mechanism places all the facilities
at one place, hence the percentile vector $\vec{v}=(v,v,\dots,v)$ for a
$v\in[0,1]$. In this case, every $\vec{v}=(v,v,\dots,v)$ induces an absolutely
truthful and ES mechanism. By the same argument used to prove Theorem 3.16,
the best percentile mechanism places all the facilities at the median agent,
that is $\vec{m}=(0.5,0.5,\dots,0.5)$. In our case, however, the approximation
ratio guarantees are worse than the one presented in [2]. Indeed, since in our
case the capacity can be split at $m$ different locations, the optimal
solution has a further degree of freedom that heightens the approximation
ratio of the mechanism.

######  Theorem 3.28.

Let $k>1$ be the capacity of the facilities and fix $\vec{v}=(0.5,\dots,0.5)$.
If $n\leq(m+1)k$, we have that

$ar(\mathcal{PM}_{\vec{v}})=\frac{2(m-1)k+(n-(m-1)k)+1}{mk+1}.$

Otherwise, $ar(\mathcal{PM}_{\vec{v}})=\frac{2mk}{mk+1}=2-\frac{2}{mk+1}$.

######  Proof 3.29.

By definition, we have that for every input $\vec{x}\in[0,1]^{n}$ the facility
is placed at $x_{\lfloor\frac{n+1}{2}\rfloor}$. The number of agents on the
left of $y_{1}$ and the number of agents on the right of $y_{1}$ is the same,
hence the SW of the mechanism is minimized when $x_{i}=0$ when
$i<\lfloor\frac{n+1}{2}\rfloor$,
$x_{\lfloor\frac{n+1}{2}\rfloor}=\frac{1}{2}$, and $x_{i}=1$ otherwise. The SW
of the mechanism is $\frac{mk+1}{2}$.

If $n\leq(m+1)k$, the optimal SW on the instance is
$(m-1)k+\frac{n-(m-1)k}{2}+\frac{1}{2}$. Indeed, we can locate $m-1$
facilities at either $0$ or $1$ that only accommodate the agents at $0$ and
$1$. The total combined utility of the agents accommodated by these $m-1$
facilities is $(m-1)k$. Since the agents are divided evenly among $0$ and $1$,
the maximum utility attainable by the last facility is at most
$\frac{n-(m-1)k}{2}+\frac{1}{2}$. Therefore the total utility of the optimal
SW is $(m-1)k+\frac{n-(m-1)k}{2}+\frac{1}{2}$.

If $n>(m+1)k$, the optimal SW on this instance is $mk$, and it is attained
when $\lfloor\frac{m}{2}\rfloor$ facilities are placed at $0$ and the others
at $1$. To conclude the thesis it suffices to take the ratio of the optimal SW
and the SW of the mechanism.

######  Remark 3.30.

Notice that the highest approximation ratio occurs when $n=km+1$, in which
case $ar(\mathcal{PM}_{\vec{v}})=2-\frac{k}{mk+1}$. Thus, as the number of
facilities increases, we attain an approximation ratio that converges to $2$

.

Lastly, we observe that Side-By-Side mechanisms can be generalized to this
case. It suffices to distribute all facilities between the positions of two
consecutive agents. As for the case where $m=2$, the worst-case analysis of
these mechanisms is conducted in a similar manner to the AIO mechanisms,
yielding comparable results.

##  4 The Higher Dimensional Problem

In this section, we extend our study to higher dimensional settings. We recall
that an $m$-dimensional percentile mechanism is defined by a $d$ times $m$
matrix $V=(v^{(1)},v^{(2)},\dots,v^{(d)})$, where each row vector
$v^{(j)}=(v^{(j)}_{1},v^{(j)}_{2},\dots,v^{(j)}_{m})\in[0,1]^{m}$ lies within
the unit cube. Given a the agents’ reports $\vec{x}$, the percentile mechanism
associated with $V$ determines the $k$-th facility’s location by selecting,
for each dimension $j\leq d$, the $v^{(j)}_{k}$-th percentile of the ordered
projection of $\vec{x}$ on the $j$-th dimension to be the coordinate of $k$-th
facility in that dimension. More formally, we have that

$y^{(j)}=(z^{(1)}_{\lfloor v^{(1)}_{j}(n-1)\rfloor+1},z^{(2)}_{\lfloor
v^{(2)}_{j}(n-1)\rfloor+1},\dots,z^{(d)}_{\lfloor
v^{(d)}_{j}(n-1)\rfloor+1}),$

where $z^{(l)}$ is the vector containing the projections of the agents
positions on the $l$-coordinates re-ordered increasingly. To summarize, a
$d$-dimensional percentile mechanism determines the coordinates of the
facilities by running $d$ percentile mechanism along each coordinate. We call
the percentile mechanism determining the $j$-th coordinates of the $m$
facilities the $j$-th coordinate percentile mechanism.

In what follows, we extend our framework to higher-dimensional problems and
demonstrate that most of the previously presented results do not generalize to
this setting. This remains true even when we need to locate only two
facilities among agents supported in a bidimensional space. For this reason
and for the sake of simplicity, we limit our discussion to the case where two
facilities need to be located, and each agent position is a point in the unit
cube $[0,1]^{2}$.

###  4.1 The Setting

Let $\vec{x}\in([0,1]^{2})^{n}$ be the bi-dimensional vector containing the
position of $n$ agents in the interval $[0,1]^{2}$, so that
$\vec{x}=(x^{(1)},\dots,x^{(n)})$, where
$x^{(i)}=(x_{1}^{(i)},x_{i}^{(i)})\in[0,1]^{2}$ is the vector containing the
coordinates of the $i$-th agent. We denote with $\vec{k}=(k_{1},k_{2})$ the
$2$-dimensional vector containing all the capacities of the $2$ facilities,
and assume that $k_{1}+k_{2}<n$. In this case, a mechanism is a function
$M:([0,1]^{2})^{n}\to(\mathbb{R}^{2})^{2}$ that maps a vector containing the
agents’ reports to a facility location $\vec{y}=(y^{(1)},y^{(2)})$, where
$y^{(j)}\in\mathbb{R}^{2}$ is the position of the facility with capacity
$k_{j}$.

As for the one dimensional case, once the facilities are located, agents
compete in a First-Come-First-Served (FCFS) to determine their utilities. The
FCFS game is defined as in Section 2, with the only difference being that the
distance between an agent located at $\vec{x}^{(i)}$ and a facility located at
$\vec{y}^{(j)}$ is

$d(\vec{x}^{(i)},\vec{y}^{(j)})=\sqrt{\big{(}x^{(i)}_{1}-y^{(j)}_{1}\big{)}^{2}+\big{(}x^{(i)}_{2}-y^{(j)}_{2}\big{)}^{2}},$

so that the utility of every agent is either $0$ or
$\sqrt{2}-d(\vec{x}^{(i)},\vec{y}^{(j)})$ depending on the outcome of the FCFS
game. It is then easy to see that the construction used to prove Theorem 1
trivially extends to this case, so that a pure Nash Equilibrium to the FCFS
game always exists. Lastly, given a Nash Equilibrium, namely $\gamma$, we
define the Social Welfare associated with $\gamma$ as the sum of all the
agent’s utilities according to $\gamma$.

###  4.2 The Equilibrium Stable Mechanisms

We now discuss under which conditions a percentile mechanism is ES in the
higher dimensional framework. First of all, we notice that every ES percentile
mechanism $M$ must be such that each Coordinate Percentile Mechanism (CPM) is
ES. Indeed, if the first CPM was not ES, it means that there exists a one
dimensional instance $\vec{x}=(x_{1},\dots,x_{n})$ whose Nash Equilibria
induce different Social Welfare values. It is then easy to see that the
percentile mechanism $M$ is not ES by considering the instance
$\\{x^{(i)}=(x_{i},0)\\}_{i\in[n]}$. Unfortunately, assuming that each
coordinate percentile mechanism is ES does not guarantee that the percentile
mechanism is ES in higher dimensions. In particular, enforcing Theorem 3.22 to
each coordinate percentile mechanism is not enough to characterize all the ES
percentile mechanisms when $d>2$. As the next example shows, percentile
mechanisms whose coordinate percentile mechanisms are SBS or WG mechanisms no
longer ensure that the mechanism is ES.

######  Example 4.31.

Let us consider a problem in which we have $10$ agents, that is $n=10$, and
two facilities with capacity $2$, that is $k_{1}=k_{2}=2$. Let us consider the
percentile mechanism induced by $v^{(1)}=v^{(2)}=(0.4,0.5)$, so that both the
coordinate percentile mechanisms are SBS mechanisms. In what follows, we
denote this mechanism with PM. Let us consider the following instance
$x_{1}=x_{2}=x_{3}=(0,0)$, $x_{4}=(0.4,0.4)$, $x_{5}=(0.4,0.5)$,
$x_{6}=(0.5,0.5)$, and $x_{7}=\dots=x_{10}=(0.8,0.8)$, so that PM places the
facilities at $(0.4,0.4)$ and $(0.5,0.5)$. Notice that, depending on what
strategy the agent at $(0.4,0.5)$ plays, the Social Welfare induced by the
percentile mechanism changes.

Figure 2: The two Nash Equilibria described in Example 4.31. The circles
represents the agents (agents from $1$ to $4$ are represented by $x_{l}$ while
agents from $8$ to $10$ are represented by $x_{j}$), the green squares the
facilities and the red arrows the strategies played by the agents getting a
non-null utility in the two different Nash Equilibria.

Example 4.31, can be extended to handle any percentile mechanism whose
coordinates are either SBS or WG. Indeed, the only percentile mechanisms that
are ES for higher dimensional problem must determine one of the two
coordinates using an AIO mechanism. In particular, we now show that any
percentile mechanism whose CPMs are two AIO mechanisms or AIO mechanism an SBS
mechanism are ES.

######  Theorem 4.32.

A percentile mechanisms is ES if and only if all its CPMs are AIO mechanisms
or all the CPMs but one are AIO mechanisms. In the latter case, the CPM that
is not an AIO mechanism must be a SBS mechanism.

######  Proof 4.33.

If a percentile mechanism uses two AIO mechanisms to determine the coordinates
of the facilities, we have that the mechanisms places all the facilities at
the same spot, thus the mechanism is trivially ES.

Let us consider the other case, in which one coordinate is determined via an
AIO mechanism and the other one by an SBS mechanism. Without loss of
generality, let us assume that the first coordinate is determined by the SBS,
so that both the facilities have the same second coordinate, i.e.
$y^{(1)}_{2}=y^{(2)}_{2}$. Let us define the following sets

$A_{1}=\big{\\{}x^{(i)}\;\text{s.t.}\;x^{(i)}_{1}\leq
y^{(1)}_{1}\big{\\}}\quad\quad\text{and}\quad\quad
A_{2}=\big{\\{}x^{(i)}\;\text{s.t.}\;x^{(i)}_{1}\geq y^{(2)}_{1}\big{\\}}.$
(7)

From our assumptions, we have that $A_{1}\cup A_{2}=\\{x^{(i)}\\}_{i\in[n]}$
and $A_{1}\cap A_{2}=\emptyset$. By definition of $A_{1}$ and $A_{2}$, we have
that every agent in $A_{1}$ prefers $y^{(1)}$ to $y^{(2)}$. Vice-versa, every
agent in $A_{2}$ prefers $y^{(2)}$ to $y^{(1)}$. We can then conclude the
proof by using the same argument used to prove Theorem 3.18.

Lastly, we show that a mechanism determining the facilities using an AIO and a
WG mechanism is not ES.

######  Example 4.34.

Let us consider an instance for $n=10$, $k_{1}=k_{2}=2$, and the percentile
mechanism induced by the vectors $v^{(1)}=(0,0.3)$ and $v^{(2)}=(0,0)$. Owing
to Theorem 3.10, we have that each coordinate percentile mechanism is ES,
however the global percentile mechanism is not. Indeed, let us consider the
following instance $x_{1}=(0,0)$, $x_{2}=(0.2,0)$, $x_{3}=(0.2,1)$,
$x_{4}=(0.4,0)$, and $x_{5}=\dots=x_{10}=(0.7,0)$. The percentile mechanism
places the facilities at $(0,0)$ and at $(0.4,0)$. This facility location
induces two Nash Equilibria, one in which agent $x_{3}$ plays $1$ and one in
which agent $x_{3}$ plays $2$. When agent $x_{3}$ plays $1$, we have that one
of the agents located at $(0.5,0)$ is accommodated by $y_{2}$, thus the Social
Welfare is $\sqrt{2}(3.5)$. If agent $x_{3}$ plays $2$, one of the agents
located at $(0.7,0)$ is accommodate by the facility $y_{1}$, thus the Social
Welfare is $\sqrt{2}(3.1)$. We then conclude that the percentile mechanism is
not ES.

Figure 3: The two Nash Equilibria described in Example 4.34. The circles
represents the agents (agents from $5$ to $10$ are represented by $x_{j}$),
the green squares the facilities and the red arrows the strategies played by
the agents getting a non-null utility in the two different Nash Equilibria.

Lastly, we characterize the approximation ratio of the ES percentile mechanism
that determines the coordinates of both facilities using the median mechanism.
Indeed, by a similar argument used in Theorem 3.16, we have that the
percentile mechanism induced by $V=((0.5,0.5),(0.5,0.5))$ achieves the lowest
approximation ratio amongst all the possible ES higher dimensional percentile
mechanisms.

######  Theorem 4.35.

Let $M$ be the percentile mechanism whose coordinate percentile mechanisms are
median mechanisms, then we have that

$ar(M)=\frac{\sqrt{2}}{\sqrt{2}-1}-\frac{\sqrt{2}}{\sqrt{2}-1}\frac{1}{(\sqrt{2}-1)(k_{1}+k_{2})+1}\leq\frac{\sqrt{2}}{\sqrt{2}-1},$
(8)

if $k_{1},k_{2}\leq\lfloor\frac{n}{2}\rfloor$ and

$ar(M)=\frac{\sqrt{2}(k_{2}+\lfloor\frac{n}{2}\rfloor)+\sqrt{2}-1}{(\sqrt{2}-1)(k_{1}+k_{2})+1},$
(9)

otherwise.

######  Proof 4.36.

Let us consider an instance
$\vec{x}=(x^{(1)},\dots,x^{(n)})\in([0,1]^{2})^{n}$. For the sake of
simplicity, we assume $n$ to be odd, so that the median along each coordinate
is uniquely determined. Since all the coordinate percentile mechanisms of
mechanism $M$ are AIO, the output of the mechanisms places both the facilities
at the same location, which we denote with $y=(y_{1},y_{2})\in[0,2]^{2}$.
Without loss of generality, let us assume that $0<y_{1},y_{2}<1$ and that at
most one agent is located at $y$. We then have that the set $[0,1]^{2}$ is
divided into four regions $A_{1}=\\{x\in[0,1]^{2}\;\;\text{s.t.}\;x_{1}\leq
y_{1},\,x_{2}\leq y_{2}\\}$, $A_{2}=\\{x\in[0,1]^{2}\;\;\text{s.t.}\;x_{1}\leq
y_{1},\,x_{2}>y_{2}\\}$,
$A_{3}=\\{x\in[0,1]^{2}\;\;\text{s.t.}\;x_{1}>y_{1},\,x_{2}\leq y_{2}\\}$, and
$A_{4}=\\{x\in[0,1]^{2}\;\;\text{s.t.}\;x_{1}>y_{1},\,x_{2}>y_{2}\\}$ (see
Figure 4). We denote with $\mathcal{A}_{i}$ the set containing the agents
positions in $A_{i}$, that is
$\mathcal{A}_{i}=\\{x^{(j)}\;\text{s.t.}\;x^{(j)}\in A_{i}\\}$. By definition
of $M$, we have that
$|\mathcal{A}_{1}|+|\mathcal{A}_{3}|=|\mathcal{A}_{2}|+|\mathcal{A}_{4}|$ and
$|\mathcal{A}_{1}|+|\mathcal{A}_{2}|=|\mathcal{A}_{3}|+|\mathcal{A}_{4}|$,
which implies $|\mathcal{A}_{2}|=|\mathcal{A}_{3}|$ and
$|\mathcal{A}_{1}|=|\mathcal{A}_{4}|$.

Figure 4: The way $A_{1}$, $A_{2}$, $A_{3}$, and $A_{4}$ partition of
$[0,1]^{2}$ in Theorem 4.35.

Let us now assume that $|\mathcal{A}_{2}|=|\mathcal{A}_{3}|=0$, so that all
the agents are located in $A_{1}$ and $A_{4}$. Since the number of agents is
odd, we then have that the worst-case instance is such that
$\lfloor\frac{n}{2}\rfloor$ agents are located at $(0,0)$,
$\lfloor\frac{n}{2}\rfloor$ agents are located at $(1,1)$ and one agent is
located at $y=(y_{1},y_{2})$. Notice that if $y_{1}+y_{2}\neq 1$, we can
increase the approximation ratio by moving the facility (and the agent sharing
the position with it) to a point of the line $x_{1}+x_{2}=1$. Finally, we have
that the approximation ratio is maximized when either $y=(1,0)$ or $y=(0,1)$.
Notice that if either $|\mathcal{A}_{2}|,|\mathcal{A}_{3}|\neq 0$, we can find
an instance such that the Social Welfare of the mechanism is the same while
the optimal Social Welfare is equal or larger than the SW of the original
instance. Therefore, the worst-case instance for mechanism $M$ is such that
$\lfloor\frac{n}{2}\rfloor$ agents are located at $(0,0)$,
$\lfloor\frac{n}{2}\rfloor$ agents are located at $(1,1)$, and one agent is
located at $(0,1)$. Notice that the SW induced by the mechanism on this
instance is $(\sqrt{2}-1)(k_{1}+k_{2})+1$. To conclude the proof we compute
the approximation ratio of the mechanism, to do that we consider two cases.

Case $1$: $k_{2},k_{1}\leq\lfloor\frac{n}{2}\rfloor$. In this case, the
optimal SW is equal to $k_{1}+k_{2}$, thus we infer (8).

Case $2$: $k_{1}>\lfloor\frac{n}{2}\rfloor$. In this case, the optimal SW is
equal to $k_{1}+\lfloor\frac{n}{2}\rfloor+(\sqrt{2}-1)$, thus we infer (9) and
conclude the thesis.

###  4.3 Beyond $m=2$ and $d=2$

To conclude, we briefly comment on the cases in which either we have more than
two facilities to locate, i.e. $m>2$, or the agents inhabit a space whose
dimension is higher than $2$, i.e. $d>2$.

For higher dimensional problems, it is possible to adapt Example 4.31 and
Example 4.34 to show that the only percentile mechanisms that are ES must be
such that $d-1$ coordinates of the mechanisms are AIO mechanisms and the last
one is either an AIO mechanism or an SBS mechanism.

When $m>2$, we have that the results presented in this section still hold: the
only percentile mechanisms that are ES either place all the facilities at the
same spot or they place the two facilities at two positions whose coordinate
differ only in one entry. In the first case, we have that the coordinates of
the percentile mechanism are all AIO mechanisms, in the second case, the
coordinates of the mechanism are all AIO except for one coordinate which is an
SBS.

##  5 Experimental Results

In this section, we complement our theoretical study of the $m$-CFLP with
scarce resources by running several numerical experiments. In particular, we
want to evaluate the performances of the percentile mechanisms identified by
Theorem 3.14 when the inputs of the mechanisms are generated by a probability
distribution. To this extent, we consider two different metrics to assess the
efficiency of a mechanism.

The first metric we consider is the Bayesian approximation ratio, which
measures how close the expected SW induced by the mechanism and the expected
optimal SW are when the agents’ positions are samples drawn from a probability
distribution $\mu$, [33]. More formally, the Bayesian approximation of
$\mathcal{PM}_{\vec{v}}$ is

$B_{ar}(\mathcal{PM}_{\vec{v}}):=\frac{\mathbb{E}_{\vec{X}\sim\mu}[SW_{opt}(\vec{X})]}{\mathbb{E}_{\vec{X}\sim\mu}[SW_{\mathcal{PM}_{\vec{v}}}(\vec{X})]},$
(10)

where $\vec{X}$ is a $n$ dimensional random vector distributed according to
$\mu$.

The second metric we consider is the Average-Case approximation ratio, which
measures the average ratio between the optimal Social Welfare and the Social
Welfare induced by the mechanism when the agents’ positions are samples drawn
from a probability distribution $\mu$, [17]. More formally, the Average-Case
approximation ratio is defined as

$AVG_{ar}(\mathcal{PM}_{\vec{v}})=\mathbb{E}_{X\sim\mu}\Big{[}\frac{SW_{opt}(\vec{x})}{SW_{\mathcal{PM}_{\vec{v}}}(\vec{x})}\Big{]}.$
(11)

It is worthy of notice that the Bayesian approximation ratio $B_{ar}$ and the
Average-Case approximation ratio $AVG_{ar}$ are two different measures:
$B_{ar}$ measures the percentage-loss of the Social Welfare, while the
$AVG_{ar}$ measures the average Social Welfare percentage-loss.

Our aim is to show that percentile mechanisms that are optimal according to
the worst-case analysis, namely $\mathcal{PM}_{best}$ (see Theorem 3.14), are
optimal or quasi-optimal with respect to both the Bayesian approximation ratio
and the Average-Case ratio. For this reason, we run two tests:

  * •

first, we assess to what extent the Bayesian approximation ratio and the
Average-Case ratio depend on the percentile vector inducing the percentile
mechanism when all the agents are independent and identically distributed
(i.i.d.). In particular, we compare $\mathcal{PM}_{best}$ with
$\mathcal{PM}_{(0,1)}$, that is the percentile mechanism induced by
$\vec{v}=(0,1)$.

  * •

Secondly, we assess the Bayesian approximation ratio and Average-Case ratio of
$\mathcal{PM}_{best}$ when diverse agents within the populations follow
distinct distributions. This examination helps determine the suitability of
$\mathcal{PM}_{best}$ for addressing problems involving non-identically
distributed agents.

We run our experiments for different distributions $\mu$ and different
capacity vectors $\vec{k}$ in order to provide a comprehensive view. Moreover,
since the highest approximation ratio is attained when $m=2$, we only consider
cases in which we need to place two facilities.

Throughout our experiments, we sample the agents’ positions from three
different probability distributions supported over $[0,1]$:  (i) the uniform
distribution, namely $\mathcal{U}$ whose density is equal to $1$ over a
$[0,1]$,  (ii) the triangular distributions, namely $\mathcal{T}$, whose
density is equal to $2(1-x)$ over a $[0,1]$, and  (iii) the Beta distributions
of parameters $\alpha,\beta>0$, namely $\mathcal{B}(\alpha,\beta)$ whose
density is equal to $Cx^{\alpha-1}(1-x)^{\beta-1}$ over a $[0,1]$, where $C$
is a normalizing constant.  We consider different capacity vectors $\vec{k}$.
Specifically, we consider balanced capacities $\vec{k}=(k,k)$ and unbalanced
capacities $\vec{k}=(k_{1},k_{2}),k_{1}>k_{2}$. For the case of balanced
capacities, we consider $k=\alpha n$, where $\alpha=0.1,0.2,0.3$, and $0.4$.
For the case of unbalanced capacities, we consider the slightly unbalanced
capacities i.e. $\vec{k}=(0.4n,0.3n)$, and highly unbalanced capacities i.e.
$\vec{k}=(0.6n,0.2n)$, $(0.7n,0.1n)$. Lastly, for every instance $\vec{x}$, we
do not compute the optimal SW, but rather an upper bound to that quantity.
Indeed, the optimal position of the facilities can be any couple of points in
$[0,1]$. Furthermore, to select the optimal facility location we must compute
all the NE of every possible facility location and select the one achieving
the highest SW. For these reasons, we consider an easier to compute upper
bound that is obtained by considering the maximum SW achievable when the
mechanism forces agents to use a specific facility, that is

$SW_{UB}(\vec{x}):=\sup_{y_{1},y_{2}\in[0,1]}\sup_{\pi\in\Pi}\sum_{i\in[n_{u}]}\sum_{j\in[2]}(1-|x_{i}-y_{j}|)\pi_{i,j}$
(12)

where $\Pi$ is the set containing all the matching $\pi\subset[n]\times[2]$
such that  (i) every $i\in[n]$ has degree that is equal or lower than $1$ and
(ii) every $j\in[2]$ has degree equal to $k_{j}$.  This quantity is easy to
compute, as the set of optimal positions for the facilities coincides with the
positions of the agents.

###  5.1 Experiment results – Comparing different percentile mechanisms.

In this experiment we want to assess to what degree the percentile vector
affects the performances of the percentile mechanisms it induces. For this
reason, we compare the empiric Bayesian approximation ratio and the Average-
Case approximation ratio of the best percentile mechanism
$\mathcal{PM}_{best}$ (identified via Theorem 3.14), with the respective
ratios of a mechanism that places the facilities at the extreme agents’
positions. That is, the percentile mechanism induced by the vector
$\vec{w}=(0,1)$, namely $\mathcal{PM}_{(0,1)}$.

We first consider the case of balanced capacities $\vec{k}=(k,k)$. Figure 5
shows the average and the $95\%$ confidence interval (CI) of Bayesian
approximation ratio for $n=10,20,30,40,50$ when the agents are distributed
according to $\mathcal{U}$ and $\mathcal{T}$. In Figure 6 we plot the results
for the Average-Case Ratio under the same settings. Each average is computed
over $500$ instances. We observe that the percentile mechanism identified in
Theorem 3.14 achieves the a Bayesian approximation ratio that is lower than
the one obtained by $\mathcal{PM}_{(0,1)}$ for every value of $n$. Moreover,
the Bayesian approximation ratio of $\mathcal{PM}_{(0,1)}$ consistently
increases as the number of agents increases, while the Bayesian approximation
ratio of $\mathcal{PM}_{best}$ remains constant regardless of $n$. Remarkably,
these comments hold true even for th Average-Case approximation ratio, showing
that the best percentile mechanism is quasi-optimal for both the metrics under
study.

Figure 5: The Bayesian approximation ratio of $\mathcal{PM}_{best}$ and
$\mathcal{PM}_{\vec{w}}$ in the balanced case, i.e. $k_{1}=k_{2}$ for
$n=10,20,\dots,50$. Every column contains the results for different vector
$\vec{k}$. In the first row, we consider a uniform distribution. In the second
row a symmetric Beta, that is $\mathcal{B}(5,5)$. The third row contains the
results for the triangular distribution $\mathcal{T}$.

We now consider the case in which the facilities have difference capacities.
Figure 7 shows the average and the $95\%$ confidence interval (CI) of Bayesian
approximation ratio for $n=10,20,30,40,50$ when the capacities of the two
facilities are not balanced, and the agents are distributed according to
$\mathcal{T}$. In Figure 8 we plot the results for the Average-Case Ratio
under the same settings. More specifically, we consider $\vec{k}=(0.4n,0.3n)$
and $(0.7n,0.1n)$. We observe that the percentile mechanism identified by
Theorem 3.14 has a lower and more stable Bayesian approximation ratio,
highlighting how choosing a percentile vector affects the average performances
of the mechanism. The same holds for the Average-Case approxiamtion ratio.

Figure 6: The Average-Case approximation ratio of $\mathcal{PM}_{best}$ and
$\mathcal{PM}_{\vec{w}}$ in the balanced case, i.e. $k_{1}=k_{2}$ for
$n=10,20,\dots,50$. Every column contains the results for different vector
$\vec{k}$. In the first row, we consider a uniform distribution. In the second
row a symmetric Beta, that is $\mathcal{B}(5,5)$. The third row contains the
results for the triangular distribution $\mathcal{T}$.

Figure 7: The Bayesian approximation ratio of $\mathcal{PM}_{best}$ and
$\mathcal{PM}_{\vec{w}}$ when the agents are distributed according to
$\mathcal{T}$ and the facilities are unbalanced, i.e. $k_{1}=\alpha_{1}n\neq
k_{2}=\alpha_{2}n$ for $n=10,20,\dots,50$. Every column contains the results
for different vector $\vec{k}$. The first row contains the results for a
symmetric Beta distribution, that is $\mathcal{B}(5,5)$. The second row
contains the results for the triangular distribution $\mathcal{T}$. The last
row contains the results for the Uniform distribution $\mathcal{U}$.

Figure 8: The Average-Case approximation ratio of $\mathcal{PM}_{best}$ and
$\mathcal{PM}_{\vec{w}}$ when the agents are distributed according to
$\mathcal{T}$ and the facilities are unbalanced, i.e. $k_{1}=\alpha_{1}n\neq
k_{2}=\alpha_{2}n$ for $n=10,20,\dots,50$. Every column contains the results
for different vector $\vec{k}$. The first row contains the results for a
symmetric Beta distribution, that is $\mathcal{B}(5,5)$. The second row
contains the results for the triangular distribution $\mathcal{T}$. The last
row contains the results for the Uniform distribution $\mathcal{U}$.

Figure 9: The Bayesian approximation ratio of $\mathcal{PM}_{best}$ for a
population non i.d.. The capacities of the facilities are balanced, i.e.
$k_{1}=k_{2}=\alpha n$ with $\alpha=0.1,0.2,0.3$, and for $n=10,20,\dots,50$.
In the first raw, the Beta distribution is symmetric, in particular
$\mathcal{B}(5,5)$, in the second raw the Beta distribution is asymmetric, in
particular $\mathcal{B}(1,9)$. Every column contains the results for different
$\Lambda$.

Figure 10: The Average-Case approximation ratio of $\mathcal{PM}_{best}$ for a
population non i.d.. The capacities of the facilities are balanced, i.e.
$k_{1}=k_{2}=\alpha n$ with $\alpha=0.1,0.2,0.3$, and for $n=10,20,\dots,50$.
In the first raw, the Beta distribution is symmetric, in particular
$\mathcal{B}(5,5)$, in the second raw the Beta distribution is asymmetric, in
particular $\mathcal{B}(1,9)$. Every column contains the results for different
$\Lambda$.

###  5.2 Experiment results – Bayesian approximation ratio for non i.d.
populations.

In this test, we empirically evaluate the Bayesian approximation ratio of the
percentile mechanisms identified by Theorem 3.14 when agents are not
identically distributed. In particular, we consider the case in which each
agent of the population is distributed according to $\mathcal{U}$,
$\mathcal{T}$, and $\mathcal{B}(5,5)$. Every instance is identified by the
percentages of agents following each distributions, hence we set
$\Lambda=(\lambda_{U},\lambda_{B},\lambda_{T})$, where
$\lambda_{U}=\frac{n_{U}}{n}$, $\lambda_{B}=\frac{n_{B}}{n}$, and
$\lambda_{T}=\frac{n_{T}}{n}$, $n$ is the total number of agents, and $n_{U}$,
$n_{B}$, and $n_{T}$ are the number of agents following the uniform, Beta, and
Triangular distribution, respectively.

In Figure 9, we report our results for different vectors $\Lambda$. We
consider the case in which the capacities of the facilities are balanced, that
$k_{1}=k_{2}=\lfloor\alpha n\rfloor$, where $\alpha=0.1$, $0.2$, and $0.3$.
From our experiments we observe that the percentile mechanism achieves an
almost optimal Bayesian approximation ratio (peaking at $1.01$), that it is
constant regardless of $n$, and that the CI is small (around $0.003$). Our
experiments confirm that the best percentile mechanism according to the worst-
case analysis behave almost optimally in a Bayesian framework.

In Figure 10, we report our results for the Average-Case approximation ratio.
We observe that, while the expected approximation ratio of the mechanism is
still low and close to $1$, the confidence interval in this case is tighter,
which further confirms the suitability of the percentile mechanism to handle
instances in which the population is non identically distributed.

##  6 Conclusion and Future Works

In this paper, we studied the mechanism design aspects of the $m$-CFLP under
the assumption that the total capacity of the facility is smaller than the
number of agents to accommodate. We assume that, after the position of the
facility is fixed, the agents compete in a First-Come-First-Served (FCFS) game
to gain access to the facilities. Our main contribution consist in studying
the case in which $m\geq 2$, which was left as an open questions in the paper
introducing the problem [2]. Our approach emphasizes the significance of
absolutely truthful mechanisms, which prevent agents from benefiting
regardless of their strategy in the FCFS game, and ES mechanisms, whose SW
remains independent of the FCFS game equilibrium. We show that the percentile
mechanisms [13] are absolutely truthful and characterize under which
conditions they are ES. We show that ES percentile mechanisms achieve bounded
approximation ratio for every $m>1$ and characterize the best percentile
vector as a function of $n$, $k_{1}$, and $k_{2}$. Interestingly, if
$n>(2k-1)m$, the approximation ratio of the best percentile mechanism
$1+\frac{1}{2m-1}$, i.e. is asymptotically optimal with respect to the number
of facilities. Lastly, we run extensive numerical results to study the
performances of the percentile mechanism from a Bayesian perspective.

In our future works, we aim at extending this problem to the case in which the
agents are located on a generic graph. Another interesting research avenue is
to study how changing the preferences of the agents affects the performances
of the mechanisms. Finally, it would be interesting to study the asymptotic
Bayesian approximation ratio of ES percentile mechanisms. In that regard, it
is worth to notice that the upper bound we presented in (12) can be connected
to the truncated Wasserstein Distance presented in [34, 35], which enables to
apply the same techniques developed in [32].

#### Acknowledgements

Jie Zhang was partially supported by a Leverhulme Trust Research Project Grant
(2021 – 2024) and the EPSRC grant (EP/W014912/1).

## References

  *   * Auricchio et al. [2024] Auricchio, G., Clough, H.J., Zhang, J.: On the capacitated facility location problem with scarce resources. In: The 40th Conference on Uncertainty in Artificial Intelligence (2024). https://openreview.net/forum?id=3tH77YyFTs
  * Aziz et al. [2020] Aziz, H., Chan, H., Lee, B.E., Parkes, D.C.: The capacity constrained facility location problem. Games and Economic Behavior 124, 478–490 (2020)
  * Brimberg et al. [2001] Brimberg, J., Korach, E., Eben-Chaim, M., Mehrez, A.: The capacitated p-facility location problem on the real line. International Transactions in Operational Research 8(6), 727–738 (2001)
  * Pal et al. [2001] Pal, M., Tardos, T., Wexler, T.: Facility location with nonuniform hard capacities. In: Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pp. 329–338. IEEE, New York (2001)
  * Aardal et al. [2015] Aardal, K., Berg, P.L., Gijswijt, D., Li, S.: Approximation algorithms for hard capacitated k-facility location problems. European Journal of Operational Research 242(2), 358–368 (2015)
  * Balcik and Beamon [2008] Balcik, B., Beamon, B.M.: Facility location in humanitarian relief. International Journal of Logistics Research and Applications 11(2), 101–121 (2008)
  * Melo et al. [2009] Melo, M.T., Nickel, S., Saldanha-da-Gama, F.: Facility location and supply chain management – a review. European Journal of Operational Research 196(2), 401–412 (2009)
  * Ahmadi-Javid et al. [2017] Ahmadi-Javid, A., Seyedi, P., Syam, S.S.: A survey of healthcare facility location. Computers & Operations Research 79, 223–263 (2017)
  * Hastie et al. [2009] Hastie, T., Tibshirani, R., Friedman, J.H., Friedman, J.H.: The Elements of Statistical Learning: Data Mining, Inference, and Prediction vol. 2. Springer, Berlin (2009)
  * Auricchio et al. [2019] Auricchio, G., Bassetti, F., Gualandi, S., Veneroni, M.: Computing wasserstein barycenters via linear programming. In: International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pp. 355–363 (2019). Springer
  * Barda et al. [1990] Barda, O.H., Dupuis, J., Lencioni, P.: Multicriteria location of thermal power plants. European Journal of Operational Research 45(2-3), 332–346 (1990)
  * Nisan and Ronen [1999] Nisan, N., Ronen, A.: Algorithmic mechanism design. In: Proceedings of the Thirty-first Annual ACM Symposium on Theory of Computing, pp. 129–140. ACM, New York (1999)
  * Sui et al. [2013] Sui, X., Boutilier, C., Sandholm, T.: Analysis and optimization of multi-dimensional percentile mechanisms. In: IJCAI, pp. 367–374. AAAI press, Washington (2013). Citeseer
  * Walsh [2020] Walsh, T.: Strategy proof mechanisms for facility location in euclidean and manhattan space. arXiv preprint arXiv:2009.07983 (2020)
  * Fotakis and Tzamos [2014] Fotakis, D., Tzamos, C.: On the power of deterministic mechanisms for facility location games. ACM Transactions on Economics and Computation (TEAC) 2(4), 1–37 (2014)
  * Hartline and Roughgarden [2009] Hartline, J.D., Roughgarden, T.: Simple versus optimal mechanisms. In: Proceedings of the 10th ACM Conference on Electronic Commerce, pp. 225–234. ACM, New York (2009)
  * Deng et al. [2022] Deng, X., Gao, Y., Zhang, J.: Beyond the worst-case analysis of random priority: Smoothed and average-case approximation ratios in mechanism design. Inf. Comput. 285(Part), 104920 (2022) https://doi.org/10.1016/J.IC.2022.104920
  * Procaccia and Tennenholtz [2013] Procaccia, A.D., Tennenholtz, M.: Approximate mechanism design without money. ACM Transactions on Economics and Computation (TEAC) 1(4), 1–26 (2013)
  * Filos-Ratsikas et al. [2017] Filos-Ratsikas, A., Li, M., Zhang, J., Zhang, Q.: Facility location with double-peaked preferences. Auton. Agents Multi Agent Syst. 31(6), 1209–1235 (2017) https://doi.org/10.1007/S10458-017-9361-0
  * Feldman and Wilf [2013] Feldman, M., Wilf, Y.: Strategyproof facility location and the least squares objective. In: EC, pp. 873–890. ACM, New York (2013)
  * Filimonov and Meir [2021] Filimonov, A., Meir, R.: Strategyproof facility location mechanisms on discrete trees. In: AAMAS, pp. 510–518. ACM, New York (2021)
  * Lu et al. [2010] Lu, P., Sun, X., Wang, Y., Zhu, Z.A.: Asymptotically optimal strategy-proof mechanisms for two-facility games. In: EC, pp. 315–324. ACM, New York (2010)
  * Lu et al. [2009] Lu, P., Wang, Y., Zhou, Y.: Tighter bounds for facility games. In: WINE. Lecture Notes in Computer Science, vol. 5929, pp. 137–148. Springer, Berlin (2009)
  * Alon et al. [2010] Alon, N., Feldman, M., Procaccia, A.D., Tennenholtz, M.: Strategyproof approximation of the minimax on networks. Mathematics of Operations Research 35(3), 513–526 (2010)
  * Dokow et al. [2012] Dokow, E., Feldman, M., Meir, R., Nehama, I.: Mechanism design on discrete lines and cycles. In: EC, pp. 423–440. ACM, New York (2012)
  * Meir [2019] Meir, R.: Strategyproof facility location for three agents on a circle. In: SAGT. Lecture Notes in Computer Science, vol. 11801, pp. 18–33. Springer, Berlin (2019)
  * Tang et al. [2020] Tang, P., Yu, D., Zhao, S.: Characterization of group-strategyproof mechanisms for facility location in strictly convex space. In: EC, pp. 133–157. ACM, New York (2020)
  * Chan et al. [2021] Chan, H., Filos-Ratsikas, A., Li, B., Li, M., Wang, C.: Mechanism design for facility location problems: a survey. arXiv preprint arXiv:2106.03457 (2021)
  * Aziz et al. [2020] Aziz, H., Chan, H., Lee, B., Li, B., Walsh, T.: Facility location problem with capacity constraints: Algorithmic and mechanism design perspectives. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34, pp. 1806–1813. MIT Press, New York (2020)
  * Walsh [2022] Walsh, T.: Strategy proof mechanisms for facility location with capacity limits. In: Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, pp. 527–533. International Joint Conferences on Artificial Intelligence Organization, Massachusetts (2022)
  * Auricchio et al. [2024a] Auricchio, G., Wang, Z., Zhang, J.: Facility location problems with capacity constraints: Two facilities and beyond. In: IJCAI 24 (to Appear). ijcai.org, ??? (2024)
  * Auricchio et al. [2024b] Auricchio, G., Zhang, J., Zhang, M.: Extended ranking mechanisms for the m-capacitated facility location problem in bayesian mechanism design. In: Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS 24 (to Appear) (2024)
  * Hartline and Lucier [2010] Hartline, J.D., Lucier, B.: Bayesian algorithmic mechanism design. In: Proceedings of the Forty-second ACM Symposium on Theory of Computing. STOC ’10. Association for Computing Machinery, New York, NY, USA (2010)
  * Pele and Werman [2009] Pele, O., Werman, M.: Fast and robust Earth Mover’s Distances. In: Computer Vision, 2009 IEEE 12th International Conference On, pp. 460–467 (2009). IEEE
  * Auricchio et al. [2019] Auricchio, G., Gualandi, S., Veneroni, M.: The maximum nearby flow problem. Advances in Optimization and Decision Science for Society, Services and Enterprises: ODS, Genoa, Italy, September 4-7, 2019, 23–33 (2019)