# Mechanism Design With Predictions for Obnoxious Facility Location

Gabriel Istrate, Cosmin Bonchiş University of Bucharest, email:
<EMAIL_ADDRESS>University of Timişoara

###### Abstract

We study _mechanism design with predictions_ for the obnoxious facility
location problem. We present deterministic strategyproof mechanisms that
display tradeoffs between robustness and consistency on segments, squares,
circles and trees. All these mechanisms are actually group strategyproof, with
the exception of the case of squares, where manipulations from coalitions of
two agents exist. We prove that these tradeoffs are optimal in the
1-dimensional case.

Keywords:  Mechanism Design With Predictions, Robustness, Consistency

##  1 Introduction

The theory of _algorithms with predictions_ [1, 2, 3] is, without a doubt, one
of the most exciting recent research directions in algorithmics: when
supplemented by a (correct) _predictor_ , often based on machine learning, the
newly-developed algorithms are capable of outcompeting their worst-case
classical counterparts. A desirable feature of such algorithms is, of course,
to perform comparably to the (worst-case) algorithms when the predictors are
really bad. This requirement often results [2] in tradeoffs between two
measures of algorithm performance, _robustness_ and _consistency_. A
significant amount of subsequent research has followed, summarized by the
algorithms with predictions webpage [3].

Recently, the idea of augmenting algorithms by predictions has been adapted to
the game-theoretic setting of _mechanism design_ [4, 5, 6, 7]: indeed,
strategyproof mechanisms often yield solutions that are only approximately
optimal [8]. On the other hand, if the designer has access to a predictor for
the desired outcome it could conceivably take advantage of this information by
creating mechanisms that lead to an improved approximation ratio, compared to
their existing (worst-case) counterparts. Tradeoffs between robustness and
consistency similar to the ones from [2] apply to this setting as well. This
is perhaps best exemplified by the recent results in [5]: the authors
considered the classical problem of _facility location problem_ in a setting
with predictions. Procaccia and Tennenholtz [9] had given a 2-approximate
mechanism for this problem in the setting without predictions under the
utilitarian objective function, and proved it was optimal. Later on, the two-
dimensional case of the problem was shown [10] to have (optimal) approximation
ratio $\sqrt{2}$. Among many results, Agrawal et al. [5] gave a mechanism for
the 1-dimensional case that was 2-robust and 1-consistent. In the two
dimensional case they gave a mechanism with predictions parameterized by
$c\in(0,1)$ that realizes an (optimal)
$(\frac{\sqrt{2c^{2}+2}}{1+c},\frac{\sqrt{2c^{2}+2}}{1-c})$ tradeoff between
robustness and consistency.

We contribute to this research direction by studying, in the setting of
mechanism design with predictions, another version of facility location: the
_obnoxious facility location_ problem [11, 12, 13]. This is the version of
facility location where the facility is, in some sense, undesirable (e.g. a
garbage dump) and all agents may strive to be located as far as possible from
the chosen location.

###  1.1 Contributions and Outline

We give deterministic mechanisms that display an identical tradeoff between
consistency and robustness for obnoxious facility location on various
topologies: one and two-dimensional hypercubes (Algorithm 1, Theorem 1),
circles, (Algorithm 2, Theorem 2), and trees (Algorithm 3, Theorem 3). The
particular case of two-dimensional hypercubes is completely new (it had not
been investigated previously, even without predictions). However, in this case
the mechanism that we give is strategyproof but not group strategyproof, being
vulnerable to collusion from as little as two agents. We give indication that
the displayed tradeoffs may be optimal by proving this claim for one-
dimensional hypercubes (Theorem 4). We give similar results in the case of
agents with dual preferences [14, 15], at the expense of replacing group
strategyproofness with a weaker concept previously studied (for obnoxious
facility location) in [16].

The following is an outline of the paper: In Section 2 we review relevant
notations and definitions. The proofs of some of the upper-bound results
follow a common strategy: in Section 4 we give a general outline of this
strategy, and then present the specific details. In Section 6 we give details
about the lower bounds. We briefly discuss (Section 8) related work and
(Section 9) further directions and open problems.

##  2 Preliminaries

We will write $[n]$ as a substitute for $\\{1,2,\ldots,n\\}$. As usual, the
expectation of a random variable Z will be denoted by $\mathrm{E}[Z]$.

We will be dealing with the _obnoxious facility location problem_. In this
problem $n$ agents are located in a metric space $(X,d)$. The location of each
agent ($p_{i}$ for agent $1\leq i\leq n$) is private to the agent. We will
refer to elements of $X^{n}$ as _location profiles_. Let
$\mathcal{C}=(p_{1},p_{2},\ldots,p_{n})\in X^{n}$ be the vector of (true)
agent locations. The goal is to choose a single facility location
$f(\mathcal{C})\in X$, via a _mechanism_ $f:X^{n}\rightarrow X$.111As defined
the mechanism is deterministic. To model randomized mechanisms we modify the
definition of $f$ to $f:X^{n}\times\Omega\rightarrow X$, where $\Omega$ is a
probability space. Once the location has been chosen, each agent gains utlity
$u_{i}(f(\mathcal{C}))=d(f(\mathcal{C}),p_{i})$. Our goal is to choose a
location $P^{*}$ to maximize _obnoxious social welfare_
$SW(P^{*},\mathcal{C}):=\sum_{i=1}^{n}d(P^{*},p_{i})$. We will denote this
optimal value by $OPT(\mathcal{C})$ and use notation $y^{*}$ for a point
realizing it. Given mechanism $f$ and instance $\mathcal{C}$, we will use
notation $F(\mathcal{C})$ as a shorthand for $SW(f(\mathcal{C}),\mathcal{C})$.
For randomized mechanisms this changes to $F(\mathcal{C})$ for
$\mathrm{E}_{\omega\in\Omega}[SW(f(\mathcal{C},\omega),\mathcal{C})]$. We will
measure the performance of a mechanism $f$ by the ratio
$c(f):=max_{\mathcal{C}\in X^{n}}(\frac{OPT(\mathcal{C})}{F(\mathcal{C})})$.
Agents may be incentivized to misreport their location in order to maximize
their profit. Given location profile $P$ and set $S\subset[n]$ , define
$P_{-S}$ to be the profile obtained by eliminating elements $p_{i}$, $i\in S$,
from $P$. Mechanism $f$ is called _strategyproof_ if for every $1\leq i\leq n$
and $p^{\prime}_{i}\neq p_{i}$, $u_{i}(f(p_{-i},p^{\prime}_{i}))\leq
u_{i}(f(P)).$ In other words, it never pays off for agent $i$ to misreport its
location as $p^{\prime}_{i}$. The mechanism is called _group strategyproof_
iff for every $S\subset[n]$ and every location profile $(P_{-S},Q_{S})$, there
exists an index $i\in S$ such that $u_{i}(f(P_{-S},Q_{S}))\leq u_{i}(f(P)).$
In other words, agents in $S$ cannot all gain by coordinating their deviations
from their true locations.

Let $Z\subseteq X$ be a set of acceptable _prediction values_. A _mechanism
with predictions is a function_ $f:X^{n}\times Z\rightarrow X$ (or
$f:X^{n}\times\Omega\times Z\rightarrow X$, in the randomized case). It
employs a _predictor_ $\widehat{Y}\in Z$, the predicted location of the
obnoxious facility, as its last argument. Denote by
$\eta=d(P^{*},\widehat{Y})$ the prediction error. We will use the notation
$c(f,\eta)$ to refer to the adaptation of $c(f)$ to settings with prediction
$(\mathcal{C},P_{C})$ for which the condition
$d(y^{*},P_{\mathcal{C}})\leq\eta$ holds. That is, given $\mathcal{C}\in
X^{n}$ and $P_{\mathcal{C}}\in Z$, use shorthand
$F(\mathcal{C},P_{\mathcal{C}})=SW(f(\mathcal{C},P_{\mathcal{C}}),\mathcal{C})$
and define

$\displaystyle c(f,\eta):=max_{\stackrel{{\scriptstyle\mathcal{C}\in
X^{n},P_{C}\in
Z}}{{d(P_{C},y^{*})\leq\eta}}}\big{(}\frac{OPT(\mathcal{C})}{F(\mathcal{C},P_{\mathcal{C}})}\big{)}.$
(1)

######  Definition 1.

Given $\gamma,\beta\geq 1$, a mechanism with predictions $f$ is _$\gamma$
-robust_ iff $c(f,\eta)\leq\gamma$ for all $\eta$ and is _$\beta$ -consistent_
if $c(f,0)\leq\beta$.

Following [17], we will view graphs as closed, connected subsets of some
Euclidean space $\mathbb{R}^{n}$. They are composed of a finite number of
segments called edges. We will use, in particular, _trees_. Distances between
points in a tree are not computed in the ambient $\mathbb{R}^{n}$, but rather
along tree paths, by summing up the (euclidian) lengths of segments forming
the path. Since there is an unique path $[a,b]$ between any two points $a,b$
in a tree one can naturally define, for arbitrary $\lambda\in[0,1]$ the point
$\lambda a+(1-\lambda)b$ as the unique point $w$ on this path such that
$d(a,w)=\lambda d(a,b)$. In particular we will denote by $m_{a,b}$ the point
$1/2\cdot a+1/2\cdot b$, the _midpoint of path $ab$._ Vertices $a,b$ in a tree
$T$ form a _diameter of $T$_ if the distance $d(a,b)$ is the largest distance
between any two vertices in the tree. A vertex is called _peripheral_ iff it
is part of a diameter of the tree.

Finally, we will refer in the sequel to _majority voting_ , used to choose
between two items. We will used a slightly generalized version by allowing
nonintegral numbers of votes for the items.

##  3 Results

As in [2], our mechanisms will be parameterized by $\lambda\in[0,1]$, which
intuitively measures the ”agresiveness” of relying on the predictor. Our
guarantees for consistency/robustness will be functions of $\lambda$ as well.
When $\lambda=1$ we will get the case of the baseline algorithm which simply
returns the predicted point. In general this algorithm is 1-consistent but not
$\gamma$-robust for any constant $\gamma$. Indeed, let $P$,$Q$ be points in
$X$ that are farthest apart. Choose the $n$ points to be all at the same
location $P$ and let the predictor predict also $P\in X$. The optimal
obnoxious social welfare would be $n\cdot d(P,Q)$, corresponding to locating
the facility at $Q$, but the bad predictor leads to an obnoxious social
welfare of 0. We will plot the consistency/robustness curves against parameter
$\lambda\in[0,1]$. By the previous discussion, at $\lambda=1$ $\beta(1)=1$ and
$\gamma(1)=\infty.$ On the other hand at $\lambda=0$ we expect the quantities
$\beta(0)$ and $\gamma(0)$ to coincide, and be equal to the approximation
ratio of the optimal strategyproof mechanism. Moreover, as we increase
$\lambda$ from $0$ to $1$ we expect the robustness $\gamma(\lambda)$ to
diverge, while the consistency $\beta(\lambda)$ to tend towards 1. Our goal is
to obtain explicit curves $(\beta(\lambda),\gamma(\lambda))$ that display ”the
best” tradeoff between robustness and consistency.

The first setting for our results is the one where $X=[0,1]^{k}$, the
$k$-dimensional hypercube. We will employ the ”robust coordinatewise voting”
mechanism displayed in Algorithm 1. We have:

Input : $C=(x_{1},x_{2},\ldots,x_{n}),x_{i}\in[0,1]^{k}$, $\lambda\in[0,1)$.

Prediction : $P_{\mathcal{C}}=p_{1}p_{2}\ldots p_{k}\in\\{0,1\\}^{k}$.
W.l.o.g. $P_{\mathcal{C}}=1^{k}$.

for i:=1 to k

let $n_{1,k}$ be the number of indices $i$ s.t. $0\leq x_{i,k}\leq 1/2$.

let $n_{2,k}$ be the number of indices $i$ s.t. $1/2<x_{i,k}\leq 1$.

count $n_{1,k}$ votes for 1; count $n_{2,k}$ votes for 0.

count $\lambda n$ votes for $p_{i}$.

if $p_{i}$ has at least as many votes as $1-p_{i}$:

let $z_{i}=p_{i}$.

else

let $z_{i}=1-p_{i}$.

return $Z_{\mathcal{C}}:=z_{1}z_{2}\ldots z_{k}.$

Algorithm 1 $k$-dimensional robust coordinatewise voting.

$n_{2}$$n_{3}$$n_{4}$$n_{1}$DRTSUVABC

Figure 1:  (a). Consistency versus robustness. (b). Decomposition of the
square into rectangles used in the case of two-dimensional hypercubes.

######  Theorem 1.

The robust majority mechanism in one dimension with parameter $\lambda$ (see
Algorithm 1) is group strategyproof, $\frac{3+\lambda}{1-\lambda}$-robust and
$\frac{3-\lambda}{1+\lambda}$-consistent. The robust majority mechanism in two
dimensions with parameter $\lambda$ is $\frac{3+\lambda}{1-\lambda}$-robust
and $\frac{3-\lambda}{1+\lambda}$-consistent (see Figure 1 (a)). It is
strategyproof but not group strategyproof: there exists a coalition of two
agents that can manipulate it.

An analogous result holds in the case of circles. We will regard a circle
$\mathcal{C}$ as the segment $[0,1]$ where 0 and 1 are identified. The
distance between two points with coordinates $0\leq x<y\leq 1$ will be the
distance between the points as measured on the circle. That is:
$d(x,y)=min(y-x,1+x-y)$. We will employ the mechanism in Algorithm 2, and
prove that:

######  Theorem 2.

The robust majority mechanism on a circle with parameter $\lambda$ is group
strategyproof, $\frac{3+\lambda}{1+\lambda}$-robust and
$\frac{3-\lambda}{1+\lambda}$-consistent.

Input : $\mathcal{C}=(x_{1},x_{2},\ldots,x_{n})$, $\lambda\in[0,1]$.

Prediction : $P_{\mathcal{C}}\in[0,1)$.

Let $S=\\{x_{1},\ldots,x_{n}\\}$.

Let $Q$ be the point diametrally opposed to $P_{\mathcal{C}}$.

Let $n_{Q}$ be the number of points of $S$ in
$(P_{\mathcal{C}}+1/4,P_{\mathcal{C}}+3/4]$

and $n_{P}$ the number of points of $S$ in
$(P_{\mathcal{C}}-1/4,P_{\mathcal{C}}+1/4]$.

If $n_{P}\leq n_{Q}+\lambda n$ return point $P_{\mathcal{C}}$

else return point $Q$.

Algorithm 2 The robust majority mechanism on a circle.

Input : $x_{1},x_{2},\ldots,x_{n}\in T$, $\lambda\in[0,1]$.

Prediction : $P_{\mathcal{C}}\in T,$ a vertex of $T.$

Let $S=\\{x_{1},\ldots,x_{n}\\}$. Transform tree $T$ to $T^{\prime}$ by making
all points of $S$ vertices, while preserving distances.

Let $a$ be the farthest vertex from $P_{\mathcal{C}}$. Let $b$ be a vertex of
$T^{\prime}$ farthest from $a$ ($P_{\mathcal{C}}$ if possible)

Let $T_{a}$ be the connected component of $T^{\prime}$ determined by $m_{a,b}$
containing $a$, and $T_{b}$ be the complement of $T_{a}$ in $T^{\prime}$.

Let $n_{1}$ be the number of points of $S$ in $T_{a}$ and $n_{2}$ the number
of points in $T_{b}$.

If $n_{1}+\lambda n\leq n_{2}$ return point $a$

else return point $b$.

Algorithm 3 The robust majority mechanism on a tree.

Finally, we propose a version of the robust majority mechanism with parameter
$\lambda$ for trees, displayed in Figure 3. We have:

######  Theorem 3.

Under the hypothesis that the predicted point is always a peripherical point,
the robust majority mechanism on trees with parameter $\lambda$ is (also)
group strategyproof, $\frac{3+\lambda}{1+\lambda}$-robust and
$\frac{3-\lambda}{1+\lambda}$-consistent.

######  Remark 1.

Even though the algorithm from Theorem 3 displays the same tradeoff as the
ones from theorems 1 and 2, it has an important drawback, not present in the
other cases: the predicted point $P_{\mathcal{C}}$ is not necessarily among
the possible outputs of the algorithm. Indeed (see Lemma 1 below) in the case
of 1-d and 2-d hypercubes the distance is a convex function, hence the optimum
was guaranteed _a priori_ to be one of the points 0/1 ($A,B,C,D$ in the two-
dimensional case). On the other hand in the case of circles, we specifically
designed the algorithm so that $P_{\mathcal{C}}$ is one of the potential
outputs. To make the algorithm behave similarly to the previous algorithms, we
were forced to add the condition that $P_{\mathcal{C}}$ is peripheral to the
specification of the predictor: while the robustness bound carries on without
this assumption, we don’t know how to obtain the consistency bound without it.

The problem is that there are examples (see e.g. in Exercise 3.4 [18]) where
the optimal point $y^{*}$ need not be a peripheral point. In light of this
fact, while it is natural to require that the prediction point
$P_{\mathcal{C}}$ be a leaf of the tree, since optima are always reached at a
leaf [19], it seems substantially less natural to require that
$P_{\mathcal{C}}$ is peripheral. One can compute the optimum point in linear
time [20]. See also [21] for a characterization of possible outputs of group
strategyproof mechanisms.

The tradeoff we displayed in Theorems 1 is (at least in the one-dimensional
case) optimal. Indeed, we prove:

######  Theorem 4.

For every $0<c\leq 2$ and $\delta>0$, a deterministic mechanism with
predictions for obnoxious facility location on a segment that always yields
one of the endpoints and is $(1+c)$-consistent cannot be
$(1+\frac{4}{c}-\delta)$-robust. The mechanism in Algorithm 1 realizes the
best possible tradeoff, with substitution $\lambda=\frac{2-c}{2+c}$ (i.e.
$c=\frac{2(1-\lambda)}{1+\lambda}$).

###  3.1 The case of dual preferences

In [14] and [15] yet another twist on the obnoxious facility location was
proposed: the case of _dual preferences_. Specifically, agents are of two
types: those of type 1 prefer to be as close to the facility as possible,
while those of type 0 still want to maximize distance to the facility.
Denoting by $T_{1},T_{0}$ the sets of agents of type 1, type 0, respectively,
one defines the social welfare of a given choice $Y$ as $SW(P,Y)=\sum_{i\in
T_{1}}(1-d(Y,x_{i}))+\sum_{j\in T_{0}}d(Y,x_{j})$. In this case, an agent $i$
may misreport _both_ its type (we will denote by $y_{i}$) and location
$x_{i}$. However, it was noted that the problem is related to the obnoxious
facility location as follows: define for each agent $i$ its _transformed
location $x^{*}_{i}$_ as follows: $x^{*}_{i}=1-x_{i}$ if $y_{i}=1$,
$x^{*}_{i}=x_{i}$, otherwise. Zou and Li prove that applying the majority
voting mechanism on the transformed location profile yields a group-
strategyproof, 3-approximation algorithm.222The proof does not follow by
reduction but needs a direct argument, since in general $1-d(Y,x_{i})\neq
d(Y,x^{*}_{i})$. However ([14], Lemma 4) $d(Y,x_{i})+d(Y,x^{*}_{i})\leq 1$.
One can similarly extend our Theorem 1. Interestingly enough, to obtain this
we don’t extend Algorithm 1, but need to devise a new mechanism. On the other
hand we also have to give up group strategyproofness, and replace it with the
following weaker concept:

######  Definition 2.

[16] Given constant $\gamma\geq 1$, a mechanism $f$ is called _$\gamma$ -group
strategyproof_ iff for every $S\subset[n]$ and every location profile
$(P_{-S},Q_{S})$, there exists an index $i\in S$ such that
$u_{i}(f(P_{-S},Q_{S}))\leq\gamma\cdot u_{i}(f(P),p_{i}).$ In other words,
agents in $S$ cannot all improve their utilities by more that a multiplicative
factor of $\gamma$ by coordinating their deviations from their true locations.

######  Theorem 5.

The transformed robust majority mechanism (Algorithm 4) is
$\frac{1+\lambda}{1-\lambda}$-group strategyproof,
$\frac{3+\lambda}{1-\lambda}$-robust and
$\frac{3-\lambda}{1+\lambda}$-consistent.

Input : $C=(x_{1},y_{1},x_{2},y_{2},\ldots,x_{n},y_{n})$,

$x_{i}\in[0,1]$, $y_{i}\in\\{0,1\\}$, $\lambda\in[0,1)$.

Prediction : $P_{\mathcal{C}}=p_{1}\in\\{0,1\\}$. w.l.o.g. assume
$P_{\mathcal{C}}=1$.

define _transformed locations_ $x^{*}_{i}=x_{i}(1-y_{i})+(1-x_{i})y_{i}$.

let $n_{1}$ be the number of indices $i$ s.t. $0\leq
x^{*}_{i}\leq(1-\lambda)/2$.

let $n_{2}$ be the number of indices $i$ s.t. $(1-\lambda)/2<x^{*}_{i}\leq 1$.

if $n_{1}>n_{2}$ return $Z_{\mathcal{C}}:=p_{1}(=1)$

else return $Z_{\mathcal{C}}:=1-p_{1}(=0)$.

Algorithm 4 Transformed Robust Majority.

##  4 Proof Idea for Theorems 1, 2 and 3

The proofs of Theorems 1, 2 and 3 proceed by first investigating group
strategyproofness directly, and then follow a similar pattern to upperbound
robustness/consistency: for an input configuration $\mathcal{C}$ and
prediction $P_{\mathcal{C}}$ we want to upper bound the ratio
$app(\mathcal{C},P_{\mathcal{C}}):=\frac{OPT(\mathcal{C})}{F(\mathcal{C},P_{\mathcal{C}})}$
by a constant $\gamma(\lambda)$ ($\beta(\lambda)$ for consistency). To do so
we will identify a ”bad” configuration333we emphasize $\mathcal{C}_{1}$ will
not necessarily be of the same type as $\mathcal{C}$. That’s why we will write
$SW(\mathcal{C}_{1},f(\mathcal{C},P_{\mathcal{C}}))$ instead of
$F(\mathcal{C}_{1},P_{\mathcal{C}})$ in inequalities of (2). $\mathcal{C}_{1}$
and prove that:

$\displaystyle\frac{OPT(\mathcal{C})}{F(\mathcal{C},P_{\mathcal{C}})}\leq\frac{SW(\mathcal{C}_{1},y^{*})}{SW(\mathcal{C}_{1},f(\mathcal{C},P_{\mathcal{C}}))}\leq\frac{OPT(\mathcal{C}_{1})}{SW(\mathcal{C}_{1},f(\mathcal{C},P_{\mathcal{C}}))}\leq\gamma(\lambda)$
(2)

where $y^{*}$ is the point realizing the optimum for configuration
$\mathcal{C}$ (we replace $\gamma(\lambda)$ by $\beta(\lambda)$ in the
inequalities above in consistency proofs). The last inequality in (2) will
typically follow easily by computing the optimal solutions for
$\mathcal{C}_{1}$. The second is clear by the definition of $OPT$. As for the
first inequality, since $OPT(\mathcal{C})\geq F(\mathcal{C},P_{\mathcal{C}})$,
we will attempt to bound the left-hand side by

$\displaystyle\frac{OPT(\mathcal{C})}{F(\mathcal{C},P_{\mathcal{C}})}\leq\frac{OPT(\mathcal{C})-(F(\mathcal{C},P_{\mathcal{C}})-SW(\mathcal{C}_{1},f(\mathcal{C},P_{\mathcal{C}}))}{F(\mathcal{C},P_{\mathcal{C}})-(F(\mathcal{C},P_{\mathcal{C}})-SW(\mathcal{C}_{1},f(\mathcal{C},P_{\mathcal{C}}))}$

To make the inequality work we first need to prove that
$F(\mathcal{C},P_{\mathcal{C}})-SW(\mathcal{C}_{1},f(\mathcal{C},P_{\mathcal{C}}))\geq
0.$ This generally follows automatically by requiring that points of
$\mathcal{C}_{1}$ are translates of the corresponding points of $\mathcal{C}$
towards the chosen location $f(\mathcal{C},P_{\mathcal{C}})$. To make the
denominator of the right-hand side less or equal to
$SW(\mathcal{C}_{1},y^{*})$, given that
$OPT(\mathcal{C})=SW(\mathcal{C},y^{*})$, we will also need that
$\Delta:=F(\mathcal{C},P_{\mathcal{C}})-SW(\mathcal{C}_{1},f(\mathcal{C},P_{\mathcal{C}}))-SW(\mathcal{C},y^{*})+SW(\mathcal{C}_{1},y^{*})\geq
0.$ This inequality will be proved separately in each case. Proofs may employ
triangle inequalities for the metric space in question.

##  5 Proof of Theorem 1

###  5.1 One-dimensional hypercubes (segments)

Robustness: Consider an arbitrary configuration $\mathcal{C}$ and without loss
of generality assume that $P_{\mathcal{C}}=1$ (if this is not the case, simply
switch labels 1 and 0). Let $n=(n_{1},n_{2})$ be the type of $\mathcal{C}$.
Let $y^{*}$ be the point realizing the optimum social welfare for
$\mathcal{C}$. Assume first that $n_{1}+\lambda\cdot n\geq n_{2}$ (i.e.
Algorithm 1 outputs $P_{\mathcal{C}}$). The above condition is equivalent to
$n_{2}/n_{1}\leq\frac{1+\lambda}{1-\lambda}$ or
$n_{2}/n\leq\frac{2}{1-\lambda}$. Define $\mathcal{C}_{1}$ to consist of
$n_{1}$ points at 0.5 and $n_{2}$ points at 1. $\mathcal{C}_{1}$ has the same
type as $\mathcal{C}$, and the points in $\mathcal{C}_{1}$ are at least as
close to $P_{\mathcal{C}}$ as their counterparts in $\mathcal{C}$. The best we
could do for $\mathcal{C}_{1}$ is choose4440 has social welfare
$n_{2}+n_{1}/2$, 1 has social welfare $n_{1}/2$. $y^{*}=0$, with social
welfare $n_{2}+n_{1}/2$. The social welfare of the solution of the modified
majority mechanism on input $\mathcal{C}_{1}$ is, on the other hand,
$n_{1}/2$. So the approximation ratio will be upperbounded by

$\displaystyle\frac{OPT(\mathcal{C}_{1})}{SW(\mathcal{C}_{1},f(\mathcal{C},P_{\mathcal{C}}))}=\frac{\frac{n_{1}}{2}+n_{2}}{\frac{n_{1}}{2}}\leq
1+\frac{2(1+\lambda)}{1-\lambda}=\frac{3+\lambda}{1-\lambda}$ (3)

Proving $\mathbf{\Delta\geq 0:}$
$\Delta=\sum_{i=1}^{n}|x_{i}-1|-n_{1}/2-\sum_{i=1}^{n}|y^{*}-x_{i}|+$

$\displaystyle+n_{1}\cdot|1/2-y^{*}|+n_{2}\cdot|1-y^{*}|=\sum_{i:x_{i}\leq
1/2}(1-x_{i}-1/2+|1/2-y^{*}|$
$\displaystyle-|y^{*}-x_{i}|)+\sum_{i:x_{i}>1/2}(|1-x_{i}|+|y^{*}-1|-|y^{*}-x_{i}|)\geq
0$

by triangle inequalities $|x_{i}-1/2|+|1/2-y^{*}|\geq|y^{*}-x_{i}|$ and
similar ones for the second sum.

In the case $n_{1}+\lambda n<n_{2}$ (i.e. Algorithm 1 outputs $0$) take
$\mathcal{C}_{1}$ to consist of $n_{1}$ points at 0 and $n_{2}$ points at 1/2.

$\displaystyle\frac{OPT(\mathcal{C}_{1})}{SW(\mathcal{C}_{1},f(\mathcal{C},P_{\mathcal{C}}))}=\frac{\frac{n_{2}}{2}+n_{1}}{\frac{n_{2}}{2}}<1+2\frac{1-\lambda}{1+\lambda}=\frac{3-\lambda}{1+\lambda}\leq\frac{3+\lambda}{1-\lambda}$
(4)

Proving $\mathbf{\Delta\geq 0:}$
$\Delta=\sum_{i=1}^{n}|x_{i}-0|-n_{2}/2-\sum_{i=1}^{n}|y^{*}-x_{i}|+$

$\displaystyle\sum_{x_{i}\leq
1/2}|0-y^{*}|+\sum_{x_{i}>1/2}|1/2-y^{*}|=\sum_{x_{i}\leq
1/2}(|x_{i}-0|+|0-y^{*}|-$
$\displaystyle-|x_{i}-y^{*}|)+\sum_{x_{i}>1/2}(|x_{i}-1/2|+|1/2-y^{*}|-|x_{i}-y^{*}|)\geq
0$

Consistency: Without loss of generality, we assume that the predicted point
(which also realizes the optimum) is $P_{\mathcal{C}}=1$. We will also assume
that the mechanism 1 yields the opposite of the predicted point, otherwise the
consistency ratio is 1. That is $P_{\mathcal{C}}=y^{*}=1$ but
$Z_{\mathcal{C}}=0$. Given our assumptions on the predictor and algorithm, the
only possible case is $n_{1}+\lambda n<n_{2}$. We have

$\displaystyle\frac{OPT(\mathcal{C})}{F(\mathcal{C},P_{\mathcal{C}})}=\frac{\sum\limits_{i\leq
n}(1-x_{i})}{\sum\limits_{i\leq
n}x_{i}}\leq\frac{2n}{n_{2}}-1<\frac{4}{1+\lambda}-1=\frac{3-\lambda}{1+\lambda}$
(5)

(we have used the inequality $n_{2}/n>\frac{1+\lambda}{2}$, which follows
easily by taking $n_{1}=n-n_{2}$, as well as $\sum_{i}x_{i}\geq n_{2}/2$).

Group Strategyproofness: Assume that for the truthful location profile it
holds that $n_{1}+\lambda\cdot n\geq n_{2}$ (thus Algorithm 1 returns point
1). Let $S\subset[n]$ be a set of agents. If the Algorithm also returns 1 on
the modified profile then no agent has improved their utility. Therefore we
will assume that agents in $S$ colluding leads to changing the outcome of
Algorithm 1 to 0. If $S$ contains an agent in $[0,1/2]$ then the utility of
this agent has not improved by colluding. Therefore, the only case left is
that all agents in $S$ are in $(1/2,1]$. But then reporting a different
location in $(1/2,1]$ does not improve utility, and reporting a location in
$[0,1/2]$ may actually decrease it. The case $n_{1}+\lambda\cdot n<n_{2}$ is
similar.

###  5.2 Two-dimensional hypercubes (squares)

First we note the following:

######  Lemma 1.

For every configuration $\mathcal{C}$, $max_{Y}(f(\mathcal{C},Y))$ is obtained
for $y^{*}\in\\{A,B,C,D\\}$, the corners of the square in Figure 1.

Proof.  A simple consequence of the fact that $f$ is a convex function
(Property 2.1, [22]). $\Box$

Robustness:  In the two-dimensional case we will use the decomposition in
Figure 1 (b). Without loss of generality we assume that $f(\mathcal{C})=D$,
otherwise we could transform the $x$ and $y$ coordinates separately, if
needed, to make this statement true. Let $n_{1},n_{2},\ldots,n_{4}$ be
respectively the number of points of $x$ in each of the squares555There is
some ambiguity as to how to assign points on the boundary to a single rule. We
will use the following rule: whenever we have to assign boundary points we
will prefer the triangle ”with lower coordinates”, where coordinates are
considered in the order $x_{1},x_{2},\ldots,x_{k}$. For instance points on
segment $[B,R]$ could be counted either by $n_{2}$ or $n_{3}$. We will assign
them to $n_{2}$ since triangle BRV is ”to the right of triangle BRU” with
respect to first coordinate $x_{1}$. Similarly, points on [VR) will be counted
by $n_{3}$ rather than $n_{4}$, points on segment $(RS]$ by $n_{5}$, rather
than $n_{6}$ and so on.. We call four-tuple $n=(n_{1},n_{2},n_{3},n_{4})$ _the
type_ of configuration $\mathcal{C}$.

Consider configuration $\mathcal{C}_{1}$ consisting of $n_{1}$ points in $T$,
$n_{2}$ points in $R$, $n_{3}$ points in $S$, $n_{4}$ points in $D$. Clearly
$\mathcal{C}_{1}$ has type $n$ as well, thus
$F(\mathcal{C}_{1},P_{\mathcal{C}})=(n_{1}+n_{3})\frac{1}{2}+n_{2}\frac{\sqrt{2}}{2}$.
We claim that

$\displaystyle\frac{OPT(\mathcal{C}_{1})}{F(\mathcal{C}_{1},P_{\mathcal{C}})}=\frac{(n_{1}+n_{3})\sqrt{5}+(n_{2}+2n_{4})\sqrt{2}}{(n_{1}+n_{3})+n_{2}\sqrt{2}}\leq\frac{3+\lambda}{1-\lambda}$
(6)

To prove this we first need to show that
$OPT(\mathcal{C}_{1})=SW(\mathcal{C}_{1},D)$. First of all, it holds that
$SW(\mathcal{C}_{1},C)\leq SW(\mathcal{C}_{1},B)$: points $R,S$ are equally
close to $B,C$, while $T,D$ are closer to $C$ than to $B$. Similarly,
$SW(\mathcal{C}_{1},A)\leq SW(\mathcal{C}_{1},B)$. Finally
$SW(\mathcal{C}_{1},D)\leq SW(\mathcal{C}_{1},B)$: $R$ is equally close to
$B,D$, while $T,S,D$ are closer to $D$ than to $B$. Since
$f(\mathcal{C}_{1})=D$, we have $n_{1}+n_{2}+\lambda n\geq n_{3}+n_{4}$ and
$n_{2}+n_{3}+\lambda n\geq n_{1}+n_{4}$. In particular, we infer
$n_{2}+\lambda n\geq n_{4}$, i.e.
$n_{2}(1+\lambda)-n_{4}(1-\lambda)\geq-\lambda(n_{1}+n_{3})$. The last
inequality in (6) is equivalent to:

$\displaystyle(n_{1}+n_{3})(3+\lambda-\sqrt{5}(1-\lambda))+n_{2}(\sqrt{2}(3+\lambda)-\sqrt{2}(1-\lambda))-$
$\displaystyle-2\sqrt{2}n_{4}(1-\lambda)\geq 0,\mbox{ i.e. }$
$\displaystyle(n_{1}+n_{3})(3-\sqrt{5}+\lambda(1+\sqrt{5}))+2\sqrt{2}[n_{2}(1+\lambda)-n_{4}(1-\lambda)]\geq
0.$

Since $0\leq\lambda\leq 1$, it follows that
$3-\sqrt{5}+\lambda(1+\sqrt{5}-2\sqrt{2})\geq
3-\sqrt{5}-(1+\sqrt{5}-2\sqrt{2})=2(1+\sqrt{2}>\sqrt{5})>0$. We infer that
(5.2) (hence the last inequality in (6)) must be true.

Proving $\mathbf{\Delta\geq 0}$:
$\Delta=F(\mathcal{C},P_{\mathcal{C}})-SW(\mathcal{C}_{1},f(\mathcal{C},P_{\mathcal{C}}))-OPT(\mathcal{C})+$

$\displaystyle+SW(\mathcal{C}_{1},y^{*})=\sum_{i=1}^{n}d(x_{i},D)-\frac{n_{1}+n_{3}}{2}-n_{2}\frac{\sqrt{2}}{2}+n_{1}d(T,y^{*})+$
$\displaystyle+n_{2}d(R,y^{*})+n_{3}d(S,y^{*})+n_{4}d(D,y^{*})$

We know that $y^{*}\in\\{A,B,C,D\\}$. There are four cases. We treat here the
case $y^{*}=B$ (the other ones are similar). Hence

$\displaystyle\Delta=\sum_{i=1}^{n}(d(x_{i},D)-d(x_{i},B))+(n_{1}+n_{3})\frac{\sqrt{5}-1}{2}+n_{4}\sqrt{2}$
(7)

We will break $\Delta$ into eight sums, corresponding to points $x_{i}$ being
in exactly one of the triangles $ASR,AVR,BVR,BUR,CUR,CTR$, $DTR,DSR$. First,
if $x_{i}$ is in one of $AVR,BVR,BUR,CUR$ then $d(x_{i},D)$
$\geq d(x_{i},B)$, so these four sums are nonnegative. Let us show that the
remaining sum is $\geq 0$ as well, proving this way that $\Delta\geq 0$.

Let us consider, for instance, the points $x_{i}$ that belong to the triangle
$CTR$. For every such $x_{i}$ we have $d(x_{i},D)-d(x_{i},B)\geq
d(T,D)-d(T,B)=\frac{1-\sqrt{5}}{2}$, so
$d(x_{i},D)-d(x_{i},B)+\frac{\sqrt{5}-1}{2}\geq 0$. Since the number of such
points is at most $n_{1}$ and $\sqrt{5}>1$,

$\displaystyle\sum_{i:x_{i}\in
CTR}(d(x_{i},D)-d(x_{i},B))+n_{1}\frac{\sqrt{5}-1}{2}\geq 0.$ (8)

The cases of sums corresponding to points in triangles $ARS,DSR$, $DTR$ are
similar. Adding all the eight inequalities proves that $\Delta\geq 0$.

Consistency: Again without loss of generality, we assume that the predicted
point (which also realizes the optimum) is $P_{\mathcal{C}}=D$. We will also
assume that the mechanism 2 yields one of $A,B,C$, otherwise the consistency
ratio is 1. We deal here with the case where the algorithm outputs
$Z_{\mathcal{C}}=B$, the others are similar. Given our assumptions on the
predictor and algorithm, the only possible case is $n_{1}+n_{2}+\lambda
n<n_{3}+n_{4}$ and $n_{2}+n_{3}+\lambda n<n_{1}+n_{4}$. So we have
$n_{2}+\lambda n<n_{4}$, i.e.
$n_{4}(1-\lambda)-n_{2}(1+\lambda)>\lambda(n_{1}+n_{3})$ (**). Consider
configuration $\mathcal{C}_{2}$ consisting of $n_{1}$ points at $U$, $n_{2}$
points at $B$, $n_{3}$ points at $V$, $n_{4}$ points at $R$. To prove this we
first need to show that $OPT(\mathcal{C}_{2})=SW(\mathcal{C}_{2},D)$. First,
it holds that $SW(\mathcal{C}_{2},C)<SW(\mathcal{C}_{2},D)$: points $R,V$ are
equally close to $C,D$, while $U,V$ are closer to $C$ than to $B$. Similarly,
$SW(\mathcal{C}_{2},A)<SW(\mathcal{C}_{2},D)$. Finally
$SW(\mathcal{C}_{2},B)<SW(\mathcal{C}_{2},D)$: $R$ is equally close to $B,D$,
while $U,V,B$ are closer to $B$ than to $D$. Second,
$F(\mathcal{C}_{2},P_{\mathcal{C}})=SW(\mathcal{C}_{2},B)$. Thus

$\displaystyle\frac{OPT(\mathcal{C}_{2})}{F(\mathcal{C}_{2},P_{\mathcal{C}})}=\frac{(n_{1}+n_{3})\sqrt{5}+(n_{4}+2n_{2})\sqrt{2}}{(n_{1}+n_{3})+n_{4}\sqrt{2}}<\frac{3-\lambda}{1+\lambda}$
(9)

Indeed, the last inequality is equivalent to
$(n_{1}+n_{3})(3-\lambda-\sqrt{5}(1+\lambda))+2\sqrt{2}[n_{4}(1-\lambda)-n_{2}(1+\lambda)]>0$.
Applying (**) we get

$\displaystyle(n_{1}+n_{3})(3-\sqrt{5}-\lambda(1+\sqrt{5}))+2\sqrt{2}[n_{4}(1-\lambda)-n_{2}(1+\lambda)]>(n_{1}$
$\displaystyle+n_{3})[3-\sqrt{5}-\lambda(1+\sqrt{5}-2\sqrt{2})]\geq
2(n_{1}+n_{3})[1-\sqrt{5}+\sqrt{2}]\geq 0.$

thus proving (9) (we have used inequalities, $1+\sqrt{5}-2\sqrt{2}>0$,
$0\leq\lambda\leq 1$ and $1-\sqrt{5}+\sqrt{2}>0$). To complete the proof of
the consistency bound all we have to prove is that

$\displaystyle\frac{OPT(\mathcal{C})}{F(\mathcal{C},P_{\mathcal{C}})}\leq\frac{SW(\mathcal{C}_{2},y^{*})}{F(\mathcal{C}_{2},P_{\mathcal{C}})}\leq\frac{OPT(\mathcal{C}_{2})}{F(\mathcal{C}_{2},P_{\mathcal{C}})}$
(10)

Similarly to the proof of robustness, to prove inequality (10) we consider
quantity
$\Delta_{2}:=F(\mathcal{C},P_{\mathcal{C}})-F(\mathcal{C}_{2},P_{\mathcal{C}})-OPT(\mathcal{C})+SW(\mathcal{C}_{2},y^{*})$,
and aim to prove that $\Delta_{2}\geq 0$.

Proving $\mathbf{\Delta_{2}\geq 0}$:
$\Delta_{2}=F(\mathcal{C},P_{\mathcal{C}})-F(\mathcal{C}_{2},P_{\mathcal{C}})-OPT(\mathcal{C})+SW(\mathcal{C}_{2},y^{*})$

$\displaystyle=\sum_{i=1}^{n}d(x_{i},B)-\frac{n_{1}+n_{3}}{2}-n_{4}\frac{\sqrt{2}}{2}-\sum_{i=1}^{n}d(x_{i},y^{*})+n_{1}d(U,y^{*})+$
$\displaystyle+n_{2}d(B,y^{*})+n_{3}d(V,y^{*})+n_{4}d(R,y^{*})$

We know that $y^{*}\in\\{A,B,C,D\\}$. There are four cases. We treat here the
case $y^{*}=D$ (the other ones are similar). Hence

$\displaystyle\Delta_{2}=\sum_{i=1}^{n}(d(x_{i},B)-d(x_{i},D))+(n_{1}+n_{3})\frac{\sqrt{5}-1}{2}+n_{2}\sqrt{2}$
(11)

The proof that $\Delta_{2}\geq 0$ uses the same idea of triangle decomposition
as the corresponding proof for $\Delta\geq 0$.

Strategyproofness: Let $\mathcal{C}=(p_{1},p_{2},\ldots,p_{n})$ be an
arbitrary configuration, and without loss of generality assume that
$f(\mathcal{C})=D$. Let $i\in[n]$ be an agent, and assume that by misreporting
location as $q_{i}$, agents $i$ is able to strictly improve its utility. This
means that in the new profile $\mathcal{C}^{\prime}$,
$f(\mathcal{C}^{\prime})\neq f(\mathcal{C})$. There are two cases:

  * •

$\mathbf{f(\mathcal{C}^{\prime})\in\\{A,C\\}.}$ These two cases are symmetric
and without loss of generality we can assume that $f(\mathcal{C}^{\prime})=A$.
This means that $n_{1}+n_{2}+\lambda n\geq n_{3}+n_{4}$ and
$n_{2}+n_{3}+\lambda n\geq n_{1}+n_{4}$ but the corresponding inequalities for
$n_{1}^{\prime},n_{2}^{\prime},n_{3}^{\prime},n_{4}^{\prime}$ read

$\displaystyle n_{1}^{\prime}+n_{2}^{\prime}+\lambda n\geq
n_{3}^{\prime}+n_{4}^{\prime}\mbox{ but }n_{2}^{\prime}+n_{3}^{\prime}+\lambda
n<n_{1}^{\prime}+n_{4}^{\prime}.$ (12)

In particular $n_{2}+n_{3}\geq n\frac{1-\lambda}{2}\mbox{ but
}n_{2}^{\prime}+n_{3}^{\prime}<n\frac{1-\lambda}{2}$. No point whose location
is in the rectangle $BUSA$ gains by misreporting it ($D$ is at least as far as
$A$). So i does not belong to rectangle $BUSA$. But this implies
$n_{2}+n_{3}\leq n_{2}^{\prime}+n_{3}^{\prime}$, a contradiction.

  * •

$\mathbf{f(\mathcal{C}^{\prime})=B.}$ Then $n_{1}+n_{2}+\lambda n\geq
n_{3}+n_{4}$ and $n_{2}+n_{3}+\lambda n\geq n_{1}+n_{4}$, but
$n_{1}^{\prime}+n_{2}^{\prime}+\lambda n<n_{3}^{\prime}+n_{4}^{\prime}$ and
$n_{2}^{\prime}+n_{3}^{\prime}+\lambda n<n_{1}^{\prime}+n_{4}^{\prime}$. Hence
$n_{1}+n_{2}\geq n\frac{1-\lambda}{2}>n_{1}^{\prime}+n_{2}^{\prime}$ and
$n_{2}+n_{3}\geq n\frac{1-\lambda}{2}>n_{2}^{\prime}+n_{3}^{\prime}$.

Since misreporting a single point decreases both sums $n_{2}+n_{3}$ and
$n_{1}+n_{2}$, we infer the fact that agent $i$ is in the rectangle $BURV$ and
$n_{1}+n_{2}=n_{3}+n_{4}$, $n_{2}+n_{3}=n_{1}+n_{4}$. But this is a
contradiction: no point whose true location is in the rectangle $BURV$ gains
by misreporting its location ($D$ is already their farthest point). So $f$ is
strategyproof.

A counterexample that shows that a coalition of two agents can manipulate
Mechanism 2 is presented in Figure 2: $\mathcal{C}$ consists of 3 agents at
$T,S$ each, one at each of $R,D$. Clearly $f(\mathcal{C})=D$. On the other
hand, making one agent from each of $T,S$ misreport their location as $D$
yields a configuration $\mathcal{C}^{\prime}$ such that
$f(\mathcal{C}^{\prime})=B$. Both agents benefit from misreporting.

$n_{2}$$n_{3}$$n_{4}$$n_{1}$1$D$1$R$3$T$3$S$$U$$V$$A$$B$$C$+1+1

$n_{2}$$n_{3}$$n_{4}$$n_{1}$3$D$1$R$2$T$2$S$$U$$V$$A$$B$$C$

Figure 2: Manipulation by a coalition of size 2.

###  5.3 Proof of Theorem 2

Robustness: Without loss of generality let us choose coordinates such that
point $P_{\mathcal{C}}$ has coordinate 1/4.

We first deal with the case
$\mathbf{f(\mathcal{C},P_{\mathcal{C}})=P_{\mathcal{C}}}$, that is $n_{P}\leq
n_{Q}+\lambda n$ or, equivalently, by substituting $n_{Q}=n-n_{P}$, $n_{P}\leq
n(1+\lambda)/2$.

Let $\mathcal{C}_{1}$ be the configuration consisting of $n_{Q}$ points at
$P_{\mathcal{C}}-1/4$, together with $n_{P}$ points at $P_{\mathcal{C}}$
(Figure 3). The algorithm will output point $P_{\mathcal{C}}$. Hence
$SW(\mathcal{C}_{1},f(\mathcal{C},P_{\mathcal{C}}))=n_{Q}/4.$

$P_{C}$Q1, 0$n_{Q}$$n_{P}$

$P_{C}$Q1, 0$n_{Q}$$n_{P}$

Figure 3: (a). Configuration $\mathcal{C}_{1}$ (b). Configuration
$\mathcal{C}_{2}$.

Let us find $x\in[0,1]$ such that $SW(\mathcal{C}_{1},x)$ is maximized. On
each of the segments $[0,1/4],[0,1/4],[1/2,3/4],[3/4,1]$ the objective
function is a linear function in $x$ (generally a different one from segment
to segment). Hence the maximum is reached at one of the points
$x=0,x=1/4,x=1/2,x=3/4$. These values are, respectively,
$n_{P}/4,n_{Q}/4,n_{P}/2+n_{Q}/4,n_{P}/4+n_{Q}/2$. We infer that
$OPT(\mathcal{C}_{1})=\frac{n+max(n_{P},n_{Q})}{4}$, reached for $y^{*}=Q=3/4$
(if $n_{P}\geq n_{Q}$) and $y^{*}=1/2$ (if $n_{P}<n_{Q}$). If $n_{P}\leq
n_{Q}$ then the fraction
$\frac{OPT(\mathcal{C}_{1})}{SW(\mathcal{C}_{1},f(\mathcal{C},P_{\mathcal{C}}))}$
is at most 3. Otherwise it is $\frac{n_{Q}+2n_{P}}{n_{Q}}$. Hence

$\displaystyle\frac{OPT(\mathcal{C}_{1})}{SW(\mathcal{C}_{1},f(\mathcal{C},P_{\mathcal{C}}))}\leq
max(3,1+2\frac{1+\lambda}{1-\lambda})=\frac{3+\lambda}{1-\lambda}$ (13)

$\mathbf{\Delta\geq 0}$:
$\Delta=F(\mathcal{C},P_{\mathcal{C}})-SW(\mathcal{C}_{1},f(\mathcal{C},P_{\mathcal{C}}))-SW(\mathcal{C},y^{*})+SW(\mathcal{C}_{1},y^{*})$

$\displaystyle+SW(\mathcal{C}_{1},y^{*})=\sum_{i=1}^{n}d(x_{i},P_{\mathcal{C}})-\frac{n_{Q}}{4}-\sum_{i=1}^{n}d(x_{i},Q)+\frac{n_{Q}+2n_{P}}{4}=$
$\displaystyle\frac{n_{P}}{2}+\sum_{i=1}^{n}(d(x_{i},\widehat{P})-d(x_{i},\widehat{Q}))=\sum_{x_{i}\in[1/2,1]}(d(x_{i},P_{\mathcal{C}})-d(x_{i},Q))$
$\displaystyle+\sum_{x_{i}\in[0,1/2]}(d(x_{i},P_{\mathcal{C}})-d(x_{i},Q))+n_{P}/2.$

The first sum consists of non-negative terms only, since for $z\in[1/2,1]$,
$d(z,P_{\mathcal{C}})\geq d(z,Q)$. For the remaining terms, when $z\in[0,1/2]$
we claim that $d(z,P_{\mathcal{C}})-d(z,Q)\geq-1/2$. This is obvious since
$d(z,P_{\mathcal{C}})\geq 0$ and $d(z,Q)\leq 1/2$, with equality when
$z=P_{\mathcal{C}}$. Since the number of points in $[0,1/2]$ is $n_{P}$,
$\Delta\geq 0$ follows.

The case $\mathbf{f(\mathcal{C},P_{\mathcal{C}})=Q}$, that is
$n_{P}>n_{Q}+\lambda n$ or, equivalently, $n_{P}(1-\lambda)>n_{Q}(1+\lambda)$,
is similar: let $\mathcal{C}_{2}$ be the configuration consisting of $n_{P}$
points at $P_{\mathcal{C}}+1/4$, together with $n_{Q}$ points at $Q$. The
algorithm will output point $Q$, with social welfare
$SW(\mathcal{C}_{2},f(\mathcal{C},P_{\mathcal{C}}))=n_{P}/4.$ A similar
analysis to that of the first case yields
$OPT(\mathcal{C}_{2})=(n+max(n_{P},n_{Q}))/4=n+n_{P}=(2n_{P}+n_{Q})/4$. Hence

$\displaystyle\frac{OPT(\mathcal{C}_{2})}{SW(\mathcal{C}_{2},f(\mathcal{C},P_{\mathcal{C}}))}=2+\frac{n_{Q}}{n_{P}}<2+\frac{1-\lambda}{1+\lambda}=\frac{3+\lambda}{1+\lambda}\leq\frac{3+\lambda}{1-\lambda}$
(14)

Proving $\Delta\geq 0$ follows a similar pattern to that of the first case.

Consistency: Without loss of generality assume that $P_{\mathcal{C}}=1/4$. If
$f(\mathcal{C},P_{\mathcal{C}})=P_{\mathcal{C}}$ then the consistency ratio is
one. Assume thus that $f(\mathcal{C},P_{\mathcal{C}})=Q$ but
$OPT(\mathcal{C})$ is reached at $P_{\mathcal{C}}$. By the definition of the
algorithm, the only possible case is $n_{P}>n_{Q}+\lambda n$, i.e.
$\frac{n_{Q}}{n_{P}}<\frac{1-\lambda}{1+\lambda}$. Let $\mathcal{C}_{1}$ be
the configuration consisting of the $n_{P}$ points of $\mathcal{C}$, together
with $n_{Q}$ points at $Q$. Since for every $y$ we have $d(P,y)+d(Q,y)=1/2$,
it follows that the optimum social welfare of $\mathcal{C}_{1}$ is still
reached at $P_{\mathcal{C}}$, and is equal to $\Sigma+n_{Q}/2$, where
$\Sigma:=\sum_{x_{i}\in(0,1/2)}|x_{i}-1/4|$. On the other hand
$SW(\mathcal{C}_{1},P_{\mathcal{C}})=\sum_{x_{i}\in(0,1/2)}1/2-|x_{i}-1/4|=n_{P}/2-\Sigma$.
Since $\Sigma\leq n_{P}/4$, the approximation ratio is

$\frac{OPT(\mathcal{C}_{1})}{F(\mathcal{C}_{1},P_{\mathcal{C}})}=\frac{\Sigma+n_{Q}/2}{n_{P}/2-\Sigma}\leq\frac{\frac{n_{P}}{4}+\frac{n_{Q}}{2}}{\frac{n_{P}}{2}-\frac{n_{P}}{4}}=1+\frac{2n_{Q}}{n_{P}}\leq
1+2\frac{1-\lambda}{1+\lambda}=\frac{3-\lambda}{1+\lambda}.$

But $OPT(\mathcal{C})\leq OPT(\mathcal{C}_{1})$ and
$F(\mathcal{C}_{1},P_{\mathcal{C}})\geq F(\mathcal{C},P_{\mathcal{C}})$. The
consistency upperbound follows.

Group strategyproofness: Assume first that $n_{P}\leq n_{Q}+\lambda n$, i.e.
Algorithm 2 outputs point $P_{\mathcal{C}}$. Let $S\subset[n]$ be a set of
agents. If $S$ contained a point $W$ such that $d(W,P_{\mathcal{C}})\geq
d(W,Q)$ then $W$ cannot increase its utility by misreporting location. So all
points in $S$ are farther to $Q$ than to $P$. This means that all points in
$S$ are counted into $n_{P}$ and by misreporting their location they will lead
to point $P_{\mathcal{C}}$ being chosen as well. The case $n_{P}>n_{Q}+\lambda
n$ is similar.

###  5.4 Proof of Theorem 3

First, a well-known problem in algorithms, a method to find diameters in
trees, implies the fact that the algorithm is correct: if $a$ is the farthest
from $P_{\mathcal{C}}$ then $P$ is a peripheral point: the farthest point $b$
from $a$ induces a diameter $ab$ in $T^{\prime}$. Moreover, by the definition
of points $a,b$, we have $d(P_{\mathcal{C}},b)\leq d(P_{\mathcal{C}},a)$.

Group strategyproofness:  This is similar to the corresponding proof in [12],
and is based on the fact that points in $T_{a}$ are closer to $a$ than to $b$,
while points in $T_{b}$ are closer to $b$ than to $a$.

Robustness:  We first consider the case $n_{1}+\lambda n>n_{2}$, that is the
algorithm outputs point $b$. Let $y^{*}$ be the optimal location for
configuration $\mathcal{C}$ and $u^{*}$ the projection of $y^{*}$ on $[a,b]$.
Consider configuration $\mathcal{C}_{1}$ in which there are $n_{1}$ points at
$m_{a,b}$ and $n_{2}$ points at $b$. $SW(\mathcal{C}_{1},y^{*})=n_{1}\cdot
d(m_{a,b},y^{*})+n_{2}\cdot d(y^{*},b)\leq
n_{1}\cdot\frac{d(a,b)}{2}+n_{2}d(a,b)<n_{1}d(a,b)[\frac{1}{2}+\frac{1+\lambda}{1-\lambda}]=n_{1}\cdot
d(a,b)\cdot\frac{3+\lambda}{2(1-\lambda)}$. On the other hand
$F(\mathcal{C}_{1},P_{C})=n_{1}\cdot d(m_{a,b},b)+n_{2}\cdot
d(b,b)=n_{1}\frac{d(a,b)}{2}$. So

$\frac{SW(\mathcal{C}_{1},y^{*})}{F(\mathcal{C}_{1},P_{C})}<\frac{3+\lambda}{1-\lambda}$

$\Delta\geq 0$:
$\Delta=F(\mathcal{C},P_{\mathcal{C}})-SW(\mathcal{C}_{1},f(\mathcal{C},P_{\mathcal{C}}))-OPT(\mathcal{C})+SW(\mathcal{C}_{1},y^{*})=$

$\displaystyle=\sum_{x_{i}\in\mathcal{C}}d(x_{i},b)-n_{1}d(m_{a,b},b)-\sum_{x_{i}\in\mathcal{C}}d(x_{i},y^{*})+n_{1}d(m_{a,b},y^{*})$
$\displaystyle+n_{2}d(b,y^{*})=\sum_{x_{i}\in
T_{a}}(d(x_{i},b)-d(m_{a,b},b)-d(x_{i},w^{*})+d(m_{a,b},w^{*}))$
$\displaystyle+\sum_{x_{i}\in
T_{b}}(d(x_{i},b)-d(x_{i},w^{*})+d(b,w^{*}))=\sum_{x_{i}\in
T_{a}}(d(m_{a,b},w^{*})$
$\displaystyle+d(m_{a,b},x_{i})-d(x_{i},w^{*}))+\sum_{x_{i}\in
T_{b}}(d(x_{i},b)+d(b,w^{*})-d(x_{i},w^{*})\geq 0$

by triangle inequalities.

Consider now the case $n_{1}+\lambda n\leq n_{2}$, that is the algorithm
chooses the point $a$. Consider the configuration $\mathcal{C}_{2}$ in which
there are $n_{1}$ points at $a$ and $n_{2}$ points at $m_{a,b}$.
$SW(\mathcal{C}_{2},y^{*})=n_{1}\cdot d(a,y^{*})+n_{2}\cdot
d(y^{*},m_{a,b})\leq n_{1}\cdot d(a,b)+n_{2}d(a,b)/2\leq
n_{2}d(a,b)[\frac{1}{2}+\frac{1-\lambda}{1+\lambda}]=n_{1}\cdot
d(a,b)\cdot\frac{3-\lambda}{2(1+\lambda)}$. On the other hand
$F(\mathcal{C}_{2},P_{C})=n_{1}\cdot d(a,a)+n_{2}\cdot
d(m_{a,b},a)=n_{2}\frac{d(a,b)}{2}$. So

$\frac{SW(\mathcal{C}_{2},y^{*})}{F(\mathcal{C}_{2},P_{C})}\leq\frac{3-\lambda}{1+\lambda}\leq\frac{3+\lambda}{1-\lambda}$
(15)

$\Delta\geq 0$:
$\Delta=F(\mathcal{C},P_{\mathcal{C}})-SW(\mathcal{C}_{1},f(\mathcal{C},P_{\mathcal{C}}))-OPT(\mathcal{C})+SW(\mathcal{C}_{1},y^{*})$

$\displaystyle=\sum_{x_{i}\in\mathcal{C}}d(x_{i},a)-n_{2}d(m_{a,b},a)-\sum_{x_{i}\in\mathcal{C}}d(x_{i},y^{*})+n_{1}d(a,y^{*})+$
$\displaystyle+n_{2}d(m_{a,b},y^{*})=\sum_{x_{i}\in
T_{a}}(d(x_{i},a)-d(x_{i},w^{*})+d(a,w^{*}))$ $\displaystyle+\sum_{x_{i}\in
T_{b}}(d(x_{i},a)-d(m_{a,b},a)-d(x_{i},w^{*})+d(m_{a,b},w^{*}))=$
$\displaystyle=\sum_{x_{i}\in T_{a}}d(a,w^{*})+d(a,x_{i})-d(x_{i},w^{*})+$
$\displaystyle+\sum_{x_{i}\in
T_{b}}(d(x_{i},m_{a,b})+d(m_{a,b},w^{*})-d(x_{i},w^{*})\geq 0$

by triangle inequalities.

Consistency:  Assume that $P_{\mathcal{C}}=y^{*}$ is a peripheral point. There
are two cases:

Case 1: $\mathbf{n_{1}+\lambda n\leq n_{2}}$. That is the algorithm outputs
point $a$. We actually obtained the desired bound in the course of proving
robustness (first inequality in equation (15)).

Case 1: $\mathbf{n_{1}+\lambda n>n_{2}}$. That is the algorithm outputs point
$b$. But by the definition of the algorithm (the fact that we take
$b=P_{\mathcal{C}}$ if possible) it follows that $P_{\mathcal{C}}=y^{*}=b$.
The approximation ratio is 1.

##  6 Proof of Theorem 4

We will use characterization of strategyproof mechanisms from [23, 13]. They
prove that strategyproof mechanisms have the following form: there exist
$0\leq r<s\leq 1$ and $0\leq k\leq n$ s.t., if $v=\frac{r+s}{2}$ then

$T_{k}^{r,s}(s_{1},s_{2},\ldots s_{n})=\left\\{\begin{array}[]{ll}r,&\mbox{ if
}|\\{i:s_{i}\leq v\\}|\leq k,\\\ s,&\mbox{ otherwise.}\\\ \end{array}\right.$

In our cases clearly $r=0,s=1$, hence $v=1/2$. We will compute next the
approximation ratios for the threshold mechanism $T_{k}^{0,1}$ under each of
the hypotheses $y^{*}=0$, $y^{*}=1$.

Clearly $OPT(\mathcal{C})=max(\sum_{i}x_{i},\sum_{i=1}^{n}(1-x_{i}))$. To find
the approximation ratios of $T_{k}^{0,1}$ we will look for configurations
$\mathcal{C}$ for which the optimum is realized at $y^{*}=0$ while
$T_{k}(\mathcal{C})=1$ (or viceversa).

Indeed, to realize the optimum at $y^{*}=0$ while $T_{k}(\mathcal{C})=1$ we
need to maximize $\sum_{i}x_{i}$ while making sure that at least $k+1$ points
of $\mathcal{C}$ are in $[0,1/2]$. This is achieved by taking
$\mathcal{C}_{1}$ to be the configuration consisting of $k+1$ points at 1/2
and $n-k-1$ points at 1. It can be verified that the optimum for
$\mathcal{C}_{1}$ is indeed realized at $y^{*}=0$, since
$\sum_{i}x_{i}=k/2+n-k=n-k/2$, while $\sum_{i}(1-x_{i})=k/2$. So

$\frac{OPT(\mathcal{C}_{1})}{T_{k}(\mathcal{C}_{1})}=\frac{n-k/2}{k/2}=\frac{2n}{k}-1.$

On the other hand, to realize the optimum at $Y^{*}=1$ while
$T_{k}(\mathcal{C})=0$ we need to minimize $\sum_{i}x_{i}$ while making sure
that at most $k$ points of $\mathcal{C}$ are in $[0,1/2]$. Let
$\mathcal{C}_{2}$ the configuration consisting of $k$ points at 0 and $n-k$
points at $1/2+\epsilon$. It can be verified that for small enough
$\epsilon>0$ the optimum for $\mathcal{C}_{2}$ is indeed realized at $P=1$
since $\sum_{i}x_{i}=(n-k)(1/2+\epsilon)\approx\frac{n-k}{2}$, while
$\sum_{i}(1-x_{i})=k+(n-k)(1/2-\epsilon)\approx(n-k)/2+k$.

$\frac{OPT(\mathcal{C}_{2})}{T_{k}(\mathcal{C}_{2})}=\frac{(n+k)/2-\epsilon(n-k)}{(n-k)/2+(n-k)\epsilon}\leq\frac{n+k}{n-k}=\frac{2n}{n-k}-1.$

In conclusion, for $k\leq n/2$ $T_{k}$ has approximation ratio
$\frac{2n}{k}-1$, while for $k>n/2$ $T_{k}$ has approximation ratio
$\frac{2n}{n-k}-1$.

Consider now a mechanism with predictions
$f:X^{n}\times\\{0,1\\}\rightarrow\\{0,1\\}$ and its restrictions
$f_{0},f_{1}$ to each of the cases $P_{\mathcal{C}}=0$, $P_{\mathcal{C}}=1$.
Mechanisms $f_{0},f_{1}$ are strategyproof. Since $f$ is $(1+c)$-consistent,
for every $\mathcal{C}$ such that $OPT(\mathcal{C})=0$,
$\frac{OPT(\mathcal{C})}{SW(\mathcal{C},f_{0}(\mathcal{C}))}\leq 1+c$, and
similarly, for every $\mathcal{C}$ s.t. $OPT(\mathcal{C})=1$,
$\frac{OPT(\mathcal{C})}{SW(\mathcal{C},f_{1}(\mathcal{C}))}\leq 1+c$.

By the previous discussion it follows that there exist numbers $k_{0},k_{1}$
such that $f_{0}\equiv T_{k_{0}}$ and $f_{1}\equiv T_{k_{1}}$. Furthermore,
since $f$ is $(1+c)$-consistent, we infer that $\frac{2n}{k_{0}}-1\leq 1+c$
or, equivalently, $k_{0}\geq\frac{2n}{2+c}$. Similarly,
$\frac{2n}{n-k_{1}}-1\leq 1+c$, hence $k_{1}\leq
n-\frac{2n}{2+c}=\frac{2cn}{2+c}$.

Now let’s consider the case of wrong predictions: suppose $P_{\mathcal{C}}=0$
but, in fact, $y^{*}=1$. This means that $f$ acts on $\mathcal{C}$ as
$T_{k_{0}}$ would do. Consider again configuration $\mathcal{C}_{2}$
consisting of $k_{0}$ points at $0$, the rest at $1/2+\epsilon$. Clearly the
optimum of this configuration is obtained at $y^{*}=1$. On the other hand
$\frac{OPT(\mathcal{C}_{2})}{F(\mathcal{C}_{2},P_{C_{2}})}=\frac{(n+k_{0})/2-\epsilon(n-k_{0})}{(n-k_{0})/2+(n-k_{0})\epsilon}$.
Since $k_{0}\geq\frac{2n}{2+c}$,
$\frac{OPT(\mathcal{C}_{2})}{F(\mathcal{C}_{2},P_{C_{2}})}\geq\frac{\frac{n}{2}(1-\epsilon)+\frac{2n}{2+c}(\frac{1}{2}+\epsilon)}{\frac{n}{2}(1+2\epsilon)-\frac{2n}{2+c}(1/2+\epsilon)}=\frac{\frac{1}{2}+\frac{1}{(2+c)}+\epsilon\frac{2-c}{2(2+c)}}{\frac{1}{2}-\frac{1}{2+c}+\epsilon\frac{c}{2+c}}$.
The limit (as $\epsilon\rightarrow 0$) of the right-hand side is
$\frac{\frac{1}{2}+\frac{1}{(2+c)}}{\frac{1}{2}-\frac{1}{2+c}}=\frac{4+c}{c}=1+\frac{4}{c}$.
So for any $\delta>0$ we can find $\epsilon>0$ such that configuration $C_{2}$
witnesses the fact that the mechanism $f$ is not
$(1+\frac{4}{c}+\delta)$-robust.

##  7 Proof of Theorem 5

$\gamma$-group strategyproofness: The proof is very similar to the
corresponding proof in [14] (and our own arguments for Theorem 1), and is
omitted from this extended abstract. We only highlight the fact that (because
the intervals we consider are $[0,\frac{1-\lambda}{2}),[1-\lambda/2,1]$, which
have unequal lengths), for $\lambda>0$ the mechanism cannot be group-
strategyproof, otherwise it would contradict the characterization [23] of
strategyproof mechanisms for agents of type 0.

Robustness:  The result will follow from the following lemmas:

######  Lemma 2.

Let $\mathcal{C}$ be a configuration with all agents of type 1. Then

$\frac{OPT(\mathcal{C})}{f(\mathcal{C},P_{\mathcal{C}})}\leq\frac{3+\lambda}{1-\lambda}$
(16)

###### Proof.

Without loss of generality assume that $P_{\mathcal{C}}=1$ (if this is not the
case, simply switch labels 1 and 0). Let $y^{*}$ be the point realizing the
optimum social welfare for $\mathcal{C}$. $y^{*}$ can be characterized as the
point that maximizes $\sum_{i=1}^{n}(1-d(x_{i},y^{*}))$ (that is, it minimizes
$\sum_{i=1}^{n}d(x_{i},y^{*})$. It is well-known (e.g. [9]) that $y^{*}$ is
the median point of configuration $\mathcal{C}$ (any point between the two
median points, if $n$ is even). That is: let $\mathcal{C}=x_{1}\leq
x_{2}\leq\ldots\leq x_{n}$. If $n=2k+1$ then $y^{*}=x_{k+1}$. Otherwise
$y^{*}\in[x_{k},x_{k+1}]$ and we will take $y^{*}=\frac{x_{k}+x_{k+1}}{2}$.

Assume first that $\mathbf{n_{1}\leq n_{2}}$ (i.e. Algorithm 1 outputs
$P_{\mathcal{C}}=1$). Suppose first that $n=2k$. Then, by condition
$\mathbf{n_{1}\leq n_{2}}$ it follows that there are at least $k$ members of
$\mathcal{C}$ in the interval $[0,\frac{1+\lambda}{2}]$. So
$x_{k}\leq\frac{1+\lambda}{2}$. For $1\leq r\leq k$ we have:

$\displaystyle\frac{u_{r}(y^{*})+u_{n+1-r}(y^{*})}{u_{r}(f(\mathcal{C},P_{\mathcal{C}}))+u_{n+1-r}(f(\mathcal{C},P_{\mathcal{C}}))}=\frac{2-|x_{r}-y^{*}|-|x_{n+1-r}-y^{*}|}{2-x_{r}-x_{n+1-r}}$
$\displaystyle=\frac{2-|x_{n+1-r}-x_{r}|}{2-2x_{r}-|x_{n+1-r}-x_{r}|}\leq\frac{2-(1-x_{r})}{2-2x_{r}-(1-x_{r})}=$
$\displaystyle=\frac{1+x_{r}}{1-x_{r}}\leq\frac{1+\frac{1+\lambda}{2}}{1-\frac{1+\lambda}{2}}=\frac{3+\lambda}{1-\lambda}$

In the previous inequalities we have used the fact that $x_{r}\leq y^{*}\leq
x_{n+1-r}$, that $x_{n+1-r}-x_{r}\leq 1-x_{r}$, that
$x_{r}\leq\frac{1+\lambda}{2}$. In conclusion

$\displaystyle
u_{r}(y^{*})+u_{n+1-r}(y^{*})\leq\frac{3+\lambda}{1-\lambda}\cdot(u_{r}(f(\mathcal{C},P_{\mathcal{C}}))+u_{n+1-r}(f(\mathcal{C},P_{\mathcal{C}})))$

Summing up all these inequalities for $r=1,\ldots,k$ we get
$OPT(\mathcal{C})\leq\frac{3+\lambda}{1-\lambda}\cdot
F(\mathcal{C},P_{\mathcal{C}})$, which is what we wanted to prove. The proof
is similar for the case $n=2k+1$. In this case we sum again inequalities for
$i=1,\ldots,k$ and use the fact that $x_{k+1}=y^{*}$, so the middle term in
the sum expressing $OPT(\mathcal{C})$ is 0. We omit giving complete details.

The case $n_{1}>n_{2}$ is dealt with similarly. ∎

######  Lemma 3.

Let $\mathcal{C}_{1}$, $\mathcal{C}_{2}$ be two configurations with $n$ agents
s.t. all agents in $\mathcal{C}_{1}$ are of type 1 and the transformed
configurations of $\mathcal{C}$, $\mathcal{C}_{1}$ are identical. Then for any
$P\in\\{0,1\\}$ $f(\mathcal{C},P)=f(\mathcal{C}_{1},P)$, while
$OPT(\mathcal{C})\leq OPT(\mathcal{C}_{1})$. Hence
$app(\mathcal{C},f(\mathcal{C},P))\leq
app(\mathcal{C}_{1},f(\mathcal{C}_{1},P))$.

Proof. The first relation follows directly from the definition of Algorithm 4.
As for the second, it is enough to prove that $SW(\mathcal{C},Y)\leq
SW(\mathcal{C}_{1},Y)$ for every $Y\in[0,1]$. If $1\leq i\leq n$ and agent $i$
is of type $1$ in $\mathcal{C}$ (and in $\mathcal{C}_{1}$) then
$u_{i}(\mathcal{C},Y)=u_{i}(\mathcal{C}_{1},Y)$. Otherwise, if $i$ is of type
0 and location $x_{i}$ in $\mathcal{C}$ (but, of course, of type $1$ in
$\mathcal{C}_{1}$) then its location in $\mathcal{C}_{1}$ is $x_{i}^{*}$ and
$u_{i}(\mathcal{C},Y)=d(x_{i},Y)$, while
$u_{i}(\mathcal{C}_{1},Y)=1-d(x_{i}^{*},Y)$. Since
$d(x_{i},Y)+d(x_{i}^{*},Y)\leq 1$ ([14], Lemma 4) Lemma 3 follows.

Consistency:  We will use again Lemma 3. To prove that the algorithm is
$\frac{3-\lambda}{1+\lambda}$ consistent we only need to show that for all
configurations $\mathcal{C}$ where all agents are of type 1, if
$1=P_{C}=y^{*}$ then
$\frac{OPT(\mathcal{C})}{F(\mathcal{C},P_{C})}\leq\frac{3-\lambda}{1+\lambda}$.
If the algorithm outputs point $P_{C}$ then the approximation ratio of the
algorithm is 1. The remaining case is when the algorithm outputs the value
$0$. This means that $n_{1}>n_{2}$. Furthermore, since $y^{*}=1$, we must have
$x_{i}=1$ for all $i\geq\lceil n/2\rceil$.

Let $n=2k$. Just as in the case of proving robustness
$x_{k}\leq\frac{1-\lambda}{2}$. We have $OPT(\mathcal{C})=(n-k)\cdot
1+\sum_{i=1}^{k}x_{i}.$ On the other hand $F(\mathcal{C},P_{C})=(n-k)\cdot
1+\sum_{i=1}^{k}1-x_{i}=n+\sum_{i=1}^{k}x_{i}$. So
$\frac{OPT(\mathcal{C})}{F(\mathcal{C},P_{C})}\leq\frac{n-k+k\frac{1-\lambda}{2}}{n-k\frac{1-\lambda}{2}}=\frac{3-\lambda}{1+\lambda}$.

If $n=2k+1$ then $OPT(\mathcal{C})=n-k-1+\sum_{i=1}^{k}x_{i},$ while
$F(\mathcal{C},P_{C})=(n-k)\cdot
1+\sum_{i=1}^{k}1-x_{i}=n-\sum_{i=1}^{k}x_{i}$. So
$\frac{OPT(\mathcal{C})}{F(\mathcal{C},P_{C})}<\frac{k+k\frac{1-\lambda}{2}}{2k-k\frac{1-\lambda}{2}}=\frac{3-\lambda}{1+\lambda}$.

##  8 Related Work

For lack of space we only give the briefest sketch of related work.

As mentioned in the introduction, our work is naturally related to the
emerging literature on algorithms with predictions, [1, 2, 3]. In particular,
the robustness/consistency model was made popular (in the context of the
competitive analysis of ski-rental) by [2], and further studied in many
papers. The literature on mechanism design with predictions is, on the other
hand, very recent and limited, only including, to our best knowledge,
references [4, 5, 6, 7].

The facility location has a long history of investigation, both in a classical
(optimization) sense [22], as well as in a strategic setting (e.g. [9, 10,
11]). The classical approaches to obnoxious version of facility location have
an equally long history, starting perhaps with [24], as a topic in graph
theory/operations research, and including, e.g., [19, 20, 25]. The strategic
approach started in [26] (journal version in [12]). Other directly relevant
related references are [23, 13] that characterize stategyproof mechanisms in
two overlapping but slightly settings, that both generalize obnoxious facility
location, as well as [21], that characterize possible outputs of group
strategyproof mechanisms. Further variations include, e.g., [27, 15, 16, 28,
29]. An interesting, alternative strategic approach based on voting, that
studies a so-called _anti-Condorcet point_ , and would deserve further
attention is given in [30].

##  9 Conclusions and Open Problems

Our main contribution is showing that obnoxious facility location can be
analyzed in the framework of mechanism design with predictions. A number of
issues raised by our work remain open. The list of the most interesting ones
includes, we believe, the following:

  1. 1.

In the 2-d case can we give a group-strategyproof mechanism displaying the
optimum tradeoff ?

  2. 2.

What are the optimal tradeoffs between robustness and consistency in the case
of $d$-dimensional hypercubes, $d\geq 3$ ?

  3. 3.

Can we give an algorithm for trees that overcomes the issue(s) discussed in
Remark 1 ?

  4. 4.

What about randomized algorithms ? Such bounds exist in the case without
predictions. We attempted to give such bounds but failed, due to the
complexity of resulting calculations.

## References

  * [1] M. Mitzenmacher and S. Vassilvitskii.  Algorithms with predictions.  In Chapter 29 in [31], 2021.
  * [2] Manish Purohit, Zoya Svitkina, and Ravi Kumar.  Improving online algorithms via ml predictions.  Advances in Neural Information Processing Systems, 31, 2018.
  * [3] Alexander Lindermayr and Nicole Megow.  Algorithms with predictions webpage.  https://algorithms-with-predictions.github.io, 2022.  accessed October 2022.
  * [4] Chenyang Xu and Pinyan Lu.  Mechanism design with predictions.  Proceedings of IJCAI’22, 2022.
  * [5] Priyank Agrawal, Eric Balkanski, Vasilis Gkatzelis, Tingting Ou, and Xizhi Tan.  Learning-augmented mechanism design: Leveraging predictions for facility location.  Proceedings of EC’22, 2022.
  * [6] Vasilis Gkatzelis, Kostas Kollias, Alkmini Sgouritsa, and Xizhi Tan.  Improved price of anarchy via predictions.  In Proceedings of EC’22, 2022.
  * [7] Eric Balkanski, Vasilis Gkatzelis, and Xizhi Tan.  Strategyproof scheduling with predictions.  arXiv preprint arXiv:2209.04058, 2022.
  * [8] Jason D Hartline.  Mechanism design and approximation.  Book draft. October, 2022.
  * [9] Ariel D Procaccia and Moshe Tennenholtz.  Approximate mechanism design without money.  ACM Transactions on Economics and Computation (TEAC), 1(4):1–26, 2013.
  * [10] Reshef Meir.  Strategyproof facility location for three agents on a circle.  In International Symposium on Algorithmic Game Theory, pages 18–33. Springer, 2019.
  * [11] 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, 2020.
  * [12] Lili Mei, Deshi Ye, and Guochuan Zhang.  Mechanism design for one-facility location game with obnoxious effects on a line.  Theoretical Computer Science, 734:46–57, 2018.
  * [13] Ken Ibara and Hiroshi Nagamochi.  Characterizing mechanisms in obnoxious facility game.  In International conference on combinatorial optimization and applications, pages 301–311. Springer, 2012.
  * [14] 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.
  * [15] Itai Feigenbaum and Jay Sethuraman.  Strategyproof mechanisms for one-dimensional hybrid and obnoxious facility location models.  In AAAI workshop: Incentive and trust in E-communities, 2015.
  * [16] Morito Oomine, Aleksandar Shurbevski, and Hiroshi Nagamochi.  Parameterization of strategy-proof mechanisms in the obnoxious facility game.  J. Graph Algorithms Appl., 21(3):247–263, 2017.
  * [17] James Schummer and Rakesh V Vohra.  Strategy-proof location on a network.  Journal of Economic Theory, 104(2):405–428, 2002.
  * [18] Atif Abueida, Michael Ackerman, and Choi Sul-Young.  Centrality and anticentrality in trees.  DIMACS Educational Module, (08-03), 2008.
  * [19] Richard L Church and Robert S Garfinkel.  Locating an obnoxious facility on a network.  Transportation science, 12(2):107–118, 1978.
  * [20] Shen-Sheng Ting.  A linear-time algorithm for maxisum facility location on tree networks.  Transportation Science, 18(1):76–84, 1984.
  * [21] Morito Oomine and Hiroshi Nagamochi.  Characterizing output locations of gsp mechanisms to obnoxious facility game in trees.  IEICE TRANSACTIONS on Information and Systems, 99(3):615–623, 2016\.
  * [22] R. Love, J Morris, and G Wesolowsky.  Facilities location: Models and methods.  North Holland, 1988.
  * [23] Qiaoming Han and Donglei Du.  Moneyless strategy-proof mechanism on single-sinked policy domain: characterization and applications.  Faculty of Business Administration, University of New Brunswick, 2012\.
  * [24] Bohdan Zelinka.  Medians and peripherians of trees.  Archivum Mathematicum, 4(2):87–95, 1968.
  * [25] Arie Tamir.  Obnoxious facility location on graphs.  SIAM Journal on Discrete Mathematics, 4(4):550–567, 1991.
  * [26] Deshi Ye, Lili Mei, and Yong Zhang.  Strategy-proof mechanism for obnoxious facility location on a line.  In International Computing and Combinatorics Conference, pages 45–56. Springer, 2015.
  * [27] Yukun Cheng, Qiaoming Han, Wei Yu, and Guochuan Zhang.  Obnoxious facility game with a bounded service range.  In International conference on theory and applications of models of computation, pages 272–281. Springer, 2013.
  * [28] Yuhei Fukui, Aleksandar Shurbevski, and Hiroshi Nagamochi.  $\lambda$-group strategy-proof mechanisms for the obnoxious facility game in star networks.  IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences, 102(9):1179–1186, 2019.
  * [29] Fu Li, C Gregory Plaxton, and Vaibhav B Sinha.  The obnoxious facility location game with dichotomous preferences.  arXiv preprint arXiv:2109.05396, 2021.
  * [30] Martine Labbé.  Location of an obnoxious facility on a network: a voting approach.  Networks, 20(2):197–207, 1990.
  * [31] Tim Roughgarden.  Beyond the worst-case analysis of algorithms.  Cambridge University Press, 2021.