# Facility Location with Entrance Fees

Mengfan Ma
School of Computer Science
and Engineering, University of
Electronic Science and Technology of China
<EMAIL_ADDRESS>
&Mingyu Xiao
School of Computer Science
and Engineering, University of
Electronic Science and Technology of China
<EMAIL_ADDRESS>
&Tian Bai
School of Computer Science
and Engineering, University of
Electronic Science and Technology of China
<EMAIL_ADDRESS>
&Bakh Khoussainov
School of Computer Science
and Engineering, University of
Electronic Science and Technology of China
<EMAIL_ADDRESS>

###### Abstract

In mechanism design, the facility location game is an extensively studied
problem. In the classical model, the cost of each agent is her distance to the
nearest facility. In this paper, we consider a new model, where there is a
location-dependent entrance fee to the facility. Thus, in our model, the cost
of each agent is the sum of the distance to the facility and the entrance fee
of the facility. This is a refined generalization of the classical model. We
study the model and design strategyproof mechanisms. For one and two
facilities, we provide upper and lower bounds for the approximation ratio
given by deterministic and randomized mechanisms, with respect to the
utilitarian objective and the egalitarian objective. Most of our bounds are
tight and these bounds are independent of the entrance fee functions. Our
results are as general as possible because the entrance fee function we
consider is arbitrary.

##  1 Introduction

#### 1.1 Facility location game on real line.

In the one-dimensional facility location problem, agents are located on the
real line and a planner is to build facilities on the line to serve the
agents. The cost of an agent is her distance to the nearest facility. The
problem asks for facility locations that minimize the total cost of all agents
(the utilitarian objective), or the maximum cost among all agents (the
egalitarian objective). It is well-known that both optimization problems can
be solved in polynomial time. Over the past decade, these problems have been
intensively studied from the perspective of mechanism design. A key conversion
in the models is that now each agent becomes strategic and may misreport her
position to decrease her cost. These new problems are called the _facility
location games_ , which require to design _mechanisms_ that truthfully elicit
the positions of agents and (approximately) minimize the objective of total
cost or maximum cost.

The seminal work of Procaccia and Tennenholtz [2009] initiates the study of
mechanism design without money for the facility location game. They study
strategyproof mechanisms for one and two-facility games through the lens of
_approximation ratio_. Since then, the facility location game has become one
of the main playgrounds for approximate mechanism design without money and has
attracted numerous follow-up research. For the one-facility game, most results
in Procaccia and Tennenholtz [2009] are already tight. For the two-facility
game with the total cost objective, Lu et al. [2009] provide an upper bound of
$n/2$ and a lower bound of $1.045$ for randomized strategyproof mechanisms. Lu
et al. [2010] improve the lower bound to $(n-1)/2$ and propose a randomized
strategyproof $4$-approximation mechanism. Fotakis and Tzamos [2014]
characterize deterministic strategyproof mechanisms and provide the lower
bound of $n-2$ matching the upper bound of Procaccia and Tennenholtz [2009].
The current status of the classic facility location games on the real line is
summarized in Table 1. As one can see, most bounds are tight. We note that
this line of research mainly focuses on mechanisms in one and two facilities
settings, and Fotakis and Tzamos [2014] have proved that, in the setting of
more than two facilities, no deterministic strategyproof mechanism can achieve
a bounded approximation ratio.

Variants of the classical model have also been studies flourishingly to
accommodate more practical scenarios. For example, for the one-facility
location game, Cheng et al. [2013] propose obnoxious facility games where
every agent wants to stay away from the facility. Feigenbaum and Sethuraman
[2015] and Zou and Li [2015] study the dual preference game where some agents
want to stay close to the facility while the others want to stay away. Cai et
al. [2016] study another criterion of fairness other than maximum cost and Li
et al. [2019] study the facility game with externalities. For the two-facility
location game, research has been extended from the original homogeneous
facility setting to the heterogeneous facility setting where facilities serve
different purposes [Serafino and Ventre 2014; Serafino and Ventre 2015; Yuan
et al. 2016; Fong et al. 2018; Li et al. 2020]. There are also works setting a
distance constraint between the facilities [Zou and Li 2015; Chen et al. 2018;
Duan et al. 2019]. Besides, Aziz et al. [2020a] and Aziz et al. [2020b] study
the location game with two capacitated facilities. The recent survey by Chan
et al. [2021] depicts the state of the art.

#### 1.2 Facility location with entrance fee.

In the classical model and its variants, the cost of an agent is measured by
her distance to the closest facility. This cost can be considered as the
_travel fee_. In innumerable real life scenarios, except for the travel fee,
the agent may also need pay a service fee or entrance fee to the facility she
uses, such as tickets for swimming pools and museums. The entrance fee may
also differ for different positions of the facility, as the cost to build the
facility on different positions may be different. Therefore, it is natural to
consider entrance fees in the classical facility location problem. In this
paper, we initiate the study of the _facility location problem with entrance
fee_. In our setting, given a set of agents on the real line $\mathbb{R}$, the
planner needs to locate a given number of facilities on $\mathbb{R}$. Each
facility, once located, has an entrance fee determined by its location. Any
agent who uses this facility is charged the entrance fee. Thus the agent
incurs two costs. The first is the travel fee and the second is the entrance
fee. Therefore, the overall cost of the agent using the facility is the sum of
the travel fee and the entrance fee.

The facility location problem with entrance fee models many real-world
scenarios. Examples are plentiful: (1) The government would like to build
various social infrastructures, e.g., cinemas, hospitals, bridges, all of
which charge their clients an entrance fee. (2) The voters have a single-
peaked preference over the potential candidates, while after the election, the
winning candidates will enforce their own tax policy on the voters. (3) The
students in a classroom may need to decide the temperature of the air
conditioner. The electricity bill, the amount of which depends on the
temperature, is then evenly divided among the students.

For the facility location game with the entrance fee, we have a set of agents
located on the real line. We need to locate a number of facilities. Each agent
$i$ has her position $x_{i}$ as the private information and wants to use one
facility at a minimum cost. Facility located at $\ell$ charges each customer
the entrance fee $e(\ell)$, where $e:\mathbb{R}\rightarrow\mathbb{R}_{\geq 0}$
is the _entrance fee function_. Each agent $i$, in addition to the distance
from $x_{i}$ to $\ell$, also considers the entrance fee to decide whether she
uses the facility. Intuitively, the agent might prefer a distant facility with
a lower entrance fee than a nearby facility with a much higher entrance fee.
Thus, each agent selects the facility that minimizes her overall cost. The
example in Figure 1 illustrates the concept of entrance fee function.

Figure 1: An example of entrance fee function. The horizontal axis stands for
$\mathbb{R}$, i.e., the set of all possible positions of agents. The three
black dots represent three agents. The vertical axis stands for the value of
entrance fee. The curve stands for the entrance fee function $e(\cdot)$. If
the facility is located at $\ell$, the entrance fee of the facility is
$e(\ell)$. The travel fee for agent $i$ at $x_{i}$ is $|\ell-x_{i}|$. Assume
that there is only one facility, then the cost of agent $i$ is $|\ell-
x_{i}|+e(\ell)$.

#### 1.3 Our contribution

First, we provide a new model for the facility location problem, which firstly
introduces the concept of entrance fee to the classic model. The novelty is
that our model enhances the classical facility location game by adding the
location-dependent entrance fee function. Our model is as general as possible
as no conditions are imposed on the entrance fee functions. We believe our
model can brings in an idea of revisiting many existing facility location
games, such as capacitated facilities [Aziz et al. 2020a], heterogeneous
facilities [Li et al. 2020] and so on. Second, for one-facility and two-
facility games, we design deterministic and randomized mechanisms for the
utilitarian and egalitarian objectives. We also achieve lower bound results.
Table 2 summarizes our mechanism design results. Most of our bounds are tight.
We note that our approximation ratios (upper bounds) and lower bounds involve
a parameter $r_{e}$, which is defined as the ratio of the greatest entrance
fee to the smallest one over the domain of the entrance fee function
$e(\cdot)$ and thus $r_{e}\geq 1$. For the classical model where $e(\cdot)=0$,
we stipulate that $r_{e}=1$. Comparing Tables 1 and 2, we can conclude that,
on the one hand, most of our upper bound results matches the classical upper
bound results by letting $r_{e}=1$. This implies that our mechanisms include
the classical mechanisms as a special case. On the other hand, most of our
lower bound results are greater than the classical ones, which can be seen as
the difficulty introduced by the entrance fee function.

In our model, the entrance fee function is part of the input and we consider
_arbitrary_ entrance fee function. This gives rise to new challenges. First of
all, the classical mechanisms are no longer strategyproof. Intuitively,
consider the classical median mechanism that puts the facility at the position
of the median agent, although the her travel fee is $0$ her entrance fee can
be large. Thus she may deviate to a position where the sum of both fees is
smaller. To tackle this, we define the optimal location for each agent as the
facility location that minimize her cost and design mechanisms over the space
of optimal locations of agents instead of their positions. The proof of
strategyproofness needs new insights such as monotonicity of the optimal
location. Second, even if we can design strategyproof mechanisms for arbitrary
entrance fee function, the optimal facility location for either objective now
highly depends on the structure of entrance fee function. Thus it can be
difficult to analyze the approximation ratio of the mechanisms, even for one-
facility game. To overcome this, we build new techniques such as domination
and virtual facility to bound the solution values of our mechanisms and the
optimal solution and finally achieve constant approximation ratios for
arbitrary entrance fee function.

Table 1: Results for one-facility and two-facility location games of the
classical model without entrance fee.

| Total cost | Maximum cost
---|---|---
UB | LB | UB | LB
Deterministic Mechanisms | one-facility |  | $1$
---
(Procaccia and Tennenholtz 2009)
| $1$
---
(Procaccia and Tennenholtz 2009)
$2$ (Procaccia and Tennenholtz 2009) |  $2$ (Procaccia and Tennenholtz 2009)
two-facility |  | $n-2$
---
(Procaccia and Tennenholtz 2009)
| $n-2$
---
(Fotakis and Tzamos 2014)
Randomized Mechanisms | one-facility |  | $1$
---
(Procaccia and Tennenholtz 2009)
| $1$
---
(Procaccia and Tennenholtz 2009)
| $3/2$
---
(Procaccia and Tennenholtz 2009)
$3/2$ (Procaccia and Tennenholtz 2009)
two-facility |  | $4$
---
(Lu et al. 2010)
| $1.045$
---
(Lu et al. 2010)
| $5/3$
---
(Procaccia and Tennenholtz 2009)

Table 2: Results for one-facility and two-facility location games of the new
model with entrance fee, where we use $r_{e}$ to denote the ratio of the
highest entrance fee to the lowest entrance fee of the entrance fee function
$e(\cdot)$. Theorems and propositions of our results are in bold.

| Total cost | Maximum cost
---|---|---
UB | LB | UB | LB
Deterministic Mechanisms | one-facility |  | ${3-\dfrac{4}{r_{e}+1}}$
---
(Theorem 2)
| $3-\dfrac{4}{r_{e}+1}$
---
(Theorem 3)
$2$, if $r_{e}\leq 2$ $3-\dfrac{3}{r_{e}+1}$, if $r_{e}>2$ (Theorem 7 and Proposition 4) |  $2$, if $r_{e}\leq 2$ $3-\dfrac{4}{r_{e}+1}$, if $r_{e}>2$ (Theorem 8 and Theorem 9) (Proposition 5 and Proposition 6)
two-facility |  | $n-2$
---
(Proposition 3)
| $n-2\text{ if }r_{e}=1$
---
(Fotakis and Tzamos 2014)
Randomized Mechanisms | one-facility |  | $2-\dfrac{2}{r_{e}+1}$
---
(Theorem 5)
|  $2$ if $r_{e}=\infty$
---
(Theorem 6)
$2$ if $r_{e}=\infty$ (Theorem 10 and Proposition 7)
two-facility |  | $n-2$
---
(Proposition 3)
| $1.045$
---
(Lu et al. 2010)

The reminder of the paper is organized as follows. In Section 2, we present
the formal definitions of our model and concepts. In Section 3, we define the
optimal location for an position and derive local properties such as
monotonicity and domination. These properties are crucial in designing and
analyzing our mechanisms. Additionally, we show that the two offline
optimization versions of our model can be solved in polynomial time. Section 4
and Section 5 present our main results for the one-facility game. Section 4
focuses on the objective of total cost. We design deterministic and randomized
mechanisms for one-facility game, and achieve tight upper and lower bounds.
Section 5 focuses on the objective of maximum cost. We achieve tight
deterministic upper and lower bounds and establish a lower bound for
strategyproof randomized mechanisms. In Section 6, we extend our results for
one-facility game to two-facility game. Some conclusions are drawn in Section
7.

##  2 Model

Let $N=\\{1,\dots,n\\}$ be a set of _agents_ on real line $\mathbb{R}$. Let
$x_{i}$ be the location of agent $i$. The _location profile of all agents_ is
$\bm{x}=(x_{1},\cdots,x_{n})$. We need to put $m$ _facilities_ on $\mathbb{R}$
to serve the agents. Suppose we put facility $j$ at location $\ell_{j}$. This
gives us the _location profile of the facilities_
$\bm{\ell}=(\ell_{1},\cdots,\ell_{m})$.

For an agent $i$, if it is served by a facility $j$, then the agent bears the
travel fee measured by the distance $|x_{i}-\ell_{j}|$. Furthermore, each
facility charges its customers an _entrance fee_ determined by its location.
Formally, there is an _entrance fee function_
$e:\mathbb{R}\rightarrow\mathbb{R}_{\geq 0}$. Then, the entrance fee of
facility at location $\ell$ is $e(\ell)$. So if an agent $i$ selects facility
$j$, the cost incurred by the agent is the sum:
$|x_{i}-\ell_{j}|+e(\ell_{j})$. For an entrance fee function $e$, let
$e_{max}=\max_{x\in\mathbb{R}}e(x)$ and $e_{min}=\min_{x\in\mathbb{R}}e(x)$.
The _max-min ratio_ of $e$, denoted by $r_{e}$ is defined as $r_{e}=1$ if
$e_{min}=e_{max}=0$; $r_{e}=+\infty$ if $e_{min}=0$ and $e_{max}>0$; else,
$r_{e}=e_{max}/e_{min}$.

Each agent always selects a facility that minimizes the sum of her travel fee
and entrance fee. So, we define the _cost_ of agent $i$ for a given facility
location profile $\bm{\ell}$ as $\mathrm{cost}(x_{i},\bm{\ell}):=\min_{j\in
F}\\{|x_{i}-\ell_{j}|+e(\ell_{j})\\}$. If there is more than one facility that
minimizes the agent’s cost, we use the tie-breaking rule:

######  Definition 1 (Tie-breaking rule).

Select the facility with the smallest entrance fee. If there are two such
facilities with equal smallest entrance fees, select the right most one.

We consider two classical objectives: the _utilitarian objective_ and
_egalitarian objective_. For utilitarian objective, we want to minimize the
total cost of all agents that we denote by:
$TC(\bm{x},\bm{\ell})=\sum_{i=1}^{n}\mathrm{cost}(x_{i},\bm{\ell}).$ For
egalitarian objective, we want to minimize the maximum cost of all agents that
is denoted by $MC(\bm{x},\bm{\ell})=max_{i\in
N}\\{\mathrm{cost}(x_{i},\bm{\ell})\\}.$

######  Remark 1.

To keep our exposition as general as possible, we assume that there is an
oracle that computes $e(x)$ for a given $x\in\mathbb{R}$ and for any integer
$a$ and $b$, finds the minimum of $ae(x)+bx$ in a given interval.

In the setting of mechanism design, each agent $i$’s location $x_{i}$ is
private. The agent is required to report location $x_{i}^{\prime}$ which may
be different from her true position. A (deterministic) _mechanism_ outputs
facility location profile $\bm{\ell}$ according to the entrance fee function
$e$ and the reported location profile
$\bm{x}^{\prime}=(x_{1}^{\prime},\cdots,x_{n}^{\prime})$:

######  Definition 2 (Deterministic Mehchanism).

A deterministic mechanism is a function
$f(\cdot,\cdot):\mathcal{E}\times\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$,
where $\mathcal{E}$ is the set of all entrance fee functions
$e:\mathbb{R}\rightarrow\mathbb{R}_{\geq 0}$.

In the classical model, a mechanism is a function from $\mathbb{R}^{n}$ to
$\mathbb{R}^{m}$ that given a location profile of agents outputs a location
profile of facilities. Definition 2 stipulates that the entrance fee functions
are part of the input of our mechanisms. Thus, for our deterministic mechanism
$f(\cdot,\cdot)$, given an entrance fee function
$e(\cdot):\mathbb{R}\rightarrow\mathbb{R}_{\geq 0}$ as an input, we get a
classical deterministic mechanism
$f(e,\cdot):\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$.

We can also define randomized mechanisms in our setting:

######  Definition 3 (Randomized Mehchanism).

A randomized mechanism is a function
$f(\cdot,\cdot):\mathcal{E}\times\mathbb{R}^{n}\rightarrow\Delta(\mathbb{R}^{m})$,
where $\mathcal{E}$ is the set of all entrance fee functions
$e:\mathbb{R}\rightarrow\mathbb{R}_{\geq 0}$ and $\Delta(\mathbb{R}^{m})$ is
the set of all probability distributions over $\mathbb{R}^{m}$.

For an given $e(\cdot):\mathbb{R}\rightarrow\mathbb{R}_{\geq 0}$ and a
randomized mechanism $f(\cdot,\cdot)$, if $f(e,\bm{x})=P$, where $P$ is a
probability distribution, the cost of an agent $i\in N$ is defined as the
expected cost of $i$, i.e., $\mathrm{cost}(x_{i},P):=\mathbb{E}_{\bm{\ell}\sim
P}\mathrm{cost}(x_{i},\bm{\ell})$

Note that the number of facilities $m$ and the entrance fee function $e$ are
publicly known. Given that an agent might misreport her location to decrease
her cost, it is necessary to design _(group) strategyproof_ mechanisms.

######  Definition 4 (Group strategyproof).

A mechanism $f(\cdot,\cdot)$ is group strategyproof if for any entrance fee
function $e$, any profile $\bm{x}$, any coalition $S\subseteq N$ with any sub-
location profile $\bm{x}_{S}^{\prime}\in\mathbb{R}^{|S|}$, there exists an
agent $i\in S$ such that
$\mathrm{cost}(x_{i},f(e,\bm{x}))\leq\mathrm{cost}(x_{i},f(e,\bm{x}^{\prime}))$,
where $\bm{x}^{\prime}=(\bm{x}_{S}^{\prime},\bm{x}_{-S})$ is obtained from
$\bm{x}$ by replacing the location profile of all agents in $S$ with
$\bm{x}_{S}^{\prime}$.

In Definition 4 if $S$ only contains one agent, then definition is referred to
as _strategyproof_. (Group) strategyproof mechanisms may not be able to
achieve the optimal value of the two objectives. Therefore we use
_approximation ratio_ to evaluate the performance of the mechanism. For an
entrance fee function $e$ and location profile $\bm{x}\in\mathbb{R}^{n}$, let
$OPT_{tc}(e,\bm{x})$ and $OPT_{mc}(e,\bm{x})$ be the optimal total cost and
the optimal maximum cost of the optimization problems, respectively.

######  Definition 5 (Approximation ratio).

For an entrance fee function $e$ and location profile $\bm{x}$, the
approximation ratio of $f(e,\bm{x})$ is
$\gamma(f(e,\bm{x})):={TC(\bm{x},f(e,\bm{x}))}/{OPT_{tc}(e,\bm{x})}$, the
approximation ratio of $f(e,\cdot)$ is defined as
$\gamma(f(e,\cdot)):=\sup_{\bm{x}}\gamma(f(e,\bm{x}))$, and the approximation
ratio of $f(\cdot,\cdot)$ is defined as
$\gamma(f(\cdot,\cdot)):=\sup_{e\in\mathcal{E}}\gamma(f(e,\cdot))$.

The approximation ratio for the maximum cost is defined in the same way by
replacing $TC(\bm{x},f(e,\bm{x}))/OPT_{tc}(e,\bm{x})$ with
${MC(\bm{x},f(e,\bm{x}))}/{OPT_{mc}(e,\bm{x})}$.

##  3 Structural Properties

###  3.1 Local monotonicity and optimization

Let $e:\mathbb{R}\rightarrow\mathbb{R}_{\geq 0}$ be an entrance fee function.
Given a location $x\in\mathbb{R}$ of an agent, let $x^{*}$ be the facility
location that minimizes the cost of the agent:
$x^{*}:=\operatorname*{arg\,min}_{\ell\in\mathbb{R}}(|x-\ell|+e(\ell))$. If
there are multiple locations minimizing the cost, we use the tie-breaking rule
in Definition 1. We single out the value $x^{*}$:

######  Definition 6.

In the setting above, we call $x^{*}$ the optimal location for $x$, and
$e(x^{*})$ the optimal entrance fee for $x$. We call
$C_{i}:=\mathrm{cost}(x_{i},x_{i}^{*})$ the optimal cost for the agent $i$.

In order to find the optimal location $x^{*}$ for $x$, the definition asks us
to search the whole space of reals. This global search can be reduced to local
search in the neighborhood of $x$ as shown in the next lemma.

######  Lemma 1.

The optimal location for an agent at $x\in\mathbb{R}$ is

$\displaystyle x^{*}=\operatorname*{arg\,min}_{\ell:|\ell-x|\leq
e(x)}|\ell-x|+e(\ell).$

###### Proof.

If the facility is placed at location $\ell=x$, then the cost for the agent at
$\ell=x$ is $e(x)$. Therefore any location $\ell$ placed at distance more that
$e(x)$ cannot be optimal. Hence,
$x^{*}=\operatorname*{arg\,min}_{\ell:|\ell-x|\leq e(x)}|\ell-x|+e(\ell)$. ∎

By Remark 1, $x^{*}$ can be computed in a constant time.

######  Lemma 2 (Monotonicity).

For any $x_{1},x_{2}\in\mathbb{R}$, we have $x_{1}^{*}\leq x_{2}^{*}$ if and
only if $x_{1}\leq x_{2}$.

###### Proof.

By the definition of $x_{1}^{*}$ and $x_{2}^{*}$ we have

$\displaystyle\mathrm{cost}(x_{1},x_{1}^{*})-\mathrm{cost}(x_{1},x_{2}^{*})$
$\displaystyle=|x_{1}-x_{1}^{*}|-|x_{1}-x_{2}^{*}|+$ $\displaystyle\quad
e(x_{1}^{*})-e(x_{2}^{*})\leq 0,$ (1)
$\displaystyle\mathrm{cost}(x_{2},x_{2}^{*})-\mathrm{cost}(x_{2},x_{1}^{*})$
$\displaystyle=|x_{2}-x_{2}^{*}|-|x_{2}-x_{1}^{*}|+$ $\displaystyle\quad
e(x_{2}^{*})-e(x_{1}^{*})\leq 0.$ (2)

By adding (1) and (2), we get

$\displaystyle|x_{1}-x_{1}^{*}|+|x_{2}-x_{2}^{*}|\leq|x_{1}-x_{2}^{*}|+|x_{2}-x_{1}^{*}|.$
(3)

Assume that $x_{1}<x_{2}$ but $x_{1}^{*}>x_{2}^{*}$. If
$(x_{1},x_{2})\cap(x_{2}^{*},x_{1}^{*})\neq\emptyset$, then (3) does not hold.
If $(x_{1},x_{2})\cap(x_{2}^{*},x_{1}^{*})=\emptyset$, then (3) turns into
equality. By (1) and (2), we get
$\mathrm{cost}(x_{2},x_{2}^{*})=\mathrm{cost}(x_{2},x_{1}^{*})$ and
$\mathrm{cost}(x_{1},x_{1}^{*})=\mathrm{cost}(x_{1},x_{2}^{*})$. Then by tie-
breaking rule in Definition 1, we have $x_{1}^{*}=x_{2}^{*}$. ∎

Let $I(x)$ be the open interval between $x$ and $x^{*}$. The next lemma
connects $I(x)$ and $x^{*}$.

######  Lemma 3.

Either $I(x_{1})\cap I(x_{2})=\emptyset$ or $x_{1}^{*}=x_{2}^{*}$.

###### Proof.

Let $x_{1}<x_{2}$. Then $x_{1}^{*}\leq x_{2}^{*}$ by the Monotonicity Lemma.
Suppose for contradiction that $I(x_{1})\cap I(x_{2})\neq\emptyset$ and
$x_{1}^{*}\neq x_{2}^{*}$. Then we have $x_{1}<x_{2}\leq x_{1}^{*}<x_{2}^{*}$.
Then

$\mathrm{cost}(x_{1},x_{1}^{*})=(x_{2}-x_{1})+(x_{1}^{*}-x_{2})+e(x_{1}^{*})=$
$x_{2}-x_{1}+\mathrm{cost}(x_{2},x_{1}^{*})\geq
x_{2}-x_{1}+\mathrm{cost}(x_{2},x_{2}^{*})=$
$(x_{2}-x_{1})+(x_{2}^{*}-x_{2})+e(x_{2}^{*})=\mathrm{cost}(x_{1},x_{2}^{*})$.

This implies
$\mathrm{cost}(x_{1},x_{1}^{*})\geq\mathrm{cost}(x_{1},x_{2}^{*})$. Strict
inequality cannot happen. Therefore,
$\mathrm{cost}(x_{1},x_{1}^{*})\geq\mathrm{cost}(x_{1},x_{2}^{*})$. By the
tie-breaking rule in Definition 1, $x_{1}^{*}=x_{2}^{*}$. ∎

######  Lemma 4.

Assume that $x_{1}\leq x_{2}\leq x_{3}$. Then we have
$\mathrm{cost}(x_{1},x_{1}^{*})\leq\mathrm{cost}(x_{1},x_{2}^{*})\leq\mathrm{cost}(x_{1},x_{3}^{*})$.
Similarly,
$\mathrm{cost}(x_{3},x_{3}^{*})\leq\mathrm{cost}(x_{3},x_{2}^{*})\leq\mathrm{cost}(x_{3},x_{1}^{*})$.

###### Proof.

It is clear that
$\mathrm{cost}(x_{1},x_{1}^{*})\leq\mathrm{cost}(x_{1},x_{2}^{*})$. Also, by
the Monotonicity Lemma, we have $x_{1}^{*}\leq x_{2}^{*}\leq x_{3}^{*}$. If
$x_{1}^{*}=x_{2}^{*}$ or $x_{2}^{*}=x_{3}^{*}$, then this lemma is clearly
true. Thus, we assume that $x_{1}^{*}<x_{2}^{*}<x_{3}^{*}$. Now consider the
case when $x_{1}\leq x_{1}^{*}$, $x_{2}\leq x_{2}^{*}$ and $x_{3}\leq
x_{3}^{*}$. Then, we have
$\mathrm{cost}(x_{1},x_{3}^{*})=(x_{3}-x_{1})+e(x_{3}^{*})$ by definition.
Hence,

$\displaystyle\mathrm{cost}(x_{1},x_{2}^{*})$
$\displaystyle=|x_{1}-x_{2}^{*}|+e(x_{2}*)$
$\displaystyle\leq(x_{2}-x_{1})+(x_{3}^{*}-x_{2})+e(x_{3}^{*})$
$\displaystyle=\mathrm{cost}(x_{1},x_{3}^{*}).$

The other cases are verified similarly. ∎

Next, we capture the property that one location is preferred by each agent
over another location.

######  Definition 7 (Domination).

Location $\ell_{1}$ dominates location $\ell_{2}$ if
$\mathrm{cost}(x_{i},\ell_{1})\leq\mathrm{cost}(x_{i},\ell_{2})$ for all $i\in
N$.

######  Lemma 5.

For any $x\in\mathbb{R}$, $x^{*}$ dominates all locations in $I[x]$.

###### Proof.

Assume without loss of generality that $x\leq x^{*}$. Let $\ell\in I[x]$ and
$i\in N$. For each agent $i$, there are three cases.

Case 1: $x_{i}\leq\ell$. Note that $e(\ell)\geq x^{*}-\ell+e(x^{*})$ as
$\mathrm{cost}(x,\ell)\geq\mathrm{cost}(x,x^{*})$. Therefore, we have

$\displaystyle\mathrm{cost}(x_{i},\ell)$ $\displaystyle=\ell-
x_{i}+e(\ell)\geq(\ell-x_{i})+(x^{*}-\ell)+e(x^{*})$
$\displaystyle=cost(x_{i},x^{*}).$

Case 2: $\ell<x_{i}<x^{*}$. We have the following calculations:

$\displaystyle\mathrm{cost}(x_{i},\ell)$ $\displaystyle=x_{i}-\ell+e(\ell)\geq
x_{i}-\ell+x^{*}-\ell+e(x^{*})$ $\displaystyle\geq
x^{*}-x_{i}+e(x^{*})=cost(x_{i},x^{*}).$

Case 3: $x^{*}\leq x_{i}$. Similarly: $\mathrm{cost}(x_{i},\ell)\leq
cost(x_{i},x^{*})$. ∎

###  3.2 Global optimization

By the Monotonicity Lemma, $x_{1}^{*}\leq x_{n}^{*}$. For $m=1$, let
$\ell_{tc}$ be the location that minimizes the total cost, i.e.,
$\ell_{tc}=\operatorname*{arg\,min}_{\ell\in\mathbb{R}}TC(\bm{x},\ell)$. If
there are multiple solutions, then we use the tie-breaking rule from
Definition 1. Define $\ell_{mc}$ as the location that minimizes the maximum
cost similarly.

######  Lemma 6.

$\ell_{tc}$ and $\ell_{mc}\in[x_{1}^{*},x_{n}^{*}]$.

###### Proof.

Suppose for contradiction that $\ell_{tc}<x_{1}^{*}$ or $\ell_{tc}>x_{n}^{*}$.
We will only disprove $\ell_{tc}<x_{1}^{*}$ since $\ell_{tc}>x_{n}^{*}$ can be
disproved by symmetry.

Case 1: $x_{1}^{*}<x_{1}$. We have
$\mathrm{cost}(x_{1},\ell_{tc})\geq\mathrm{cost}(x_{1},x_{1}^{*})$. Thus
$x_{1}^{*}$ dominates $\ell_{tc}$. This implies $TC(\bm{x},\ell_{tc})\geq
TC(\bm{x},x_{1}^{*})$. This is a contradiction.

Case 2: $x_{1}^{*}\geq x_{1}$. Then we must have $\ell_{tc}<x_{1}$ because of
Lemma 5. Thus, $x_{1}^{*}$ dominates $\ell_{tc}$. Given the tie-breaking rule
in Definition 1, this is a contradiction.

In a similar way, we can prove $\ell_{mc}\in[x_{1}^{*},x_{n}^{*}]$. ∎

We would like to design effective algorithms that find the optimal facility
locations.

######  Lemma 7.

When there is only one facility, the two optimization problems can be solved
in $O(n)$ time.

###### Proof.

Let $\ell_{tc}^{(k)}$ be the location in $(x_{k},x_{k+1}]$ such that the total
cost is minimized:

$\displaystyle\ell_{tc}^{(k)}$
$\displaystyle=\operatorname*{arg\,min}_{\ell\in(x_{k},x_{k+1}]}TC(\bm{x},\ell)=\operatorname*{arg\,min}_{\ell\in(x_{k},x_{k+1}]}\sum_{i=1}^{i=n}|x_{i}-\ell|+ne(\ell)$
$\displaystyle=\operatorname*{arg\,min}_{\ell\in(x_{k},x_{k+1}]}\sum_{i=1}^{i=k}(\ell-
x_{i})+\sum_{i=k+1}^{i=n}(x_{i}-\ell)+ne(\ell)$
$\displaystyle=\operatorname*{arg\,min}_{\ell\in(x_{k},x_{k+1}]}(ne(\ell)+(2k-n)\ell-\sum_{i=1}^{i=k}x_{i}+\sum_{i=k+1}^{i=n}x_{i}).$

By Lemma 6, it is sufficient to optimize over at most $n+1$ intervals and we
get $\ell_{tc}$. To obtain $\ell_{mc}$, we only need to optimize over agents
$1$ and $n$. ∎

When $m>1$, we have the following lemma that describes the structure of a
solution.

######  Lemma 8.

For a given facility location profile, if two agents select the same facility,
then any agent located between these two agents also selects the same
facility.

###### Proof.

Let $\bm{\ell}=\\{\ell_{1},\cdots,\ell_{n}\\}$ be the facility location
profile, $p,q,r\in N$ be three agents such that $x_{p}<x_{q}<x_{r}$ and $p,r$
select the same facility, say $\ell_{1}$. Let $M$ be a large positive, say
$n\cdot\mathrm{TC}(\bm{x},\bm{\ell})$. Then we construct a new entrance fee
function $e^{\prime}:\mathbb{R}^{n}\rightarrow\mathbb{R}$ such that
$e^{\prime}(\ell)=e(\ell_{i})$ if $\ell=\ell_{i}$ for a certain $i\in N$ and
$e^{\prime}(\ell)=M$ if $\ell\neq\ell_{i}$ for any $i\in N$. We claim that,
the optimal location for an agent under $e^{\prime}$ is the location of the
facility selected by the agent. Denote by $x_{i}^{*}(e^{\prime})$ be the
optimal location for agent $i$ under entrance fee function
$e^{\prime}(\cdot)$. Thus we have
$x_{i}^{*}(e^{\prime})=x_{k}^{*}(e^{\prime})=\ell_{1}$. Since
$x_{i}<x_{j}<x_{k}$, by the Monotonicity Lemma, we have
$x_{j}^{*}(e^{\prime})=\ell_{1}$. ∎

Equipped with Lemmas 6 and 8, the next lemma shows that the optimal solutions
when $m>1$ can be found in polynomial time.

######  Proposition 1.

For general $m$ number of facilities, the two optimization problems can be
solved in $O(n^{3}m)$ time.

###### Proof.

Let $N_{j}$ be the set of customers of facility $j$, $\ell_{j}$ be the
location of facility $j$, then a solution is denoted by
$\\{(\ell_{j},N_{j})\\}_{j=1}^{m}$ where $\bigcup_{j=1}^{n}N_{j}=N$ and the
sets $N_{j}$ are pairwise disjoint. Recall that $x_{1}\leq\cdots x_{n}$, we
say a subset of agents $N_{j}\subseteq N$ is _continuous_ if
$N_{i}=\\{x_{j_{1}},x_{j_{1}+1},\cdots,x_{j_{2}}\\}$ for some $1\leq j_{1}\leq
j_{2}\leq n$. By Lemma 8, we have that $N_{j}$ is continuous. Denote by
$[i,j]$ the continuous set of agents $\\{i,i+1,\cdots,j\\}$.

First, we consider the problem of minimizing the total cost. We use
$OPT_{tc}(i,j,k)$ to represent the minimum total cost when agents $[1,j]$ are
divided into $k$ partitions, and $i\leq j$ are in the $k$th partition. Thus
the optimal total cost to our problem is $OPT_{tc}(n,n,m)$. Denote by
$v_{tc}(i,j)$ the optimal total cost incurred by agents $[i,j]$ when they are
served by a single facility. By Lemma 7, $v_{tc}(i,j)$ can be computed in
$O(n)$ time.

We will make use of a $n\times n\times m$ array $M$, whose entries are
initially set to empty. We invoke Algorithm 1 to compute $OPT_{tc}(n,n,m)$ and
recover the solution from the values stored in $M$.

Algorithm 1 $OPT_{tc}(i,j,k)$

1: if $i=0$ or $j=0$ or $k=0$ then

2: Return $0$.

3: else if $M(i,j,k)$ not empty then

4: Return $M(i,j,k)$.

5: else

6:
$M(i,j,k)\leftarrow\min\\{OPT_{tc}(i-1,j,k),OPT_{tc}(i-1,i-1,k-1)+v_{tc}(i,j)\\}$
Return $M(i,j,k)$

7: end if

We argue for the correctness. The base case is clear. The total cost is zero
if there are no agents or no facilities. Suppose we want to compute
$OPT_{tc}(i,j,k)$ and we have already computed
$OPT_{tc}(i^{\prime},j^{\prime},k^{\prime})$ where $i^{\prime}<i$ or
$j^{\prime}<j$ or $k^{\prime}<k$. We distinguish between two cases depending
on whether or not agent $i-1$ is still in the $k$th partition. If agent $i-1$
is also in the $k$th partition, then $OPT_{tc}(i,j,k)=OPT_{tc}(i-1,j,k)$.
Otherwise we know that $i-1$ is exactly on the right boundary of the $(k-1)$th
partition and agents in $[i,j]$ are served by a single facility, thus
$OPT_{tc}(i,j,k)=OPT_{tc}(i-1,i-1,k-1)+v_{tc}(i,j)$. Actually, we derive the
following transition function:

$\displaystyle OPT_{tc}(i,j,k)$ $\displaystyle=\min\\{OPT_{tc}(i-1,j,k),$
$\displaystyle OPT_{tc}(i-1,i-1,k-1)+v_{tc}(i,j)\\}.$

It easy to see the running time of Algorithm 1 is $O(mn^{3})$ by using
memorization.

Next, we consider the problem of minimizing the maximum cost. Let
$OPT_{mc}(i,j,k)$ be the minimum maximum cost of agents $[1,j]$ when agents
$[1,j]$ are divided into $k$ partitions, and $i\leq j$ are in the $k$th
partition. Let $v_{mc}(i,j)$ the optimal maximum cost of agents $[i,j]$ when
they are served by a single facility. In slightly different way, we derive the
transition function for the maximum cost as follows, and the algorithm to
compute $OPT_{mc}(i,j,k)$ is similar to Algorithm 1

$\displaystyle OPT_{mc}(i,j,k)=\min\\{OPT_{mc}(i-1,j,k),$
$\displaystyle\min\\{OPT_{mc}(i-1,i-1,k-1),v_{mc}(i,j)\\}\\}.$

∎

##  4 Utilitarian Version With One Facility

In this section, we consider the objective of minimizing the total cost for
the one-facility game. We will first investigate deterministic mechanisms, and
then turn our attention to randomized mechanisms.

###  4.1 Deterministic Mechanisms

Let $\bm{x}=(x_{1},\cdots,x_{n})$ be the reported location profile by the
agents. We assume that the agents are ordered such that $x_{1}\leq\dots\leq
x_{n}$. Denote by $m_{i}(\cdot,\cdot)$ the mechanism that outputs the optimal
location $x_{i}^{*}$ for agent $i$ for any input $e$ and $\bm{x}$.

######  Theorem 1.

The mechanism $m_{i}(\cdot,\cdot)$ is group strategyproof.

###### Proof.

Obviously, any agent at $x_{i}$ has no incentive to misreport. To modify the
output of $m_{i}(\cdot,\cdot)$, at least one agent located in $[x_{1},x_{i})$
has to misreport a location strictly greater than $x_{i}$ or at least one
agent in $(x_{i},x_{n}]$ has to misreport a location strictly smaller than
$x_{i}$. We will prove that in either case the agent will not benefit from
misreporting.

We only consider the case when agent $j$ with $x_{j}<x_{i}$ misreports a
location $x_{j}^{\prime}>x_{i}$. The other case is proved in a similar way.
Let $x_{i}^{\prime}$ be the $i$th order statics in
$(x_{j}^{\prime},\bm{x}_{-j})$. Then we have $x_{j}<x_{i}\leq x_{i}^{\prime}$.
Let $\bm{x}^{\prime}=(x_{j}^{\prime},\bm{x}_{-j})$ and
$x_{i}^{\prime*}=m_{i}(e,\bm{x}^{\prime})$. By Lemma 4, we have
$\mathrm{cost}(x_{j},x_{i}^{*})\leq\mathrm{cost}(x_{j},x_{i}^{\prime*})$.
Therefore, agent $j$ has no incentive to misreport. ∎

Let $m_{med}(\cdot,\cdot)$ be the mechanism that always outputs the optimal
location $x_{med}^{*}$ for the median agent $med=\lceil n/2\rceil$.

We analyze the approximation ratio of $m_{med}(\cdot,\cdot)$ for the total
cost. Let $\bm{x}\in\mathbb{R}^{n}$, $\ell\in\mathbb{R}$ and
$e_{\ell}\in\mathbb{R}_{\geq 0}$. To ease our analysis, we introduce the
notion of _virtual total cost_ $VT(\bm{x},\ell,e_{\ell}):=\sum_{i\in
N}|x_{i}-\ell|+n\cdot e_{\ell}$, which is the total cost of $\bm{x}$ when a
_virtual facility_ is located at $\ell$ with entrance fee $e_{\ell}$. It is
possible $e_{\ell}\neq e(\ell)$. When $e_{\ell}=e(\ell)$, we have
$VT(\bm{x},\ell,e_{\ell})=TC(\bm{x},\ell)$. The _virtual cost_ of agent $i$ is
$\mathrm{vcost}(x_{i},\ell,e_{\ell}):=|x_{i}-\ell|+e_{\ell}$. Clearly,
$\mathrm{vcost}(x_{i},\ell,e(\ell))=\mathrm{cost}(x_{i},\ell)$ when
$e_{\ell}=e(\ell)$.

######  Observation 1.

Let $\bm{x}\in\mathbb{R}^{n}$, $\ell_{1},\ell_{2}\in\mathbb{R}$ and
$e_{1},e_{2}\in\mathbb{R}_{\geq 0}$ such that $e_{1}<e_{2}$. If
$\ell_{2}\leq\ell_{1}\leq x_{med}$ or $x_{med}\leq\ell_{1}\leq\ell_{2}$, then
$VT(\bm{x},\ell_{1},e_{1})<VT(\bm{x},\ell_{1},e_{2})\leq
VT(\bm{x},\ell_{2},e_{2})$.

Next, we show that the approximation ratio of $m_{med}(\cdot,\cdot)$ can be
bounded by a constant.

######  Theorem 2.

For each entrance fee function $e$ with max-min ratio $r_{e}$, the
approximation ratio of $m_{med}(e,\cdot)$ for the total cost is at most
$3-\frac{4}{r_{e}+1}$. This also implies that the approximation ratio of
$m_{med}(\cdot,\cdot)$ for the total cost is at most $3$.

###### Proof.

Assume without loss of generality that $x_{med}\leq x_{med}^{*}$. Recall that
$C_{med}$ is the optimal cost of the median agent. For any agent location
$x_{i}$, if $x_{i}\leq x_{med}$, it is easy to see that
$\mathrm{cost}(x_{i},x_{med}^{*})=\mathrm{vcost}(x_{i},x_{med},C_{med})$. If
$x_{i}>x_{med}$, we have
$\mathrm{cost}(x_{i},x_{med}^{*})<\mathrm{vcost}(x_{i},x_{med},C_{med})$. Thus

$\displaystyle TC(\bm{x},x_{med}^{*})\leq VT(\bm{x},x_{med},C_{med}).$ (4)

Next we prove $e(\ell_{tc})\leq C_{med}$. Suppose for contradiction that
$e(\ell_{tc})>C_{med}$, then by Observation 1 and (4) we have

$\displaystyle TC(\bm{x},\ell_{tc})>VT(\bm{x},x_{med},C_{med})\geq
TC(\bm{x},x_{med}^{*}).$

This is a contradiction. Hence, there is an location $\ell_{tc}^{\prime}$
between $x_{med}$ and $\ell_{tc}$ such that

$\displaystyle\mathrm{vcost}(x_{med},\ell_{tc}^{\prime},e(\ell_{tc}))=C_{med}.$
(5)

By Observation 1 we have

$\displaystyle TC(\bm{x},\ell_{tc})\geq
VT(\bm{x},\ell_{tc}^{\prime},e(\ell_{tc})).$ (6)

Thus by (6) and (4) we have

$\displaystyle\gamma(m_{med}(e,\bm{x}))$
$\displaystyle\leq\frac{VT(\bm{x},x_{med},C_{med})}{VT(\bm{x},\ell_{tc}^{\prime},e(\ell_{tc}))}.$
(7)

We will identify a location profile $\bm{x}^{\prime}\in\mathbb{R}^{n}$ for
each $\bm{x}$ such that the bound given by (7) for $\bm{x}$ is no greater than
that for $\bm{x}^{\prime}$. Let $n_{1}=|\\{i\in N|x_{i}\leq
x_{med}<\ell_{tc}^{\prime}\text{ or }x_{i}\geq
x_{med}\geq\ell_{tc}^{\prime}\\}|$ and $n_{2}-n_{1}$. Thus $n_{1}\geq n_{2}$.
Let $\bm{x}^{\prime}$ be the profile such that $n_{1}$ agents are in $x_{med}$
and $n_{2}$ agents are in $\ell_{tc}^{\prime}$. By (5) we have
$|x_{med}-\ell_{tc}^{\prime}|=|C_{med}-e(\ell_{tc})|$ . Let
$\Delta=|C_{med}-e(\ell_{tc})|$. By (7) we have

$\displaystyle\gamma(m_{med}(e,\bm{x}))$
$\displaystyle\leq\frac{VT(\bm{x}^{\prime},x_{med},C_{med})}{VT(\bm{x}^{\prime},\ell_{tc}^{\prime},e(\ell_{tc}))}$
$\displaystyle=\frac{(C_{med}+\Delta)\cdot\frac{n_{2}}{n_{1}}+C_{med}}{e(\ell_{tc})\cdot\frac{n_{2}}{n_{1}}+C_{med}}.$
(8)

Since $C_{med}+\Delta\geq e(\ell_{tc})$ and $n_{2}/n_{1}\leq 1$, (8) is
maximized when $n_{1}=n_{2}$ and $e_{min}\leq e(\ell_{tc})\leq C_{med}\leq
e_{max}$, we have

$\displaystyle\gamma(m_{med}(e,\bm{x}))$
$\displaystyle\leq\frac{2C_{med}+\Delta}{C_{med}+e(\ell_{tc})}\leq
3-\frac{4}{C_{med}/e(\ell_{tc})+1}$ $\displaystyle\leq 3-\frac{4}{r_{e}+1}.$

This proves the first part of the theorem. And the second part follows
immediately. ∎

The example in Figure 2 shows that the approximation ratio of
$3-\frac{4}{r_{e}+1}$ in Theorem 2 is tight for our mechanism
$m_{med}(\cdot,\cdot)$. Let $L>(e_{max}-e_{min})$ be a constant. We consider
the following entrance fee function: $e(L)=e_{min}$ and $e(\ell)=e_{max}$ for
any $\ell\neq L$. Assume that $n$ is an even number. There are $n/2$ agents
located at position $0$ and $n/2$ agents located at position $L$. In this
example, the optimal facility location the total cost is $L$, and the facility
location returned by our mechanism is $0$. We can compute the approximation
ratio easily.

Figure 2: A tight example for the approximation ratio of mechanism
$m_{med}(\cdot,\cdot)$. The black dots represent agents. The upper horizontal
line represents the entrance fee function $e$. The height of the vertical line
segment on the agent represents the entrance fee of the agent’s location.

Next, we establish a tight lower bound for the total cost approximation
against all strategyproof mechanisms. Thus we can assert that no strategyproof
mechanism can do better than $m_{med}(\cdot,\cdot)$.

######  Theorem 3.

For any given $\alpha\geq 1$, there exists an entrance fee function $e$ with
max-min ratio $r_{e}=\alpha$ such that no strategyproof mechanism
$f(e,\cdot):\mathbb{R}^{n}\rightarrow\mathbb{R}$ can achieve a total cost
approximation ratio less than $3-\frac{4}{r_{e}+1}$. This also implies that no
strategyproof mechanism
$f(\cdot,\cdot):\mathcal{E}\times\mathbb{R}^{n}\rightarrow\mathbb{R}$ can
achieve a total cost approximation ratio less than $3$.

###### Proof.

Consider the following entrance fee function:

$e(\ell)=\left\\{\begin{aligned} &d,&&\text{if }\ell\in\\{-1,1\\}\\\
&d+1,&&\text{otherwise}\end{aligned}\right.,$

and $r_{e}=(d+1)/d$. Let $f(e,\cdot)\colon\mathbb{R}^{n}\rightarrow\mathbb{R}$
be a deterministic strategyproof mechanism. Let
$\textbf{x}_{1}=(-1,\varepsilon)$, $\textbf{x}_{2}=(-\varepsilon,1)$ and
$\textbf{x}_{3}=(-1,1)$ be three location profiles, where
$\varepsilon\in(0,1)$ is a small positive number. We illustrate the example in
Figure 3.

Figure 3: Example for the deterministic lower bound $3$. The black dots are
agents and the red triangles denote facilities.

First we consider the profile $\textbf{x}_{1}$, we have

$TC(\textbf{x}_{1},\ell)=\left\\{\begin{aligned} &2d+1+\varepsilon,&&\text{if
}\ell=-1\\\ &2d+3-\varepsilon,&&\text{if }\ell=1\\\
&|\ell+1|+|\ell-\varepsilon|+2d+2\geq 2d+3+\varepsilon,&&\text{otherwise}\\\
\end{aligned}\right..$

Assume, for contradiction, that

$\gamma(f(e,\cdot))<\frac{(3-\varepsilon)r_{e}-1+\varepsilon}{(1+\varepsilon)r_{e}+1-\varepsilon}=\frac{2d+3-\varepsilon}{2d+1+\varepsilon}$

Then we have $f(e,\textbf{x}_{1})=-1$ and
$\mathrm{cost}(\varepsilon,f(e,\textbf{x}_{1}))=d+1+\varepsilon$. By the
symmetry between profiles $\textbf{x}_{1}$ and $\textbf{x}_{2}$, we also have
$f(e,\textbf{x}_{2})=1$ and
$\mathrm{cost}(-\varepsilon,f(e,\textbf{x}_{2}))=d+1+\varepsilon$.

Now consider profile $\textbf{x}_{3}$. If $f(e,\textbf{x}_{3})=-1$, then the
agent at $-\varepsilon$ in $\textbf{x}_{2}$ can deviate to $-1$ and decrease
her cost from $d+1+\varepsilon$ to $d+1-\varepsilon$, a contradiction. If
$f(e,\textbf{x}_{3})=1$, then the agent at $\varepsilon$ in $\textbf{x}_{1}$
can deviate to $1$ and decrease her cost from $d+1+\varepsilon$ to
$d+1-\varepsilon$, a contradiction. Therefore, we have
$\gamma(f(e,\cdot))\geq\frac{(3-\varepsilon)r_{e}-1+\varepsilon}{(1+\varepsilon)r_{e}+1-\varepsilon}$
for small enough $\varepsilon>0$. ∎

###  4.2 Randomized Mechanisms

For any agent location profile $\bm{x}\in\mathbb{R}^{n}$, our deterministic
mechanism $m_{med}(\cdot,\cdot)$ always outputs $x_{med}^{*}$, i.e., the
optimal location for median agent. Recall that $\ell_{tc}$ is the the optimal
location that minimizes the total cost. A natural randomized mechanism is to
randomizedly output $x_{med}^{*}$ and $\ell_{tc}$ in a strategyproof way. We
first define the _critical position_ between $x_{med}^{*}$ and $\ell_{tc}$ as
a position $x_{crit}$ such that agent in $x_{crit}$ is indifferent to
$x_{med}^{*}$ and $\ell_{tc}$, i.e.,
$|x_{crit}-x_{med}^{*}|+e(x_{med}^{*})=|x_{crit}-\ell_{tc}|+e(\ell_{tc})$. It
is easy to verify that there is one and only one critical position. A key
observation is that the preferences for $x_{med}^{*}$ and $\ell_{tc}$ will
turn over in $x_{crit}$: agents between $x_{crit}$ and $x_{med}^{*}$ prefers
$x_{med}^{*}$ to $\ell_{tc}$ while agents between $x_{crit}$ and $\ell_{tc}$
prefers $\ell_{tc}$. Let $k(\bm{x})$ be the number of agents who (weakly)
prefer $\ell_{tc}$ to $x_{med}^{*}$, i.e., $k(\bm{x})=|\\{i\in
N|x_{med}^{*}\leq x_{crit}\leq x_{i}\text{ or }x_{i}\leq x_{crit}\leq
x_{med}^{*}\\}|$. Then we define our Two-point Randomization Mechanism(TRM) as
follows:

Two-point Randomization Mechanism Given $\bm{x}$ and $e$, return the optimal
location $\ell_{tc}$ with probability $k(\bm{x})/n$, return $x_{med}^{*}$ with
probability $1-k(\bm{x})/n$.

Denote by $t(\cdot,\cdot)$ the Two-point Randomization Mechanism. In next
theorem we show that TRM is group strategyproof.

######  Theorem 4.

The Two-point Randomization Mechanism $t(\cdot,\cdot)$ is group strategyproof.

###### Proof.

Assume without loss of generality that $x_{med}^{*}\leq
x_{crit}\leq\ell_{tc}$. We will prove for any $i\in N$, the cost of agent $i$
will not decrease by misreporting any $x_{i}^{\prime}\in\mathbb{R}$. Let
$p(\bm{x})=k(\bm{x})/n$ be the probability of choosing $\ell_{tc}$. For a
given entrance fee function $e$, we write $t(e,\bm{x})$ as $t(\bm{x})$ for
simplicity. Let $\bm{x}^{\prime}=(x_{i}^{\prime},\bm{x}_{-i})$,
$x_{med}^{\prime}$ be the median of $\bm{x}^{\prime}$ and $\ell_{tc}^{\prime}$
be the optimal location of $\bm{x}^{\prime}$, then we have

$\displaystyle\mathrm{cost}(x_{i},t(\bm{x}))=(1-p(\bm{x}))\cdot\mathrm{cost}(x_{i},x_{med}^{*})+p(\bm{x})\cdot\mathrm{cost}(x_{i},\ell_{tc})$
(9)
$\displaystyle\mathrm{cost}(x_{i},t(\bm{x^{\prime}}))=(1-p(\bm{x}^{\prime}))\cdot\mathrm{cost}(x_{i},x_{med}^{\prime*})+p(\bm{x}^{\prime})\cdot\mathrm{cost}(x_{i},\ell_{tc}^{\prime})$
(10)

Case 1. $x_{i}\leq x_{crit}$.

Subcase 1.1 $x_{i}^{\prime}\leq x_{i}$. Then we have
$x_{med}^{\prime}=x_{med}$. Since $\ell_{tc}^{\prime}\leq\ell_{tc}$, we have
$p(\bm{x}^{\prime})\geq p(\bm{x})$ by definition of $p(\bm{x})$. We claim that
$\mathrm{cost}(x_{i},\ell_{tc})\leq\mathrm{cost}(x_{i},\ell_{tc}^{\prime})$
since otherwise we have $TC(\bm{x},\ell_{tc}^{\prime})\leq
TC(\bm{x},\ell_{tc})$. Thus we have
$\mathrm{cost}(x_{i},x_{med}^{*})=\mathrm{cost}(x_{i},x_{med}^{\prime*})\leq\mathrm{cost}(x_{i},\ell_{tc})\leq\mathrm{cost}(x_{i},\ell_{tc}^{\prime})$.
By (9) and (10), we have
$\mathrm{cost}(x_{i},t(\bm{x}))\leq\mathrm{cost}(x_{i},t(\bm{x^{\prime}}))$.

Subcase 1.2 $x_{i}^{\prime}>x_{i}$. In this case, we have
$x_{med}^{\prime}\geq x_{med}$ and then we have $x_{med}^{\prime*}\geq
x_{med}^{*}$ by Monotonicity Lemma. Thus we get
$\mathrm{cost}(x_{i},x_{med}^{*})\leq\mathrm{cost}(x_{i},x_{med}^{\prime*})$.
We also have
$\mathrm{cost}(x_{i},\ell_{tc})\leq\mathrm{cost}(x_{i},\ell_{tc}^{\prime})$
since $\ell_{tc}\leq\ell_{tc}^{\prime}$. By (9) and (10) we have

$\displaystyle\mathrm{cost}(x_{i},t(\bm{x}))-\mathrm{cost}(x_{i},t(\bm{x^{\prime}}))$
(11)
$\displaystyle\leq(p(\bm{x}^{\prime})-p(\bm{x}))\cdot\mathrm{cost}(x_{i},x_{med}^{\prime*})+(p(\bm{x})-p(\bm{x})^{\prime})\cdot\mathrm{cost}(x_{i},\ell_{tc}^{\prime})$
(12)
$\displaystyle=(p(\bm{x}^{\prime})-p(\bm{x}))\cdot(\mathrm{cost}(x_{i},x_{med}^{\prime*})-\mathrm{cost}(x_{i},\ell_{tc}^{\prime}))$
(13)

Since $p(\bm{x}^{\prime})\leq p(\bm{x})$ and
$\mathrm{cost}(x_{i},x_{med}^{\prime*})\geq\mathrm{cost}(x_{i},\ell_{tc}^{\prime})$,
we have
$\mathrm{cost}(x_{i},t(\bm{x}))\leq\mathrm{cost}(x_{i},t(\bm{x^{\prime}}))$.

Case 2. $x_{i}>x_{crit}$.

Subcase 2.1. $x_{i}^{\prime}\leq x_{i}$. We have $p(\bm{x}^{\prime})\geq
p(\bm{x})$ and
$\mathrm{cost}(x_{i},x_{med}^{\prime*})\geq\mathrm{cost}(x_{i},x_{med}^{\prime*})$.
By similar argument in Subcase 1.2, we have
$\mathrm{cost}(x_{i},t(\bm{x}))\leq\mathrm{cost}(x_{i},t(\bm{x^{\prime}}))$.

Subcase 2.2. $x_{i}^{\prime}>x_{i}$. In this case, we have
$x_{med}^{\prime}\geq x_{med}$ and $p(\bm{x}^{\prime})\leq p(\bm{x})$. We
claim that
$\mathrm{cost}(x_{i},\ell_{tc})\geq\mathrm{cost}(x_{i},\ell_{tc}^{\prime})$
since otherwise we have $TC(\bm{x},\ell_{tc}^{\prime})\geq
TC(\bm{x},\ell_{tc})$. Thus we have
$\mathrm{cost}(x_{i},x_{med}^{*})=\mathrm{cost}(x_{i},x_{med}^{\prime*})\geq\mathrm{cost}(x_{i},\ell_{tc}^{\prime})\geq\mathrm{cost}(x_{i},\ell_{tc})$.
By (9) and (10), we have
$\mathrm{cost}(x_{i},t(\bm{x}))\leq\mathrm{cost}(x_{i},t(\bm{x^{\prime}}))$. ∎

######  Theorem 5.

For each entrance fee function $e$ with max-min ratio $r_{e}$, the
approximation ratio of $t(e,\cdot)$ for the total cost is at most
$2-\frac{2}{r_{e}+1}$. This also implies that the approximation ratio of
$t(\cdot,\cdot)$ for the total cost is at most $2$.

###### Proof.

By definition we have

$\displaystyle\gamma(t(e,\bm{x}))=\frac{k(\bm{x})}{n}+(1-\frac{k(\bm{x})}{n})\cdot\frac{TC(\bm{x},x_{med}^{*})}{TC(\bm{x},\ell_{tc})}.$
(14)

Assume without loss of generality that $x_{med}^{*}\leq
x_{crit}\leq\ell_{tc}$. We will identify a location profile
$\bm{x}^{\prime}\in\mathbb{R}^{n}$ for each $\bm{x}$ such that the bound given
by (7) for $\bm{x}$ is no greater than that for $\bm{x}^{\prime}$. Let
$\bm{x}^{\prime}$ be the profile such that $n-k(\bm{x})$ agents are in
$x_{med}^{*}$ and $k(\bm{x})$ agents are in $\ell_{tc}$. Since
$k(\bm{x})/n\geq 1/2$, we have

$\displaystyle\gamma(t(e,\bm{x}))$
$\displaystyle\leq\gamma(t(e,\bm{x}^{\prime}))$ (15)
$\displaystyle=\frac{k(\bm{x^{\prime}})}{n}+(1-\frac{k(\bm{x}^{\prime})}{n})\cdot\frac{TC(\bm{x}^{\prime},x_{med}^{\prime*})}{TC(\bm{x},\ell_{tc})}$
(16)
$\displaystyle\leq\frac{1}{2}+\frac{1}{2}\cdot\frac{TC(\bm{x}^{\prime},x_{med}^{\prime*})}{TC(\bm{x},\ell_{tc}^{\prime})}.$
(17)

By Theorem 2 we have

$\displaystyle\frac{TC(\bm{x}^{\prime},x_{med}^{\prime*})}{TC(\bm{x},\ell_{tc}^{\prime})}\leq
3-\frac{4}{r_{e}+1}.$ (18)

By (17) and (18), we have $\gamma(t(e,\bm{x}))\leq 2-\frac{2}{r_{e}+1}$. ∎

The example in Figure 2 shows the approximation ratio in Theorem 5 is tight.
Next we establish a tight lower bound for all strategyproof randomized
mechanisms.

######  Theorem 6.

No strategyproof randomized mechanism
$f(\cdot,\cdot):\mathcal{E}\times\mathbb{R}^{n}\rightarrow\Delta(\mathbb{R})$
can achieve a total cost approximation ratio less than $2$.

###### Proof.

Consider the following entrance fee function:

$\displaystyle e(\ell)=\begin{cases}0,\text{ if }\ell=-1\\\ 0,\text{ if
}\ell=1\\\ +\infty,\text{else}\end{cases}.$

Let $f(e,\cdot):\mathbb{R}^{n}\rightarrow\mathbb{R}$ be a randomized
strategyproof mechanism with bounded approximation ratio for the total cost.
To achieve a bounded approximation ratio, we have
$\mathrm{Pr}[f(e,\textbf{x})=-1]+\mathrm{Pr}[f(e,\textbf{x})=1]=1$ for any
$\textbf{x}\in\mathbb{R}^{n}$.

Let $\textbf{x}_{1}=(-1,\epsilon)$, $\textbf{x}_{2}=(-\epsilon,1)$ and
$\textbf{x}_{3}=(-1,1)$ be three location profiles, where $\epsilon\in(0,1)$
is a small positive number. Let $\mathrm{Pr}[f(e,\textbf{x}_{1})=1]=p$ and
$\mathrm{Pr}[f(e,\textbf{x}_{2})=-1]=p^{\prime}$. We illustrate the example in
Figure 4.

Figure 4: Example for the randomized lower bound $3$. The black dots are
agents.

The approximation ratio of $f$ for $\textbf{x}_{1}$ and $\textbf{x}_{2}$ are:

$\displaystyle\gamma(f(e,\textbf{x}_{1}))=1-p+p\cdot\frac{3-\epsilon}{1+\epsilon};$
(19)
$\displaystyle\gamma(f(e,\textbf{x}_{2}))=1-p^{\prime}+p^{\prime}\cdot\frac{3-\epsilon}{1+\epsilon}.$
(20)

Now consider the case that the agent at $\epsilon$ in $\textbf{x}_{1}$
deviates to $1$. Since this agent prefers location $1$ to location $-1$, by
the strategyproofness of $f(e,\cdot)$, the probability of putting facility in
$1$ must not increase, that is, we must have
$\mathrm{Pr}[f(e,\textbf{x}_{3})=1]\leq p$. Then consider the case that the
agent at $-\epsilon$ in $\textbf{x}_{2}$ deviates to $-1$, again by the
strategyproofness of $f(e,\cdot)$, we must have
$\mathrm{Pr}[f(e,\textbf{x}_{3})=-1]\leq p^{\prime}$. By
$\mathrm{Pr}[f(e,\textbf{x}_{3})=-1]+\mathrm{Pr}[f(e,\textbf{x}_{3})=1]=1$, we
have $p+p^{\prime}\leq 1$. Without loss of generality, we assume $p\leq 1/2$.
Then by (19) and $p\leq 1/2$, we have
$\gamma(f(e,\cdot))\geq\gamma(f(e,\textbf{x}_{1}))\geq\frac{2}{1+\epsilon}$. ∎

##  5 Egalitarian Version with One Facility

Now we turn our interest to study strategyproof mechanisms that approximate
the maximum cost.

######  Theorem 7.

For each entrance fee function $e$ with max-min ratio $r_{e}$, the
approximation ratio of $m_{1}(e,\cdot)$ for the maximum cost is

$\displaystyle\gamma(m_{1}(e,\cdot))\leq\begin{cases}2,&\text{ if }r_{e}\leq
2\\\ 3-\frac{3}{r_{e}+1},&\text{ if }r_{e}>2\\\ \end{cases}.$

Hence, the approximation ratio of $m_{1}(\cdot,\cdot)$ for the maximum cost is
at most $3$.

###### Proof.

Given a location profile $\bm{x}$, recall that $\ell_{mc}$ is the location
that achieves the egalitarian objective. Set $L(\bm{x})=|x_{n}-x_{1}|$. Then
we have two natural lower bounds for $MC(\bm{x},\ell_{mc})$:

$\displaystyle MC(\bm{x},\ell_{mc})$
$\displaystyle\geq\mathrm{cost}(x_{1},\ell_{mc})\geq C_{1},$ (21)
$\displaystyle MC(\bm{x},\ell_{mc})$
$\displaystyle\geq\frac{L(\bm{x})}{2}+e_{min},$ (22)

where $C_{1}=\mathrm{cost}(x_{1},x_{1}^{*})$. Since $MC(\bm{x},x_{1}^{*})\leq
L(\bm{x})+C_{1}$, by (21) and (22) we have

$\displaystyle\gamma(m_{1}(e,\bm{x}))$
$\displaystyle=\frac{MC(\bm{x},x_{1}^{*})}{MC(\bm{x},\ell_{mc})}\leq\frac{L(\bm{x})+C_{1}}{C_{1}},$
(23) $\displaystyle\gamma(m_{1}(e,\bm{x}))$
$\displaystyle\leq\frac{L(\bm{x})+C_{1}}{L(\bm{x})/2+e_{min}}=2+\frac{2(C_{1}-2e_{min})}{L(\bm{x})+2e_{min}}$
(24) $\displaystyle\leq 2+\frac{2(e_{max}-2e_{min})}{L(\bm{x})+2e_{min}}.$
(25)

We will derive the approximation ratio based on $r_{e}$.

Case 1: $e_{max}\leq 2e_{min}$. By (25), we have $\gamma(m_{1}(e,\cdot))\leq
2$.

Case 2: $e_{max}>2e_{min}$. We will divide all possible location profiles into
three subcases based on $L(\bm{x})$.

Subcase 2.1: $L(\bm{x})<C_{1}$. By (23) we have $\gamma(m_{1}(e,\cdot))\leq
2$.

Subcase 2.2: $C_{1}\leq L(\bm{x})\leq 2C_{1}$. By (23) we have
$\gamma(m_{1}(e,\cdot))\leq 3$. Besides, if $C_{1}\leq 2e_{min}$, according to
(24), we have $\gamma(m_{1}(e,\bm{x}))\leq 2$. If $C_{1}>2e_{min}$, by (24)
and $L(\bm{x})\geq C_{1}$, we have $\gamma(m_{1}(e,\bm{x}))\leq
4-8/(r_{e}+2)$. Together with the bound of $3$, we have

$\displaystyle\gamma(m_{1}(e,\bm{x}))\leq\begin{cases}2,&\text{ if }r_{e}\leq
2\\\ 3-\frac{3}{r_{e}+1},&\text{ if }r_{e}>2\\\ \end{cases}.$ (26)

Subcase 2.3: $L(\bm{x})>2C_{1}$. Similarly, if $C_{1}\leq 2e_{min}$, according
to (24), we have $\gamma(m_{1}(e,\bm{x}))\leq 2$. If $C_{1}>2e_{min}$, by (24)
and $L(\bm{x})>2C_{1}$, we have $\gamma(m_{1}(e,\bm{x}))\leq 3-3/(r_{e}+1)$.
When $r_{e}>2$, we have $4-\frac{8}{r_{e}+2}>3-\frac{3}{r_{e}+1}>2$. So we
have (26) as our approximation ratio bound for Case $2$. ∎

When $r_{e}\leq 2$, the classical mechanism $m_{1}(\cdot)$ for maximum cost
shows that the approximation ratio $2$ can be tight. When $r_{e}>2$, the
example in Figure 5 shows that the approximation ratio of
$3-\frac{3}{r_{e}+1}$ is tight for our mechanism $m_{med}(\cdot,\cdot)$.

Figure 5: A tight example for the approximation ratio in Theorem 7. The black
dots represent agents. The upper horizontal line represent the entrance fee
function $e$. The height of the vertical line segment on the agent represent
the entrance fee of tha agent’s location.

Let $e_{max}$ and $e_{min}$ be two positives such that $e_{max}>2e_{min}$. We
consider the following entrance fee function: $e(e_{max})=e_{min}$ and
$e(\ell)=e_{max}$ for any $\ell\neq e_{max}$. There are $n=2$ agents, and the
agent location profile is $\bm{x}=(0,2e_{max})$. In this example, the optimal
facility location for the maximum cost is $e_{max}$, and the facility location
returned by our mechanism is $0$. The approximation ratio can be verified
easily.

Procaccia and Tennenholtz [2013] prove that $2$ is the smallest maximum cost
approximation ratio that any strategyproof mechanism $f(e,\cdot)$ can achieve,
where $e(\cdot)=0$. Next, we establish a stronger lower bound of $2$ for the
maximum cost approximation ratio.

######  Theorem 8.

For any given $\alpha\geq 1$, there exists an entrance fee function $e$ with
max-min ratio $r_{e}=\alpha$ such that no strategyproof mechanism
$f(e,\cdot):\mathbb{R}^{n}\rightarrow\mathbb{R}$ can achieve a total cost
approximation ratio less than $2$.

###### Proof.

We first deal with the case where $N=\\{1,2\\}$, and then extend the proof to
an arbitrary $n$. Consider the following entrance fee function $e$ with max-
min ration $\alpha\geq 1$: $e(1-\alpha)=1$ and $e(\ell)=\alpha$ for any
$\ell\neq 1-\alpha$.

Let $f(\cdot,\cdot):\mathbb{R}^{n}\rightarrow\mathbb{R}$ be strategyproof.
Assume for contradiction that, for any $e\in\mathcal{E}(\alpha)$,
$\gamma(f(e,\cdot))\leq 2-\epsilon$ for a certain $\epsilon\in(0,1)$. Consider
the location profile $\bm{x}=(0,x)$ where $x>0$. To ease the proof we also use
$f_{x}$ to represent $f(e,(0,x))$. Let $L_{\epsilon}$ be the length of
$\bm{x}$ such that
$\frac{L_{\epsilon}+\alpha}{L_{\epsilon}/2+\alpha}=2-\epsilon$, then
$L_{\epsilon}=2(\frac{1}{\epsilon}-1)\alpha$. Suppose $x>L_{\epsilon}$, we
have $\frac{x+\alpha}{x/2+\alpha}>2-\epsilon$. Note that $x+\alpha$ is the
maximum cost when the the facility is at $0\text{ or }x$ and $x/2+\alpha$ is
the optimal maximum cost. To guarantee $\gamma(f(e,(0,x)))\leq 2-\epsilon$,
the facility must be placed in $(0,x)$. Thus $f_{x}\in(0,x)$.

Next we prove $f_{x}\in(0,L_{\epsilon}]$ when $x>L_{\epsilon}$. Suppose for
contradiction that there is an $x^{\prime}>L_{\epsilon}$ such that
$f_{x^{\prime}}>L_{\epsilon}$. Then consider the location profile
$(0,f_{x^{\prime}})$. To guarantee $\gamma(f(e,(0,f_{x^{\prime}})))\leq
2-\epsilon$, we have $f((0,f_{x^{\prime}}))\in(0,f_{x^{\prime}})$. Therefore
$\mathrm{cost}(f_{x^{\prime}},f(0,f_{x^{\prime}}))>\alpha$. Then second agent
in profile $(0,f_{x^{\prime}})$ can benefit by misreporting to $x^{\prime}$.

Figure 6: The Definitions of $e,x,L_{\epsilon},\delta\text{ and }L_{\delta}$

Furthermore, we prove that $f_{y}=f_{z}$ for any distinct $y,z>L_{\epsilon}$.
Assume without loss of generality that $y\neq z$. Suppose for contradiction
that $f_{y}\neq f_{z}$. If $f_{y}>f_{z}$, then agent in $z$ can benefit by
misreporting $y$; If $f_{y}<f_{z}$, then agent in $y$ can benefit by
misreporting $z$. Thus $f_{y}=f_{z}$. Let $\delta\in(0,L_{\epsilon}]$ be the
value of $f_{x}$ for all $x>L_{\epsilon}$. Let $L_{\delta}$ be the length of
$\bm{x}$ such that
$\frac{L_{\delta}-\delta+\alpha}{L_{\delta}/2+\alpha}=2-\epsilon$, which
solves to $L_{\delta}=L_{\epsilon}+2\delta/\epsilon$. Thus we have $\delta\leq
L_{\epsilon}<L_{\delta}$, as shown Figure 6. However, when $x>L_{\delta}$, we
have $\gamma(f(e,\bm{x}))>2-\epsilon$, a contradiction.

To extend this result to arbitrary $n$, simply locate the other $n-2$ agents
at $0$ for each one of the profiles described above. All the arguments given
above go through smoothly. ∎

Next we establish a tight lower bound for the entrance fee function with max-
min ratio greater than $2$.

######  Theorem 9.

For any given $\alpha>2$, there exists an entrance fee function $e$ with max-
min ratio $r_{e}=\alpha$ such that no strategyproof mechanism
$f(e,\cdot):\mathbb{R}^{n}\rightarrow\mathbb{R}$ can achieve a total cost
approximation ratio less than $3-\frac{4}{r_{e}+1}$. This also implies that no
strategyproof mechanism
$f(\cdot,\cdot):\mathcal{E}\times\mathbb{R}^{n}\rightarrow\mathbb{R}$ can
achieve a maximum cost approximation ratio less than $3$.

###### Proof.

We have shown the maximum cost approximation ratio cannot be less than $2$.
Now we show the maximum cost approximation ratio cannot be less than
$3-\frac{4}{r_{e}+1}$ when $r_{e}\geq 2$. Consider the following entrance fee
function:

$e(\ell)=\left\\{\begin{aligned} &d+2,&&\text{if }\ell\in\\{-1,1\\}\\\
&d+4,&&\text{otherwise}\end{aligned}\right.,$

and $r_{e}=(d+4)/(d+2)\geq 2$.

Let $f(e,\cdot):\mathbb{R}^{n}\rightarrow\mathbb{R}$ be a deterministic
strategyproof mechanism. Let $\textbf{x}_{1}=(-\varepsilon,2)$,
$\textbf{x}_{2}=(-2,\varepsilon)$ and $\textbf{x}_{3}=(-2,2)$ be three
location profiles, where $\varepsilon\in(0,1)$ is a small positive number. We
illustrate the example in Figure 7.

Figure 7: Example for the deterministic lower bound $3$. The black dots are
agents and the red triangles denote facilities.

First we consider the profile $\textbf{x}_{1}$, we have

$MC(\textbf{x}_{1},\ell)=\left\\{\begin{aligned} &d+5,&&\text{if }\ell=-1\\\
&d+3+\varepsilon,&&\text{if }\ell=1\\\
&\max\\{|\ell-2|,|\ell+\varepsilon|\\}+d+4\geq
d+5+\frac{1}{2}\varepsilon,&&\text{otherwise}\\\ \end{aligned}\right..$

Assume, for contradiction, that

$\gamma(f(e,\cdot))<\frac{3r_{e}-1}{(1+\varepsilon)r_{e}+1-\varepsilon}=\frac{d+5}{d+3+\varepsilon}.$

Then we have $f(e,\textbf{x}_{1})=1$ and
$\mathrm{cost}(-\varepsilon,f(e,\textbf{x}_{1}))=d+3+\varepsilon$. By the
symmetry between profiles $\textbf{x}_{1}$ and $\textbf{x}_{2}$, we also have
$f(e,\textbf{x}_{2})=-1$ and
$\mathrm{cost}(\varepsilon,f(e,\textbf{x}_{2}))=d+3+\varepsilon$.

Now consider profile $\textbf{x}_{3}$. If $f(e,\textbf{x}_{3})=-1$, then the
agent at $-\varepsilon$ in $\textbf{x}_{1}$ can deviate to $-2$ and decrease
her cost from $d+3+\varepsilon$ to $d+3-\varepsilon$, a contradiction. If
$f(e,\textbf{x}_{3})=1$, then the agent at $\varepsilon$ in $\textbf{x}_{2}$
can deviate to $2$ and decrease her cost from $d+3+\varepsilon$ to
$d+3-\varepsilon$, a contradiction. Therefore, we have
$\gamma(f(e,\cdot))\geq\frac{3r_{e}-1}{(1+\varepsilon)r_{e}+1-\varepsilon}$
for small enough $\varepsilon>0$. ∎

As a result of Theorem 8 and Theorem 9, we have that no strategyproof
mechanism can do better than $m_{1}(\cdot,\cdot)$.

#### Lower Bound for Randomized Mechanisms

Next, we can establish lower bounds for strategyproof randomized mechanisms.

######  Theorem 10.

No strategyproof randomized mechanism
$f(\cdot,\cdot):\mathcal{E}\times\mathbb{R}^{n}\rightarrow\Delta(\mathbb{R})$
can achieve a total cost approximation ratio less than $2$.

###### Proof.

Consider the following entrance fee function:

$e(\ell)=\left\\{\begin{aligned} &0,&&\text{if }\ell\in\\{-1,1\\}\\\
&+\infty,&&\text{otherwise}\end{aligned}\right.,$

Let $f(e,\cdot)\colon\mathbb{R}^{n}\rightarrow\mathbb{R}$ be a randomized
strategyproof mechanism with bounded approximation ratio for the total cost.
To achieve a bounded approximation ratio, we have
$\Pr[f(e,\textbf{x})=-1]+\Pr[f(e,\textbf{x})=1]=1$ for any
$\textbf{x}\in\mathbb{R}^{n}$.

Let $\textbf{x}_{1}=(-\varepsilon,2)$, $\textbf{x}_{2}=(-2,\varepsilon)$ and
$\textbf{x}_{3}=(-2,2)$ be three location profiles, where
$\varepsilon\in(0,1)$ is a small positive number. Let
$\Pr[f(e,\textbf{x}_{1})=-1]=p$ and $\Pr[f(e,\textbf{x}_{2})=1]=p^{\prime}$.
We illustrate the example in Figure 8.

Figure 8: Example for the randomized lower bound $3$. The black dots are
agents and the red triangles denote facilities.

The approximation ratio of $f$ for $\textbf{x}_{1}$, $\textbf{x}_{2}$, and
$\textbf{x}_{3}$ are:

$\gamma(f(e,\textbf{x}_{1}))=\frac{3}{1+\varepsilon}p+(1-p),$

and

$\gamma(f(e,\textbf{x}_{2}))=\frac{3}{1+\varepsilon}p^{\prime}+(1-p^{\prime}).$

Now consider the case that the agent at $-\varepsilon$ in $\textbf{x}_{1}$
deviates to $-2$. Since this agent prefers location $-1$ to location $1$, by
the strategyproofness of $f(e,\cdot)$, we must have

$p\geq\Pr[f(e,\mathbf{x}_{3})=-1].$

Then consider the case that the agent at $-\varepsilon$ in $\textbf{x}_{2}$
deviates to $-1$, again by the strategyproofness of $f(e,\cdot)$, we must have

$p^{\prime}\geq\Pr[f(e,\mathbf{x}_{3})=1].$

By $\Pr[f(e,\textbf{x}_{3})=-1]+\Pr[f(e,\textbf{x}_{3})=1]=1$, we have
$p+p^{\prime}\leq 1$. Without loss of generality, we assume $p\leq 1/2$. Thus
we know that
$\gamma(f(e,\cdot))\geq\gamma(f(e,\textbf{x}_{1}))\geq\frac{2}{1+\varepsilon}$.
∎

##  6 Mechanisms with Two Facilities

In this section, we investigate the mechanism design problem when $m=2$. A
mechanism is now a function
$f(\cdot,\cdot):\mathcal{E}\times\mathbb{R}^{n}\rightarrow\mathbb{R}^{2}$,
that given $e$ and $\bm{x}$, returns the facility location profile
$\bm{\ell}\in\mathbb{R}^{2}$. Recall for $\bm{\ell}=(\ell_{1},\ell_{2})$, the
agent $i$ selects the facility with smallest sum of travel and entrance fees,
thus
$\mathrm{cost}(x_{i},\bm{\ell})=\min\\{|\ell_{1}-x_{i}|+e(\ell_{1}),|\ell_{2}-x_{i}|+e(\ell_{2})\\}$.

###  6.1 Utilitarian version with Two Facilities

Let $i,j\in N$ with $i\leq j$. Denote by
$m_{i,j}(\cdot,\cdot):\mathbb{R}^{n}\rightarrow\mathbb{R}^{2}$ the mechanism
that puts one facility in $x_{i}^{*}$ and the other facility in $x_{j}^{*}$
for any input $e$ and $\bm{x}$. Just as $m_{i}(\cdot,\cdot)$ is a group
strategyproof mechanism, below we can show that $m_{i,j}(\cdot,\cdot)$ is also
group strategyproof.

######  Proposition 2.

The mechanism $m_{i,j}(\cdot,\cdot)$ is group strategyproof.

###### Proof.

Obviously agents $i$ and $j$ have no incentive to misreport. To change the
output of the mechanism, there are only three cases to consider: (1) one agent
$k$ on the left side of $x_{i}$ misreports a location $x_{k}^{\prime}>x_{i}$;
(2) one agent $k$ between $x_{i}$ and $x_{j}$ misreports a location
$x_{k}^{\prime}<x_{i}$ or $x_{k}>x_{j}$; (3) one agent $k$ on the right side
of $x_{j}$ misreports a location $x_{k}^{\prime}<x_{j}$. By the Monotonicity
Lemma, it easy to show that the cost of agent $k$ will not decrease in each of
the three cases. ∎

When $e_{min}=e_{max}=0$, Fotakis and Tzamos [2014] prove that any
strategyproof mechanism with bounded approximation ratio (for either of the
objectives) must put facilities on $x_{1}$ and on $x_{n}$. Furthermore, no
strategyproof mechanism can achieve an total cost approximation ratio greater
than $n-2$. Thus we only consider the mechanism $m_{1,n}(\cdot,\cdot)$. The
next result shows that the total cost approximation ratio of
$m_{1,n}(\cdot,\cdot)$ matches the lower bound $n-2$.

######  Proposition 3.

The approximation ratio of $m_{1,n}(\cdot,\cdot)$ for the total cost is at
most $n-2$.

###### Proof.

For any entrance fee function $e$ and any agent location profile $\bm{x}$, we
define an entrance fee function $e^{\prime}$ and an agent location profile
$\bm{x}^{\prime}$ as follows:

  * •

$\bm{x}^{\prime}$: there are $n-2$ agents allocated at position
$(x_{1}+x_{n})/2$. The other two agents are at positions $x_{1}$ and $x_{n}$,
respectively.

  * •

$e^{\prime}$: $e^{\prime}(x)=e_{min}$ if $x=(x_{1}+x_{n})/2$, and
$e^{\prime}(x)=e_{max}$ if $x\neq(x_{1}+x_{n})/2$.

Next, we show that
$\gamma(m_{1,n}(e,\bm{x}))\leq\gamma(m_{1,n}(e^{\prime},\bm{x}^{\prime}))$.
Let $(\ell_{1},\ell_{2})$ be the optimal facility location profile for the
total cost. Assume that $\ell_{1}\leq\ell_{2}$. Let $L$ be the set of agents
who select $\ell_{1}$ and $R$ be the set of agents who select $\ell_{2}$. Then
by Lemma 8 we have $L$ and $R$ are continuous. We will construct $e^{\prime}$
and $\bm{x}^{\prime}$ form $e$ and $\bm{x}$ in the following steps:

  1. 1.

Set the entrance fee at $\ell_{1}$ and $\ell_{2}$ as $e_{min}$;

  2. 2.

Move agents in $L\setminus\\{1\\}$ to $\ell_{1}$ and agents in
$R\setminus\\{1\\}$ to $\ell_{2}$;

  3. 3.

Set the entrance fee at $\frac{x_{1}+x_{n}}{2}$ as $e_{min}$ and the entrance
fee at $x_{1}^{*}$ and $x_{n}^{*}$ is $e_{max}$, and we get
$e^{\prime}(\cdot)$.

  4. 4.

move agents at $\ell_{1}$ to $\frac{x_{1}+x_{n}}{2}$ and move agents at
$\ell_{2}$ to $\frac{x_{1}+x_{n}}{2}$, we get $\bm{x}^{\prime}$.

It is easy to see that in each above step, the approximation ratio
$\gamma(m_{1,n}(e,\bm{x})$ will only increase. Thus, when
$L(\bm{x})=|x_{n}-x_{1}|$ is large enough, the optimal total cost for
$\bm{x}^{\prime}$ and $e^{\prime}$ is $L(\bm{x})/2+(n-1)e_{min}+e_{max}$. Thus

$\displaystyle\gamma(m_{1,n}(e,\bm{x}^{\prime}))$
$\displaystyle=\frac{TC(\bm{x},m_{1,n}(e,\bm{x}^{\prime}))}{\frac{L(\bm{x}^{\prime})}{2}+(n-1)e_{min}+e_{max}}$
$\displaystyle=\frac{(n-2)\frac{L(\bm{x}^{\prime})}{2}+ne_{max}}{\frac{L(\bm{x}^{\prime})}{2}+(n-1)e_{min}+e_{max}}\leq
n-2.$

∎

###  6.2 Egalitarian Version with Two Facilities

Our mechanism for the egalitarian objective is also $m_{1,n}(\cdot,\cdot)$. We
show that the approximation ratio of $m_{1,n}(\cdot,\cdot)$ for the maximum
cost is the same as $m_{1}(\cdot,\cdot)$.

######  Proposition 4.

For each entrance fee function $e$ with max-min ratio $r_{e}$, the
approximation ratio of $m_{1,n}(e,\cdot)$ for the maximum cost is

$\displaystyle\gamma((m_{1,n}(e,\cdot))\leq\begin{cases}2,&\text{ if
}r_{e}\leq 2\\\ 3-\frac{3}{r_{e}+1},&\text{ if }r_{e}>2\\\ \end{cases}.$

Hence, the approximation ratio of $m_{1,n}(\cdot,\cdot)$ for the maximum cost
is at most $3$.

###### Proof.

Let $\bm{\ell}=(\ell_{mc}^{1},\ell_{mc}^{2})$ be the facility location profile
that minimizes the maximum cost of $\bm{x}$. Recall that the positions of
agent location profiles are ordered. Let $\bm{x}_{L}=(x_{1},\cdots,x_{p})$ and
$\bm{x}_{R}=(x_{p+1},\cdots,x_{n})$ be the sequences of agents that select the
facilities at $\ell_{mc}^{1}$ and $\ell_{mc}^{2}$, respectively. Note that
$\bm{x}_{L}$ and $\bm{x}_{R}$ are correctly defined by Lemma 8. We claim that
$\ell_{mc}^{1}$ is the location that minimizes the maximum cost of
$\bm{x}_{L}$ and $\ell_{mc}^{2}$ is the location that minimizes the maximum
cost of $\bm{x}_{R}$. Then we have two separate one-facility problems. Thus,
the approximation ratio follows from Theorem 7. ∎

In next proposition, for all the strategyproof deterministic mechanisms, we
obtain a similar lower bound as in Theorem 8.

######  Proposition 5.

For any given $\alpha\geq 1$, no strategyproof mechanism
$f(\cdot,\cdot):\mathcal{E}(\alpha)\times\mathbb{R}^{n}\rightarrow\mathbb{R}^{2}$
can achieve a maximum cost approximation ratio greater than $2$.

###### Proof.

Use the same construction as in the proof of Theorem 8 for all the agents from
$1$ through $n$, and add one more agent $0$ far away on the left side of agent
$1$. Then in order to get a $2$-approximation, one of the two facilities must
always be close to the position of the added agent $0$. Then the same
arguments as in Theorem 5 can be applied to the second facility and the rest
of the agents. ∎

By almost same argument of Proposition 5, we establish a tight lower bound for
the entrance fee function with max-min ratio greater than $2$.

######  Proposition 6.

For any given $\alpha>2$, there exists an entrance fee function $e$ with max-
min ratio $r_{e}=\alpha$ such that no strategyproof deterministic mechanism
$f(e,\cdot):\mathbb{R}^{n}\rightarrow\mathbb{R}^{2}$ can achieve a maximum
cost approximation ratio less than $3-\frac{4}{r_{e}+1}$. This also implies
that no strategyproof deterministic mechanism
$f(\cdot,\cdot):\mathcal{E}\times\mathbb{R}^{n}\rightarrow\mathbb{R}^{2}$ can
achieve a maximum cost approximation ratio less than $3$. ∎

#### Lower Bound for Randomized Mechanisms

As in the deterministic case, we observe that the lower bound in Theorem 10
also holds for in the two-facility setting.

######  Proposition 7.

No strategyproof deterministic mechanism
$f(\cdot,\cdot):\mathcal{E}\times\mathbb{R}^{n}\rightarrow\Delta(\mathbb{R}^{2})$
can achieve a maximum cost approximation ratio less than $2$.

##  7 Conclusion

In this paper, we presented a novel extension of the classical facility
location game on the real line. Our model introduces entrance fee functions
thus naturally enhancing the classical facility location game. Not only this
model is a new extension of the classical model but it also brings in an idea
of revisiting the existing facility location games, such as capacitated
facilities [Aziz et al. 2020a], heterogeneous facilities [Li et al. 2020] and
so on. We think that this model is a more realistic fit in many application
scenarios.

For the models in the paper, it is also interesting to design better
strategyproof randomized mechanisms in one-facility setting for the maximum
cost, and in two-facility setting for both objectives. Another intriguing
direction is to consider the variant that the entrance fee of a facility also
depends on the number of agents served by the facility.

## References

  * Aziz et al. [2020a] Haris Aziz, Hau Chan, Barton Lee, Bo Li, and Toby Walsh.  Facility location problem with capacity constraints: Algorithmic and mechanism design perspectives.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pages 1806–1813, 2020a.
  * Aziz et al. [2020b] Haris Aziz, Hau Chan, Barton E Lee, and David C Parkes.  The capacity constrained facility location problem.  _Games and Economic Behavior_ , 124:478–490, 2020b.
  * Cai et al. [2016] Qingpeng Cai, Aris Filos-Ratsikas, and Pingzhong Tang.  Facility location with minimax envy.  In _Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence_ , IJCAI’16, page 137–143. AAAI Press, 2016\.  ISBN 9781577357704.
  * Chan et al. [2021] Hau Chan, Aris Filos-Ratsikas, Bo Li, Minming Li, and Chenhao Wang.  Mechanism design for facility location problems: A survey.  In _Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21_ , pages 4356–4365. International Joint Conferences on Artificial Intelligence Organization, 8 2021.  Survey Track.
  * Chen et al. [2018] Xujin Chen, Xiaodong Hu, Xiaohua Jia, Minming Li, Zhongzheng Tang, and Chenhao Wang.  Mechanism design for two-opposite-facility location games with penalties on distance.  In _International Symposium on Algorithmic Game Theory_ , pages 256–260. Springer, 2018.
  * Cheng et al. [2013] Yukun Cheng, Wei Yu, and Guochuan Zhang.  Strategy-proof approximation mechanisms for an obnoxious facility game on networks.  _Theoretical Computer Science_ , 497:154–163, 2013.
  * Duan et al. [2019] Lingjie Duan, Bo Li, Minming Li, and Xinping Xu.  Heterogeneous two-facility location games with minimum distance requirement.  In _AAMAS_ , pages 1461–1469, 2019.
  * Feigenbaum and Sethuraman [2015] Itai Feigenbaum and Jay Sethuraman.  Strategyproof mechanisms for one-dimensional hybrid and obnoxious facility location models.  In _Workshops at the twenty-ninth AAAI conference on artificial intelligence_ , 2015.
  * Fong et al. [2018] Chi Kit Ken Fong, Minming Li, Pinyan Lu, Taiki Todo, and Makoto Yokoo.  Facility location games with fractional preferences.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32, 2018.
  * Fotakis and Tzamos [2014] Dimitris Fotakis and Christos Tzamos.  On the power of deterministic mechanisms for facility location games.  _ACM Transactions on Economics and Computation (TEAC)_ , 2(4):1–37, 2014.
  * Li et al. [2019] Minming Li, Lili Mei, Yi Xu, Guochuan Zhang, and Yingchao Zhao.  Facility location games with externalities.  In _Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems_ , pages 1443–1451, 2019.
  * Li et al. [2020] Minming Li, Pinyan Lu, Yuhao Yao, and Jialin Zhang.  Strategyproof mechanism for two heterogeneous facilities with constant approximation ratio.  In Christian Bessiere, editor, _Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20_ , pages 238–245. International Joint Conferences on Artificial Intelligence Organization, 7 2020.  doi: 10.24963/ijcai.2020/34.  URL https://doi.org/10.24963/ijcai.2020/34.  Main track.
  * Lu et al. [2009] Pinyan Lu, Yajun Wang, and Yuan Zhou.  Tighter bounds for facility games.  In _International Workshop on Internet and Network Economics_ , pages 137–148. Springer, 2009.
  * Lu et al. [2010] Pinyan Lu, Xiaorui Sun, Yajun Wang, and Zeyuan Allen Zhu.  Asymptotically optimal strategy-proof mechanisms for two-facility games.  In _Proceedings of the 11th ACM conference on Electronic commerce_ , pages 315–324, 2010.
  * Procaccia and Tennenholtz [2009] Ariel D. Procaccia and Moshe Tennenholtz.  Approximate mechanism design without money.  In _Proceedings of the 10th ACM Conference on Electronic Commerce_ , EC ’09, page 177–186, New York, NY, USA, 2009. Association for Computing Machinery.  ISBN 9781605584584.
  * Procaccia and Tennenholtz [2013] Ariel D Procaccia and Moshe Tennenholtz.  Approximate mechanism design without money.  _ACM Transactions on Economics and Computation (TEAC)_ , 1(4):1–26, 2013.
  * Serafino and Ventre [2014] Paolo Serafino and Carmine Ventre.  Heterogeneous facility location without money on the line.  In _ECAI 2014_ , pages 807–812. IOS Press, 2014.
  * Serafino and Ventre [2015] Paolo Serafino and Carmine Ventre.  Truthful mechanisms without money for non-utilitarian heterogeneous facility location.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 29, 2015.
  * Yuan et al. [2016] Hongning Yuan, Kai Wang, Ken CK Fong, Yong Zhang, and Minming Li.  Facility location games with optional preference.  In _ECAI 2016_ , pages 1520–1527. IOS Press, 2016.
  * Zou and Li [2015] Shaokun Zou and Minming Li.  Facility location games with dual preference.  In _Proceedings of the 2015 international conference on autonomous agents and multiagent systems_ , pages 615–623, 2015.