ifaamas [AAMAS ’24]Proc. of the 23rd International Conference on Autonomous
Agents and Multiagent Systems (AAMAS 2024)May 6 – 10, 2024 Auckland, New
ZealandN. Alechina, V. Dignum, M. Dastani, J.S. Sichman (eds.) 2024 2024 454
University of Bath Bath United Kingdom University of Bath Bath United Kingdom
Durham University Durham United Kingdom

# Extended Ranking Mechanisms for the $m$-Capacitated Facility Location
Problem in Bayesian Mechanism Design

Gennaro Auricchio<EMAIL_ADDRESS>,  Jie Zhang<EMAIL_ADDRESS>and
Mengxiao Zhang<EMAIL_ADDRESS>
###### Abstract.

In this paper, we initiate the study of the $m$-Capacitated Facility Location
Problem ($m$-CFLP) within a Bayesian Mechanism Design framework. We consider
the case in which every agent’s private information is their position on a
line and assume that every agent’s position is independently drawn from a
common and known distribution $\mu$. In this context, we propose the Extended
Ranking Mechanisms (ERMs), a truthful generalization of the recently
introduced Ranking Mechanisms, that allows to handle problems where the total
facility capacity exceeds the number of agents. Our primary results pertain to
the study of the efficiency guarantees of the ERMs. In particular, we
demonstrate that the limit of the ratio between the expected Social Cost of an
ERM and the expected optimal Social Cost is finite. En route to these results,
we reveal that the optimal Social Cost and the Social Cost of any ERMs can be
expressed as the objective value of a suitable norm minimization problem in
the Wasserstein space. We then tackle the problem of determining an optimal
ERM tailored to a $m$-CFLP and a distribution $\mu$. Specifically, we aim to
identify an ERM whose limit Bayesian approximation ratio is the lowest
compared to all other ERMs. We detail how to retrieve an optimal ERM in two
frameworks:  (i) when the total facility capacity matches the number of agents
and  (ii) when $\mu$ is the uniform distribution and we have two facilities to
place.  Lastly, we conduct extensive numerical experiments to compare the
performance of the ERMs against other truthful mechanisms and to evaluate the
convergence speed of the Bayesian approximation ratio. In summary, all our
findings highlight that a well-tuned ERM consistently outperforms all other
known mechanisms, making it a valid choice for solving the $m$-CFLP within a
Bayesian framework.

###### Key words and phrases:

Bayesian Mechanism Design, Capacitated Facility Location Problem, Optimal
Transport

##  1\. Introduction

Mechanism Design seeks to establish protocols for aggregating the private
information of a set of agents to optimize a global objective. Nonetheless,
optimizing a communal goal solely based on reported preferences frequently
leads to undesirable manipulation driven by the agents’ self-interested
behaviour. Hence, a key property that a mechanism should possess is
truthfulness, which ensures that no agent can gain an advantage by
misrepresenting their private information. Unfortunately, this stringent
condition often clashes with the goal of optimizing the communal objective,
leading to suboptimal outcomes from a truthful mechanism. To quantify the
efficiency loss entailed by a truthful mechanism, Nisan and Ronen introduced
the concept of approximation ratio, which represents the maximum ratio between
the objective achieved by the truthful mechanism and the optimal objective
attainable across all possible agents’ reports Nisan and Ronen (1999). A
prominent problem in Mechanism Design is the $m$-Facility Location Problem
($m$-FLP) Brandt et al. (2016); Chan et al. (2021). In its fundamental guise,
the $m$-FLP involves locating $m$ facilities amidst $n$ self-interested
agents. Each agent requires access to a facility, making it preferable for a
facility to be located as close as possible to their position. Furthermore,
each facility can accommodate any number of agents, thus the agents can select
which facility to use devoid of any concern about possible overload. A natural
extension of the $m$-FLP is the $m$-Capacitated Facility Location Problem
($m$-CFLP), in which every facility has a capacity limit. The capacity limit
constraints the amount of agents that the facility can serve. In this case,
the solution does not only elicit the positions of the facilities, but it also
specifies to which facility every agent is assigned to, ensuring that no
facility is overloaded. To the best of our knowledge, there are very few works
that analyzed the Mechanism Design aspects of the $m$-CFLP. Moreover, all the
existing results are conducted in the classic worst-case analysis, where the
designer has no information on the agents and therefore aims to define
mechanisms that work well on every possible input, regardless of the
likelihood of the input. This type of analysis is, however, too pessimistic
and gives little insight into how to select a mechanism for a specific task.
For example, there are currently no mechanisms capable of locating more than
two capacitated facilities while achieving a finite approximation ratio.
Furthermore, even if we restrict our attention to the case where $m=2$, the
approximation ratio of all the known truthful mechanisms depends linearly on
the number of agents Aziz et al. (2020b), making these efficiency guarantees
less meaningful as the scale of the problem increases. In this paper, we
overcome these issues by studying the $m$-CFLP from a Bayesian viewpoint. In
Bayesian Mechanism Design, every agent’s location is a random variable whose
law is known to the designer Hartline and Lucier (2010) thus the scope of the
mechanism is not to minimize the cost in the worst possible case but rather to
define truthful routines that work well in expectation.

###  1.1. Our Contribution

Our contribution is as follows:

  1. (1)

We define and study the Extended Ranking Mechanisms (ERMs), a generalization
of the class of Ranking Mechanisms introduced in Aziz et al. (2020b). Our
extension allows to tackle a broader framework in which the combined capacity
of the facilities surpasses the total amount of agents. Moreover, a Ranking
Mechanism is truthful if and only if it places all the facilities at, at most,
two locations, while a ERM does not necessarily require such constraint to
ensure truthfulness. See Section 3.

  2. (2)

We then delve into a Bayesian Framework to examine the asymptotic performances
of the ERMs. We consider the case in which every agent’s position is
represented by a set of i.i.d. random variables. Our investigation reveals
that $m$-CFLP is equivalent to a norm minimization problem over a subset of
the Wasserstein space Villani (2009). By leveraging the properties of the
Wasserstein distance, we then establish the convergence of the Bayesian
approximation ratio, i.e., the ratio between the expected cost incurred by the
mechanism and the expected optimal cost, as the number of agents tends toward
infinity. This is our primary result, as seen in Theorem 4.2. We also compute
this limit and show that it depends solely on the specifics of the problem,
namely, the probability distribution $\mu$ describing the agents, the vector
$\@vec{q}$ determining the capacities of the facilities, and the
characteristics of the mechanism. See Section 4.

  3. (3)

After that, we tackle the problem of identifying an optimal ERM tailored to
the $m$-CFLP with agents distributed according to $\mu$ given the capacities
determined by $\@vec{q}$. First, we show that an optimal ERM always exists and
characterize it as a solution to a minimization problem. Subsequently, we
narrow our focus on two specific scenarios:  (i) no-spare capacityframework in
which the total capacity of the facilities matches the total number of agents,
and  (ii) the $2$-CFLP for a population of agents distributed according to a
uniform distribution.  See Section 5.

  4. (4)

Finally, we validate our findings through extensive numerical experiments in
Section 6. In particular, we compare the performances of the ERMs with the
performances of other truthful mechanisms, such as the InnerGap Mechanism
Walsh (2022) and the Extended Endpoint Mechanism Aziz et al. (2020b). From our
experiments, we observe that a well-tuned ERM outperforms all the other
mechanisms whenever $n\geq 20$. From these comparisons, we also observe that
the limit Bayesian approximation ratio is a reliable estimation of the
Bayesian approximation ratio of the ERM when the number of agents is greater
than $20$.

Our outcomes shed light on how to outline a mechanism depending on the
problem, contributing to a better understanding of the strategic aspects of
the $m$-CFLP in a Bayesian framework. Due to space limits, all the missing
proofs are deferred to Appendix A.

###  1.2. Related Work

The $m$-Facility Location Problem ($m$-FLP) and its variations are significant
issues in various practical domains, such as disaster relief Balcik and Beamon
(2008), supply chain management Melo et al. (2009), healthcare Ahmadi-Javid et
al. (2017), clustering Hastie et al. (2009), and public facilities
accessibility Barda et al. (1990). Procaccia and Tennenholtz initially delved
into the Mechanism Design study of the $m$-FLP, laying the groundwork for this
field in their pioneering work Procaccia and Tennenholtz (2013). Following
that, a range of mechanisms with constant approximation ratios for placing one
or two facilities on trees Feldman and Wilf (2013); Filimonov and Meir (2021),
circles Lu et al. (2010, 2010); Lu et al. (2009), general graphs Alon et al.
(2010); Dokow et al. (2012), and metric spaces Meir (2019); Tang et al. (2020)
were introduced. Despite the generality of the underlying space, it is
important to stress that all these positive results are confined to the case
in which we have at most two facilities to place and/or the number of agents
is limited. Moreover, different works tried to generalize the initial
framework proposed in Procaccia and Tennenholtz (2013), by considering
different agents’ preferences Church and Garfinkel (1978); Mei et al. (2016),
different costs Feigenbaum et al. (2017), and additional constraints Filos-
Ratsikas et al. (2015); Feldman et al. (2016). In this paper, we analyze the
$m$-Capacitated Facility Location Problem ($m$-CFLP), a variant of the $m$-FLP
in which each facility can accommodate a finite number of agents. The
Mechanism Design aspects of the $m$-CFLP have only recently begun to attract
attention. Indeed, the game theoretical framework for the $m$-CFLP that we
consider was introduced in Aziz et al. (2020b). This work defined and studied
various truthful mechanisms, like the InnerPoint Mechanism, the Extended
Endpoint Mechanism, and the Ranking Mechanisms. A more theoretical study of
the problem was then presented in Walsh (2022), demonstrating that no
mechanism can position more than two capacitated facilities while adhering to
truthfulness, anonymity, and Pareto optimality. Additionally, another paper
dealing with Mechanism Design aspects of the $m$-CFLP is Aziz et al. (2020a).
However, it explores a different framework where only one facility needs to be
placed and is unable to serve all agents. To the best of our knowledge, all
the results on the $m$-CFLP concerned the classic Mechanism Design framework
that evaluates the performances of the mechanism based on worst-case analysis.
In this paper, we consider an alternative approach: the Bayesian Mechanism
Design perspective. Unlike traditional Mechanism Design, where the designer
lacks information about agent types, in the Bayesian Mechanism Design
framework each agent’s type follows a known probability distribution Hartline
et al. (2013); Chawla and Sivan (2014). In this framework, we are able to
determine a probability distribution over the set of all the possible inputs
of the mechanism, enabling us to consider the expected cost of a mechanism.
Bayesian Mechanism Design has been applied to investigate routing games
Gairing et al. (2005), facility location problems Zampetakis and Zhang (2023),
combinatorial mechanisms using $\epsilon$-greedy mechanisms Lucier and Borodin
(2010), and, notably, auction mechanism design Chawla et al. (2010, 2007);
Hartline and Roughgarden (2009); Yan (2011); Ensthaler and Giebe (2014).

##  2\. Preliminaries

In this section, we fix the notations on the $m$-CFLP, Bayesian Mechanism
Design, and Optimal Transport (OT).

#### The $m$-Capacitated Facility Location Problem.

Given a set of self-interested agents $[n]:=\\{1,\dots,n\\}$, we denote with
$\@vec{x}\in\mathbb{R}^{n}$ the vector containing the agents’ positions.
Likewise, given $m\in\mathbb{N}$, we denote with $\@vec{c}\in\mathbb{N}^{m}$
the vector containing the capacities of the facilities, namely
$\@vec{c}=(c_{1},\dots,c_{m})$. In this setting, a facility location is
defined by three objects:  (i) a $m$-dimensional vector
$\@vec{y}=(y_{1},\dots,y_{m})$ whose entries are $m$ positions on the line,
(ii) a permutation $\pi\in\mathcal{S}_{m}$ that decides the capacity of the
facility built at $y_{j}$, so that $c_{\pi(j)}$ is the capacity of the
facility built at $y_{j}$, and  (iii) a matching $\Gamma\subset[n]\times[m]$
that determines how the agents are assigned to facilities, i.e.
$(i,j)\in\Gamma$ if and only if the agent at $x_{i}$ is assigned to $y_{j}$.
Due to the capacity constraints, the degree of vertex $j\in[m]$ according to
$\Gamma$ is at most $c_{\pi(j)}$. Similarly, every agent is assigned to only
one facility, thus the degree of every $i\in[n]$ according to $\Gamma$ is $1$.
Given the positions of the facilities $\@vec{y}$ and a matching $\Gamma$, we
define the cost of an agent positioned in $x_{i}$ as
$d_{i,\Gamma}(x_{i},\@vec{y})=|x_{i}-y_{j}|$, where $(i,j)$ is the unique edge
in $\Gamma$ adjacent to $i$. Given a matching $\Gamma$ and a permutation
$\pi\in\mathcal{S}_{m}$, a cost function is a map
$C_{\Gamma}:\mathbb{R}^{n}\times\mathbb{R}^{m}\to[0,+\infty)$ that associates
to $(\@vec{x},\@vec{y})$ the overall cost of placing the facilities at the
positions in $\@vec{y}$ following the permutation $\pi$ and assigning the
agents positioned at $\@vec{x}$ according to $\Gamma$.111In what follows, we
omit $\Gamma$ from the indexes of $d$ and $C$ if it is clear from the context
which matching we are considering. Given a vector $\@vec{x}\in\mathbb{R}^{n}$
containing the agents’ positions, the $m$-Capacitated Facility Location
Problem with respect to the cost $C$, consists in finding the locations for
$m$ facilities, a permutation $\pi$, and the matching $\Gamma$ that minimize
the function $\@vec{y}\to C(\@vec{x},\@vec{y})$. The most studied cost
function is the Social Cost ($SC$), which is defined as the sum of all the
agents’ costs. Since multiplying the cost function by a constant does not
affect the approximation ratio results, throughout the paper we consider the
Social Cost rescaled by the total number of agents, that is
$SC(\@vec{x},\@vec{y})=\frac{1}{n}\sum_{i\in[n]}|x_{i}-y_{j}|$.

#### Mechanism Design, the Worst-Case Analysis, and the Ranking Mechanisms.

An $m$-facility location mechanism is a function $f$ that takes the agents’
reports $\@vec{x}$ in input and returns a set of $m$ positions $\@vec{y}$ on
the line, a permutation $\pi\in\mathcal{S}_{m}$, and a matching $\Gamma$ to
allocate the agents to the facilities. In general, an agent may misreport its
position if it would result in a set of facility locations such that the
agent’s incurred cost is smaller than reporting truthfully. A mechanism $f$ is
said to be truthful (or strategy-proof) if, for every agent, its cost is
minimized when it reports its true position. That is,
$d_{i}(x_{i},f(\@vec{x}))\leq d_{i}(x_{i},f(\@vec{x}_{-i},x_{i}^{\prime}))$
for any misreport $x_{i}^{\prime}\in\mathbb{R}$, where $\@vec{x}_{-i}$ is the
vector $\@vec{x}$ without its $i$-th component. Although deploying a truthful
mechanism prevents agents from getting a benefit by misreporting their
positions, this leads to a loss of efficiency. To evaluate this efficiency
loss, Nisan and Ronen introduced the notion of approximation ratio Nisan and
Ronen (1999). Given a truthful mechanism $f$, its approximation ratio with
respect to the Social Cost is defined as
$ar(f):=\sup_{\@vec{x}\in\mathbb{R}^{n}}\frac{SC_{f}(\@vec{x})}{SC_{opt}(\@vec{x})},$
where $SC_{f}(\@vec{x})$ is the Social Cost of placing the facilities and
assigning the agents to them following the output of $f$, while
$SC_{opt}(\@vec{x})$ is the optimal Social Cost achievable when the agents’
report is $\@vec{x}$. The Ranking Mechanisms are a class of mechanisms for the
$m$-CFLP that work under the assumption that the total capacity of the
facilities matches the number of agents, Aziz et al. (2020b). Each Ranking
Mechanism is defined by two parameters: a permutation $\pi\in\mathcal{S}_{m}$
and a vector $\@vec{t}=(t_{1},\dots,t_{m})\in[n]^{m}$. Given $\pi$ and
$\@vec{t}$ the routine of the Ranking Mechanism is as follows:  (i) given
$\@vec{x}$ the vector containing the agents’ reports ordered non-decreasingly,
then the mechanism places the facility with capacity $c_{\pi(j)}$ at
$x_{t_{j}}$.  (ii) The agents are assigned to the facility from left to right
while respecting the capacity constraints.  It was shown in Aziz et al.
(2020b) that a Ranking Mechanism is truthful if and only if every $t_{j}$
admits at most two different values. Moreover, the approximation ratio of
these mechanisms is bounded only when the number of agents is even, the number
of facilities to places is $2$, and the two facilities have the same capacity.
In this case, the mechanism is also called InnerPoint Mechanism (IM) and its
approximation ratio is $\frac{n}{2}-1$.

#### Bayesian Mechanism Design.

In Bayesian Mechanism Design, every agent’s type is described by a random
variable $X_{i}$. In what follows, we assume that every $X_{i}$ is identically
distributed according to a law $\mu$ and independent from the other random
variables. In this framework, a mechanism is truthful if, for every agent $i$,
it holds

$\mathbb{E}_{\@vec{X}_{-i}}[d_{i}(x_{i},f(x_{i},\@vec{X}_{-i}))]\leq\mathbb{E}_{\@vec{X}_{-i}}[d_{i}(x_{i},f(x_{i}^{\prime},\@vec{X}_{-i}))],\;\forall
x_{i}\in\mathbb{R},$ (1)

where $x_{i}$ agent $i$’s true type, $\@vec{X}_{-i}$ is the
$(n-1)$-dimensional random vector that describes the other agents’ type, and
$\mathbb{E}_{\@vec{X}_{-i}}$ is the expectation with respect to the joint
distribution of $\@vec{X}_{-i}$. It is easy to see that if a mechanism is
truthful in the classic Mechanism Design framework, it is also truthful in the
Bayesian framework. Given $\beta\in\mathbb{R}$, a mechanism $f$ is a
$\beta$-approximation if it holds
$\mathbb{E}[SC_{f}(\@vec{X}_{n})]\leq\beta\,\mathbb{E}[SC_{opt}(\@vec{X}_{n})]$,
where $\mathbb{E}$ is the expectation with respect to the joint distribution
of $\@vec{X}_{n}$. Similarly to what happens for the approximation ratio, the
lower $\beta$ is, the better the mechanism is. To unify the notation, we
define the Bayesian approximation ratio of a mechanism $f$ as the ratio
between the expected Social Cost of a mechanism and the expected optimal
Social Cost. More formally, given a mechanism $f$, its Bayesian approximation
ratio with respect to the Social Cost is defined as follows

$B_{ar}(f):=\frac{\mathbb{E}[SC_{f}(\@vec{X}_{n})]}{\mathbb{E}[SC_{opt}(\@vec{X}_{n})]},$
(2)

where the expected value is taken over the joint distribution of the vector
$\@vec{X}_{n}:=(X_{1},\dots,X_{n})$. Notice that, if $B_{ar}(f)<+\infty$, then
$f$ is a $B_{ar}(f)$-approximation.

#### The Wasserstein Distance.

Let us denote with $\mathcal{P}(\mathbb{R})$ the set of probability measures
over $\mathbb{R}$. Given $\gamma\in\mathcal{P}(\mathbb{R})$, we denote with
$spt(\gamma)\subset\mathbb{R}$ the support of $\gamma$ and with $med(\gamma)$
the smallest median of $\gamma$. We denote with $\mathcal{P}_{m}(\mathbb{R})$
the set of probability measures over $\mathbb{R}$ whose support contains at
most $m$ points, thus a measure $\nu\in\mathcal{P}_{m}(\mathbb{R})$ is such
that $\nu=\sum_{j=1}^{m}\nu_{j}\delta_{x_{j}}$, where $x_{j}\in\mathbb{R}$ for
all $j\in[m]$, $\nu_{j}$ are non-negative values satisfying
$\sum_{j=1}^{m}\nu_{j}=1$, and $\delta_{x_{j}}$ is the Dirac delta measure
centered at $x_{j}$. Given two measures
$\alpha,\beta\in\mathcal{P}(\mathbb{R})$, the Wasserstein distance between
$\alpha$ and $\beta$ is defined as
$W_{1}(\alpha,\beta)=\min_{\pi\in\Pi(\alpha,\beta)}\int_{\mathbb{R}\times\mathbb{R}}|x-y|d\pi,$
where $\Pi(\alpha,\beta)$ is the set of probability measures over
$\mathbb{R}\times\mathbb{R}$ whose first marginal is equal to $\alpha$ and the
second marginal is equal to $\beta$ Kantorovich (2006). For a comprehensive
introduction to Optimal Transport theory, we refer to Villani (2009) and
Santambrogio (2015).

#### Basic Assumptions.

Finally, we layout the basic assumptions of our framework. In what follows, we
tacitly assume that the underlying distribution $\mu$ satisfies all the
following properties:  (i) The measure $\mu$ is absolutely continuous. We
denote with $\rho_{\mu}$ its density.  (ii) The support of $\mu$ is an
interval, which can be bounded or not, and that $\rho_{\mu}$ is strictly
positive on the interior of the support.  (iii) The density function
$\rho_{\mu}$ is differentiable on the support of $\mu$.  (iv) The probability
measure $\mu$ has finite first moment, i.e.
$\int_{\mathbb{R}}|x|d\mu<+\infty$.  Notice that, according to this set of
assumptions, the cumulative distribution function (c.d.f.) of $\mu$, namely
$F_{\mu}$, is locally bijective.

##  3\. The Extended Ranking Mechanism

Since our study aims to examine the behaviour of the mechanism as the number
of agents goes to infinity, expressing the problem in terms of absolute
capacities is unsuitable. For this reason, we need to rephrase the specifics
of the $m$-CFLP in terms of percentages. In particular, instead of considering
a collection of capacities $c_{j}\in\mathbb{N}$ for each $j\in[m]$, we shift
our focus to the percentage capacity vector (p.c.v.) $\@vec{q}\in(0,1)^{m}$.
Each value $q_{j}$ corresponds to the percentage of agents that the $j$-th
facility can accommodate. Given $\@vec{q}$ and a number of agents $n$, we
recover the absolute capacity of the $j$-th facility by setting
$c_{j}=\left\lfloor q_{j}(n-1)\right\rfloor+1$. Conversely, when we are given
the absolute capacities $c_{j}$ for a given number of agents $n$, the
corresponding p.c.v. is $q_{j}=\frac{c_{j}}{n}$. Without loss of generality,
we assume that the entries of $\@vec{q}$ are ordered non-increasingly.

######  Mechanism 1 (Extended Ranking Mechanisms (ERMs)).

Let $\@vec{q}=(q_{1},\dots,q_{m})$ be a p.c.v.. Given a permutation
$\pi\in\mathcal{S}_{m}$ and an non-decreasingly ordered vector
$\@vec{p}=(p_{1},\dots,p_{m})\in[0,1]^{m}$, that is $p_{j}\leq p_{j+1}$, the
routine of the ERM associated with $\pi$ and $\@vec{p}$, namely
$\mathtt{ERM}^{(\pi,\@vec{p})}$, is as follows:  (i) First, we collect the
reports of the agents and order them non-decreasingly. We denote with
$\@vec{x}$ the ordered vector containing the agents’ reports, thus $x_{i}\leq
x_{i+1}$.  (ii) Second, we elicit $m$ positions on the line by setting
$y_{j}=x_{\left\lfloor p_{j}(n-1)\right\rfloor+1}$ for every $j\in[m]$ and
place the facility with capacity $q_{\pi(j)}$ at $y_{j}$.  (iii) Finally, we
assign every agent to the facility closer to the position they reported (break
ties arbitrarily without overloading the facilities).

Notice that, in the routine of the ERM, the vector $\@vec{p}$ plays the role
that $\@vec{t}$ plays in the routine of a Ranking Mechanism. Indeed, the main
difference between the Ranking Mechanisms and our generalization lies in how
the mechanism matches the agents to the facilities. While the Ranking
Mechanisms assign the agents monotonically from left to right, the ERM assigns
every agent to the facility that is closer to their report. Depending on the
pair $(\pi,\@vec{p})$ and $\@vec{q}$, however, the matching returned by the
ERM might overload some of the facilities. We say that a couple
$(\pi,\@vec{p})$ induces a feasible ERM if, for every $n\in\mathbb{N}$ and
every $\@vec{x}\in\mathbb{R}^{n}$, the output of
$\mathtt{ERM}^{(\pi,\@vec{p})}$ is a facility location for the $m$-CFLP
induced by $\@vec{q}$. Given a p.c.v. $\@vec{q}$, the set of parameters
$(\pi,\@vec{p})$ that induce a feasible ERM is characterizable through a
system of inequalities. For the sake of simplicity, we first consider the case
in which $\@vec{p}$ does not have two equal entries, that is $p_{j}\neq p_{l}$
for every $j\neq l$.

######  Theorem 3.1.

Given $\@vec{q}$ and $\@vec{p}$ such that $p_{j}\neq p_{i}$ for every $j\neq
i\in[m]$, then $\mathtt{ERM}^{(\pi,\@vec{p})}$ is feasible if and only if the
following system of inequalities are satisfied

$\begin{cases}q_{\pi(1)}\geq p_{2}\\\ q_{\pi(2)}\geq p_{3}-p_{1}\\\
\quad\quad\vdots\\\ q_{\pi(m-1)}\geq p_{m}-p_{m-2}\\\ q_{\pi(m)}\geq
1-p_{m-1}\end{cases}.$ (3)

The feasibility of the ERM ensures also its truthfulness.

######  Theorem 3.2.

Given a p.c.v. $\@vec{q}$, any feasible $\mathtt{ERM}^{(\pi,\@vec{p})}$ is
truthful. Thus it is also truthful in the Bayesian framework.

The truthfulness of any ERM is bound to the fact that every facility $y_{j}$
can accommodate all the agents between $y_{j-1}$ and $y_{j+1}$. This
constraint limits the set of $\@vec{p}$ for which there exists a
$\pi\in\mathcal{S}_{m}$ such that $\mathtt{ERM}^{(\pi,\@vec{p})}$ is feasible.

######  Corollary 3.3.0.

Given a p.c.v. $\@vec{q}\in(0,1)^{m}$, let us fix $\@vec{p}\in[0,1]^{m}$.
Then, if $(\max_{j\in[m]}p_{j}-\min_{j\in[m]}p_{j})>\sum_{j\in[m]}q_{j}-1$,
the mechanism $\mathtt{ERM}^{(\pi,\@vec{p})}$ is not feasible for every
$\pi\in\mathcal{S}_{m}$.

Finally, we notice that if $\@vec{p}$ has at least two equal entries, not all
the feasible ERMs necessarily satisfy system (3). For example, the all-median
mechanism that places all the facilities at the median agent is always
feasible and truthful.222In this case, we do not need to specify which agent
is served by which facility nor $\pi\in\mathcal{S}_{m}$, since all the agents
and all the facilities are served/located at the same place. However,
depending on $\@vec{q}$, the vector $\@vec{p}=(0.5,\dots,0.5)$ may not satisfy
system (3) for any $\pi\in\mathcal{S}_{m}$. Indeed, if $p_{j}=p_{l}$ for some
indices $j,l\in[m]$, we need to consider all the facilities placed at
$x_{\left\lfloor p(n-1)\right\rfloor+1}$ as if they were a unique facility
whose capacity is the total capacity of the facilities placed at
$x_{\left\lfloor p(n-1)\right\rfloor+1}$. By doing so, we are able to extend
Theorem 3.1 and 3.2 to the case in which $\@vec{p}$ has at least two equal
entries. In particular, given $\@vec{p}\in[0,1]^{m}$, let
$\@vec{p}^{\prime}\in[0,1]^{m^{\prime}}$ be the vector containing all the
different entries of $\@vec{p}$, then, the mechanism
$\texttt{ERM}^{(\pi,\@vec{p})}$ is feasible if and only if the following
system is satisfied

$\begin{cases}\sum_{l\in[m];\;s.t.\;p_{\pi(l)}=p_{1}^{\prime}}q_{\pi(l)}\geq
p_{2}^{\prime}\\\
\sum_{l\in[m];\;s.t.\;p_{\pi(l)}=p_{2}^{\prime}}q_{\pi(l)}\geq
p_{3}^{\prime}-p_{1}^{\prime}\\\ \quad\quad\vdots\\\
\sum_{l\in[m];\;s.t.\;p_{\pi(l)}=p_{m-1}^{\prime}}q_{\pi(l)}\geq
p_{m^{\prime}}^{\prime}-p_{m^{\prime}-2}^{\prime}\\\
\sum_{l\in[m];\;s.t.\;p_{\pi(l)}=p_{m^{\prime}}^{\prime}}q_{\pi(l)}\geq
1-p_{m^{\prime}-1}^{\prime}\end{cases}.$

Lastly, we notice that, except in a few specific cases, the approximation
ratio of the Ranking Mechanisms is unbounded. Consequentially, it is
impossible to retrieve a bound on the approximation ratio of any ERM for
generic $m$-CFLPs. Since the classic worst-case analysis does not give any
insight into the performances of the ERMs, we move our attention to the
Bayesian analysis.

##  4\. The Bayesian Analysis of the ERMs

In this section, we present our main result, which characterizes the limit of
the Bayesian approximation ratio of any feasible ERM as a function of
$\@vec{p}$, $\pi$, $\mu$, and $\@vec{q}$. As a preliminary lemma, we relate
the $m$-CFLP to a norm minimization problem in the Wasserstein Space.

######  Lemma 4.1.

Given a p.c.v. $\@vec{q}$, let $\@vec{x}\in\mathbb{R}^{n}$ be the vector
containing the agents’ reports. Let us fix
$\mu_{\@vec{x}}:=\frac{1}{n}\sum_{i\in[n]}\delta_{x_{i}}$. Then, it holds

$SC_{opt}(\@vec{x})=\min_{\sigma\in\mathcal{S}_{m}}\min_{\zeta\in\mathcal{P}_{\sigma,\@vec{q}}(\mathbb{R})}W_{1}(\mu_{n},\zeta),$
(4)

where $\mathcal{P}_{\sigma,\@vec{q}}(\mathbb{R})$ is the set of probability
measures such that $\zeta=\sum_{j\in[m]}\zeta_{j}\delta_{y_{j}}$, where
$y_{1}\leq y_{2}\leq\dots\leq y_{m}$ and $\zeta_{j}\leq q_{\sigma(j)}$ for
every $j\in[m]$. Similarly, given a permutation $\pi\in\mathcal{S}_{m}$ and a
vector $\@vec{p}$ that induce a feasible ERM, it holds

$SC_{\pi,\@vec{p}}(\@vec{x})=\min_{\lambda_{j}\leq
q_{\pi(j)},\sum_{j\in[m]\lambda_{j}=1}}W_{1}(\mu_{n},\lambda),$ (5)

where $SC_{\pi,\@vec{p}}(\@vec{x})$ is the Social Cost attained by
$\mathtt{ERM}^{(\pi,\@vec{p})}$ on instance $\@vec{x}$,
$\lambda=\sum_{j\in[m]}\lambda_{j}\delta_{x_{r_{j}}}$, and $r_{j}=\left\lfloor
p_{j}(n-1)\right\rfloor+1$.

The proof of Lemma 4.1 consists in showing that, for any given instance
$\@vec{x}$ and given an optimal facility location for the $m$-CFLP, it is
possible to construct a measure $\nu$ such that
$W_{1}(\mu_{n},\nu)=SC_{opt}(\@vec{x})$ and, vice-versa, given a measure $\nu$
that minimizes (4), it is possible to retrieve an optimal facility location
problem for the $m$-CFLP. Since the $m$-CFLP admits a solution, problem (4) is
well-posed and admits a solution. By a similar argument, we infer the same
conclusions for problem (5). The connection between the $m$-CFLP and Optimal
Transport theory highlighted in Lemma 4.1 enables us to exploit the properties
of the Wasserstein distances and to characterize the limit Bayesian
approximation ratio of every feasible ERM.

######  Theorem 4.2.

Given the p.c.v. $\@vec{q}$, let $\@vec{p}\in(0,1)^{m}$ and
$\pi\in\mathcal{S}_{m}$ be such that $\mathtt{ERM}^{(\pi,\@vec{p})}$ is
feasible. Then, it holds

$\lim_{n\to+\infty}\frac{\mathbb{E}[SC_{\pi,\@vec{p}}(\@vec{x})]}{\mathbb{E}[SC_{opt}(\@vec{x})]}=\frac{W_{1}(\mu,\nu_{\@vec{p}})}{W_{1}(\mu,\nu_{m})},$
(6)

where $\nu_{m}$ is a solution to the following minimization problem

$\min_{\sigma\in\mathcal{S}_{m}}\min_{\zeta\in\mathcal{P}_{\sigma,\@vec{q}}(\mathbb{R})}W_{1}(\mu,\zeta),$
(7)

and $\nu_{\@vec{p}}$ is a solution to

$\min_{\lambda_{j}\leq
q_{\pi(j)},\sum_{j\in[m]}\lambda_{j}=1}W_{1}\Big{(}\mu,\sum_{j\in[m]}\lambda_{j}\delta_{F_{\mu}^{[-1]}(p_{j})}\Big{)}.$
(8)

###### Sketch of the proof.

The proof consists of three steps:  (i) First, we show that the expected
optimal Social Cost for the $m$-CFLP converges to the objective value of the
minimization problem in (7).  (ii) Second, we show that the expected Social
Cost of $\mathtt{ERM}^{(\pi,\@vec{p})}$ converges to the objective value of
the minimization problem in (8).  (iii) We combine the two convergence results
to retrieve (6).

The limit of the expected optimal Social Cost. Let $\nu_{m}$ be such that
$W_{1}(\mu,\nu_{m})=\min_{\sigma\in\mathcal{S}_{m}}\min_{\zeta\in\mathcal{P}_{\sigma,\@vec{q}}(\mathbb{R})}W_{1}(\mu,\zeta)$.
From Lemma 4.1, we know that, for every $n\in\mathbb{N}$ and for every
$\@vec{x}\in\mathbb{R}^{n}$, there exists a $\nu_{\@vec{x},m}$ such that
$SC_{opt}(\@vec{x})=W_{1}(\mu_{n},\nu_{\@vec{x},m})$. By definition of
$\nu_{m}$, we have that $W_{1}(\mu,\nu_{m})\leq W_{1}(\mu,\nu_{\@vec{x},m})$.
Since $W_{1}$ is a distance, it holds $W_{1}(\mu,\nu_{m})\leq
W_{1}(\mu,\nu_{\@vec{x},m})\leq
W_{1}(\mu,\mu_{n})+W_{1}(\mu_{n},\nu_{\@vec{x},m})$. By rearranging the terms
and by taking the expected value with respect to the distribution of
$\@vec{X}$, we obtain
$\mathbb{E}[W_{1}(\mu,\nu_{m})]-\mathbb{E}[W_{1}(\mu_{n},\nu_{\@vec{x},m})]\leq\mathbb{E}[W_{1}(\mu,\mu_{n})]$.
By a similar argument, we have that $W_{1}(\mu_{n},\nu_{\@vec{x},m})\leq
W_{1}(\mu_{n},\nu_{m})\leq W_{1}(\mu,\mu_{n})+W_{1}(\mu,\nu_{m})$, hence
$\mathbb{E}[W_{1}(\mu_{n},\nu_{\@vec{x},m})]-\mathbb{E}[W_{1}(\mu,\nu_{m})]\leq\mathbb{E}[W_{1}(\mu,\mu_{n})]$.
We then infer that

$|\mathbb{E}[W_{1}(\mu,\nu_{m})]-\mathbb{E}[W_{1}(\mu_{n},\nu_{\@vec{x},m})]|\leq\mathbb{E}[W_{1}(\mu,\mu_{n})].$

Since the right handside of this inequality converges to $0$ as $n$ goes to
$+\infty$ (see Bobkov and Ledoux (2019)), we infer that
$\lim_{n\to\infty}\mathbb{E}[W_{1}(\mu_{n},\nu_{\@vec{x},m})]=W_{1}(\mu,\nu_{m})$,
which concludes the first part of the proof.

The limit of the expected Social Cost of the Mechanism. The argument used for
this part is similar to the one used for the limit expected optimal Social
Cost but more delicate. Indeed, in this case, the set on which we minimize the
Wasserstein distance does depend on the agents’ report $\@vec{x}$. In
particular, the sets on which are formulated problem (8) and (5) are, in
general, different. To overcome this issue, we need to define two auxiliary
probability measures, namely $\phi$ and $\psi$. Given
$\@vec{x}\in\mathbb{R}^{n}$, let $\nu_{\@vec{p}}$ and
$\nu_{\@vec{x},\@vec{p}}$ be the solutions to problem (8) and (5),
respectively. We define the measures
$\phi=\sum_{j\in[m]}(\nu_{\@vec{x},\@vec{p}})_{j}\delta_{y_{j}}$, where
$y_{j}$ is the support of the measure $\nu_{\@vec{p}}$. For every
$n\in\mathbb{N}$ and every $\@vec{x}\in\mathbb{R}^{n}$, we have that
$W_{1}(\mu,\nu_{\@vec{p}})\leq W_{1}(\mu,\phi)\leq
W_{1}(\mu,\mu_{n})+W_{1}(\mu_{n},\nu_{\@vec{x},\@vec{p}})+W_{1}(\nu_{\@vec{x},\@vec{p}},\phi).$
We therefore infer

$W_{1}(\mu,\nu_{\@vec{p}})-W_{1}(\mu_{n},\nu_{\@vec{x},\@vec{p}})\leq
W_{1}(\mu,\mu_{n})+W_{1}(\nu_{\@vec{x},\@vec{p}},\phi).$ (9)

Similarly, given $\@vec{x}\in\mathbb{R}^{n}$, we define
$\psi=\sum_{j\in[m]}(\nu_{\@vec{p}})_{j}\delta_{y_{\@vec{x},j}}$, where
$\\{y_{\@vec{x},j}\\}_{j\in[m]}$ is the support of $\nu_{\@vec{x},\@vec{p}}$.
We then have

$W_{1}(\mu_{n},\nu_{\@vec{x},\@vec{p}})-W_{1}(\mu,\nu_{\@vec{p}})\leq
W_{1}(\mu,\mu_{n})+W_{1}(\nu_{\@vec{p}},\psi).$ (10)

Since the Wasserstein distance is always non negative, we can combine the
estimations in (9) and (10), to obtain

$|W_{1}(\mu_{n},\nu_{\@vec{x},\@vec{p}})-W_{1}(\mu,\nu_{\@vec{p}})|\leq
W_{1}(\mu,\mu_{n})+W_{1}(\nu_{\@vec{p}},\psi)+W_{1}(\nu_{\@vec{x},\@vec{p}},\phi).$

If we take the expectation of both sides of the inequality the inequality
still holds. Thus, if we show that
$\lim_{n\to\infty}\mathbb{E}[W_{1}(\nu_{\@vec{p}},\psi)]=\lim_{n\to\infty}\mathbb{E}[W_{1}(\nu_{\@vec{x},\@vec{p}},\phi)]=0$,
we conclude this second step of the proof since, by Bobkov and Ledoux (2019),
we have that $\lim_{n\to\infty}\mathbb{E}[W_{1}(\mu_{n},\mu)]=0$. Let us
consider $\mathbb{E}[W_{1}(\nu_{\@vec{p}},\psi)]$, the convergence of
$\mathbb{E}[W_{1}(\nu_{\@vec{x},\@vec{p}},\phi)]$ follows by a similar
argument. We notice that $\psi$ and $\nu_{\@vec{p}}$ have different supports,
but $\psi_{j}=(\nu_{\@vec{p}})_{j}$, thus it holds
$\mathbb{E}[W_{1}(\nu_{\@vec{p}},\psi)]\leq\sum_{j\in[m]}\psi_{j}\mathbb{E}[|y_{j}-y_{\@vec{x},j}|]$,
where $y_{\@vec{x},j}$ is the $j$-th point in the support of
$\nu_{\@vec{x},\@vec{p}}$. By definition of ERM, it holds
$y_{\@vec{x},j}=x_{\left\lfloor p_{j}(n-1)\right\rfloor+1}$. Since the
$\big{(}\left\lfloor p_{j}(n-1)\right\rfloor+1\big{)}$-th order statistics
converges to the $p_{j}$-th quantile of $\mu$ Kiefer (1967); De Haan and
Taconis-Haantjes (1979), we have that $\mathbb{E}[|y_{j}-y_{\@vec{x},j}|]\to
0$ as $n\to\infty$, which concludes the second part of the proof.

Characterizing the Bayesian approximation ratio. To conclude, notice that the
distance between an absolutely continuous measure and a discrete measure is
always greater than zero, thus
$\lim_{n\to\infty}\mathbb{E}[SC_{opt}(\@vec{X})]>0$. For this reason, we have
that the limit of the ratio is equal to the ratio of the limits, which proves
(6). ∎

Notice that our result applies only to feasible
$\mathtt{ERM}^{(\pi,\@vec{p})}$, such that $\@vec{p}\in(0,1)^{m}$, since, for
general measures $\mu$, the values $F_{\mu}^{[-1]}(0)$ and $F_{\mu}^{[-1]}(1)$
might not be finite. Moreover, in Appendix C, we show that Theorem 4.2 allows
to study the limit Bayesian approximation ratio of other mechanisms, such as
the InnerPoint Mechanism or the Ranking Mechanisms. Finally, we notice that
the Bayesian approximation ratio is invariant to positive affine
transformation of $\mu$. In particular, the limit of the Bayesian
approximation ratio remains the same across all the Gaussian-distributed
populations.

######  Corollary 4.3.0.

Let $\@vec{q}$ be a p.c.v. and let $X$ be the random variable associated with
$\mu$. Given $\alpha>0$ and $\beta\in\mathbb{R}$, let $\mu_{\alpha,\beta}$ be
the probability distribution associated with $\alpha X+\beta$. Then, the
asymptotical Bayesian approximation ratio of any feasible ERM is the same
regardless of whether the agent type is distributed according to $\mu$ or
$\mu_{\alpha,\beta}$.

##  5\. How to Select an Optimal ERM

As shown in Theorem 4.2, the limit Bayesian approximation ratio of any ERM
hinges upon $\mu$, $\@vec{q}$, $\pi$, and $\@vec{p}$. While $\mu$ and
$\@vec{q}$ are beyond the control of the mechanism designer, both $\pi$ and
$\@vec{p}$ serve as parameters that can be tuned depending upon $\mu$ and
$\@vec{q}$. In this section, we study how to determine an optimal ERM tailored
to $\mu$ and $\@vec{q}$. Given $\mu$ and $\@vec{q}$, we say that a feasible
$\mathtt{ERM}^{(\pi,\@vec{p})}$ is optimal if

$\lim_{n\to\infty}B_{ar}\big{(}\mathtt{ERM}^{(\pi,\@vec{p})}\big{)}\leq\lim_{n\to\infty}B_{ar}\big{(}\texttt{ERM}^{(\pi^{\prime},\@vec{p}^{\prime})}\big{)}$

for any other feasible $\texttt{ERM}^{(\pi^{\prime},\@vec{p}^{\prime})}$. The
main result of the section assesses that an optimal ERM exists and
characterizes its parameters $(\pi,\@vec{p})$ as the solution to a suitable
minimization problem.

######  Theorem 5.1.

Given $\mu$ and a p.c.v. $\@vec{q}$, there always exist a tuple
$(\pi,\@vec{p})$ whose associated ERM, that is
$\mathtt{ERM}^{(\pi,\@vec{p})}$, is optimal. Moreover, the couple
$(\pi,\@vec{p})$ is a solution to the following minimization problem

$\displaystyle\min_{\pi\in\mathcal{S}_{m}}\min_{\@vec{p}\in(0,1)^{m}}$
$\displaystyle
W_{1}\Big{(}\mu,\sum_{j\in[m]}\eta_{j}\delta_{F_{\mu}^{[-1]}(p_{j})}\Big{)}$
(11) such that $\displaystyle p_{j+1}-p_{j-1}\leq
q_{\pi(j)}\;\;\text{for}\;\;j=2,\dots,m-1,$ $\displaystyle p_{1}\leq
q_{\pi(q)},\;\text{and}\;\;p_{m}\leq 1-q_{\pi(m)},$

where
$\eta_{1}=F_{\mu}\Big{(}\frac{F^{[-1]}_{\mu}(p_{2})+F^{[-1]}_{\mu}(p_{1})}{2}\Big{)}$,
$\eta_{j}=F_{\mu}\Big{(}\frac{F^{[-1]}_{\mu}(p_{j+1})+F^{[-1]}_{\mu}(p_{j})}{2}\Big{)}-F_{\mu}\Big{(}\frac{F^{[-1]}_{\mu}(p_{j})+F^{[-1]}_{\mu}(p_{j-1})}{2}\Big{)}$
for $j=2,\dots,m-1$, and $\eta_{m}=1-\eta_{m-1}$.

Notice that the limit Bayesian approximation ratio of the optimal ERM does not
necessarily converge to $1$, as the next example shows.

######  Example 0.

Let $\mu$ be the uniform distribution $\mathcal{U}[0,1]$ and let
$\@vec{q}=(0.8,0.4)$ be a p.c.v.. Since $\mu$ is symmetric, one of the
solutions to problem (7) is $\nu_{2}=(0.4)\delta_{0.2}+(0.6)\delta_{0.7}$ (the
other one is $\nu_{2}^{\prime}=(0.6)\delta_{0.3}+(0.4)\delta_{0.8}$). However,
by Corollary 3.3, there does not exist a permutation $\pi\in\mathcal{S}_{m}$
such that $\texttt{ERM}^{((0.2,0.7),\pi)}$ is feasible. Thus, by Theorem 4.2,
no feasible ERM is such that
$\lim_{n\to\infty}B_{ar}(\mathtt{ERM}^{(\pi,\@vec{p})})=1$.

We now characterize the optimal ERM in two specific cases. In the first one,
the total capacity of the facilities is the same as the number of agents. In
the second one, we need to place two capacitated facilities and $\mu$ is a
uniform distribution.

###  5.1. The No-Spare Capacity Case

In the no-spare capacity case, the total capacity of the facilities matches
the number of agents, thus $\sum_{j\in[m]}q_{j}=1$. Due to Corollary 3.3, we
have that the only feasible ERMs are the ones for which it holds
$p_{j}=p\in[0,1]$ for every $j\in[m]$. Thus, owing to the properties of the
$W_{1}$ distance and to Lemma 4.1, the optimal ERM is the all-median
mechanism, i.e. $\texttt{ERM}^{(Id,(0.5,\dots,0.5))}$.

######  Theorem 5.3.

In the no-spare capacity case, the optimal ERM is unique and is the all-median
mechanism.

When the agents are distributed following a uniform distribution, that is
$\mu=\mathcal{U}[0,1]$, we can express the limit Bayesian approximation ratio
of the all-median mechanism as a function of $\@vec{q}$. Indeed, since
$\sum_{j\in[m]}q_{j}=1$, any solution to problem (7) separates the interval
$[0,1]$ into $m$ intervals whose length is $q_{j}$. Notice that the order in
which $[0,1]$ is divided is irrelevant. Furthermore, the facility is placed at
the median of such interval, thus the objective value of (7) is
$\frac{1}{4}\sum_{j\in[m]}q_{j}^{2}$. By Theorem 4.2, the limit Bayesian
approximation ratio of the all-median mechanism is
$\lim_{n\to\infty}B_{ar}(\texttt{all-median})=(\sum_{j\in[m]}q_{j}^{2})^{-1}$,
since the asymptotic cost of placing all the facilities at the median point is
$\int_{0}^{1}|x-0.5|dx=\frac{1}{4}$. Notice that the limit Bayesian
approximation ratio gets closer to $1$ as the values of $\@vec{q}$ become
concentrated at one index. Conversely, if all the facilities have the same
capacity $\frac{1}{m}$, we have that the Bayesian approximation ratio of the
all-median becomes the largest possible, that is
$\lim_{n\to\infty}B_{ar}(\mathtt{ERM}^{(\pi,\@vec{p})})=m$.

#### Comparing the Ranking Mechanisms with the ERMs

To the best of our knowledge, the only other truthful mechanisms capable of
placing more than $2$ facilities in the no-spare capacity case are the Ranking
Mechanisms Aziz et al. (2020b). To close the section, we show that the all-
median mechanism is also the asymptotically best possible Ranking Mechanism.
Indeed, by Aziz et al. (2020b), we know that a truthful Ranking Mechanism
either  (i) puts all the facilities at the same position or  (ii) places all
the facilities at two adjacent agents’ reports, namely $x_{t}$ and $x_{t+1}$.
However, not all the values of $t$ are feasible, as it must exist
$J^{\prime}\subset[m]$ such that $t=\sum_{j\in J^{\prime}}c_{j}$.  Owing to
Theorem 5.3, in case (i), the best possible mechanism is the all-median
mechanism. In case (ii) the limit Bayesian approximation ratio of any
mechanism is either equal or higher (see Appendix C). Indeed, consider a
population distributed as a Uniform distribution, i.e. $\mu=\mathcal{U}[0,1]$,
and $\@vec{q}=(\frac{1}{3},\frac{1}{3},\frac{1}{3})$, and the Ranking
Mechanism that places $q_{1}$ at
$x_{\left\lfloor\frac{n-1}{3}\right\rfloor+1}$ and the other two facilities at
$x_{\left\lfloor\frac{n-1}{3}\right\rfloor+2}$. Since every agent is assigned
to its closest facility, it is possible to adapt Lemma 4.1 and Theorem 4.2 and
show that the limit of the expected Social Cost of the mechanism is
$W_{1}(\mu,\delta_{\frac{1}{3}})=\frac{5}{18}$. Hence, the limit Bayesian
approximation ratio of the considered Ranking Mechanism is $\sim 3.33$, while
$\lim_{n\to\infty}B_{ar}(\texttt{all-median})=3$.

###  5.2. Placing two capacitated facilities for a uniform population.

In this section, we retrieve the optimal ERMs when $\mu=\mathcal{U}[0,1]$ and
$m=2$. For the sake of simplicity, we divide the discussion into three steps.
First, we demonstrate that both permutations in $\mathcal{S}_{2}$ yield
equally optimal ERMs. Second, we explicit the objective function of problem
(11) as a function of $\@vec{p}$ and compute its derivatives. Lastly, we
retrieve the optimal ERM for any given $\@vec{q}$ using Lagrangian
multipliers. In Appendix B, we show how to generalize this process to the case
in which $\mu$ is symmetric and other relevant frameworks.

First, notice that, since $F_{\mathcal{U}[0,1]}^{[-1]}(p)=p$ for every
$p\in[0,1]$, the objective value of problem (11) boils down to

$\mathcal{W}(\@vec{p}):=W_{1}\Big{(}\mu,\frac{p_{1}+p_{2}}{2}\delta_{p_{1}}+\big{(}1-\frac{p_{1}+p_{2}}{2}\big{)}\delta_{p_{2}}\Big{)}.$

Step $1$. Since $m=2$, $\mathcal{S}_{2}=\\{Id,\theta\\}$, where the
permutation $Id$ is such that $Id(i)=i$, and $\theta$ switches $1$ and $2$.
First, we show if $(Id,\@vec{p})$ satisfies system (3), there exists a vector
$\@vec{p}^{\prime}$ such that $(\theta,\@vec{p}^{\prime})$ satisfies (3) and
$\mathcal{W}(\@vec{p})=\mathcal{W}(\@vec{p}^{\prime})$. Given
$\@vec{p}=(p_{1},p_{2})$, let us define
$\@vec{p}^{\prime}=(p_{1}^{\prime},p_{2}^{\prime})=(1-p_{2},1-p_{1})$. If
$(Id,\@vec{p})$ satisfies system (3), we have that $p_{2}\leq q_{Id(1)}=q_{1}$
and $1-p_{1}\leq q_{Id(2)}=q_{2}$. It is then easy to see that
$p_{2}^{\prime}=1-p_{1}\leq q_{2}=q_{\theta(1)}$ and, likewise
$1-p_{1}^{\prime}\leq q_{\theta(2)}$. Thus, $(\theta,\@vec{p}^{\prime})$
satisfies (3). Finally, due to the symmetry of $\mu$ with respect to $0.5$, we
have that $\mathcal{W}(\@vec{p})=\mathcal{W}(\@vec{p}^{\prime})$. Therefore,
for both $Id$ and $\theta$, there exists a vector $\@vec{p}$ that induces an
optimal ERM.

Step $2$. Let us fix $\pi=Id$. Due to the properties of the optimal
transportation plan on the line Santambrogio (2015), have that
$\mathcal{W}(\@vec{p})=\int_{0}^{1}\min\\{|x-p_{1}|,|x-p_{2}|\\}dx$, thus
$\mathcal{W}(\@vec{p})=\frac{p_{1}^{2}}{2}+\frac{(1-p_{2})^{2}}{2}+\frac{(p_{2}-p_{1})^{2}}{4}$.
From a simple computation, we infer that the objective function
$\mathcal{W}(\@vec{p})$ is differentiable and retrieve the formula of its
gradient as
$\nabla\mathcal{W}(\@vec{p})=\frac{1}{2}\big{(}3p_{1}-p_{2},3p_{2}-2-p_{1}\big{)}$.
Notice that the set of points on which the first derivative of $\mathcal{W}$
nullifies is the line $p_{2}=3p_{1}$, while the set of points on which the
second derivative of $\mathcal{W}$ nullifies is $p_{2}=\frac{1}{3}(p_{1}+2)$,
thus $\nabla\mathcal{W}(\@vec{p})=(0,0)$ if and only if
$\@vec{p}=(0.25,0.75)$.

Step $3$. Lastly, to detect an optimal ERM, we need to implement the
feasibility constraints described in Theorem 3.1. From Step $1$, we focus on
the set of constraints induced by $Id\in\mathcal{S}_{m}$. In this case, we
have that $\@vec{p}$ must satisfy the following constraints  (i) $p_{2}\leq
q_{1}$,  (ii) $1-p_{1}\leq q_{2}$that is $1-q_{2}\leq p_{1}$, and  (iii)
$p_{1}\leq p_{2}$.  Thus the set of feasible $\@vec{p}$ is a triangle, namely
$T(\@vec{q})$, whose vertexes are $(q_{1},q_{1})$, $(1-q_{2},1-q_{2})$, and
$(1-q_{2},q_{1})$. Finally, we retrieve the best vector $\@vec{p}$ depending
on the value of $\@vec{q}$. First, notice that if $(0,25,0.75)\in
T(\@vec{q})$, i.e. if and only if $q_{1},q_{2}\geq 0.75$, then the minimum is
attained in $\@vec{p}=(0,25,0.75)$ as it is the only point in which the
gradient $\nabla\mathcal{W}$ nullifies and the Hessian matrix is positive
definite. For all the other values of $\@vec{q}$, we need to search the
minimum over the boundary of $T(\@vec{q})$, since the gradient is never null
on the interior of $T(\@vec{q})$. First, notice that the minimum cannot lay in
the segment connecting the vertexes $(1-q_{2},1-q_{2})$ and $(q_{1},q_{1})$.
In this case, we have that $\nabla\mathcal{W}(\@vec{p})=\frac{1}{2}(2p,2p-2)$,
hence the gradient is never perpendicular to the line $p_{1}=p_{2}$. We then
need to search for the minimum in the sets
$\\{(1-q_{2},t)\;\text{s.t.}\;t\in[1-q_{2},q_{1}]\\}$ and
$\\{(t,q_{1})\;\text{s.t.}\;t\in[1-q_{2},q_{1}]\\}$.

######  Theorem 5.4.

Let $\@vec{q}$ be a p.c.v. such that $q_{2}\leq q_{1}$, then an optimal ERM
for a uniformly distributed population is induced by $(Id,\@vec{p})$ where
(i) $\@vec{p}=(0.25,0.75)$if $q_{2}\geq 0.75$,  (ii)
$\@vec{p}=(1-q_{2},q_{1})$if $3q_{2}-2-q_{1}\leq 0$, and  (iii)
$\@vec{p}=(1-q_{2},1-\frac{q_{2}}{3})$otherwise.

Lastly, we compare the performances of an optimal ERM and the Extended
Endpoint Mechanism (EEM), introduced in Aziz et al. (2020b).

#### Bayesian Analysis of the EEM

The EEM is a truthful mechanism that can locate any two capacitated
facilities. The routine of the EEM is as follows. Given
$\@vec{x}=(x_{1},\dots,x_{n})$ a vector containing the agents’ reports ordered
non-decreasingly, we define
$A_{1}=\big{\\{}x_{i}\;\text{s.t.}\;|x_{i}-x_{1}|\leq\frac{|x_{1}-x_{n}|}{2}\big{\\}}$
and
$A_{2}=\big{\\{}x_{i}\;\text{s.t.}\;|x_{i}-x_{n}|>\frac{|x_{1}-x_{n}|}{2}\big{\\}}$.
Depending on the cardinality of the sets $A_{i}$ and the capacities of the
facilities, the EEM determines the positions of the facilities following one
of six possible routines (see Appendix C). To analyze the convergence of the
Bayesian approximation ratio of the EEM we need to study all the costs of all
the six possible outcomes, weight them by the likelihood of them occurring,
and take the limit for $n$ goes to $+\infty$.333Since the EEM cannot be
phrased as an ERM, we cannot rely on Theorem 4.2. For instance, let us
consider Example 5.2. In this case, we have that, as the number of agents
increases, the EEM will either  (1) place the facility with capacity $q_{2}$
at $y_{1}=x_{1}$ and the other facility at $y_{2}=2x_{n-(\left\lfloor
q_{1}(n-1)\right\rfloor+1)}-x_{1}$ with probability $0.5$ or  (2) place the
facility with capacity $q_{2}$ at $y_{2}=x_{n}$ and the other facility at
$y_{1}=2x_{\left\lfloor q_{1}(n-1)\right\rfloor+2}-x_{n}$ with probability
$0.5$.  Since $\mu=\mathcal{U}[0,1]$, we have that $x_{1}\to 0$, $x_{n}\to 1$,
$x_{n-\left\lfloor q_{2}(n-1)\right\rfloor+2}\to
F_{\mu}^{[-1]}(1-q_{2})=1-q_{2}$, and $x_{\left\lfloor
q_{2}(n-1)\right\rfloor+1}\to F_{\mu}^{[-1]}(q_{2})=q_{2}$. In particular, the
limit expected Social Cost of the mechanism is then
$\frac{1}{2}W_{1}(\mu,q_{2}\delta_{2q_{2}-1}+(1-q_{2})\delta_{1})+\frac{1}{2}W_{1}(\mu,(1-q_{2})\delta_{0}+q_{2}\delta_{2-2q_{2}})$.
Since $\mu$ is symmetric with respect to $\frac{1}{2}$, we have that
$W_{1}(\mu,q_{2}\delta_{2q_{2}-1}+(1-q_{2})\delta_{1})=W_{1}(\mu,(1-q_{2})\delta_{0}+q_{2}\delta_{2-2q_{2}})=\frac{(1-q_{2})^{2}}{2}+\frac{q_{2}(2-3q_{2})}{2}=0.34$,
hence the limit Bayesian approximation ratio of the EEM is $\sim 2.62$. By
Theorem 5.4, the optimal ERM is the one induced by $\@vec{p}=(0.6,0.8)$, thus
its limit Bayesian approximation ratio is $\sim 1.62$. The sub-efficiency of
the EEM with respect to an optimal ERM is due to the fact that the EEM places
both the facilities outside the interval $(x_{1},x_{n})$, which, in the limit,
leads to a loss of efficiency. Moreover, it is worth to notice that the
convergence of the expected Social Cost of the EEM depends on the convergence
of the first or last order statistic.

##  6\. Numerical Experiments

In this section, we complement our theoretical study of the ERMs by running
several numerical experiments. Indeed, most of our results pertain to the
limit analysis of the mechanism. For this reason, we want to test two aspects
of the ERMs. First, we want to compare the Bayesian approximation ratio of the
ERMs with the Bayesian approximation ratios of other truthful mechanisms when
the number of agents $n$ is small. Since the Ranking Mechanisms are a subset
of the ERMs and have been discussed in Section 5.1, we only consider the EEM
and, when possible, the IG. Second, we want to evaluate the convergence speed
of the Bayesian approximation ratio of $\mathtt{ERM}^{(\pi,\@vec{p})}$. More
specifically, we want to assess how close the Bayesian approximation ratio of
an ERM and the limit detected in Theorem 4.2 are when the number of agents is
small. We run our experiments for different distributions $\mu$ and percentage
capacity vector $\@vec{q}$. All the experiments are performed in Matlab 2023a
on macOS Monterey system with Apple M1 Pro CPU and 16GB RAM. The code is
available on https://anonymous.4open.science/r/Bayesian-CFLP-38D5/.

#### Experiment setup

Throughout our experiments, we sample the agents’ positions from three
different probability distributions: the uniform distribution
$\mathcal{U}[0,1]$, standard normal distribution $\mathcal{N}(0,1)$, and
exponential distribution $\text{Exp}(1)$. Owing to Corollary 4.3, we do not
consider other parameter choices since testing the mechanisms over the
standard Gaussian distribution is the same as testing over a generic normal
distribution $\mathcal{N}(\mathfrak{m},\sigma^{2})$. Since our goal is to
compare the performances of the ERMs to other relevant mechanisms, we limit
our tests to cases in which $m=2$, as all the known truthful mechanisms
different from the Ranking Mechanisms operate only under this restriction. We
consider different percentage capacity vectors $\@vec{q}\in(0,1)^{2}$.
Specifically, we consider balanced capacities $\@vec{q}=(q,q)$ and unbalanced
capacities $\@vec{q}=(q_{1},q_{2}),q_{1}\neq q_{2}$. For the case of balanced
capacities, we consider $q=0.7,0.8$ and $0.9$. For the case of unbalanced
capacities, we consider the slightly unbalanced capacities i.e.
$\@vec{q}=(0.85,0.75)$, and extremely unbalanced capacities i.e.
$\@vec{q}=(0.8,0.4)$, $(0.85,0.35)$. As benchmark mechanisms, we consider the
EEM Aziz et al. (2020b) and, when possible, the IG Walsh (2022).

#### Experiment results – Comparison with the EEM and the IG

We first consider the case of balanced capacities $\@vec{q}=(q,q)$, in which
we are able to compare the Bayesian approximation ratio of three different
mechanisms for the $m$-CFLP: the EEM, the IG, and the ERMs. Regardless of the
distribution, we consider the optimal ERM with respect to the uniform
distribution, i.e. $\mathtt{ERM}^{(\pi,\@vec{p})}$, with $\pi=Id$ and
$\@vec{p}=(\max\\{0.25,1-q\\},\min\\{0.75,q\\})$. Figure 1 (and Table 1 in
Appendix D) shows the average and the $95\%$ confidence interval (CI) of
Bayesian approximation ratio for $n=10,20,30,40,50$. Each average is computed
over $500$ instances. We observe that, in most cases, the ERM achieves the
lowest Bayesian approximation ratio comparing to the other two mechanisms.
When $q=0.7$, the ERM is still better than the EEM but slightly worse than the
IG. However, the empirical Bayesian approximation ratio of the ERM and IG
converges to the same value as the number of agents increases.

Next, we consider the case of unbalanced capacities, where $q_{1}\neq q_{2}$,
specifically $\@vec{q}=(0.85,0.75),(0.8,0.4),(0.85,0.35)$. Since the IG
requires the two capacities to be identical, we compare only the ERM and the
EEM. Amongst the possible ERMs, we select the one optimal with respect to the
Uniform distribution, obtained via Theorem 5.4. Thus the parameters of
$\mathtt{ERM}^{(\pi,\@vec{p})}$ are  (i) $\pi=Id$for every $\@vec{q}$ and
(ii) $\@vec{p}=(0.25,0.75)$for $\@vec{q}=(0.85,0.75)$, $\@vec{p}=(0.6,0.8)$
for $\@vec{q}=(0.8,0.4)$, and $\@vec{p}=(0.65,0.85)$ for
$\@vec{q}=(0.85,0.35)$.  In this case, we consider only symmetric probability
distributions, i.e. the Gaussian and the Uniform distribution. Figure 2 (and
Table 2 in Appendix D) shows the average and the $95\%$ CI of Bayesian
approximation ratio computed over 500 instances. Whenever $n\geq 20$, the ERM
has a much lower approximation ratio. It is particularly interesting the case
$\@vec{q}=(0.75,0.85)$. In this case, the ERM is optimal in both cases, and
its limit Bayesian approximation ratio is $1$. Indeed, the Bayesian
approximation ratio of the ERM is almost equal to $1$ for every $n\geq 10$ and
gets closer as $n$ increases, however the Bayesian approximation ratio of the
EEM is always $\geq 1.79$ and gets worse as $n$ increases.

Figure 1. The Bayesian approximation ratio of ERM, IG, and EEM in the balanced
case, i.e. $q_{1}=q_{2}$ for $n=10,20,\dots,50$. Every column contains the
results for different vector $\@vec{q}$. The first row contains the results
for the Uniform distribution, the second row the results for the Gaussian
distribution, and the third one the results for the Exponential distribution.
Every value is computed as the average of $500$ runs. Figure 2. The Bayesian
approximation ratio of ERM and EEM in the unbalanced case, i.e. $q_{1}\neq
q_{2}$ for $n=10,20,\dots,50$. Every column contains the results for a
different vector $\@vec{q}$. The first row contains the results for the
Uniform distribution. The second row contains the results for the Gaussian
distribution. Every value is computed as the average of $500$ runs.

#### Experiment results – Convergence speed of the limit Bayesian
approximation ratio.

Lastly, we test how close the Bayesian approximation ratio of the ERM is to
the limit detected in Theorem 4.2. That is, we calculate the relative error as

$err_{rel}=\frac{\text{empirical }B_{ar}-\text{limit of }B_{ar}}{\text{limit
of }B_{ar}}.$

Figure 3 (and Table 3 in Appendix D) show the relative error for the six
cases. Each average is computed over $500$ instances. We observe that the
relative error decreases as the number of agents increases, regardless of the
distribution or the p.c.v. $\@vec{q}$. Moreover, in all cases but
$\@vec{q}=(0.8,0.4),(0.85,0.35)$, the relative errors of the ERM are less than
$0.05$ as long as $n\geq 20$, which validates Theorem 4.2 as a tool to predict
the Bayesian approximation ratio for small values of $n$. In other cases, we
observe a slower convergence, as the percentage error is slightly larger and
its highest value is $0.33$.

Figure 3. The relative error of ERM for $n=10,20,\dots,50$ for the Uniform and
Gaussian distributions. The first row shows the results for the balanced case
while the second row shows the results for unbalanced case.

##  7\. Conclusion and Future Works

In this paper, we introduced the Extended Ranking Mechanisms, a generalization
of Ranking Mechanisms introduced in Aziz et al. (2020b). After establishing
the conditions under which ERMs remain truthful, we examined them from a
Bayesian Mechanism Design perspective. Specifically, we characterized the
limit of the Bayesian approximation ratio for every truthful ERM in terms of
the probability distribution $\mu$, the p.c.v. $\@vec{q}$, and the mechanism’s
parameters, namely $\pi$ and $\@vec{p}$. We also delved into the study of
optimal ERMs. We have shown that such a mechanism exists and characterized it
via a minimization problem, which we solved in two relevant frameworks.
Lastly, we conducted extensive numerical experiments to validate our findings,
from which we inferred that a well-tuned ERM consistently outperforms all
other known mechanisms.

For future works, we aim to extend our studies to include other relevant
metrics, such as the Maximum Cost or the $l_{p}$-costs. Another interesting
extension would be to extend the ERMs to handle problems in higher dimensions
using the decomposition proposed in Auricchio et al. (2018). Lastly, we plan
to study the connections between the Optimal Transportation problem and other
Mechanism Design problems.

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

## References

  * (1)
  * Ahmadi-Javid et al. (2017) Amir Ahmadi-Javid, Pardis Seyedi, and Siddhartha S Syam. 2017\.  A survey of healthcare facility location.  _Computers & Operations Research_ 79 (2017), 223–263.
  * Alon et al. (2010) Noga Alon, Michal Feldman, Ariel D. Procaccia, and Moshe Tennenholtz. 2010.  Strategyproof Approximation of the Minimax on Networks.  _Mathematics of Operations Research_ 35, 3 (2010), 513–526.
  * Auricchio et al. (2018) Gennaro Auricchio, Federico Bassetti, Stefano Gualandi, and Marco Veneroni. 2018.  Computing Kantorovich-Wasserstein Distances on $d$-dimensional histograms using $(d+1)$-partite graphs.  _Advances in Neural Information Processing Systems_ 31 (2018), 2441–2469.
  * Auricchio and Veneroni (2022) Gennaro Auricchio and Marco Veneroni. 2022.  On the Structure of Optimal Transportation Plans between Discrete Measures.  _Applied Mathematics & Optimization_ 85, 3 (2022), 42\.
  * Aziz et al. (2020b) Haris Aziz, Hau Chan, Barton Lee, Bo Li, and Toby Walsh. 2020b.  Facility location problem with capacity constraints: Algorithmic and mechanism design perspectives. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 34. MIT Press, New York, 1806–1813.
  * Aziz et al. (2020a) Haris Aziz, Hau Chan, Barton E Lee, and David C Parkes. 2020a.  The capacity constrained facility location problem.  _Games and Economic Behavior_ 124 (2020), 478–490.
  * Bahadur (1966) R. R. Bahadur. 1966\.  A Note on Quantiles in Large Samples.  _The Annals of Mathematical Statistics_ 37, 3 (1966), 577 – 580.
  * Balcik and Beamon (2008) B. Balcik and B. M. Beamon. 2008.  Facility location in humanitarian relief.  _International Journal of Logistics Research and Applications_ 11, 2 (2008), 101–121.
  * Barda et al. (1990) O Haluk Barda, Joseph Dupuis, and Pierre Lencioni. 1990\.  Multicriteria location of thermal power plants.  _European Journal of Operational Research_ 45, 2-3 (1990), 332–346.
  * Bobkov and Ledoux (2019) Sergey Bobkov and Michel Ledoux. 2019.  _One-dimensional empirical measures, order statistics, and Kantorovich transport distances_. Vol. 261.  American Mathematical Society, Providence, Rhode Island.
  * Brandt et al. (2016) Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D Procaccia. 2016\.  _Handbook of computational social choice_.  Cambridge University Press.
  * Chan et al. (2021) Hau Chan, Aris Filos-Ratsikas, Bo Li, Minming Li, and Chenhao Wang. 2021.  Mechanism Design for Facility Location Problems: A Survey. In _30th International Joint Conference on Artificial Intelligence_. International Joint Conferences on Artificial Intelligence Organization, 4356–4365.
  * Chawla et al. (2007) Shuchi Chawla, Jason D Hartline, and Robert Kleinberg. 2007\.  Algorithmic pricing via virtual valuations. In _Proceedings of the 8th ACM Conference on Electronic Commerce_. ACM, New York, 243–251.
  * Chawla et al. (2010) Shuchi Chawla, Jason D Hartline, David L Malec, and Balasubramanian Sivan. 2010.  _Multi-parameter mechanism design and sequential posted pricing_.  ACM, New York. 311–320 pages.
  * Chawla and Sivan (2014) Shuchi Chawla and Balasubramanian Sivan. 2014.  Bayesian algorithmic mechanism design.  _ACM SIGecom Exchanges_ 13, 1 (2014), 5–49.
  * Church and Garfinkel (1978) Richard L Church and Robert S Garfinkel. 1978.  Locating an obnoxious facility on a network.  _Transportation science_ 12, 2 (1978), 107–118.
  * David and Nagaraja (2004) Herbert A David and Haikady N Nagaraja. 2004.  _Order statistics_.  John Wiley & Sons, New York.
  * De Haan and Taconis-Haantjes (1979) Laurens De Haan and Elselien Taconis-Haantjes. 1979\.  On Bahadur’s representation of sample quantiles.  _Ann. Inst. Statist. Math_ 31, Part A (1979), 299–308.
  * Dokow et al. (2012) Elad Dokow, Michal Feldman, Reshef Meir, and Ilan Nehama. 2012.  Mechanism design on discrete lines and cycles. In _EC_. ACM, New York, 423–440.
  * Ensthaler and Giebe (2014) Ludwig Ensthaler and Thomas Giebe. 2014.  Bayesian optimal knapsack procurement.  _European Journal of Operational Research_ 234, 3 (2014), 774–779.
  * Feigenbaum et al. (2017) Itai Feigenbaum, Jay Sethuraman, and Chun Ye. 2017\.  Approximately optimal mechanisms for strategyproof facility location: Minimizing lp norm of costs.  _Mathematics of Operations Research_ 42, 2 (2017), 434–447.
  * Feldman et al. (2016) Michal Feldman, Amos Fiat, and Iddan Golomb. 2016\.  On voting and facility location. In _Proceedings of the 2016 ACM Conference on Economics and Computation_. ACM, New York, 269–286.
  * Feldman and Wilf (2013) Michal Feldman and Yoav Wilf. 2013.  Strategyproof facility location and the least squares objective. In _EC_. ACM, New York, 873–890.
  * Filimonov and Meir (2021) Alina Filimonov and Reshef Meir. 2021.  Strategyproof Facility Location Mechanisms on Discrete Trees. In _AAMAS_. ACM, New York, 510–518.
  * Filos-Ratsikas et al. (2015) Aris Filos-Ratsikas, Minming Li, Jie Zhang, and Qiang Zhang. 2015.  Facility Location with Double-Peaked Preferences. In _Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25-30, 2015, Austin, Texas, USA_ , Blai Bonet and Sven Koenig (Eds.). AAAI Press, 893–899.  https://doi.org/10.1609/AAAI.V29I1.9297
  * Gairing et al. (2005) Martin Gairing, Burkhard Monien, and Karsten Tiemann. 2005\.  Selfish routing with incomplete information. In _Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures_. ACM, New York, 203–212.
  * Hartline et al. (2013) Jason D Hartline et al. 2013\.  Bayesian mechanism design.  _Foundations and Trends® in Theoretical Computer Science_ 8, 3 (2013), 143–263.
  * Hartline and Lucier (2010) Jason D Hartline and Brendan Lucier. 2010.  Bayesian algorithmic mechanism design. In _Proceedings of the forty-second ACM symposium on Theory of computing_. ACM, New York, 301–310.
  * Hartline and Roughgarden (2009) Jason D Hartline and Tim Roughgarden. 2009.  Simple versus optimal mechanisms. In _Proceedings of the 10th ACM conference on Electronic commerce_. ACM, New York, 225–234.
  * Hastie et al. (2009) Trevor Hastie, Robert Tibshirani, Jerome H Friedman, and Jerome H Friedman. 2009.  _The elements of statistical learning: data mining, inference, and prediction_. Vol. 2.  Springer, Berlin.
  * Kantorovich (2006) Leonid V Kantorovich. 2006\.  On the translocation of masses.  _Journal of mathematical sciences_ 133, 4 (2006), 1381–1382.
  * Kiefer (1967) J Kiefer. 1967.  On Bahadur’s representation of sample quantiles.  _The Annals of Mathematical Statistics_ 38, 5 (1967), 1323–1342.
  * Lu et al. (2010) Pinyan Lu, Xiaorui Sun, Yajun Wang, and Zeyuan Allen Zhu. 2010\.  Asymptotically optimal strategy-proof mechanisms for two-facility games. In _EC_. ACM, New York, 315–324.
  * Lu et al. (2009) Pinyan Lu, Yajun Wang, and Yuan Zhou. 2009.  Tighter Bounds for Facility Games. In _WINE_ _(Lecture Notes in Computer Science, Vol. 5929)_. Springer, Berlin, 137–148.
  * Lucier and Borodin (2010) Brendan Lucier and Allan Borodin. 2010.  Price of anarchy for greedy auctions. In _Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms_. SIAM, Society for Industrial and Applied Mathematics, Philadelphia, 537–553.
  * Mei et al. (2016) Lili Mei, Deshi Ye, and Guochuan Zhang. 2016.  Mechanism Design for One-Facility Location Game with Obnoxious Effects. In _International Workshop on Frontiers in Algorithmics_. Springer, Berlin, 172–182.
  * Meir (2019) Reshef Meir. 2019\.  Strategyproof Facility Location for Three Agents on a Circle. In _SAGT_ _(Lecture Notes in Computer Science, Vol. 11801)_. Springer, Berlin, 18–33.
  * Melo et al. (2009) M.T. Melo, S. Nickel, and F. Saldanha da Gama. 2009\.  Facility location and supply chain management – A review.  _European Journal of Operational Research_ 196, 2 (2009), 401–412.
  * Nisan and Ronen (1999) Noam Nisan and Amir Ronen. 1999.  Algorithmic mechanism design. In _Proceedings of the thirty-first annual ACM symposium on Theory of computing_. ACM, New York, 129–140.
  * Procaccia and Tennenholtz (2013) Ariel D Procaccia and Moshe Tennenholtz. 2013.  Approximate mechanism design without money.  _ACM Transactions on Economics and Computation (TEAC)_ 1, 4 (2013), 1–26.
  * Santambrogio (2015) Filippo Santambrogio. 2015\.  Optimal transport for applied mathematicians.  _Birkäuser, NY_ 55, 58-63 (2015), 94.
  * Sui et al. (2013) Xin Sui, Craig Boutilier, and Tuomas Sandholm. 2013.  Analysis and Optimization of Multi-Dimensional Percentile Mechanisms.. In _IJCAI_. Citeseer, AAAI press, Massachusetts, 367–374.
  * Tang et al. (2020) Pingzhong Tang, Dingli Yu, and Shengyu Zhao. 2020.  Characterization of Group-strategyproof Mechanisms for Facility Location in Strictly Convex Space. In _EC_. ACM, New York, 133–157.
  * Villani (2009) Cédric Villani. 2009\.  _Optimal transport: old and new_. Vol. 338.  Springer, Berlin.
  * Walsh (2022) Toby Walsh. 2022\.  Strategy Proof Mechanisms for Facility Location with Capacity Limits. In _Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22_. International Joint Conferences on Artificial Intelligence Organization, Massachusetts, 527–533.
  * Wilks (2012) Samuel Stanley Wilks. 2012\.  _Mathematical statistics_.  Read Books Ltd, New York.
  * Yan (2011) Qiqi Yan. 2011.  Mechanism design via correlation gap. In _Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms_. SIAM, San Francisco, 710–719.
  * Zampetakis and Zhang (2023) Emmanouil Zampetakis and Fred Zhang. 2023.  Bayesian Strategy-Proof Facility Location via Robust Estimation. In _International Conference on Artificial Intelligence and Statistics_. PMLR, London, 4196–4208.

## Appendix

In this appendix, we report all the missing material. In Appendix A, we report
the missing proofs. In Appendix B, we study the optimal ERM for symmetric
measures. In Appendix C, we report the Bayesian study of the InnerPoint
Mechanism and Extended Endpoint Mechanism. In Appendix D, we report the
additional numerical results.

##  Appendix A Missing Proofs

###### Proof of Theorem 3.1.

Let $\@vec{x}$ be the vector that contains the agents’ reports ordered in a
non-decreasing order. First, we show that every time the system (3) holds,
then $\mathtt{ERM}^{(\pi,\@vec{p})}$ does not overload any facility. By
definition of $\mathtt{ERM}^{(\pi,\@vec{p})}$, we have that every agent is
assigned to its closest facility. Furthermore, every facility shares its
position with an agent, depending on the vector $\@vec{p}$. Let us now focus
the $j$-th facility, which, by definition, it is placed at
$y_{j}=x_{\left\lfloor p_{j}(n-1)\right\rfloor+1}$. Without loss of
generality, let us assume that $1<j<m$, thus there are two facilities, namely
$y_{j-1}$ and $y_{j+1}$, such that $y_{j-1}\leq y_{j}\leq y_{j+1}$. The
maximum number of agents whose report is closer to $y_{j}$ is $\left\lfloor
p_{j+1}(n-1)\right\rfloor-\left\lfloor p_{j-1}(n-1)\right\rfloor-1$. Since the
capacity of the $j$-th facility is $\left\lfloor
q_{\pi(j)}(n-1)\right\rfloor+1$, we have that the facility at $y_{j}$ cannot
be overloaded if and only if $\left\lfloor
q_{\pi(j)}(n-1)\right\rfloor+1\geq\left\lfloor
p_{j+1}(n-1)\right\rfloor-\left\lfloor p_{j-1}(n-1)\right\rfloor-1$. We now
show that the latter condition is implied by $q_{\pi(j)}\geq p_{j+1}-p_{j-1}$
or, equivalently, $q_{\pi(j)}(n-1)\geq(p_{j+1}-p_{j-1})(n-1)$. Indeed, it is
easy to see that $\left\lfloor q_{\pi(j)}(n-1)\right\rfloor+1\geq
q_{\pi(j)}(n-1)\geq\left\lfloor q_{\pi(j)}(n-1)\right\rfloor$, thus we have

$\displaystyle\left\lfloor q_{\pi(j)}(n-1)\right\rfloor+1$ $\displaystyle\geq
q_{\pi(j)}(n-1)\geq(p_{j+1}-p_{j-1})(n-1)$ $\displaystyle\geq\left\lfloor
p_{j+1}(n-1)\right\rfloor-\left\lfloor p_{j-1}(n-1)\right\rfloor-1.$

Through a similar argument, we deal with $y_{1}$ and $y_{m}$.

We now show the inverse implication, i.e. if $(\pi,\@vec{p})$ satisfies system
(3.1), then $\mathtt{ERM}^{(\pi,\@vec{p})}$ is feasible. Toward a
contradiction, assume that one of the inequalities does not holds. Without
loss of generality, assume that $p_{2}>q_{\pi(1)}$, there then exists a value
$N\in\mathbb{N}$ such that $p_{2}-\frac{2}{N-1}>q_{\pi(1)}$. Let us then
consider $n=N$, then it holds $\left\lfloor
p_{2}(N-1)\right\rfloor-1>\left\lfloor q_{\pi(1)}(N-1)\right\rfloor$, hence
$\left\lfloor p_{2}(N-1)\right\rfloor>\left\lfloor
q_{\pi(1)}(N-1)\right\rfloor+1$. Let us then consider the instance
$\@vec{x}\in\mathbb{R}^{N}$ defined as $x_{i}=0$ if $i=1,\dots,\left\lfloor
p_{2}(N-1)\right\rfloor$ and $x_{i}=1$ otherwise. On this instance
$\mathtt{ERM}^{(\pi,\@vec{p})}$ place a facility at $y_{1}=0$ and all the
others at $1$, the facility at $0$ has capacity $\left\lfloor
q_{\pi(1)}(N-1)\right\rfloor+1$. By definition, the number of agents whose
closest facility is $y_{1}$ is $\left\lfloor
p_{2}(N-1)\right\rfloor>\left\lfloor q_{\pi(1)}(N-1)\right\rfloor+1$, which
contradicts the feasibility of the mechanism. ∎

###### Proof of Theorem 3.2.

Let $\@vec{q}$ be a p.c.v. and let $\mathtt{ERM}^{(\pi,\@vec{p})}$ be a
feasible ERM. Toward a contradiction, let $\@vec{x}$ be an instance in which
an agent is able to manipulate. Without loss of generality, let us assume that
the manipulative agent’s real position is $x_{i}$. Since every agent is
assigned to the facility that is closer to the position they report, the
manipulation performed by the agent at $x_{i}$ must alter the position of the
facilities, as otherwise the cost of the manipulative agent cannot decrease.
We notice that the positions of the facilities are determined through the same
routine of the Percentile mechanisms, Sui et al. (2013). Owing to the
truthfulness of the Percentile mechanisms for the $m$-FLP, we infer that no
agent can misreport in such a way that a facility gets closer to its position,
which concludes the proof. ∎

###### Proof of Corollary 3.3.

It follows from Theorem 3.1, indeed if $\mathtt{ERM}^{(\pi,\@vec{p})}$ is
feasible, then (3) holds. If we sum all the inequalities of system (3), we get

$\displaystyle\sum_{j\in[m]}q_{\pi(j)}=\sum_{j\in[m]}q_{j}$ $\displaystyle\geq
p_{2}+(p_{3}-p_{1})+\dots$
$\displaystyle\quad\dots+(p_{m}-p_{m-2})+(1-p_{m-1})$
$\displaystyle=1+p_{m}-p_{1},$

since $\@vec{p}$ is ordered increasingly. Thus, if

$p_{m}-p_{1}=\big{(}\max_{j\in[m]}p_{j}-\min_{j\in[m]}p_{j}\big{)}>\sum_{j\in[m]}q_{j}-1$

holds, system (3) does not, which concludes the proof. ∎

###### Proof of Lemma 4.1.

First, we show that (7) holds. Given $\@vec{x}$ and $\@vec{q}$, let us
consider an optimal solution to the $m$-CFLP. In particular, we denote with
$\@vec{y}$ be the vector containing $m$ positions on the line, $\sigma$ the
permutation that determines how to distribute the facilities among the
positions in $\@vec{y}$, and $\Gamma$ a matching that assigns every agent to a
facility without overloading the facilities. Let us now consider the following
transportation plan

$\pi_{x_{i},y_{j}}=\begin{cases}\frac{1}{n}\quad\text{if}\quad(i,j)\in\Gamma,\\\
0\quad\text{otherwise.}\end{cases}$

By definition of $\Gamma$, we have that
$\sum_{j\in[m]}\pi_{x_{i},y_{j}}=\frac{1}{n}$ and

$\sum_{i\in[n]}\pi_{x_{i},y_{j}}=\frac{k_{j}}{n}\leq\frac{c_{\sigma(j)}}{n}=q_{\sigma(j)},$

where $k_{j}$ is the degree of $j\in[m]$ according to $\Gamma$. Thus, if we
set $\nu_{n,m}=\sum_{j\in[m]}\frac{k_{j}}{n}\delta_{y_{j}}$, we have that
$\nu_{n,m}\in\mathcal{P}_{\sigma,m}(\mathbb{R})$. It is easy to see that
$SC(\@vec{x})=\sum_{i\in[n],j\in[m]}|x_{i}-y_{j}|\pi_{x_{i},y_{j}}\geq
W_{1}(\mu_{n},\nu_{n,m})$, hence

$SC_{opt}(\@vec{x})\geq\min_{\sigma\in\mathcal{S}_{m}}\min_{\zeta\in\mathcal{P}_{\sigma,m}(\mathbb{R})}W_{1}(\mu_{n},\zeta).$

To conclude, we show that the inverse inequality holds.

Let $(\sigma,\nu_{m,n})$ be a minimizer of the right hand side of (5), we show
that there exists a set of $m$ locations $\@vec{y}$, a permutation
$\sigma^{\prime}$, and a matching $\Gamma$ whose Social Cost is
$W_{1}(\mu_{n},\nu_{n,m})$. First, let us set $\@vec{y}=(y_{1},\dots,y_{m})$,
where $\\{y_{j}\\}_{j\in[m]}$ is the support of $\nu_{m,n}$. Without loss of
generality, we assume that $q_{j}=\frac{c_{j}}{n}$, thus there exists an
optimal transportation plan $\pi$ between $\mu_{n}$ and $\nu_{m,n}$ such that
for every $i\in[n]$, there exists a unique $j\in[m]$ such that
$\pi_{x_{i},y_{j}}\neq 0$, see Auricchio and Veneroni (2022). Notice that, by
definition of transportation plan, if $\pi_{x_{i},y_{j}}\neq 0$ for only a
couple of values $i\in[n]$, $j\in[m]$, then $\pi_{x_{i},y_{j}}=\frac{1}{n}$.
Thus, the set
$\Gamma=\\{(i,j)\in[n]\times[m];\;\pi_{x_{i},y_{j}}=\frac{1}{n}\\}$ is well
defined. Since for every $i\in[n]$ we have that there exists a unique
$j\in[m]$ for which it holds $\pi_{x_{i},y_{j}}=\frac{1}{n}$, we have that the
degree of every $i\in[n]$ is one. Since
$\sum_{i\in[n]}\pi_{x_{i},y_{j}}=(\nu_{m,n})_{j}\leq\frac{c_{\sigma(j)}}{n}$,
we have that the degree of every $j\in[m]$ is less than $c_{\sigma(j)}$. Thus
the triplet $(\@vec{y},\sigma,\Gamma)$ is a feasible location for the
$m$-CFLP. Since the Social Cost of $(\@vec{y},\sigma,\mu)$ is equal to
$\sum_{i\in[n],j\in[m]}|x_{i}-y_{j}|\pi_{x_{i},y_{j}}=W_{1}(\mu_{n},\nu_{m,n})$,
we have that

$\min_{\sigma\in\mathcal{S}_{m}}\min_{\zeta\in\mathcal{P}_{\sigma,m}(\mathbb{R})}W_{1}(\mu_{n},\zeta)=W_{1}(\mu_{n},\nu_{m,n})\geq
SC_{opt}(\@vec{x}),$

which concludes the proof.

Notice that, since
$\min_{\sigma\in\mathcal{S}_{m}}\min_{\zeta\in\mathcal{P}_{\sigma,m}(\mathbb{R})}W_{1}(\mu_{n},\zeta)=SC_{opt}(\@vec{x})$
holds, we can refine the previous argument and show that, given an optimal
facility location for the $m$-CFLP it is possible to build a solution to the
minimization problem in the right hand side of (4). Vice-versa, given a
solution to the minimization problem in the right hand side of (4), it is
possible to build an optimal facility location for the $m$-CFLP.

Using the same argument and the same constructions, it is possible to show
that (5) holds. ∎

###### Proof of Theorem 4.2.

To complete the proof of Theorem 4.2, we need to prove the following:  (i)
First, we need to show that a solution $\nu_{m}$ to problem (7) always exists.
This would complete the proof of the first step.  (ii) We need to show that
there always exists a solution $\nu_{\@vec{p}}$ to problem (8), and  (iii) we
need to show that
$\lim_{n\to\infty}\mathbb{E}[W_{1}(\nu_{\@vec{x},\@vec{p}},\phi)]\to 0$ when
$n\to\infty$.

(i) Existence of a solution $\nu_{m}$. Since for every $m$ the number of
permutation is finite, it suffices to show that, for every
$\sigma\in\mathcal{S}_{m}$ there exists a solution to the problem

$\min_{\zeta\in\mathcal{P}_{\sigma,m}(\mathbb{R})}W_{1}(\mu,\zeta).$

Since $\mu$ has finite first moment, i.e. $\int_{\mathbb{R}}|x|d\mu<+\infty$,
the minimization problem is well-posed and its minimum is finite. Moreover,
the set $\mathcal{P}_{\sigma,m}(\mathbb{R})$ is a closed set in
$\mathcal{P}(\mathbb{R})$, thus a solution to the minimization problem does
exist (although it may not be unique).

(ii) Existence of a solution $\nu_{\@vec{p}}$. We show this point by
constructing a minimizer to problem (8). Given $\@vec{p}$, let us set
$y_{j}=F_{\mu}^{[-1]}(p_{j})$. For every
$\lambda=\sum_{j\in[m]}\lambda_{j}\delta_{y_{j}}$ such that
$\sum_{j\in[m]}\lambda_{j}=1$, we have that

$W_{1}(\mu,\lambda)=\sum_{j\in[m]}\int_{F_{\mu}^{[-1]}\big{(}\sum_{l=1}^{j-1}\lambda_{l}\big{)}}^{F_{\mu}^{[-1]}\big{(}\sum_{l=1}^{j}\lambda_{l}\big{)}}|x-y_{j}|d\mu\geq\int_{\mathbb{R}}\min_{j\in[m]}|x-y_{j}|d\mu.$

Let us now consider the measure

$\lambda_{min}=\sum_{j\in[m]}\Big{(}F_{\mu}(z_{j})-F_{\mu}(z_{j-1})\Big{)}\delta_{y_{j}},$

where $z_{j}=\frac{y_{j+1}+y_{j}}{2}$ if $j=2,\dots,m-1$, $z_{0}=-\infty$ and
$z_{m}=+\infty$. We then have

$\displaystyle W_{1}(\mu,\lambda_{min})$
$\displaystyle=\sum_{j\in[m]}\int_{F_{\mu}^{[-1]}\big{(}\sum_{l=1}^{j-1}F_{\mu}(z_{l})-F_{\mu}(z_{l-1})\big{)}}^{F_{\mu}^{[-1]}\big{(}\sum_{l=1}^{j}F_{\mu}(z_{l})-F_{\mu}(z_{l-1})\big{)}}|x-y_{j}|d\mu$
$\displaystyle=\sum_{j\in[m]}\int_{z_{j-1}}^{z_{j}}|x-y_{j}|d\mu$
$\displaystyle=\int_{\mathbb{R}}\min_{j\in[m]}|x-y_{j}|d\mu.$

Thus $\lambda_{min}$ is a minimizer.

(iii) Convergence of $\mathbb{E}[W_{1}(\nu_{\@vec{x},\@vec{p}},\phi)]$. We
recall that

$\phi=\sum_{j\in[m]}(\nu_{\@vec{x},\@vec{p}})_{j}\delta_{y_{j}}.$

Since $(\nu_{\@vec{x},\@vec{p}})_{j}\leq 1$ for every $j\in[m]$, we infer

$\mathbb{E}[W_{1}(\nu_{\@vec{x},\@vec{p}},\phi)]\leq\sum_{j\in[m]}\mathbb{E}[|y_{\@vec{x},j}-y_{j}|],$

where $y_{\@vec{x},j}=x_{\left\lfloor p_{j}(n-1)\right\rfloor+1}$ and
$y_{j}=F_{\mu}^{[-1]}(p_{j})$. Using Bahadur’s representation formula (see
Bahadur (1966) and De Haan and Taconis-Haantjes (1979)), we have that

$X_{\left\lfloor(n-1)p_{j}\right\rfloor+1}-F_{\mu}^{[-1]}(p_{j})=\frac{S_{n}(F_{\mu}^{[-1]}(p_{j}))-p_{j}}{\rho_{\mu}(F_{\mu}^{[-1]}(p_{j}))}+R_{n},$
(12)

where $R_{n}$ is the rest of the Bahadur’s formula, for which holds $R_{n}\leq
O(n^{-\frac{3}{4}})$ with probability $1$, $\rho_{\mu}$ is the density of
$\mu$, and $S_{n}(t)=\frac{1}{n}\sum_{i=1}^{n}\mathbb{I}(X_{i})_{\\{X_{i}\leq
t\\}}$ where

$\mathbb{I}(X_{i})_{\\{X_{i}\leq t\\}}=\begin{cases}1\quad\text{if}\quad
X_{i}\leq t,\\\ 0\quad\text{otherwise.}\end{cases}$

Since by hypothesis the density of $\mu$ is always strictly positive on the
interior of the support of $\mu$ and $p_{j}\in(0,1)$ for every $j=1,\dots,m$,
we have

$\displaystyle\mathbb{E}[|y_{\@vec{x},j}-y_{j}|]$ $\displaystyle\leq
K\mathbb{E}\big{[}|S_{n}(F_{\mu}^{[-1]}(p_{j}))-p_{j}|\big{]}+\mathbb{E}[|R_{n}|]$
$\displaystyle\leq
K\mathbb{E}\bigg{[}\frac{1}{n}|\sum_{i=1}^{n}(\mathbb{I}(X_{i})_{\\{X_{i}\leq
F_{\mu}^{[-1]}(p_{j})\\}}-p_{j})|\bigg{]}+Cn^{-\frac{3}{4}}$
$\displaystyle\leq
K\mathbb{E}\Big{[}\Big{|}\sum_{i=1}^{n}\frac{(\mathbb{I}(X_{i})_{\\{X_{i}\leq
F_{\mu}^{[-1]}(p_{j})\\}})-p_{j})}{n}\Big{|}\Big{]}+Cn^{-\frac{3}{4}}$
$\displaystyle\leq\frac{K}{\sqrt{n}}Var(\mathbb{I}(X_{1})_{\\{X_{1}\leq
F_{\mu}^{[-1]}(p_{j})\\}})+Cn^{-\frac{3}{4}},$

since the $X_{i}$ are i.i.d. and $\mathbb{I}(X_{i})_{\\{X_{i}\leq
F_{\mu}^{[-1]}(p_{j})\\}}$ is a Bernoulli variable that with probability
$p_{j}$ is equal to $1$ and equal to $0$ otherwise hence its variance is
finite. We then conclude that
$\mathbb{E}[W_{1}(\nu_{\@vec{x},\@vec{p}},\phi)]$ converges to $0$. Similarly,
it is possible to show that $\mathbb{E}[W_{1}(\nu_{\@vec{p}},\psi)]$ converges
to $0$. ∎

###### Proof of Corollary 4.3.

Let $\nu_{m}$ be the solution to (7) and let $\nu^{(\alpha,\beta)}_{m}$ be the
solution to

$\min_{\sigma\in\mathcal{S}_{m}}\min_{\zeta\in\mathcal{P}_{\sigma,m}(\mathbb{R})}W_{1}(\mu_{\alpha,\beta},\zeta)$

Let us fix $L(x)=\alpha x+\beta$. Since $\alpha>0$, $L$ is a bijective and
monotone-increasing function. We denote the inverse function of $L$ with $H$.
It is well-known that if $X$ is a random variable whose law is $\mu$, then the
law of $L(X)=\alpha X+\beta$ is $L_{\\#}\mu$. We recall that $L_{\\#}\mu$ is
the pushforward of the measure $\mu$, defined as $L_{\\#}\mu(A)=\mu(H(A))$,
see Villani (2009). By definition, we have that
$L_{\\#}\delta_{x}=\delta_{\alpha x+\beta}$, thus
$L_{\\#}(\sum_{j\in[m]}\lambda_{j}\delta_{x_{j}})=\sum_{j\in[m]}\lambda_{j}\delta_{\alpha
x_{j}+\beta}$. We now show that $\nu^{(\alpha,\beta)}_{m}=L_{\\#}\nu_{m}$.
First, notice that, since $\alpha>0$ the function $L$ is monotone increasing,
thus if $\nu_{m}\in\mathcal{P}_{\sigma,m}(\mathbb{R})$, then
$L_{\\#}\nu_{m}\in\mathcal{P}_{\sigma,m}(\mathbb{R})$. Toward a contradiction,
let us now assume that $\gamma$ is such that

$W_{1}(\gamma,L_{\\#}\mu)<W_{1}(L_{\\#}\nu_{m},L_{\\#}\mu).$

Let us now define $\eta=H_{\\#}\gamma\in\mathcal{P}_{k}(\mathbb{R})$. Since
$H$ is also monotone increasing, we have
$\gamma\in\mathcal{P}_{\sigma,m}(\mathbb{R})$ and $\gamma=L_{\\#}\eta$.
Furthermore, by the properties of the Wasserstein distance, we have

$W_{1}(L_{\\#}\eta,L_{\\#}\mu)=\alpha W_{1}(\eta,\mu)$ (13)

and

$W_{1}(L_{\\#}\nu_{m},L_{\\#}\mu)=\alpha W_{1}(\nu_{m},\mu).$

In particular, we get

$W_{1}(\eta,\mu)<W_{1}(\nu_{m},\mu),$

which contradicts the optimality of $\nu_{m}$. We therefore conclude that
$L_{\\#}\nu_{m}=\nu^{(\alpha,\beta)}_{m}$ and that

$W_{1}(\nu^{(\alpha,\beta)}_{m}\mu_{\alpha,\beta})=\alpha W_{1}(\nu_{m},\mu).$

To conclude, we observe that

$\displaystyle\min_{\lambda_{j}\leq
q_{\sigma(j)},\sum_{j\in[m]}\lambda_{j}=1}$ $\displaystyle
W_{1}\Big{(}\mu_{\alpha,\beta},\sum_{j\in[m]}\lambda_{j}\delta_{\alpha
y_{j}+\beta}\Big{)}$ $\displaystyle\quad=\alpha\min_{\lambda_{j}\leq
q_{\sigma(j)},\sum_{j\in[m]}\lambda_{j}=1}W_{1}\Big{(}\mu,\sum_{j\in[m]}\lambda_{j}\delta_{y_{j}}\Big{)},$

for any set of $m$ values $\\{y_{j}\\}_{j\in[m]}$. We then observe that
$F^{[-1]}_{\mu_{\alpha,\beta}}(p_{j})=\alpha F^{[-1]}_{\mu}(p_{j})+\beta$,
thus

$\displaystyle\min_{\lambda_{j}\leq
q_{\sigma(j)},\sum_{j\in[m]}\lambda_{j}=1}W_{1}\Big{(}\mu_{\alpha,\beta},\sum_{j\in[m]}\lambda_{j}\delta_{\alpha
F^{[-1]}_{\mu}(p_{j})+\beta}\Big{)}$
$\displaystyle\quad\quad=\min_{\lambda_{j}\leq
q_{\sigma(j)},\sum_{j\in[m]}\lambda_{j}=1}W_{1}\Big{(}\mu_{\alpha,\beta},\sum_{j\in[m]}\lambda_{j}\delta_{F^{[-1]}_{\mu_{\alpha,\beta}}(p_{j})}\Big{)}.$

Finally, we notice that by taking the ratio of the two expectations, the
factor $\alpha$ evens out. Thus the limit of the Bayesian approximation ratio
of any ERM does not depend on the values of $\alpha$ nor $\beta$. ∎

###### Proof of Theorem 5.1.

Since for every $m$ there are a finite number of $\pi\in\mathcal{S}_{m}$, it
suffices to show that for every $\sigma\in\mathcal{S}_{m}$ there exists a
solution to problem

$\displaystyle\min_{\@vec{p}\in(0,1)^{m}}$ $\displaystyle
W_{1}\Big{(}\mu,\sum_{j\in[m]}\eta_{j}(\@vec{p})\delta_{F_{\mu}^{[-1]}(p_{j})}\Big{)}$
(14) such that $\displaystyle p_{j+1}-p_{j-1}\leq
q_{\pi(j)}\;\;\text{for}\;\;j=2,\dots,m-1,$ $\displaystyle p_{1}\leq
q_{\pi(q)},\;\text{and}\;\;p_{m}\leq 1-q_{\pi(m)},$

where

$\displaystyle\eta_{j}(\@vec{p})=$ $\displaystyle
F_{\mu}\Big{(}\frac{F^{[-1]}_{\mu}(p_{j+1})+F^{[-1]}_{\mu}(p_{j})}{2}\Big{)}$
$\displaystyle\quad-
F_{\mu}\Big{(}\frac{F^{[-1]}_{\mu}(p_{j})+F^{[-1]}_{\mu}(p_{j-1})}{2}\Big{)}$

for $j=2,\dots,m-1$,

$\eta_{1}(\@vec{p})=F_{\mu}\Big{(}\frac{F^{[-1]}_{\mu}(p_{2})+F^{[-1]}_{\mu}(p_{1})}{2}\Big{)},$

and $\eta_{m}(\@vec{p})=1-\eta_{m-1}(\@vec{p})$. By the same argument used
during the second step of proof of Theorem 4.2, we have that, given
$\@vec{p}$, the measure

$\eta(\@vec{p})=\sum_{j\in[m]}\eta_{j}(\@vec{p})\delta_{F_{\mu}^{[-1]}(p_{j})}$

is such that

$W_{1}(\mu,\eta(\@vec{p}))=\min_{\lambda_{j}\leq
q_{\sigma(j)},\sum_{j\in[m]}\lambda_{j}=1}W_{1}\Big{(}\mu,\sum_{j\in[m]}\lambda_{j}\delta_{F_{\mu}^{[-1]}(p_{j})}\Big{)}.$

First, we consider the case in which $\mu$ has a compact support, hence the
minimization problem is well defined over the closed set $[0,1]^{m}$, since
the values $F_{\mu}^{[-1]}(0)$ and $F_{\mu}^{[-1]}(1)$ are well-defined.
Notice that $[0,1]^{m}$ is compact, thus if we show that the objective
function of the problem is continuous with respect to $\@vec{p}$ we conclude
the proof for this case. Let $\@vec{p}^{(n)}$ be a succession of feasible
vectors that converges to $\@vec{p}$. By the assumptions on $\mu$, we have
that both $F_{\mu}$ and $F_{\mu}^{[-1]}$ are continuous, hence

$\@vec{p}\to\eta_{j}(\@vec{p})$

is continuous for every $j\in[m]$. Likewise, the function

$\@vec{p}\to y_{j}(\@vec{p}):=F_{\mu}^{[-1]}(p_{j})$

is continuous for every $j\in[m]$. As a consequence the sequence
$\eta_{n}=\eta(\@vec{p}^{(n)})$ weakly converges to $\eta(\@vec{p})$ in
$\mathcal{P}(\mathbb{R})$, Villani (2009). Since $W_{1}$ induces the weak
convergences Villani (2009) over $\mathcal{P}(\mathbb{R})$, we infer

$\lim_{n\to\infty}W_{1}(\mu,\eta(\@vec{p}^{(n)}))=W_{1}(\mu,\eta(\@vec{p})).$

To conclude the proof, we need to show that the minimizer, namely $\@vec{p}$,
is such that $p_{j}\neq 0,1$ for every $j\in[m]$. Toward a contradiction, let
us assume that $p_{1}=0$. Without loss of generality, let us assume that
$p_{2}>0$, thus $y_{1}<y_{2}$. By definition, we have that
$F_{\mu}^{[-1]}(p_{1})=a$ and $F_{\mu}(F_{\mu}^{[-1]}(p_{1}))=p_{1}=0$. Let us
denote with $[a,b]$ the support of $\mu$, then there exists a $\epsilon>0$
such that $a+\epsilon<F_{\mu}^{[-1]}(p_{2})$, thus

$\displaystyle\mathcal{W}(\@vec{p})$
$\displaystyle=\int_{a}^{b}\min_{j\in[m]}|x-F_{\mu}^{[-1]}(p_{j})|d\mu$
$\displaystyle=\int^{\frac{a+F_{\mu}^{[-1]}(p_{2})}{2}}_{a}(x-a)d\mu+\sum_{j>1}^{m}\int_{\frac{a+y_{2}}{2}}^{b}\min_{j>1}|x-F_{\mu}^{[-1]}(p_{j})|d\mu$
$\displaystyle>\int_{a}^{\frac{a+F_{\mu}^{[-1]}(p_{2})}{2}}|x-(a+\epsilon)|d\mu$
$\displaystyle\quad\quad+\sum_{j>1}^{m}\int_{\frac{a+F_{\mu}^{[-1]}(p_{2})}{2}}^{b}\min_{j>1}|x-F_{\mu}^{[-1]}(p_{j})|d\mu$
$\displaystyle>\int_{a}^{b}\min_{j\in[m]}|x-F_{\mu}^{[-1]}(p^{(\epsilon)}_{j})|d\mu=\mathcal{W}(\@vec{p}^{(\epsilon)}),$

where $\@vec{p}^{(\epsilon)}=(F_{\mu}(a+\epsilon),p_{2},\dots,p_{m})$, which
contradicts the optimality of $\@vec{p}$.

Let us now consider the case in which $\mu$ has unbounded support. Let
$\@vec{p}^{(n)}$ be a minimizing sequence. Up to a sub-sequence, we can assume
that the $\@vec{p}^{(n)}$ converges to $\@vec{p}$ in $[0,1]^{m}$. We now show
that $\@vec{p}\in(0,1)^{m}$. First, let us assume that there exists a
$j\in[m]$ for which $p_{j}\in(0,1)$. Without loss of generality, let us assume
that $p_{1}=0$ and that $1>p_{2}>0$ (if there are multiple entries of
$\@vec{p}$ that are equal to $0$ the study is the same). Let us now consider
$\@vec{v}^{(n)}$ be such that $v^{(n)}_{1}=p_{1}^{(n)}$ and
$v_{j}^{(n)}=p_{j}$ for $j>1$. Since $\@vec{v}^{(n)}$ and $\@vec{p}^{(n)}$
have the same limit and $\mathcal{W}$ is continuous, we have that
$\@vec{v}^{(n)}$ is a minimizing sequence. Since $p^{(n)}_{1}\to 0$, we have
that $F_{\mu}^{[-1]}(p_{1}^{(n)})\to-\infty$, thus

$\displaystyle\mathcal{W}(\@vec{p}^{(n)})$
$\displaystyle=\int_{-\infty}^{\frac{y_{1}^{(n)}+y_{2}}{2}}|x-F_{\mu}^{[-1]}(p_{1}^{(n)})|d\mu$
$\displaystyle\quad\quad+\int_{\frac{y_{1}^{(n)}+y_{2}}{2}}^{+\infty}\min_{j>1}|x-F_{\mu}^{[-1]}(p_{j})|d\mu.$

Since $F_{\mu}^{[-1]}(p_{1}^{(n)})\to-\infty$, we have that

$\mathcal{W}(\@vec{p})=\int_{-\infty}^{-\infty}\min_{j>1}|x-F_{\mu}^{[-1]}(p_{j})|d\mu.$

Let us consider the vector
$\@vec{p}^{(\epsilon)}=(\epsilon,p_{2},\dots,p_{m})$, where
$p_{2}>\epsilon>0$, then it holds

$\displaystyle\mathcal{W}(\@vec{p})$
$\displaystyle=\int_{-\infty}^{-\infty}\min_{j>1}|x-F_{\mu}^{[-1]}(p_{j})|d\mu$
$\displaystyle>\int_{-\infty}^{-\infty}\min_{j\in[m]}|x-F_{\mu}^{[-1]}(p^{(\epsilon)}_{j})|d\mu=\mathcal{W}(\@vec{p}^{(\epsilon)}),$

which contradicts the optimality of $\@vec{p}$. Through a similar argument, we
deal with the case $\@vec{p}\in\\{0,1\\}^{m}$.

Finally, we notice that the case in which the support of $\mu$ is unbounded
only from one side is similar. ∎

###### Proof of Theorem 5.3.

By Corollary 3.3, we have that any truthful ERM, namely
$\mathtt{ERM}^{(\pi,\@vec{p})}$, must be such that $\@vec{p}=(p,p,\dots,p)$
where $p\in(0,1)$. Thus to complete the proof it is sufficient to prove that
the function

$M:y\to\int_{\mathbb{R}}|x-y|d\mu$ (15)

is decreasing on $(-\infty,med(\mu))$ and increasing on $(med(\mu),+\infty)$.
We do that by computing the derivative of $M$ with respect to $y$. Without
loss of generality, let us assume that $y\in(-\infty,med(\mu))$ and let us
consider

$\lim_{h\to
0^{+}}\frac{\int_{\mathbb{R}}|x-(y+h)|d\mu-\int_{\mathbb{R}}|x-y|d\mu}{h}.$

By the linearity of the integral, we have that

$\int_{\mathbb{R}}|x-y|d\mu=\int_{-\infty}^{y}(y-x)d\mu+\int_{y}^{+\infty}(x-y)d\mu,$

similarly
$\int_{\mathbb{R}}|x-(y+h)|d\mu=\int_{-\infty}^{y+h}(y+h-x)d\mu+\int_{y+h}^{+\infty}(x-y-h)d\mu$,
so that

$\displaystyle\int_{\mathbb{R}}|x-(y+h)|d\mu$
$\displaystyle-\int_{\mathbb{R}}|x-y|d\mu$
$\displaystyle=2\int_{y}^{y+h}(y-x)d\mu+\int_{-\infty}^{y}hd\mu-\int_{y}^{+\infty}hd\mu$
$\displaystyle\leq h^{2}+\int_{-\infty}^{y}hd\mu-\int_{y}^{+\infty}hd\mu,$

thus $\partial_{y}M(y)=F_{\mu}(y)-(1-F_{\mu}(y))$. Since $y<med(\mu)$, we
infer that $\partial_{y}M(y)<0$. Similarly, it holds $\partial_{y}M(y)>0$ if
$y>med(\mu)$, which concludes the proof. ∎

###### Proof of Theorem 5.4.

Let $\@vec{q}$ be such that $0.75\geq q_{2}$. Then $\@vec{p}=(0.25,0.75)$ is a
feasible vector and it holds $\nabla\mathcal{W}(0.25,0.75)=(0,0)$. By
computing the Hessian of $\mathcal{W}$ we have that

$H\mathcal{W}(\@vec{p})=\frac{1}{2}\begin{pmatrix}3&-1\\\ -1&3\end{pmatrix},$

hence the matrix is definite positive and thus $(0.25,0.75)$ is the minimum
for this case. Let us now consider the case in which $3q_{2}-2-q_{1}\leq 0$,
in this case we have that $\partial_{y_{1}}\mathcal{W}(\@vec{p})>0$ and
$\partial_{y_{2}}\mathcal{W}(\@vec{p})<0$. Thus the gradient cannot be
perpendicular to either $\\{(1-q_{2},t)\;\text{s.t.}\;t\in[1-q_{2},q_{1}]\\}$
and $\\{(t,q_{1})\;\text{s.t.}\;t\in[1-q_{2},q_{1}]\\}$, hence the minimum is
at the vertex $(1-q_{2},q_{1})$, which concludes the proof for this case. In
the remaining cases, we have that the boundary of $T(\@vec{q})$ intersect the
line on which $\partial_{y_{2}}\mathcal{W}=0$. In particular,
$\\{\partial_{y_{2}}\mathcal{W}=0\\}$ intersects with the edge
$\\{(1-q_{2},t)\;\text{s.t.}\;t\in[1-q_{2},q_{1}]\\}$ at the point
$(1-q_{2},1-\frac{q_{2}}{3})$. On such point, we have that the gradient is
perpendicular to the boundary of $T(\@vec{q})$ and points inward, thus is a
relative minimum. To conclude, we show that this is the only possible relative
minimum. Indeed, it is easy to see that if the boundary of $T(\@vec{q})$
intersect the line $p_{2}=3p_{1}$, the gradient points outward due to the sign
of $\nabla\mathcal{W}$. We then conclude the proof. ∎

##  Appendix B Placing $2$ Facilities among Symmetrically Distributed Agents

In this Appendix we generalize the procedure described in Section 5.2. First,
we consider the case in which $m=2$ and $\mu$ is symmetric. Since $\mu$ is
symmetric, the asymptotic expected Social Cost of any feasible
$\mathtt{ERM}^{(\pi,\@vec{p})}$ does not depend on $\pi\in\mathcal{S}_{2}$.
For this reason, in what follows, we fix $\pi=Id$ and search for the best
vector $\@vec{p}=(p_{1},p_{2})$, with $p_{1}\leq p_{2}$, that induces the
optimal ERM.

First, we rewrite the objective value of problem (11) in terms of
$y_{i}=F_{\mu}^{[-1]}(p_{i})$ for $i=1,2$. Since $F_{\mu}^{[-1]}$ is monotone,
we have that $y_{1}\leq y_{2}$. We then have

$\mathcal{W}(y_{1},y_{2})=W_{1}\Bigg{(}\mu,F_{\mu}\Big{(}\frac{y_{1}+y_{2}}{2}\Big{)}\delta_{y_{1}}+\Big{(}1-F_{\mu}\Big{(}\frac{y_{1}+y_{2}}{2}\Big{)}\Big{)}\delta_{y_{2}}\Bigg{)}.$
(16)

Since both $F_{\mu}$ and $F_{\mu}^{[-1]}$ are bijective, any
$\@vec{y}=(y_{1},y_{2})$ identifies a unique $\@vec{p}$ and vice-versa. Using
the properties of the Wasserstein distances on the line Santambrogio (2015),
we obtain

$\mathcal{W}(y_{1},y_{2})=\int_{-\infty}^{\frac{y_{1}+y_{2}}{2}}|x-y_{1}|\rho_{\mu}(x)dx+\int_{\frac{y_{1}+y_{2}}{2}}^{+\infty}|x-y_{2}|\rho_{\mu}(x)dx.$
(17)

We now show that $\mathcal{W}$ is differentiable and compute its gradient.

######  Theorem B.1.

Let $\mu$ be a symmetric probability measure. Then we have that the function
$\mathcal{W}$ is differentiable and its gradient is defined by the formula

$\nabla\mathcal{W}(y_{1},y_{2})=\Bigg{(}2F_{\mu}(y_{1})-F_{\mu}\Big{(}\frac{y_{1}+y_{2}}{2}\Big{)},2F_{\mu}(y_{2})-1-F_{\mu}\bigg{(}\frac{y_{1}+y_{2}}{2}\bigg{)}\Bigg{)}.$

Furthermore, $\mathcal{W}$ is twice differentiable. Lastly, it holds

$\nabla\mathcal{W}(F_{\mu}^{[-1]}(0.25),F_{\mu}^{[-1]}(0.75))=(0,0).$

###### Proof.

Let $\@vec{q}$ be a p.c.v., due to the symmetry of $\mu$, without loss of
generality, we assume that $y_{1}\leq y_{2}$ are the positions of the facility
and that $y_{1}$ has capacity $q_{1}$ and $y_{2}$ has capacity $q_{2}$. We
then define

$\displaystyle\mathcal{W}(y_{1},y_{2})$
$\displaystyle=\int_{\mathbb{R}}\min\\{|x-y_{1}|,|x-y_{2}|\\}\rho_{\mu}(x)dx$
$\displaystyle=\int_{-\infty}^{y_{1}}(y_{1}-x)\rho_{\mu}(x)dx+\int_{y_{1}}^{\frac{y_{1}+y_{2}}{2}}(x-y_{1})\rho_{\mu}(x)dx$
$\displaystyle\quad+\int_{\frac{y_{1}+y_{2}}{2}}^{y_{2}}(y_{2}-x)\rho_{\mu}(x)dx+\int_{y_{2}}^{+\infty}(x-y_{2})\rho_{\mu}(x)dx$
$\displaystyle=A(y_{1},y_{2})+B(y_{1},y_{2})+C(y_{1},y_{2})+D(y_{1},y_{2}),$

where

$\displaystyle A(y_{1},y_{2})$
$\displaystyle=\int_{-\infty}^{y_{1}}(y_{1}-x)\rho_{\mu}(x)dx$ $\displaystyle
B(y_{1},y_{2})$
$\displaystyle=\int_{y_{1}}^{\frac{y_{1}+y_{2}}{2}}(x-y_{1})\rho_{\mu}(x)dx$
$\displaystyle C(y_{1},y_{2})$
$\displaystyle=\int_{\frac{y_{1}+y_{2}}{2}}^{y_{2}}(y_{2}-x)\rho_{\mu}(x)dx$
$\displaystyle D(y_{1},y_{2})$
$\displaystyle=\int_{y_{2}}^{+\infty}(x-y_{2})\rho_{\mu}(x)dx.$

We now compute the derivative of $\mathcal{W}$ with respect to $y_{1}$ and
$y_{2}$. Let us consider the derivative
$\partial_{y_{1}}\mathcal{W}(y_{1},y_{2})$. By definition, we have

$\partial_{y_{1}}\mathcal{W}(y_{1},y_{2})=\partial_{y_{1}}A(y_{1},y_{2})+\partial_{y_{1}}B(y_{1},y_{2})+\partial_{y_{1}}C(y_{1},y_{2}),$

since $\partial_{y_{1}}D(y_{1},y_{2})=0$. First, let us consider
$\partial_{y_{1}}A(y_{1},y_{2})$. We have that

$\displaystyle\frac{1}{h}\Big{(}$
$\displaystyle\int_{-\infty}^{y_{1}+h}(y_{1}+h-x)\rho_{\mu}(x)dx-\int_{-\infty}^{y_{1}}(y_{1}-x)\rho_{\mu}(x)dx\Big{)}$
$\displaystyle=\frac{1}{h}\Big{(}h\int_{-\infty}^{y_{1}+h}\rho_{\mu}(x)dx-\int_{y_{1}}^{y_{1}+h}(y_{1}-x)\rho_{\mu}(x)dx\Big{)}$
$\displaystyle=\int_{-\infty}^{y_{1}+h}\rho_{\mu}(x)dx+\frac{1}{h}\int_{y_{1}}^{y_{1}+h}(y_{1}-x)\rho_{\mu}(x)dx.$

By the Lebesgue’s theorem, we have that

$\lim_{h\to 0}\frac{1}{h}\int_{y_{1}}^{y_{1}+h}(y_{1}-x)\rho_{\mu}(x)dx=0,$

thus $\partial_{y_{1}}A(y_{1},y_{2})=F_{\mu}(y_{1})$.

Second, let us compute $\partial_{y_{1}}B(y_{1},y_{2})$. We have that

$\displaystyle\frac{1}{h}\Big{(}$
$\displaystyle\int_{y_{1}+h}^{\frac{y_{1}+y_{2}}{2}+\frac{h}{2}}(x-y_{1}-h)\rho_{\mu}(x)dx-\int_{y_{1}}^{\frac{y_{1}+y_{2}}{2}}(x-y_{1})\rho_{\mu}(x)dx\Big{)}$
$\displaystyle\frac{1}{h}\Big{(}-h\int_{y_{1}+h}^{\frac{y_{1}+y_{2}}{2}+\frac{h}{2}}\rho_{\mu}(x)dx+\int_{\frac{y_{1}+y_{2}}{2}}^{\frac{y_{1}+y_{2}}{2}+\frac{h}{2}}(x-y_{1})\rho_{\mu}(x)dx$
$\displaystyle\quad\quad\quad-\int_{y_{1}}^{y_{1}+h}(x-y_{1})\rho_{\mu}(x)dx\Big{)}.$

Owing again to Lebesgue’s theorem, we have

$\partial_{y_{1}}B(y_{1},y_{2})=-\Big{(}F_{\mu}\big{(}\frac{y_{1}+y_{2}}{2}\big{)}-F_{\mu}(y_{1})\Big{)}+\frac{(y_{2}-y_{1})}{4}\rho_{\mu}\Big{(}\frac{y_{1}+y_{2}}{2}\Big{)}.$

Finally, we compute $\partial_{y_{1}}C(y_{1},y_{2})$. We have that

$\displaystyle\frac{1}{h}\Big{(}$
$\displaystyle\int_{\frac{y_{1}+y_{2}}{2}+\frac{h}{2}}^{y_{2}}(y_{2}-x)\rho_{\mu}(x)dx-\int_{\frac{y_{1}+y_{2}}{2}}^{y_{2}}(y_{2}-x)\rho_{\mu}(x)dx\Big{)}$
$\displaystyle\frac{1}{h}\Big{(}-\int_{\frac{y_{1}+y_{2}}{2}}^{\frac{y_{1}+y_{2}}{2}+\frac{h}{2}}(y_{2}-x)\rho_{\mu}(x)dx\Big{)}.$

Owing again to the Lebesgue’s theorem, we have that

$\partial_{y_{1}}C(y_{1},y_{2})=-\frac{y_{2}-y_{1}}{4}\rho_{\mu}\Big{(}\frac{y_{1}+y_{2}}{2}\Big{)}.$

Putting all together, we infer

$\partial_{y_{1}}\mathcal{W}(y_{1},y_{2})=2F_{\mu}(y_{1})-F_{\mu}\Big{(}\frac{y_{1}+y_{2}}{2}\Big{)}.$

Through a similar argument, we have that

$\partial_{y_{2}}\mathcal{W}(y_{1},y_{2})=2F_{\mu}(y_{2})-1-F_{\mu}\bigg{(}\frac{y_{1}+y_{2}}{2}\bigg{)},$

which concludes the first part of the proof.

Since $\mu$ is absolutely continuous, we have that $F_{\mu}$ is
differentiable, thus $\mathcal{W}$ is twice differentiable.

Finally, due to the properties of cumulative distribution functions of
symmetric measures, we infer that

$\nabla\mathcal{W}\Big{(}F_{\mu}^{[-1]}(0.25),F_{\mu}^{[-1]}(0.75)\Big{)}=(0,0).$

∎

Now that we have an explicit formula for the gradient of $\mathcal{W}$, we
need to express the set of feasible $\@vec{y}$. From Theorem 3.1, we have that
$p_{2}\leq q_{1}$ and $1-p_{2}\leq q_{2}$, i.e. $1-q_{2}\leq p_{2}$. Since
$F_{\mu}^{[-1]}$ is monotone, we have that $y_{2}=F_{\mu}^{[-1]}(p_{2})\leq
F_{\mu}^{[-1]}(q_{1})$ and that $F_{\mu}^{[-1]}(1-q_{2})\leq y_{1}$. Therefore
we have that the set of feasible $\@vec{y}$ lays in a triangle, namely
$T(\@vec{q})$, whose vertexes are
$(F_{\mu}^{[-1]}(1-q_{2}),F_{\mu}^{[-1]}(q_{1}))$,
$(F_{\mu}^{[-1]}(q_{1}),F_{\mu}^{[-1]}(q_{1}))$, and
$(F_{\mu}^{[-1]}(1-q_{2}),F_{\mu}^{[-1]}(1-q_{2}))$.

Asymmetric probability distributions $\mu$. Finally, we want to stress that
the procedure outlined above, it is applicable also for non-symmetric measures
as long as the two facilities have the same capacity. Indeed, in this case,
the permutation we chose is irrelevant, since the facilities have the same
capacity and thus are interchangeable. In this case, we can still compute the
derivative of the objective function and retrieve the optimal $\@vec{p}$ based
on how the set $T(\@vec{q})$ intersects the set of points in which the
derivatives of $\mathcal{W}$ are equal to $0$. Of course, in this case, the
point $(F_{\mu}^{[-1]}(0.25),F_{\mu}^{[-1]}(0.75))$ is no longer necessarily a
point on which the gradient $\nabla\mathcal{W}$ nullifies.

###  B.1. Optimal Extended Ranking Mechanisms in the Generic Framework

Lastly, we propose a sufficient and necessary condition that guarantees the
existence of an optimal ERM whose limit Bayesian approximation ratio converges
to $1$ that is applicable regardless of $m$ and $\mu$.

######  Theorem B.2.

Give $\mu$ and $\@vec{q}$, let $(\pi,\nu_{m})$ be a solution to Problem (7).
We denote with $\\{y_{j}\\}_{j\in[m]}$ the points in the support of $\nu_{m}$
ordered non-decreasingly, and set $y_{0}=-\infty$ and $y_{m+1}=+\infty$.
Finally, we define $\zeta_{j}=F_{\mu}(y_{j+1})-F_{\mu}(y_{j-1})$ and denote
with $\hat{\pi}\in\mathcal{S}_{m}$ a permutation that orders the values
$\zeta_{j}$ in a non-increasing order. Then, the optimal ERM has limit
Bayesian approximation ratio equal to $1$ if and only if
$\zeta_{\hat{\pi}(j)}\leq q_{j}$ for every $j\in[m]$.

###### Proof of Theorem B.2.

Let $(\sigma,\nu_{m})$ be a solution to (7). Since
$\nu_{m}\in\mathcal{P}_{m}(\mathbb{R})$, we have
$spt(\nu_{m})=\\{y_{j}\\}_{j\in[m]}$. Let us define $p_{j}=F_{\mu}(y_{j})$.
Furthermore, let us fix $\gamma=\hat{\pi}^{-1}\in\mathcal{S}_{m}$. By
definition of $p_{j}$ and by hypothesis, we have that
$p_{j+1}-p_{j-1}=F_{\mu}(y_{j+1})-F_{\mu}(y_{j-1})\leq q_{\gamma(j)}$ for
every $j\in[m]$, hence $\texttt{ERM}^{(\gamma,\@vec{p})}$ is feasible (Theorem
3.1). Owing to Theorem 4.2, the asymptotic expected Social Cost of
$\texttt{ERM}^{(\gamma,\@vec{p})}$ converges to $W_{1}(\mu,\nu_{\@vec{p}})$,
where $\nu_{\@vec{p}}$ is a solution to

$\min_{\lambda_{j}\leq
q_{\gamma(j)},\sum_{j\in[m]\lambda_{j}=1}}W_{1}\Big{(}\mu,\sum_{j\in[m]}\lambda_{j}\delta_{y_{j}}\Big{)}$
(18)

since, by definition, we have $p_{j}=F_{\mu}(y_{j})$.

To conclude, we need to show that $(\gamma,\nu_{\@vec{p}})$ is a solution to
(7). Due to the optimality of $\sigma\in\mathcal{S}_{m}$, it suffices to show
that

$\min_{\zeta\in\mathcal{P}_{\sigma,m}(\mathbb{R})}W_{1}(\mu,\zeta)\geq
W_{1}(\mu,\nu_{\@vec{p}}).$

First, let us consider the following minimization problem

$\min_{\sum_{j\in[m]}\lambda_{j}=1}W_{1}\Big{(}\mu,\sum_{j\in[m]}\lambda_{j}\delta_{y_{j}}\Big{)}.$
(19)

Notice that the only difference between problem (19) and problem (18) are the
constraints $\lambda_{j}\leq q_{\sigma(j)}$. Let us now consider the
probability measure
$\nu=\sum_{j\in[m]}(F_{\mu}(z_{j})-F_{\mu}(z_{j-1}))\delta_{y_{j}}$, where
$z_{j}=\frac{y_{j}+y_{j+1}}{2}$ for every $j\in[m-1]$, $z_{0}=-\infty$, and
$z_{m}=+\infty$. Since the optimal transportation plan between two measures on
a line is monotone (see Theorem 2.9, Santambrogio (2015)), we infer

$W_{1}(\mu,\nu)=\int_{\mathbb{R}\times\mathbb{R}}\min_{j\in[m]}|x-y_{j}|\,d\mu,$

thus $\nu$ is a minimizer of problem (19). Finally, since $F_{\mu}$ is
monotone increasing, it holds $F_{\mu}(z_{j})-F_{\mu}(z_{j-1})\leq
F_{\mu}(y_{j+1})-F_{\mu}(y_{j-1})\leq q_{\gamma(j)}$. In particular, $\nu$ is
feasible for problem (18), thus $W_{1}(\mu,\nu)=W_{1}(\mu,\nu_{\@vec{p}})$.
Likewise, $\nu_{m}$ is feasible for problem (19), thus
$W_{1}(\mu,\nu_{\@vec{p}})=W_{1}(\mu,\nu)\leq W_{1}(\mu,\nu_{m})$, which
concludes the proof. ∎

##  Appendix C The Bayesian Analysis of the Innerpoint Mechanism and the
Extended Endpoint Mechanism

In this appendix, we report the Bayesian analysis of other known mechanisms.
In particular, we consider the InnerPoint Mechanism and the Extended Endpoint
Mechanism, both introduced in Aziz et al. (2020b). The study of the InnerPoint
Mechanisms can be easily generalized to include all the Ranking Mechanisms
that place the two facilities at two different points.

###  C.1. The Bayesian approximation ratio of the Innerpoint Mechanism

Consider now the $2$-CFLP in which we have an even number of agents, thus
$n=2k$, and the two facilities have the same capacity, so that
$\@vec{q}=(0.5,0.5)$. In this context, the Innerpoint Mechanism (IM) places
the two facilities at $y_{1}$ and $y_{2}$, where $y_{1}$ is the $k$-th agent
report from the left and $y_{2}$ the $(k+1)$-th agent report from the left.
Every agent whose report is on the left of $y_{1}$ is assigned to the facility
at $y_{1}$, while the others to $y_{2}$. Since the IM works only for instances
with an even number of agents, the limit will taken for $k\to\infty$. It is
easy to see that, for every given $k\in\mathbb{N}$, the IM can be written as a
Ranking Mechanism. Indeed, if we set $\@vec{p}=(0.5-\frac{1}{2k},0.5)$ and
$\pi=Id$444where $Id$ is the identity permutation, that is $\pi(i)=i$ for
every $i\in[n]$., the output of the IM and the output of the ERM associated to
$\@vec{p}$ and $\pi$ coincide on every instance. However, the vector
$\@vec{p}$ determining the output of the ERM depends on $k$, thus we cannot
directly apply Theorem 4.2 to infer the limit Bayesian approximation ratio of
the IM. To overcome this issue, we consider the Ranking Mechanism induced by
the vector $\@vec{p}=(0.5,0.5)$.555Since the two facilities have the same
capacity the mechanism does not depend on the permutation we choose, thus we
will omit it for the sake of simplicity. Indeed, for every $k\in\mathbf{N}$
and $\@vec{x}\in\mathbb{R}^{2k}$, it holds $SC_{IM}(\@vec{x})\leq
SC_{RM^{(Id,\@vec{p})}}(\@vec{x})$, hence

$\displaystyle\lim_{k\to\infty}\frac{\mathbb{E}[SC_{IM}(\@vec{X})]}{\mathbb{E}[SC_{opt}(\@vec{X})]}$
$\displaystyle\leq\lim_{n\to\infty}\frac{\mathbb{E}[SC_{Id,\@vec{p}}(\@vec{X})]}{\mathbb{E}[SC_{opt}(\@vec{X})]}$
$\displaystyle=\frac{W_{1}(\mu,\delta_{med(\mu)})}{W_{1}(\mu,\nu_{m})},$ (20)

where $\nu_{m}$ is a solution to problem (7). Notice the inequality in (C.1)
allows us to conclude that the Bayesian approximation ratio of the IM is
finite. We now prove the other inequality. Notice that if $k>10$ and
$\epsilon\in(0,0.1)$, it holds true the following

$SC_{IM}(\@vec{x})\geq
SC_{\texttt{ERM}^{(Id,\@vec{p}_{\epsilon})}}(\@vec{x}),$

where $\@vec{p}_{\epsilon}=(0.5-\epsilon,0.5)$. Notice that the mechanism
$\texttt{ERM}^{(Id,\@vec{p}_{\epsilon})}$ is not feasible for
$\@vec{q}=(0.5,0.5)$, but it is feasible if we consider
$\@vec{q}_{\epsilon}=(0.5+\epsilon,0.5+\epsilon)$. Indeed, for
$\@vec{q}_{\epsilon}$ the routine of the IM is still well-defined and the cost
of the output of IM does not depend on which $\@vec{q}$ we consider, thus the
inequality holds. If we take the average and the limits for $k\to\infty$ on
both sides, we infer from Theorem 4.2 that

$\displaystyle\lim_{k\to\infty}\frac{\mathbb{E}[SC_{IM}(\@vec{X})]}{\mathbb{E}[SC_{opt}(\@vec{X})]}$
$\displaystyle\geq\lim_{n\to\infty}\frac{\mathbb{E}[SC_{Id,\@vec{p}_{\epsilon}}(\@vec{X})]}{\mathbb{E}[SC_{opt}(\@vec{X})]}=\frac{W_{1}(\mu,\eta_{\epsilon})}{W_{1}(\mu,\nu_{m})},$

where
$\eta_{\epsilon}=\lambda_{\epsilon}\delta_{F^{[-1]}_{\mu}(0.5-\epsilon)}+(1-\lambda_{\epsilon})\delta_{med(\mu)}$
and

$\lambda_{\epsilon}=F_{\mu}\Big{(}\frac{F^{[-1]}_{\mu}(0.5-\epsilon)+F^{[-1]}_{\mu}(0.5)}{2}\Big{)}.$

Since the measure $\eta_{\epsilon}$ converges in probability to
$\delta_{med(\mu)}$ when $\epsilon\to 0$, we infer that

$\lim_{k\to\infty}\frac{\mathbb{E}[SC_{IM}(\@vec{X})]}{\mathbb{E}[SC_{opt}(\@vec{X})]}\geq\frac{W_{1}\big{(}\mu,\delta_{med(\mu)}\big{)}}{W_{1}(\mu,\nu_{m})},$

hence the Bayesian approximation ratio of the IM is
$\frac{W_{1}(\mu,\delta_{med(\mu)})}{W_{1}(\mu,\nu_{m})}$, where $\nu_{m}$ is
the solution to problem (7). By a similar argument, we can show that also the
InnerChoice Mechanism proposed in Walsh (2022) and any truthful Ranking
Mechanism have bounded limit Bayesian approximation ratio. In particular, the
InnerChoice Mechanism has the same limit Bayesian approximation ratio of the
IM.

###  C.2. The Extended Endpoint Mechanism

Given a p.c.v. $\@vec{q}$ , the Extended Endpoint Mechanism (EEM) is a
mechanism proposed in Aziz et al. (2020a) feasible to handle any $2$-CFLP. In
our formalism, the routine of the EEM is as follows. Let $\@vec{x}$ be a
vector containing the agents’ report. Without loss of generality, we assume
that $\@vec{x}$ is ordered non decreasingly, i.e. $x_{i}\leq x_{i+1}$. We
define
$A_{1}=\\{x_{i}\;\textrm{s.t.}\;|x_{i}-x_{1}|\leq\frac{1}{2}|x_{1}-x_{n}|\\}$
and $A_{2}=\\{x_{i}\;\textrm{s.t.}\;x_{i}\notin A_{1}\\}$. If
$|A_{1}|\geq|A_{2}|$, the EEM determines the position of two facilities as
follows:

  1. (i)

If $|A_{1}|\leq\left\lfloor q_{1}(n-1)\right\rfloor+1$ and
$|A_{2}|\leq\left\lfloor q_{2}(n-1)\right\rfloor+1$, we set $y_{1}=x_{1}$ and
$y_{2}=x_{n}$, we place the facility with capacity $q_{1}$ at $y_{1}$ and the
facility with capacity $q_{2}$ at $y_{2}$.

  2. (ii)

If $|A_{1}|>\left\lfloor q_{1}(n-1)\right\rfloor+1$ and
$|A_{2}|\leq\left\lfloor q_{2}(n-1)\right\rfloor+1$, we set
$y_{1}=2x_{\left\lfloor q_{1}(n-1)\right\rfloor+2}-x_{n}$ and $y_{2}=x_{n}$,
we place the facility with capacity $q_{1}$ at $y_{1}$ and the facility with
capacity $q_{2}$ at $y_{2}$.

  3. (iii)

If $|A_{1}|\leq\left\lfloor q_{1}(n-1)\right\rfloor+1$ and
$|A_{2}|>\left\lfloor q_{2}(n-1)\right\rfloor+1$, we set $y_{1}=x_{1}$ and
$y_{2}=2x_{n-(\left\lfloor q_{2}(n-1)\right\rfloor+1)}-x_{1}$, we place the
facility with capacity $q_{1}$ at $y_{1}$ and the facility with capacity
$q_{2}$ at $y_{2}$.

In all of the cases above, every agent is assigned to the facility that is
closer to the position (break ties arbitrarily without overloading any
facility). Finally, if $|A_{1}|>|A_{2}|$, it suffices to switch the roles of
the two facilities in the cases described above.

We now study the limit Bayesian approximation ratio of the EEM when the agents
are distributed according to a uniform distribution and $\@vec{q}=(0.8,0.4)$.
For the sake of simplicity, we consider only a odd number of agents $n=2k+1$.
First, we notice that we can restrict our attention to the class of instances
in which $|A_{1}|>|A_{2}|$. Indeed, due to the symmetry of the uniform
distribution, we have that the every instance for which $|A_{1}|>|A_{2}|$
holds, uniquely identifies an instance for which it holds
$|A_{1}|<|A_{2}|$666Since $n$ is odd we have that we cannot have
$|A_{1}|=|A_{2}|$.. Let us consider the expected Social Cost of the instances
for which it holds $|A_{1}|>|A_{2}|$, which we denote with $\mathcal{A}$.
Using the properties of the expected values, we can compute the expected
Social Cost of the EEM as the sum of three conditioned expected values

$\displaystyle\mathbb{E}[SC_{\pi,\@vec{p}}(\@vec{X})]$
$\displaystyle=\mathbb{E}[SC_{\pi,\@vec{p}}(\@vec{X})|\@vec{X}\in
C_{1}]P(\@vec{X}\in C_{1})$
$\displaystyle\quad+\mathbb{E}[SC_{\pi,\@vec{p}}(\@vec{X})|\@vec{X}\in
C_{2}]P(\@vec{X}\in C_{2})$
$\displaystyle\quad+\mathbb{E}[SC_{\pi,\@vec{p}}(\@vec{X})|\@vec{X}\in
C_{3}]P(\@vec{X}\in C_{3}),$

where  (i) $C_{1}$contains all the instances for which
$|A_{1}|\leq\left\lfloor q_{1}(n-1)\right\rfloor+1$ and
$|A_{2}|\leq\left\lfloor q_{2}(n-1)\right\rfloor+1$;  (ii) $C_{2}$contains all
the instances for which $|A_{1}|>\left\lfloor q_{1}(n-1)\right\rfloor+1$ and
$|A_{2}|\leq\left\lfloor q_{2}(n-1)\right\rfloor+1$; and  (iii)
$C_{3}$contains all the instances for which $|A_{1}|\leq\left\lfloor
q_{1}(n-1)\right\rfloor+1$ and $|A_{2}|>\left\lfloor
q_{2}(n-1)\right\rfloor+1$.  Notice that $\mathcal{A}=C_{1}\cup C_{2}\cup
C_{3}$. Moreover, every $C_{i}$ is disjoint from the other, hence, since we
are restricting our attention to only the instances in $\mathcal{A}$, we have

$P(\@vec{X}\in C_{3})=1-P(\@vec{X}\in C_{1})-P(\@vec{X}\in C_{2}).$

We first show that both $P(\@vec{X}\in C_{1})$ and $P(\@vec{X}\in C_{2})$ go
to $0$ as the number of agents go to infinity and then show that

$\lim_{n\to\infty}\mathbb{E}[SC_{\pi,\@vec{p}}(\@vec{X})|\@vec{X}\in
C_{3}]=W_{1}(\mu,(1-q_{2})\delta_{0}+q_{2}\delta_{1.2}).$

First, let us consider $P(\@vec{X}\in C_{1})$. Notice that

$\displaystyle P(\@vec{X}\in C_{1})$ $\displaystyle=P(|A_{1}|\leq\left\lfloor
q_{1}(n-1)\right\rfloor+1,|A_{2}|\leq\left\lfloor q_{2}(n-1)\right\rfloor+1)$
$\displaystyle\leq P(|A_{2}|\leq\left\lfloor q_{2}(n-1)\right\rfloor+1)$
$\displaystyle\leq P\Big{(}X_{\left\lfloor
0.55(n-1)\right\rfloor+1}\leq\frac{X_{1}+X_{n}}{2}\Big{)},$

where the last inequality comes from the fact that if

$|A_{2}|\leq\left\lfloor q_{2}(n-1)\right\rfloor+1$

then it must be that $X_{\left\lfloor
0.55(n-1)\right\rfloor+1}\leq\frac{X_{1}+X_{n}}{2}$, since $q_{2}=0.4$. Let us
now set $\epsilon>0$ and $r=\left\lfloor 0.55(n-1)\right\rfloor+1$, then we
have

$\displaystyle P$ $\displaystyle(\@vec{X}\in C_{1})\leq
P\Big{(}X_{r}\leq\frac{X_{1}+X_{n}}{2}\Big{)}$
$\displaystyle=P\Big{(}X_{r}\leq\frac{X_{1}+X_{n}}{2}\Big{|}X_{1}\leq\epsilon,X_{n}\geq
1-\epsilon\Big{)}P(X_{1}\leq\epsilon,X_{n}\geq 1-\epsilon)$
$\displaystyle\quad+P\Big{(}X_{r}\leq\frac{X_{1}+X_{n}}{2}\Big{|}X_{1}\geq\epsilon,X_{n}\leq
1-\epsilon\Big{)}P(X_{1}\geq\epsilon,X_{n}\leq 1-\epsilon)$ $\displaystyle\leq
P\Big{(}X_{r}\leq\frac{1+\epsilon}{2}\Big{)}\big{(}P(X_{1}\leq\epsilon)+P(X_{n}\geq
1-\epsilon)\big{)}$ $\displaystyle\quad+P(X_{1}\geq\epsilon)+P(X_{n}\leq
1-\epsilon),$

since
$P\Big{(}X_{r}\leq\frac{X_{1}+X_{n}}{2}\Big{|}X_{1}\geq\epsilon,X_{n}\leq
1-\epsilon\Big{)}\leq 1$. Notice that the cumulative distribution function of
the $n$-th order statistic of a uniform ditributed random variable is

$t\to\Big{(}F_{\mu}(t)\Big{)}^{n}=t^{n}$

hence

$P(X_{n}\leq 1-\epsilon)=(1-\epsilon)^{n}$

hence $\lim_{n\to\infty}P(X_{n}\leq 1-\epsilon)=0$. Likewise, we have that

$\lim_{n\to\infty}P(X_{1}\geq\epsilon)=0.$

Lastly, we need to show that $P\Big{(}X_{r}\leq\frac{1+\epsilon}{2}\Big{)}$
goes to $0$ as $n$ goes to infinity. It is well-known that, for a suitable
constant $K$, it holds $K\sqrt{n}(X_{\left\lfloor
0.55(n-1)\right\rfloor+1}-0.55)$ converges in distribution to the standard
Gaussian $Z\sim\mathcal{N}(0,1)$. Given $\epsilon<0.05$, we have that

$\displaystyle P\Big{(}X_{r}$ $\displaystyle\leq\frac{1+\epsilon}{2}\Big{)}$
$\displaystyle=P\Big{(}K\sqrt{n}(X_{\left\lfloor
0.55(n-1)\right\rfloor+1}-0.55)\leq
K\sqrt{n}\Big{(}\frac{1+\epsilon}{2}-0.55\Big{)}\Big{)}.$

Thus

$\displaystyle P\Big{(}X_{r}\leq\frac{1+\epsilon}{2}\Big{)}$
$\displaystyle\leq\Bigg{|}P\Big{(}X_{r}\leq\frac{1+\epsilon}{2}\Big{)}\Big{)}-P\Big{(}Z\leq
K\sqrt{n}\Big{(}\frac{1+\epsilon}{2}-0.55\Big{)}\Big{)}\Bigg{|}$
$\displaystyle\quad+P\Big{(}Z\leq
K\sqrt{n}\Big{(}\frac{1+\epsilon}{2}-0.55\Big{)}\Big{)}.$

Since $\Big{(}\frac{1+\epsilon}{2}-0.55\Big{)}<0$, we have that

$\lim_{n\to\infty}P\Big{(}Z\leq
K\sqrt{n}\Big{(}\frac{1+\epsilon}{2}-0.55\Big{)}\Big{)}=0.$

Finally, by the convergence in distribution of $X_{r}$,see Wilks (2012); David
and Nagaraja (2004), we have

$\lim_{n\to\infty}\Bigg{|}P\Big{(}X_{r}\leq\frac{1+\epsilon}{2}\Big{)}\Big{)}-P\Big{(}Z\leq
K\sqrt{n}\Big{(}\frac{1+\epsilon}{2}-0.55\Big{)}\Big{)}\Bigg{|}=0,$

which allows us to conclude that $\lim_{n\to\infty}P(\@vec{X}\in C_{1})=0$.

Similarly, we have that $\lim_{n\to\infty}P(\@vec{X}\in C_{2})=0$. We thus
infer $\lim_{n\to\infty}P(\@vec{X}\in C_{3})=1$.

Lastly, we need to show that

$\lim_{n\to\infty}\mathbb{E}[SC_{\pi,\@vec{p}}(\@vec{X})|\@vec{X}\in
C_{3}]=W_{1}(\mu,(1-q_{2})\delta_{0}+q_{2}\delta_{1.2}).$

Notice that if $\@vec{x}\in C_{3}$, the EEM places a facility at $x_{1}$ and
the other one at $2x_{n-(\left\lfloor q_{2}(n-1)\right\rfloor+2)}-x_{1}$, the
first $n-(\left\lfloor q_{2}(n-1)\right\rfloor+1)$ agents are assigned to the
facility placed at $x_{1}$, while the others to the facility at
$2x_{n-\left\lfloor q_{2}(n-1)\right\rfloor+2}-x_{1}$. Since every agent is
assigned to its closest facility, we can adapt the argument used to prove
Lemma 4.1, and infer that

$SC_{EEM}(\@vec{x})=W_{1}(\mu_{n},q_{1}\delta_{x_{1}}+(1-q_{1})\delta_{2x_{n-\left\lfloor
q_{2}(n-1)\right\rfloor+2}-x_{1}}).$

By the same argument used in the proof of Theorem 4.2, it is possible to show
that

$\displaystyle\lim_{n\to\infty}W_{1}(\mu_{n},q_{1}\delta_{x_{1}}$
$\displaystyle+(1-q_{1})\delta_{2x_{\left\lfloor
q_{1}(n-1)\right\rfloor+2}-x_{1}})$
$\displaystyle=W_{1}(\mu,(1-q_{2})\delta_{0}+q_{2}\delta_{1.2}),$

which concludes the proof.

It is important to emphasize that the examination of the limit Bayesian
approximation ratio of the EEM is feasible due to the compact support of the
uniform distribution. Indeed, since every output of the EEM places one of the
facilities either at $x_{1}$ or $x_{n}$, a rigorous investigation into the
limit study is only possible if we can ensure the convergence of at least one
between the first and last order statistic. In particular, the study is
impossible for measures with unbounded support. Consequently, any meaningful
analytical investigation into the limit Bayesian approximation ratio of the
EEM necessitates measures with at least one side of their support being
bounded.

##  Appendix D Additional Experimental Results

In this Appendix, we report the values plotted in Figure 1, 2, and 3. In
particular, Table 1 reports the Bayesian approximation ratios for the balanced
case, plotted in Figure 1. Table 2 reports the values of the Bayeisan
approximation ratios for the unbalanced case, plotted in Figure 2. Finally, in
Table 3, we report the values of the relative error of the Bayesian
approximation ratios, plotted in Figure 3.

p.c.v. $\@vec{q}$ | Measure $\mu$ | Mech. | $n=10$ | 20 | 30 | 40 | 50
---|---|---|---|---|---|---|---
lb | mean | ub | lb | mean | ub | lb | mean | ub | lb | mean | ub | lb | mean | ub
$(0.7,0.7)$ | Uniform | ERM | 1.12 | 1.14 | 1.16 | 1.09 | 1.10 | 1.11 | 1.07 | 1.08 | 1.09 | 1.07 | 1.07 | 1.08 | 1.06 | 1.06 | 1.07
IG | 1.04 | 1.04 | 1.05 | 1.04 | 1.05 | 1.05 | 1.04 | 1.05 | 1.05 | 1.05 | 1.05 | 1.05 | 1.04 | 1.05 | 1.05
EEM | 1.77 | 1.81 | 1.85 | 1.87 | 1.90 | 1.93 | 1.91 | 1.93 | 1.95 | 1.95 | 1.97 | 1.99 | 1.95 | 1.96 | 1.98
Gaussian | ERM | 1.11 | 1.13 | 1.15 | 1.07 | 1.08 | 1.09 | 1.06 | 1.06 | 1.07 | 1.06 | 1.06 | 1.07 | 1.05 | 1.06 | 1.06
IG | 1.04 | 1.05 | 1.06 | 1.04 | 1.05 | 1.05 | 1.04 | 1.04 | 1.05 | 1.04 | 1.05 | 1.05 | 1.04 | 1.04 | 1.05
EEM | 2.05 | 2.10 | 2.14 | 2.60 | 2.65 | 2.71 | 2.87 | 2.93 | 2.98 | 3.04 | 3.09 | 3.15 | 3.19 | 3.24 | 3.30
Exp. | ERM | 1.26 | 1.30 | 1.34 | 1.15 | 1.16 | 1.17 | 1.14 | 1.15 | 1.16 | 1.12 | 1.13 | 1.14 | 1.12 | 1.13 | 1.14
IG | 1.08 | 1.09 | 1.10 | 1.07 | 1.08 | 1.09 | 1.09 | 1.10 | 1.11 | 1.09 | 1.09 | 1.10 | 1.09 | 1.10 | 1.11
EEM | 2.60 | 2.72 | 2.84 | 3.82 | 4.01 | 4.20 | 4.81 | 5.00 | 5.20 | 5.67 | 5.89 | 6.11 | 6.05 | 6.28 | 6.52
$(0.8,0.8)$ | Uniform | ERM | 1.15 | 1.18 | 1.20 | 1.04 | 1.05 | 1.06 | 1.03 | 1.04 | 1.04 | 1.02 | 1.02 | 1.03 | 1.02 | 1.02 | 1.02
IG | 1.18 | 1.19 | 1.20 | 1.12 | 1.12 | 1.13 | 1.09 | 1.09 | 1.10 | 1.08 | 1.08 | 1.08 | 1.07 | 1.07 | 1.07
EEM | 1.74 | 1.78 | 1.81 | 1.88 | 1.91 | 1.94 | 1.91 | 1.93 | 1.95 | 1.93 | 1.95 | 1.97 | 1.95 | 1.97 | 1.99
Gaussian | ERM | 1.13 | 1.15 | 1.17 | 1.04 | 1.04 | 1.05 | 1.03 | 1.04 | 1.04 | 1.02 | 1.02 | 1.03 | 1.02 | 1.02 | 1.03
IG | 1.19 | 1.20 | 1.21 | 1.11 | 1.12 | 1.12 | 1.09 | 1.09 | 1.10 | 1.07 | 1.08 | 1.08 | 1.07 | 1.07 | 1.07
EEM | 2.00 | 2.04 | 2.08 | 2.47 | 2.51 | 2.56 | 2.82 | 2.86 | 2.91 | 2.99 | 3.04 | 3.08 | 3.16 | 3.21 | 3.26
Exp. | ERM | 1.29 | 1.33 | 1.37 | 1.13 | 1.15 | 1.17 | 1.11 | 1.12 | 1.13 | 1.08 | 1.09 | 1.09 | 1.08 | 1.09 | 1.10
IG | 1.14 | 1.15 | 1.16 | 1.11 | 1.12 | 1.12 | 1.09 | 1.10 | 1.10 | 1.07 | 1.08 | 1.08 | 1.07 | 1.08 | 1.08
EEM | 1.85 | 1.92 | 2.00 | 2.66 | 2.79 | 2.93 | 3.51 | 3.70 | 3.88 | 4.18 | 4.40 | 4.63 | 4.36 | 4.56 | 4.76
$(0.9,0.9)$ | Uniform | ERM | 1.14 | 1.16 | 1.18 | 1.04 | 1.05 | 1.05 | 1.03 | 1.04 | 1.04 | 1.02 | 1.02 | 1.03 | 1.02 | 1.02 | 1.02
IG | 1.72 | 1.75 | 1.78 | 1.52 | 1.54 | 1.55 | 1.46 | 1.48 | 1.49 | 1.44 | 1.45 | 1.46 | 1.42 | 1.43 | 1.44
EEM | 1.72 | 1.75 | 1.78 | 1.86 | 1.88 | 1.91 | 1.92 | 1.94 | 1.97 | 1.93 | 1.96 | 1.98 | 1.96 | 1.98 | 2.00
Gaussian | ERM | 1.12 | 1.14 | 1.16 | 1.04 | 1.04 | 1.05 | 1.03 | 1.04 | 1.04 | 1.02 | 1.03 | 1.03 | 1.02 | 1.02 | 1.02
IG | 1.99 | 2.03 | 2.06 | 1.67 | 1.69 | 1.71 | 1.58 | 1.60 | 1.61 | 1.54 | 1.56 | 1.57 | 1.51 | 1.53 | 1.54
EEM | 1.99 | 2.03 | 2.06 | 2.48 | 2.53 | 2.57 | 2.77 | 2.82 | 2.86 | 3.00 | 3.05 | 3.09 | 3.09 | 3.14 | 3.18
Exp. | ERM | 1.35 | 1.39 | 1.43 | 1.14 | 1.15 | 1.17 | 1.12 | 1.13 | 1.15 | 1.08 | 1.09 | 1.10 | 1.09 | 1.10 | 1.11
IG | 1.64 | 1.67 | 1.70 | 1.41 | 1.42 | 1.44 | 1.36 | 1.38 | 1.39 | 1.32 | 1.33 | 1.34 | 1.31 | 1.32 | 1.32
EEM | 1.64 | 1.67 | 1.70 | 2.00 | 2.08 | 2.16 | 2.20 | 2.31 | 2.42 | 2.49 | 2.63 | 2.76 | 2.68 | 2.83 | 2.97

Table 1. The Bayesian approximation ratio of ERM, IG, and EEM in the balanced
case, i.e. $q_{1}=q_{2}$. Every row contains the results for different
mechanism, measure $\mu$, and vector $\@vec{q}$. Every column contains the
results for different $n\in\\{10,20,\ldots,50\\}$. Every value is computed as
the average of $500$ runs.

p.c.v. $\@vec{q}$ | Measure $\mu$ | Mech. | $n=10$ | 20 | 30 | 40 | 50
---|---|---|---|---|---|---|---
lb | mean | ub | lb | mean | ub | lb | mean | ub | lb | mean | ub | lb | mean | ub
$(0.85,0.75)$ | Uniform | ERM | 1.15 | 1.17 | 1.20 | 1.04 | 1.05 | 1.05 | 1.03 | 1.04 | 1.04 | 1.02 | 1.02 | 1.03 | 1.02 | 1.02 | 1.02
EEM | 1.75 | 1.79 | 1.82 | 1.89 | 1.92 | 1.95 | 1.90 | 1.92 | 1.94 | 1.93 | 1.95 | 1.97 | 1.96 | 1.97 | 1.99
Gaussian | ERM | 1.14 | 1.16 | 1.18 | 1.04 | 1.05 | 1.05 | 1.03 | 1.04 | 1.04 | 1.02 | 1.03 | 1.03 | 1.02 | 1.02 | 1.03
EEM | 1.99 | 2.02 | 2.06 | 2.48 | 2.53 | 2.58 | 2.75 | 2.80 | 2.84 | 3.01 | 3.06 | 3.11 | 3.15 | 3.20 | 3.24
$(0.8,0.4)$ | Uniform | ERM | 2.09 | 2.17 | 2.24 | 1.85 | 1.89 | 1.93 | 1.78 | 1.82 | 1.85 | 1.74 | 1.76 | 1.78 | 1.71 | 1.73 | 1.76
EEM | 1.89 | 1.95 | 2.00 | 2.10 | 2.14 | 2.18 | 2.21 | 2.25 | 2.28 | 2.23 | 2.27 | 2.30 | 2.26 | 2.29 | 2.32
Gaussian | ERM | 1.77 | 1.82 | 1.87 | 1.59 | 1.62 | 1.64 | 1.53 | 1.55 | 1.57 | 1.51 | 1.52 | 1.54 | 1.49 | 1.51 | 1.52
EEM | 2.10 | 2.14 | 2.19 | 2.63 | 2.68 | 2.73 | 2.88 | 2.93 | 2.98 | 3.11 | 3.16 | 3.21 | 3.26 | 3.31 | 3.35
$(0.85,0.35)$ | Uniform | ERM | 2.10 | 2.17 | 2.24 | 1.96 | 2.00 | 2.03 | 1.86 | 1.89 | 1.92 | 1.85 | 1.87 | 1.89 | 1.82 | 1.85 | 1.87
EEM | 1.88 | 1.93 | 1.97 | 2.25 | 2.30 | 2.35 | 2.34 | 2.38 | 2.42 | 2.42 | 2.46 | 2.49 | 2.46 | 2.50 | 2.53
Gaussian | ERM | 1.78 | 1.83 | 1.88 | 1.69 | 1.71 | 1.74 | 1.60 | 1.62 | 1.64 | 1.59 | 1.61 | 1.62 | 1.55 | 1.57 | 1.58
EEM | 2.11 | 2.16 | 2.21 | 2.68 | 2.73 | 2.78 | 2.96 | 3.01 | 3.06 | 3.17 | 3.22 | 3.27 | 3.33 | 3.38 | 3.43

Table 2. The Bayesian approximation ratio of ERM and EEM in the unbalanced case, i.e. $q_{1}\neq q_{2}$. Every row contains the results for different mechanism, measure $\mu$, and vector $\@vec{q}$. Every column contains the results for different $n\in\\{10,20,\ldots,50\\}$. Every value is computed as the average of $500$ runs. p.c.v. $\@vec{q}$ | Measure $\mu$ | $n=10$ | 20 | 30 | 40 | 50
---|---|---|---|---|---|---
$(0.7,0.7)$ | Uniform | 0.10 | 0.06 | 0.04 | 0.03 | 0.02
Gaussian | 0.10 | 0.05 | 0.03 | 0.03 | 0.03
$(0.8,0.8)$ | Uniform | 0.18 | 0.05 | 0.04 | 0.02 | 0.02
Gaussian | 0.15 | 0.04 | 0.04 | 0.02 | 0.02
$(0.9,0.9)$ | Uniform | 0.16 | 0.05 | 0.04 | 0.02 | 0.02
Gaussian | 0.14 | 0.04 | 0.04 | 0.03 | 0.02
$(0.85,0.75)$ | Uniform | 0.17 | 0.05 | 0.04 | 0.02 | 0.02
Gaussian | 0.16 | 0.05 | 0.04 | 0.03 | 0.02
$(0.8,0.4)$ | Uniform | 0.33 | 0.16 | 0.12 | 0.08 | 0.07
Gaussian | 0.28 | 0.14 | 0.09 | 0.07 | 0.06
$(0.85,0.35)$ | Uniform | 0.23 | 0.14 | 0.07 | 0.06 | 0.05
Gaussian | 0.24 | 0.16 | 0.09 | 0.09 | 0.06
Table 3. The relative error of ERM. For every row, we compute the relative
error of the ERM for different $\@vec{q}$, different probability
distributions, while for every column we compute the relative error for
different $n\in\\{10,20,\dots,50\\}$.