=Paper=
{{Paper
|id=Vol-3072/paper19
|storemode=property
|title=The Obnoxious Facility Location Game with Dichotomous Preferences
|pdfUrl=https://ceur-ws.org/Vol-3072/paper19.pdf
|volume=Vol-3072
|authors=Fu Li,Gregor Plaxton,Vaibhav Sinha
|dblpUrl=https://dblp.org/rec/conf/ictcs/LiPS21
}}
==The Obnoxious Facility Location Game with Dichotomous Preferences==
https://ceur-ws.org/Vol-3072/paper19.pdf
The Obnoxious Facility Location Game with
Dichotomous Preferences?
Fu Li, C. Gregory Plaxton, and Vaibhav B. Sinha
University of Texas at Austin, USA
{fuli,plaxton,vaibhavsinha}@utexas.edu
Abstract. We consider a facility location game in which n agents reside
at known locations on a path, and k heterogeneous facilities are to be
constructed on the path. Each agent is adversely affected by some subset
of the facilities, and is unaffected by the others. We design two classes of
mechanisms for choosing the facility locations given the reported agent
preferences: utilitarian mechanisms that strive to maximize social wel-
fare (i.e., to be efficient), and egalitarian mechanisms that strive to max-
imize the minimum welfare. For the utilitarian objective, we present a
weakly group-strategyproof efficient mechanism for up to three facilities,
we give a strongly group-strategyproof mechanism that guarantees at
least half of the optimal social welfare for arbitrary k, and we prove that
no strongly group-strategyproof mechanism achieves an approximation
ratio of 5/4 for one facility. For the egalitarian objective, we present a
strategyproof egalitarian mechanism for arbitrary k, and we prove that
√
no weakly group-strategyproof mechanism achieves a o( n) approxima-
tion ratio for two facilities. We extend our egalitarian results to the case
where the agents are located on a cycle, and we extend our first egali-
tarian result to the case where the agents are located in the unit square.
Keywords: Mechanism Design · Facility Location.
1 Introduction
The facility location game (FLG) was introduced by Procaccia and Tannenholtz
[21]. In this setting, a central planner wants to build a facility that serves agents
located on a path. The agents report their locations, which are fed to a mecha-
nism that decides where the facility should be built. Procaccia and Tannenholtz
studied two different objectives that the planner seeks to minimize: the sum of
the distances from the facility to all agents and the maximum distance of any
agent to the facility.
Every agent aims to maximize their welfare, which increases as their distance
to the facility decreases. An agent or a coalition of agents can misreport their
location(s) to try to increase their welfare. It is natural to seek strategyproof (SP)
or group-strategyproof (GSP) mechanisms, which incentivize truthful reporting.
?
Copyright © 2021 for this paper by its authors. Use permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0).
2 F. Li et al.
Often such mechanisms cannot simultaneously optimize the planner’s objective.
In these cases, it is desirable to approximately optimize the planner’s objective.
In real scenarios, an agent might dislike a certain facility, such as a power
plant, and want to stay away from it. This variant, called the obnoxious facility
location game (OFLG), was introduced by Cheng et al., who studied the problem
of building an obnoxious facility on a path [6]. In the present paper, we consider
the problem of building multiple obnoxious facilities on a path. With multiple
facilities, there are different ways to define the welfare function. For example, in
the case of two facilities, the welfare of the agent can be the sum, minimum, or
maximum of the distances to the two facilities. In our work, as all the facilities are
obnoxious, a natural choice for welfare is the minimum distance to any obnoxious
facility: the closest facility to an agent causes them the most annoyance, and if
it is far away, then the agent is satisfied.
A facility might not be universally obnoxious. Consider, for example, a school
or sports stadium. An agent with no children might consider a school to be
obnoxious due to the associated noise and traffic, while an agent with children
might not consider it to be obnoxious. Another agent who is not interested in
sports might similarly consider a stadium to be obnoxious. We assume that each
agent has dichotomous preferences; they dislike some subset of the facilities and
are indifferent to the others. Each agent reports a subset of facilities to the
planner. As the dislikes are private information, the reported subset might not
be the subset of facilities that the agent truly dislikes. On the other hand, we
assume that the agent locations are public and cannot be misreported.
In this paper, we study a variant of FLG, which we call DOFLG (Dichotomous
Obnoxious Facility Location Game), that combines the three aspects mentioned
above: multiple (heterogeneous) obnoxious facilities, minimum distance as wel-
fare, and dichotomous preferences. We seek to design mechanisms that perform
well with respect to either a utilitarian or egalitarian objective. The utilitarian
objective is to maximize the social welfare, that is, the total welfare of all the
agents. A mechanism that maximizes social welfare is said to be efficient. The
egalitarian objective is to maximize the minimum welfare of any agent. For both
objectives, we seek mechanisms that are SP, or better yet, weakly or strongly
group-strategyproof (WGSP / SGSP).
1.1 Our contributions
We study DOFLG with n agents. In Section 3, we consider the utilitarian objec-
tive. We present 2-approximate SGSP mechanisms for any number of facilities
when the agents are located on a path, cycle, or square. We obtain the following
two additional results for the path setting. In the first main result of the paper,
we obtain a mechanism that is WGSP for any number of facilities and efficient
for up to three facilities. To show that this mechanism is WGSP, we relate it to
a weighted approval voting mechanism. To prove its efficiency, we identify two
crucial properties that the welfare function satisfies, and we use an exchange
argument. For the path setting, we also show that no SGSP mechanism can
achieve an approximation ratio better than 5/4, even for one facility.
The Obnoxious Facility Location Game with Dichotomous Preferences 3
In Section 4, we consider the egalitarian objective. We provide SP mecha-
nisms for any number of facilities when the agents are located on a path, cycle, or
square. In the second main result of the paper, √
we prove that the approximation
ratio achieved by any WGSP mechanism is Ω( n), even for two facilities. Also,
we present a straightforward O(n)-approximate WGSP mechanism. Both of the
results for WGSP mechanisms hold for DOFLG when the agents are located on
a path or cycle. Table 1 summarizes our results.
Table 1. Summary of our results for DOFLG when the agents are located on a path.
The heading LB (resp., UB) stands for lower (resp., upper) bound. The results in the
egalitarian column also hold when the agents are located on a cycle. Boldface results
hold when the agents are located on a path, cycle, or square.
Utilitarian Egalitarian
LB UB LB UB
SP 1 1
1 1 for k ≤ 3
WGSP √
Ω( n) O(n)
SGSP 5/4 2
Due to space limitations, some of our proofs are omitted or sketched. Com-
plete proofs are presented in the full version of the paper.
1.2 Related work
FLG was introduced by Procaccia and Tannenholtz [21]. Many generalizations
and extensions of FLG have been studied [1, 8, 11–14, 19, 27]; here we highlight
some of the most relevant work. Cheng et al. introduced OFLG and presented a
WGSP mechanism to build a single facility on a path [6]. Later they extended
the model to cycles and trees [7]. A complete characterization of single-facility
SP/WGSP mechanisms for paths has been developed [16, 17]. Duan et al. studied
the problem of locating two obnoxious facilities at least distance d apart [9].
Other variants of OFLG have been considered [5, 15, 20, 25].
Agent preferences over the facilities were introduced to FLG in [10] and [28].
Serafino and Ventre studied FLG for building two facilities where each agent likes
a subset of the facilities [22]. Anastasiadis and Deligkas extended this model to
allow the agents to like, dislike, or be indifferent to the facilities [2]. The afore-
mentioned works address linear (sum) welfare function. Yuan et al. studied non-
linear welfare functions (max and min) for building two non-obnoxious facilities
[26]; their results have subsequently been strengthened [4, 18]. In the present
paper, we initiate the study of a non-linear welfare function (min) for building
multiple obnoxious facilities.
2 Preliminaries
The problems considered in this paper involve a set of agents located on a path,
cycle, or square. In the path (resp., cycle, square) setting, we assume without loss
4 F. Li et al.
of generality that the path (resp., cycle, square) is the unit interval (resp., unit-
circumference circle, unit square). We map the points on the unit-circumference
circle to [0, 1), in the natural manner. Thus, in the path (resp., cycle, square)
setting, each agent i is located in [0, 1] (resp., [0, 1), [0, 1]2 ). The distance between
any two points x and y is denoted d(x, y). In the path and square settings, d(x, y)
is defined as the Euclidean distance between x and y. In the cycle setting, d(x, y),
is defined as the length of the shorter arc between x and y. In all settings, we
index the agents from 1. Each agent has a specific location in the path, cycle, or
square. A location profile x is a vector (x1 , . . . , xn ) of points, where n denotes
the number of agents and xi is the location of agent i. Sections 3 and 4.1 present
our results for the path setting. Section 4.2 presents our results for the square
setting. Results for the cycle setting and some other results are presented in our
full paper.
Consider a set of agents 1 through n and a set of facilities F, where we assume
that each agent dislikes (equally) certain facilities in F and is indifferent to the
rest. In this context, we define an aversion profile a as a vector (a1 , . . . , an )
where each component ai is a subset of F. We say that such an aversion profile
is true if each component ai is equal to the subset of F disliked by agent i. In
this paper, we also consider reported aversion profiles where each component ai
is equal to the set of facilities that agent i claims to dislike. Since agents can
lie, a reported aversion profile need not be true. For any aversion profile a and
any subset C of agents [n], aC (resp., a−C ) denotes the aversion profile for the
agents in (resp., not in) C. For a singleton set of agents {i}, we abbreviate a−{i}
as a−i .
An instance of the dichotomous obnoxious facility location (DOFL) problem
is given by a tuple (n, k, x, a) where n denotes the number of agents, there is a set
of k facilities F = {F1 , . . . , Fk } to be built, x = (x1 , . . . , xn ) is a location profile
for the agents, and a = (a1 , . . . , an ) is an aversion profile (true or reported) for
the agents with respect to F. A solution to such a DOFL instance is a vector
y = (y1 , . . . , yk ) where component yj specifies the point at which to build Fj . We
say that a DOFL instance is true (resp., reported) if the associated aversion profile
is true (resp., reported). For any DOFL instance I = (n, k, x, a) and any j in [k],
we define haters(I, j) as {i ∈ [n] | Fj ∈ ai }, and indiff(I) as {i ∈ [n] | ai = ∅}.
For any DOFL instance I = (n, k, x, a) and any associated solution y, we
define the welfare of agent i, denoted w(I, i, y), as minj:Fj ∈ai d(xi , yj ), i.e., the
minimum distance from xi to any facility in ai . Remark: If ai is empty, we define
w(I, i, y) as 1/2 in the cycle setting, max(d(xi , 0), d(xi , 1)) in the path setting,
and the maximum distance from xi to a corner in the square setting.
The foregoing definition of agent welfare is suitable for true DOFL instances,
and is only meaningful for reported DOFL instances where the associated aver-
sion profile is close to true. In this paper, reported aversion profiles arise in
the context of mechanisms that incentivize truthful reporting, so it is reason-
able to expect such aversion profiles to be close to true. We define the social
welfare (resp., minimum welfare) as the sum (resp., minimum) of the individ-
ual agent welfares. When the facilities are built at y, the social welfare and
The Obnoxious Facility Location Game with Dichotomous Preferences 5
minimum welfare
P are denoted by SW(I, y) and MW(I, y), respectively. Thus
SW(I, y) = i∈[n] w(I, i, y) and MW(I, y) = mini∈[n] w(I, i, y).
Definition 2.1. For α ≥ 1, a DOFL algorithm A is α-efficient if for any DOFL
instance I,
max SW(I, y) ≤ α SW(I, A(I)).
y
Similarly, A is α-egalitarian if for any DOFL instance I,
max MW(I, y) ≤ α MW(I, A(I)).
y
A 1-efficient (resp., 1-egalitarian) DOFL algorithm, is said to be efficient (resp.,
egalitarian).
We are now ready to define a DOFL-related game, which we call DOFLG. It
is convenient to describe a DOFLG instance in terms of a pair (I, I 0 ) of DOFL
instances where I = (n, k, x, a) is true and I 0 = (n, k, x, a0 ) is reported. There
are n agents indexed from 1 to n, and a planner. There is a set of k facilities
F = {F1 , . . . , Fk } to be built. The numbers n and k are publicly known, as
is the location profile x of the agents. Each component ai of the true aversion
profile a is known only to agent i. Each agent i submits component a0i of the
reported aversion profile a0 to the planner. The planner, who does not have
access to a, runs a DOFL algorithm, call it A, to map I 0 to a solution. The input-
output behavior of A defines a DOFLG mechanism, call it M ; in the special case
where k = 1, we say that M is a single-facility DOFLG mechanism. We would
like to choose A so that M enjoys strong game-theoretic properties. We say
that M is α-efficient (resp., α-egalitarian, efficient, egalitarian) if A is α-efficient
(resp., α-egalitarian, efficient, egalitarian). As indicated earlier, such properties
(which depend on the notion of agent welfare) are only meaningful if the reported
aversion profile is close to true. To encourage truthful reporting, we require our
mechanisms to be SP, as defined below; we also consider the stronger properties
WGSP and SGSP.
The SP property says that no agent can increase their welfare by lying about
their dislikes.
Definition 2.2. A DOFLG mechanism M is SP if for any DOFLG instance
(I, I 0 ) with I = (n, k, x, a), and I 0 = (n, k, x, a0 ), and any agent i in [n] such
that a0 = (a−i , a0i ), we have
w(I, i, M (I)) ≥ w(I, i, M (I 0 )).
The WGSP property says that if a non-empty coalition C ⊆ [n] of agents
lies, then at least one agent in C does not increase their welfare.
Definition 2.3. A DOFLG mechanism M is WGSP if for any DOFLG instance
(I, I 0 ) with I = (n, k, x, a), and I 0 = (n, k, x, a0 ), and any non-empty coalition
C ⊆ [n] such that a0 = (a−C , a0C ), there exists an agent i in C such that
w(I, i, M (I)) ≥ w(I, i, M (I 0 )).
6 F. Li et al.
The SGSP property says that if a coalition C ⊆ [n] of agents lies and some
agent in C increases their welfare then some agent in C decreases their welfare.
Definition 2.4. A DOFLG mechanism M is SGSP if for any DOFLG instance
(I, I 0 ) with I = (n, k, x, a), and I 0 = (n, k, x, a0 ), and any coalition C ⊆ [n] such
that a0 = (a−C , a0C ), if there exists an agent i in C such that
w(I, i, M (I)) < w(I, i, M (I 0 )),
then there exists an agent i0 in C such that
w(I, i0 , M (I)) > w(I, i0 , M (I 0 )).
Every SGSP mechanism is WGSP and every WGSP mechanism is SP.
3 Efficient Mechanisms
Before studying efficient mechanisms for our problem, we review a variant of
the approval voting mechanism [3]. An instance of Dichotomous Voting (DV)
is a tuple (m, n, C, w+ , w− ) where m voters 1, . . . , m have to elect a candidate
among the set of candidates C = {c1 , . . . , cn }. Each voter i has dichotomous
preferences, that is, voter i partitions all of the candidates into two equivalence
classes: a top (most preferred) tier Ci and a bottom tier Ci = C \Ci . Each voter i
has associated (and publicly known) weights wi+ ≥ wi− ≥ 0. The symbols C, w+ ,
and w− denote length-m vectors with ith element Ci , wi+ , and wi− , respectively.
We now present our weighted approval voting mechanism.1
Mechanism 1 Given a DV instance (m, n, C, w+ , w− ), every voter i votes by
partitioning C into Ci0 and Ci0 . Let the weight function w be such that for voter
+ 0 −
i and candidate cj , w(i, j) = wPi if cj is in Ci and w(i, j) = wi otherwise. For
any j in [n], we define A(j) = i∈[m] w(i, j) as the approval of candidate cj . The
candidate cj with highest approval A(j) is declared the winner. Ties are broken
according to a fixed ordering of the candidates (e.g., in favor of lower indices).
Like approval voting, weighted approval voting is WGSP.
Theorem 3.1. Mechanism 1 is WGSP.
We now present our efficient mechanism for DOFLG.
Mechanism 2 For a given reported DOFL instance I = (n, k, x, a), output the
lexicographically least solution y in {0, 1}k that maximizes the social welfare
SW(I, y).
Theorem 3.2. Mechanism 2 is WGSP.
1
Our mechanism differs from the homonymous mechanism of Massó et al., which has
weights for the candidates instead of the voters [24].
The Obnoxious Facility Location Game with Dichotomous Preferences 7
Proof. To establish this theorem, we show that Mechanism 2 can be equivalently
expressed in terms of the approval voting mechanism. Hence Theorem 3.1 implies
the theorem.
Let (I, I 0 ) denote a DOFLG instance where I = (n, k, x, a) and I 0 = (n, k, x, a0 ).
We view each agent i ∈ [n] as a voter, and each y in {0, 1}k as a candidate. We
obtain the top-tier candidates Ci of voter i, and their reported top-tier candi-
dates Ci0 , from ai and a0i , respectively. Assume without loss of generality that
xi ≤ 1/2 (the other case can be handled similarly). Set Ci = {y = (y1 , . . . , yk ) ∈
{0, 1}k | yj = 1 for all Fj ∈ ai } and similarly Ci0 = {y = (y1 , . . . , yk ) ∈ {0, 1}k |
yj = 1 for all Fj ∈ a0i }. Also set wi+ = 1 − xi and wi− = xi . With this notation, it
is easy to see that A(y) = SW(I 0 , y), and that choosing the y with the highest
social welfare in Mechanism 2 is the same as electing the candidate with the
highest approval in Mechanism 1. t
u
We show that Mechanism 2 is efficient for k = 3. First, we note a well-known
result about the 1-Maxian problem. In this problem, there are n points located
at z1 , . . . , zn in the interval [a, b], and the task is to choose a point in [a, b] such
that the sum of the distances from that point to all zi s is maximized.
Lemma 3.1 (Optimality of the 1-Maxian Problem). PLet [a, b] be a real
interval, let z1 , . . . , zn belong to [a, b], and let f (z) denote i∈[n] |z − zi |. Then
maxz∈[a,b] f (z) belongs to {f (a), f (b)}.
Before proving the main theorem, we establish Lemma 3.2, which follows
from Lemma 3.1.
Lemma 3.2. Let (n, k, x, a) be a DOFL instance, let Y denote the set of all y
in [0, 1] such that it is efficient to build all k facilities at y, and assume that Y
is non-empty. Then Y ∩ {0, 1} is non-empty.
Theorem 3.3. Mechanism 2 is efficient for k = 3.
Proof. Let I = (n, k, x, a) be a DOFL instance and let y∗ = (y1∗ , y2∗ , y3∗ ) be an
efficient solution for I such that y1∗ ≤ y2∗ ≤ y3∗ .
Consider fixing variables y1 and y3 in the social welfare function SW(I, y).
That is, we have
X
SW(I, y)|y1 =y1∗ ,y3 =y3∗ = w(I, i, y)|y1 =y1∗ ,y3 =y3∗ .
i∈[n]
For convenience, let SW(y2 ) denote SW(I, y)|y1 =y1∗ ,y3 =y3∗ and let wi (y2 ) denote
w(I, i, y)|y1 =y1∗ ,y3 =y3∗ for each agent i.
Claim 1: For each agent i, the welfare function wi (y2 ) with y2 ∈ [y1∗ , y3∗ ]
satisfies at least one of the following two properties:
1. wi (y2 ) = |y2 − xi |;
2. wi (y1∗ ) = wi (y3∗ ) = maxy∈[y1∗ ,y3∗ ] wi (y).
8 F. Li et al.
Proof: Consider an agent i. We consider five cases.
Case 1: F2 ∈ / ai . Since the welfare of agent i is independent of the location
of F2 , wi is a constant function. Hence property 2 is satisfied.
Case 2: ai = {F2 }. By definition, we have wi (y2 ) = |y2 −xi |. Hence property 1
is satisfied.
Case 3: ai = {F1 , F2 }. By definition, we have wi (y2 ) = min(|y1∗ −xi |, |y2 −xi |).
Notice that wi (y1∗ ) = min(|y1∗ − xi |, |y1∗ − xi |) = |y1∗ − xi | = maxy∈[y1∗ ,y3∗ ] wi (y).
Moreover, wi (y3∗ ) = min(|y1∗ − xi |, |y3∗ − xi |). We consider two cases.
Case 3.1: |y1∗ − xi | > |y3∗ − xi |. Then wi (y3∗ ) = |y3∗ − xi | and hence wi (y2 ) =
|y2 − xi | for all y2 in [y1∗ , y3∗ ], that is, wi (y2 ) satisfies property 1.
Case 3.2: |y1∗ − xi | ≤ |y3∗ − xi |. Then wi (y3∗ ) = |y1∗ − xi | = maxy∈[y1∗ ,y3∗ ] wi (y) =
wi (y1∗ ) and hence wi (y2 ) satisfies property 2.
Case 4: ai = {F2 , F3 }. This case is symmetric to Case 3 and can be handled
similarly.
Case 5: ai = {F1 , F2 , F3 }. By definition, we have wi (y2 ) = min(|y1∗ −xi |, |y2 −
xi |, |y3∗ − xi |). Notice that wi (y1∗ ) = wi (y3∗ ) = min(|y1∗ − xi |, |y3∗ − xi |). Also
notice that for any y2 in [y1∗ , y3∗ ], wi (y2 ) = min(|y1∗ − xi |, |y2 − xi |, |y3∗ − xi |) ≤
min(|y1∗ − xi |, |y3∗ − xi |) = wi (y1∗ ). Hence property 1 holds.
This concludes our proof of Claim 1.
Claim 2: There is a solution that optimizes maxy SW(I, y) and builds facili-
ties in at most two locations.
Proof: We establish the claim by proving that either SW(I, (y1∗ , y1∗ , y3∗ )) ≥
SW(I, y∗ ) or SW(I, (y1∗ , y3∗ , y3∗ )) ≥ SW(I, y∗ ).
Claim 1 implies that the set of agents [n] can be partitioned into two sets
(S, S) such that wi (y2 ) satisfies property 1 for all P i in S, and wP i (y2 ) satisfies
property 2 for all i in S. Thus, we have SW(y2 ) = i∈[n] wi (y2 ) = i∈S wi (y2 )+
w (y ). By Lemma 3.1, there is a b in {y1∗ , y3∗ } such that i∈S wi (b) ≥
P P
Pi∈S i 2 ∗ ∗
i∈S wi (y2 ) for all y2 in [y1 , y3 ]. For any i in S, we deduce from property 2 that
wi (b) ≥ wi (y2 ) for all y2 in [y1∗ , y3∗ ]. Therefore, SW(b) ≥ SW(y2 ) for all y2 in
[y1∗ , y3∗ ]. This completes our proof of Claim 2.
Having established Claim 2, we can assume without loss of generality that
y2∗ = y3∗ . A similar argument as above can be used to prove that either (0, y2∗ , y2∗ )
or (y2∗ , y2∗ , y2∗ ) is an efficient solution. Now if (0, y2∗ , y2∗ ) is efficient, then one can
use a similar argument to prove that either (0, 0, 0) or (0, 1, 1) is efficient. And if
(y2∗ , y2∗ , y2∗ ) is efficient, then by applying Lemma 3.2 with k = 3, we deduce that
either (0, 0, 0) or (1, 1, 1) is efficient. Thus, there is a 0-1 efficient solution. The
efficiency of Mechanism 2 follows. t
u
When k = 2 (resp., 1), we can add one (resp., two) dummy facilities and
use Theorem 3.3 to establish that Mechanism 2 is efficient for k = 2 (resp., 1).
Theorem 3.4 below provides a lower bound on the approximation ratio of any
SGSP efficient mechanism; this result implies that Mechanism 2 is not SGSP.
Theorem 3.4. There is no SGSP α-efficient DOFLG mechanism with α < 5/4.
Proof. Let n be a large even integer. We construct two 3n
2 + 1 -agent single-
facility DOFLG instances (I, I) and (I, I 0 ). In both (I, I) and (I, I 0 ), agent 1 is
The Obnoxious Facility Location Game with Dichotomous Preferences 9
located at 0 and dislikes {F1 }, n/2 agents are located at 1 and dislike {F1 }, and
the remaining n agents, which we denote by the set U , are located at 0 and
dislike ∅. In I, all agents report truthfully, while in I 0 , all agents in U report
{F1 } and the remaining agents report truthfully.
Let the maximum social welfare for instances I and I 0 be OPT and OPT0 ,
respectively. It is easy to see that OPT = 3n/2 and OPT0 = n + 1 (obtained
by building F1 at 0 and 1, respectively). Let the social welfare achieved by some
SGSP DOFLG mechanism M on these instances be ALG and ALG0 , respectively.
ny
Let M build F1 at y on I. It follows that ALG = y + 3n 2 − 2 . If the agents
in U and agent 1 form a coalition in I and the agents in U report {F1 }, then the
instance becomes I 0 . Thus, as M is SGSP, M cannot build F1 to the right of y in
I 0 . Using this fact, it is easy to see that ALG0 ≤ (n+1)y + n2 (1−y) = ny n
2 + 2 +y.
3n 3n ny
Using OPT = 2 and ALG = y + 2 − 2 , we obtain
3n
2
α≥ . (1)
y + 2 − ny
3n
2
Similarly, using OPT0 = n + 1 and ALG0 ≤ ny n
2 + 2 + y, we obtain
n+1
α ≥ ny n . (2)
2 + 2 +y
Let f (y) denote
3n
2 n+1
max ,
ny ny n .
y + 3n
2 − 2 2 + 2 +y
From (1) and (2) we deduce that α ≥ f (y). Let y ∗ denote a value of y in [0, 1]
2
minimizing f (y). It is easy to verify that y ∗ satisfies f (y ∗ ) = 5n4n(n+1)
+4n−4
. Thus,
α ≥ f (y ∗ ). As n approaches infinity, f (y ∗ ) approaches 5/4. Thus, for any SGSP
α-efficient mechanism, we have α ≥ 5/4. t
u
In view of Theorem 3.4, it is natural to try to determine the minimum value
of α for which an SGSP α-efficient DOFLG mechanism exists. Below we present
a 2-efficient SGSP mechanism. It remains an interesting open problem to im-
prove the approximation ratio of 2, or to establish a tighter lower bound for the
approximation ratio.
Mechanism 3 P Let I = (n, k,
Px, a) denote the reported DOFL instance. Build all
facilities at 0 if i∈[n] xi ≥ i∈[n] (1 − xi ); otherwise, build all facilities at 1.
Theorem 3.5. Mechanism 3 is SGSP.
Proof. Reported dislikes do not affect the locations at which the facilities are
built. Hence the theorem follows. t
u
Theorem 3.6. Mechanism 3 is 2-efficient.
10 F. Li et al.
Proof. Let I = (n, k, x, a) denote the reported DOFL instance. Let ALG denote
the social welfare obtained by Mechanism 3 on this instance, and let OPT denote
the maximum possible social welfare on this instance. We need to prove that
2 · ALG ≥ OPT.
Assume without loss of generality that Mechanism 3 builds all facilities at
0. (A symmetric argument handles the case where all facilities are built at 1).
0
Then the welfare of an agent i not in indiff(I) is xi and
Pthe welfare of an agent i
in indiff(I) is max(xi0 , 1 − xi0 ) ≥ xi0 . Thus, ALG ≥ i∈[n] xi . As Mechanism 3
P P
builds the facilities at 0 and not 1, we have i∈[n] xi ≥ i∈[n] (1 − xi ), which
P
implies that i∈[n] xi ≥ n/2. Combining the above two inequalities, we have
ALG ≥ n/2. Since no agent has welfare greater than 1, we have n ≥ OPT.
Thus, 2 · ALG ≥ n ≥ OPT, as required. t
u
In our full paper, we show that the analysis of Theorem 3.6 is tight by
exhibiting a two-facility DOFL instance on which Mechanism 3 achieves only
half of the optimal social welfare. We also present variations of Mechanism 3
that are SGSP and 2-efficient when the agents are located on a cycle or square.
4 Egalitarian Mechanisms
We now design egalitarian mechanisms for DOFLG when the agents are located
on an interval, circle, or square.
In Definition 4.1 below, we introduce a simple way to convert a single-facility
DOFLG mechanism into a DOFLG mechanism. Observe that for single-facility
DOFLG mechanisms, specifying the input DOFL instance I = (n, 1, x, a) is equiv-
alent to specifying (n, 1, x, haters(I, 1)).
Definition 4.1. For any single-facility DOFLG mechanism M , Parallel(M ) de-
notes the DOFLG mechanism that takes as input a DOFL instance I = (n, k, x, a)
and outputs y = (y1 , . . . , yk ), where yj is the location at which M builds the fa-
cility on input (n, 1, x, haters(I, j)).
Lemmas 4.1 and 4.2 below reduce the task of designing a SP egalitarian
DOFLG mechanism to the single-facility case.
Lemma 4.1. Let M be a SP single-facility DOFLG mechanism. Then Parallel(M )
is a SP DOFLG mechanism.
Lemma 4.2. Let M be an egalitarian single-facility DOFLG mechanism. Then
Parallel(M ) is an egalitarian DOFLG mechanism.
4.1 Egalitarian mechanisms for the unit interval
We begin by describing a SP egalitarian mechanism for single-facility DOFLG
when the agents are located in the unit interval.
The Obnoxious Facility Location Game with Dichotomous Preferences 11
Mechanism 4 Let I = (n, 1, x, a) denote the reported DOFL instance and let
H denote haters(I, 1). If H is empty, build F1 at 0. Otherwise, let H contain `
agents z1 , . . . , z` such that xz1 ≤ xz2 ≤ · · · ≤ xz` . Let d1 = xz1 and d3 = 1 − xz` .
If ` = 1, then build F1 at 0 if d1 ≥ d3 , and at 1 otherwise. If ` > 1, let m be
the midpoint of the leftmost largest interval between consecutive agents in H.
Formally, m = (xzo + xzo+1 )/2, where o is the smallest number in [` − 1] such
that xzo+1 − xzo = maxj∈[`−1] (xzj+1 − xzj ). Let d2 = m − xzo . Then build facility
F1 at 0 if d1 ≥ d2 and d1 ≥ d3 , at m if d2 ≥ d3 , and at 1 otherwise.
The following lemma shows that Mechanism 4 is SP. It is established by
examining how the location of the facility changes when an agent lies.
Lemma 4.3. Mechanism 4 is SP for single-facility DOFLG.
Lemma 4.4. Mechanism 4 is egalitarian for single-facility DOFLG.
Proof. Let I = (n, 1, x, a) denote the reported DOFL instance and let H denote
haters(I, 1). The welfare of any agent in [n] \ H is independent of the location of
the facility. Thus, a mechanism is egalitarian if it maximizes the minimum welfare
of any agent in H. Mechanism 4 ignores the agents that are not in H. Thus it is
sufficient to show that Mechanism 4 maximizes the minimum welfare on instances
where all agents belong to H. Hence for the remainder of the proof, we assume
that all agents belong to H. Let y ∗ denote an optimal location for the facility and
let OPT denote MW(I, y ∗ ). Let y 0 denote the location where Mechanism 4 builds
the facility and let ALG denote MW(I, y 0 ). Below we establish that ALG ≥
OPT, which implies that Mechanism 4 is egalitarian.
If H is empty then trivially Mechanism 4 is egalitarian. For the remainder
of the proof, assume that H is non-empty. We say that an agent in H is tight
if it is as close to y ∗ as any other agent in H. Thus for any tight agent i,
OPT = |y ∗ − xi |. Similarly , ALG is the distance between y 0 and a closest agent
in H.
If y ∗ = 0, consider any tight agent i. Then no agent in H is located in [0, xi ).
It follows that d1 = xi = OPT. As ALG ≥ d1 , we have ALG ≥ OPT. A
symmetric argument can be made for the case y ∗ = 1.
It remains to consider the case where y ∗ does not belong to {0, 1}. As-
sume that xi < y ∗ where i is a tight agent (the other case can be handled
symmetrically). We have OPT = y ∗ − xi . Thus no agent in H is located in
(xi = y ∗ − OPT, y ∗ + OPT). We consider two cases.
Case 1: There is no agent i0 to the right of y ∗ . Thus d3 ≥ OPT. Since
ALG ≥ d3 , we have ALG ≥ OPT.
Case 2: There is an agent in H to the right of y ∗ . Consider the leftmost such
agent i0 . Since xi0 ≥ y ∗ + OPT, we have d2 ≥ OPT. Since ALG ≥ d2 , we have
ALG ≥ OPT. t
u
We define Mechanism 5 as the DOFLG mechanism Parallel(M ), where M
denotes Mechanism 4. Using Lemmas 4.1 through 4.4, we immediately obtain
Theorem 4.1 below.
12 F. Li et al.
Theorem 4.1. Mechanism 5 is SP and egalitarian.
Below we provide a lower bound on the approximation ratio of any WGSP
egalitarian mechanism. Theorem 4.2 implies that Mechanism 5 is not WGSP.
√
Theorem 4.2. Let M be a WGSP α-egalitarian mechanism. Then α is Ω( n),
where n is the number of agents.
Proof. Let q be a large even integer, let p denote q 2 + 1, and let U (resp., V )
denote the set of all integers i such that 0 < i < q 2 /2 (resp., q 2 /2 < i < q 2 ). We
construct two (p + 3)-agent two-facility DOFLG instances (I, I) and (I, I 0 ). In
both (I, I) and (I, I 0 ), there is an agent located at i/q 2 , called agent i, for each i
in U ∪ V , and there are two agents each at 0, 1/2, and 1. In I, each agent i such
that i is in U dislikes {F2 }, each agent i such that i is in V dislikes {F1 }, one
agent at 0 (resp., 1/2, 1) dislikes {F1 }, and the other agent at 0 (resp., 1/2, 1)
dislikes {F2 }. In I 0 , agents i such that i is in U \ {1, . . . , q − 1}, have alternating
reports: agent q reports {F1 }, agent q + 1 reports {F2 }, agent q + 2 reports {F1 },
and so on. Symmetrically, the agents i such that i is in V \{q 2 −q +1, . . . , q 2 −1},
have alternating reports: agent q 2 −q reports {F2 }, agent q 2 −q −1 reports {F1 },
agent q 2 − q − 2 reports {F2 }, and so on. All other agents in I 0 report truthfully.
Let the optimal minimum welfare for DOFL instance I (resp., I 0 ) be OPT
(resp., OPT0 ). It is easy to see that OPT = 1/4 and OPT0 = 2q 1
(obtained
1 1
by building the facilities at (1/4, 3/4) and ( 2q , 1 − 2q ), respectively). Let ALG
(resp., ALG0 ) denote the minimum welfare achieved by M on instance I (resp.,
I 0 ). Below we prove that either OPT/ALG ≥ 4q or OPT0 /ALG0 ≥ q/2.
Let M build facilities at (y1 , y2 ) (resp., (y10 , y20 )) on instance I (resp., I 0 ). We
consider two cases.
Case 1: 0 ≤ y10 < 1/q and 1 − 1/q < y20 ≤ 1. Let S denote the set of agents
who lie in I 0 . If y10 < y1 and y20 > y2 , then all agents in S benefit by lying. Hence
for M to be WGSP, either y10 ≥ y1 or y20 ≤ y2 . Let us assume that y10 ≥ y1 ;
the other case can be handled symmetrically. Since y10 < 1/q, we have y1 < 1/q.
Note that there is an agent at 0 who reported {F1 }. Thus ALG ≤ y1 < 1/q.
Hence OPT/ALG ≥ 4q .
Case 2: y10 ≥ 1/q or y20 ≤ 1 − 1/q. If y10 ≥ 1/q, then at least one agent within
distance 1/q 2 of y10 reported {F1 } in I 0 . A similar observation holds for the case
y20 ≤ 1 − 1/q. Thus ALG0 ≤ 1/q 2 . Hence OPT0 /ALG0 ≥ q/2. √
√
The preceding case analysis shows that α ≥ q/4. Since q = p − 1 = n − 4,
the theorem holds. t
u
The following variant of Mechanism 5 is SGSP. In this variant, we first replace
the reported dislikes of all agents with {F1 } and use Mechanism 4 to determine
where to build F1 . Then we build all of the remaining facilities at the same loca-
tion as F1 . This mechanism is SGSP because it disregards the reported aversion
profile. We claim that this mechanism is 2(n+1)-egalitarian, where n denotes the
number of agents. To prove this claim, we first observe that when Mechanism 4 is
run as a subroutine within this mechanism, we have max(d1 , 2d2 , d3 ) ≥ 1/(n+1).
The Obnoxious Facility Location Game with Dichotomous Preferences 13
Thus the minimum welfare achieved by the mechanism is at least 1/(2(n + 1)).
Since the optimal minimum welfare is at most 1, the claim holds.
In our full paper, we extend some of the previous results to the case where
the agents are located on a cycle: we show how to modify Mechanism 5 to obtain
a SP egalitarian mechanism for the cycle; we prove that the approximation ratio
lower bound for WGSP mechanisms given in Theorem 4.2 also holds for the
cycle; we show that the SGSP mechanism presented in the previous paragraph
can be adapted to obtain a n-egalitarian mechanism for the cycle.
4.2 An egalitarian mechanism for the unit square
We extend Mechanism 4 to a SP egalitarian mechanism for single-facility DOFLG
when the agents are located in the unit square. Let S denote [0, 1]2 , let B denote
the boundary of S, and let xi = (ai , bi ) denote the location of agent i. For
convenience, we assume that all agents are located at distinct points; the results
below generalize easily to the case where this assumption does not hold.
Mechanism 6. Let I = (n, 1, x, a) denote the reported DOFL instance and let
H denote haters(I, 1). If H is empty, build F1 at (0, 0). Otherwise, construct the
Voronoi diagram D associated with the locations of the agents in H. Let V be
the union of the following three sets of vertices: the vertices of D in the interior
of S; the points of intersection between B and D; the four vertices of S. For each
v in V , let dv denote the minimum distance from v to any agent in H. Build
F1 at a vertex v maximizing dv , breaking ties first by x-coordinate and then by
y-coordinate.
Toussaint presents an efficient O(n log n) algorithm to find the optimal v in
Mechanism 6 [23]. The following lemma establishes that Mechanism 6 is egali-
tarian. The lemma is shown using Theorem 2 of [23] for the largest empty circle
with location constraints problem.
Lemma 4.5. Mechanism 6 is egalitarian for single-facility DOFLG.
In our full paper, we use a case analysis to establish Lemma 4.6 below. The
most interesting case deals with an agent i who dislikes F1 but does not report
it. In this case, the key insight is that when agent i misreports, facility F1 is
built either (1) at the same location as when agent i reports truthfully, or (2)
inside or on the boundary of the Voronoi region that contains xi when agent i
reports truthfully.
Lemma 4.6. Mechanism 6 is SP for single-facility DOFLG.
We define Mechanism 7 as the DOFLG mechanism Parallel(M ), where M
denotes Mechanism 6. Using Lemmas 4.1, 4.2, 4.5, and 4.6, we immediately
obtain Theorem 4.3 below.
Theorem 4.3. Mechanism 7 is SP and egalitarian.
14 F. Li et al.
5 Concluding Remarks
In this paper, we studied the obnoxious facility location game with dichotomous
preferences. This game generalizes obnoxious facility location game to more real-
istic scenarios. All of the mechanisms presented in this paper run in polynomial
time, except that the running time of Mechanism 2 has exponential dependence
on k (and polynomial dependence on n). We can extend the results of Section 4.2
to obtain an analogue of Theorem 4.3 that holds for arbitrary convex polygon.
We showed that Mechanism 2 is WGSP for all k and is efficient for k ≤ 3. Prop-
erties 1 and 2 in the proof of our associated theorem, Theorem 3.3, do not hold
for k > 3. Nevertheless, we conjecture that Mechanism 2 is efficient for√all k. It
remains an interesting open problem to reduce the gap between the Ω( n) and
O(n) bounds on the approximation ratio α of WGSP α-egalitarian mechanisms.
References
1. Alon, N., Feldman, M., Procaccia, A.D., Tennenholtz, M.: Strategyproof approxi-
mation of the minimax on networks. Mathematics of Operations Research 35(3),
513–526 (2010)
2. Anastasiadis, E., Deligkas, A.: Heterogeneous facility location games. In: Proceed-
ings of the 17th International Conference on Autonomous Agents and Multiagent
Systems. pp. 623–631 (2018)
3. Brams, S.J., Fishburn, P.C.: Approval voting. The American Political Science Re-
view 72(3), 831–847 (1978)
4. Chen, Z., Fong, K.C.K., Li, M., Wang, K., Yuan, H., Zhang, Y.: Facility location
games with optional preference. Theoretical Computer Science 847, 185–197 (2020)
5. Cheng, Y., Han, Q., Yu, W., Zhang, G.: Obnoxious facility game with a bounded
service range. In: Proceedings of the 10th Annual Conference on Theory and Ap-
plications of Models of Computation. pp. 272–281 (2013)
6. Cheng, Y., Yu, W., Zhang, G.: Mechanisms for obnoxious facility game on a path.
In: Proceedings of the 5th International Conference on Combinatorial Optimization
and Applications. pp. 262–271 (2011)
7. Cheng, Y., Yu, W., Zhang, G.: Strategy-proof approximation mechanisms for an
obnoxious facility game on networks. Theoretical Computer Science 497, 154–163
(2013)
8. Dokow, E., Feldman, M., Meir, R., Nehama, I.: Mechanism design on discrete lines
and cycles. In: Proceedings of the 13th ACM Conference on Electronic Commerce.
pp. 423–440 (2012)
9. Duan, L., Li, B., Li, M., Xu, X.: Heterogeneous two-facility location games with
minimum distance requirement. In: Proceedings of the 18th International Confer-
ence on Autonomous Agents and Multiagent Systems. pp. 1461–1469 (2019)
10. Feigenbaum, I., Sethuraman, J.: Strategyproof mechanisms for one-dimensional
hybrid and obnoxious facility location models. In: Incentive and Trust in E-
Communities (AAAI Workshop). vol. WS-15-08 (2015)
11. Feldman, M., Wilf, Y.: Strategyproof facility location and the least squares objec-
tive. In: Proceedings of the 14th ACM Conference on Electronic Commerce. pp.
873–890 (2013)
The Obnoxious Facility Location Game with Dichotomous Preferences 15
12. Filos-Ratsikas, A., Li, M., Zhang, J., Zhang, Q.: Facility location with double-
peaked preferences. Autonomous Agents and Multi-Agent Systems 31(6), 1209–
1235 (2017)
13. Fotakis, D., Tzamos, C.: Winner-imposing strategyproof mechanisms for multi-
ple facility location games. In: Proceedings of the 6th International Workshop on
Internet and Network Economics. pp. 234–245 (2010)
14. Fotakis, D., Tzamos, C.: Strategyproof facility location with concave costs. SIGe-
com Exchanges 12(2), 46–49 (2014)
15. Fukui, Y., Shurbevski, A., Nagamochi, H.: λ-group strategy-proof mechanisms for
the obnoxious facility game in star networks. IEICE Transactions on Fundamen-
tals of Electronics, Communications and Computer Sciences E102.A, 1179–1186
(2019)
16. Han, Q., Du, D.: Moneyless strategy-proof mechanism on single-sinked policy do-
main: characterization and applications. Manuscript (2012)
17. Ibara, K., Nagamochi, H.: Characterizing mechanisms in obnoxious facility game.
In: Proceedings of the 6th International Conference Combinatorial Optimization
and Applications. pp. 301–311 (2012)
18. Li, M., Lu, P., Yao, Y., Zhang, J.: Strategyproof mechanism for two heterogeneous
facilities with constant approximation ratio. In: Proceedings of the 29th Interna-
tional Joint Conference on Artificial Intelligence. pp. 238–245 (2020)
19. Lu, P., Sun, X., Wang, Y., Zhu, Z.A.: Asymptotically optimal strategy-proof mech-
anisms for two-facility games. In: Proceedings of the 11th ACM Conference on
Electronic Commerce. pp. 315–324 (2010)
20. Oomine, M., Shurbevski, A., Nagamochi, H.: Parameterization of strategy-proof
mechanisms in the obnoxious facility game. In: Proceedings of the 10th Interna-
tional Workshop on Algorithms and Computation. pp. 286–297 (2016)
21. Procaccia, A.D., Tennenholtz, M.: Approximate mechanism design without money.
In: Proceedings of the 10th ACM Conference on Electronic Commerce. pp. 177–186
(2009)
22. Serafino, P., Ventre, C.: Heterogeneous facility location without money. Theoretical
Computer Science 636, 27–46 (2016)
23. Toussaint, G.T.: Computing largest empty circles with location constraints. Inter-
national Journal of Computer and Information Sciences 12(5), 347–358 (1983)
24. Vorsatz, M., Massó, J.: Weighted approval voting. Economic Theory 36(1), 129–
146 (2008)
25. Ye, D., Mei, L., Zhang, Y.: Strategy-proof mechanism for obnoxious facility location
on a line. In: Proceedings of the 21st International Conference on Computing and
Combinatorics. pp. 45–56 (2015)
26. Yuan, H., Wang, K., Fong, K.C.K., Zhang, Y., Li, M.: Facility location games with
optional preference. In: Proceedings of the 22nd European Conference on Artificial
Intelligence. pp. 1520–1527 (2016)
27. Zhang, Q., Li, M.: Strategyproof mechanism design for facility location games with
weighted agents on a line. Journal of Combinatorial Optimization 28, 756–773
(2014)
28. Zou, S., Li, M.: Facility location games with dual preference. In: Proceedings of
the 14th International Conference on Autonomous Agents and Multiagent Systems.
pp. 615–623 (2015)