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 a ected by some subset of the facilities, and is una ected 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 welfare (i.e., to be e cient), and egalitarian mechanisms that strive to maximize the minimum welfare. For the utilitarian objective, we present a weakly group-strategyproof e cient 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(pn) approximation ratio for two facilities. We extend our egalitarian results to the case where the agents are located on a cycle, and we extend our rst egalitarian result to the case where the agents are located in the unit square.
The facility location game (FLG) was introduced by Procaccia and Tannenholtz
[
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).
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 [
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 tra c, 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 indi erent 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 welfare, 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 e cient. 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
We study DOFLG with n agents. In Section 3, we consider the utilitarian objective. 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 rst main result of the paper, we obtain a mechanism that is WGSP for any number of facilities and e cient for up to three facilities. To show that this mechanism is WGSP, we relate it to a weighted approval voting mechanism. To prove its e ciency, we identify two crucial properties that the welfare function satis es, 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.
In Section 4, we consider the egalitarian objective. We provide SP
mechanisms 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 (pn), 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.
FLG was introduced by Procaccia and Tannenholtz [
Agent preferences over the facilities were introduced to FLG in [
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 of generality that the path (resp., cycle, square) is the unit interval (resp., unitcircumference 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 de ned as the Euclidean distance between x and y. In the cycle setting, d(x; y), is de ned as the length of the shorter arc between x and y. In all settings, we index the agents from 1. Each agent has a speci c location in the path, cycle, or square. A location pro le 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 indi erent to the rest. In this context, we de ne an aversion pro le a as a vector (a1; : : : ; an) where each component ai is a subset of F . We say that such an aversion pro le 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 pro les where each component ai is equal to the set of facilities that agent i claims to dislike. Since agents can lie, a reported aversion pro le need not be true. For any aversion pro le a and any subset C of agents [n], aC (resp., a C ) denotes the aversion pro le for the agents in (resp., not in) C. For a singleton set of agents fig, we abbreviate a fig 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 = fF1; : : : ; Fkg to be built, x = (x1; : : : ; xn) is a location pro le for the agents, and a = (a1; : : : ; an) is an aversion pro le (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 speci es the point at which to build Fj . We say that a DOFL instance is true (resp., reported) if the associated aversion pro le is true (resp., reported). For any DOFL instance I = (n; k; x; a) and any j in [k], we de ne haters(I; j) as fi 2 [n] j Fj 2 aig, and indi (I) as fi 2 [n] j ai = ;g.
For any DOFL instance I = (n; k; x; a) and any associated solution y, we de ne the welfare of agent i, denoted w(I; i; y), as minj:Fj2ai d(xi; yj ), i.e., the minimum distance from xi to any facility in ai. Remark: If ai is empty, we de ne 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 de nition of agent welfare is suitable for true DOFL instances, and is only meaningful for reported DOFL instances where the associated aversion pro le is close to true. In this paper, reported aversion pro les arise in the context of mechanisms that incentivize truthful reporting, so it is reasonable to expect such aversion pro les to be close to true. We de ne the social welfare (resp., minimum welfare) as the sum (resp., minimum) of the individual agent welfares. When the facilities are built at y, the social welfare and minimum welfare are denoted by SW(I; y) and MW(I; y), respectively. Thus SW(I; y) = Pi2[n] w(I; i; y) and MW(I; y) = mini2[n] w(I; i; y).
instance I,
max SW(I; y) y
SW(I; A(I)): max MW(I; y) y
MW(I; A(I)): A 1-e cient (resp., 1-egalitarian) DOFL algorithm, is said to be e cient (resp., egalitarian).
We are now ready to de ne a DOFL-related game, which we call DOFLG. It is convenient to describe a DOFLG instance in terms of a pair (I; I0) of DOFL instances where I = (n; k; x; a) is true and I0 = (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 = fF1; : : : ; Fkg to be built. The numbers n and k are publicly known, as is the location pro le x of the agents. Each component ai of the true aversion pro le a is known only to agent i. Each agent i submits component a0i of the reported aversion pro le a0 to the planner. The planner, who does not have access to a, runs a DOFL algorithm, call it A, to map I0 to a solution. The inputoutput behavior of A de nes 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 -e cient (resp., -egalitarian, e cient, egalitarian) if A is -e cient (resp., -egalitarian, e cient, egalitarian). As indicated earlier, such properties (which depend on the notion of agent welfare) are only meaningful if the reported aversion pro le is close to true. To encourage truthful reporting, we require our mechanisms to be SP, as de ned 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.
(I; I0) with I = (n; k; x; a), and I0 = (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 (I0)):
The WGSP property says that if a non-empty coalition C lies, then at least one agent in C does not increase their welfare. [n] of agents
(I; I0) with I = (n; k; x; a), and I0 = (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 (I0)):
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.
(I; I0) with I = (n; k; x; a), and I0 = (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 then there exists an agent i0 in C such that w(I; i; M (I)) < w(I; i; M (I0)); w(I; i0; M (I)) > w(I; i0; M (I0)):
Every SGSP mechanism is WGSP and every WGSP mechanism is SP. 3
E
cient Mechanisms
Before studying e cient mechanisms for our problem, we review a variant of
the approval voting mechanism [
Like approval voting, weighted approval voting is WGSP.
We now present our e cient mechanism for DOFLG.
Mechanism 2 For a given reported DOFL instance I = (n; k; x; a), output the lexicographically least solution y in f0; 1gk that maximizes the social welfare SW(I; y).
1 Our mechanism di ers from the homonymous mechanism of Masso et al., which has
weights for the candidates instead of the voters [
Let (I; I0) denote a DOFLG instance where I = (n; k; x; a) and I0 = (n; k; x; a0). We view each agent i 2 [n] as a voter, and each y in f0; 1gk as a candidate. We obtain the top-tier candidates Ci of voter i, and their reported top-tier candidates Ci0, from ai and a0i, respectively. Assume without loss of generality that xi 1=2 (the other case can be handled similarly). Set Ci = fy = (y1; : : : ; yk) 2 f0; 1gk j yj = 1 for all Fj 2 aig and similarly Ci0 = fy = (y1; : : : ; yk) 2 f0; 1gk j yj = 1 for all Fj 2 a0ig. Also set wi+ = 1 xi and wi = xi. With this notation, it is easy to see that A(y) = SW(I0; 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. tu
We show that Mechanism 2 is e cient 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 zis is maximized.
interval, let z1; : : : ; zn belong to [a; b], and let f (z) denote Pi2[n] jz zij. Then maxz2[a;b] f (z) belongs to ff (a); f (b)g.
Before proving the main theorem, we establish Lemma 3.2, which follows from Lemma 3.1.
in [0; 1] such that it is e cient to build all k facilities at y, and assume that Y is non-empty. Then Y \ f0; 1g is non-empty.
Theorem 3.3. Mechanism 2 is e cient for k = 3.
Proof. Let I = (n; k; x; a) be a DOFL instance and let y = (y1 ; y2 ; y3 ) be an e cient solution for I such that y1 y2 y3 .
Consider xing variables y1 and y3 in the social welfare function SW(I; y). That is, we have
SW(I; y)jy1=y1 ;y3=y3 =
w(I; i; y)jy1=y1 ;y3=y3 : X i2[n] For convenience, let SW(y2) denote SW(I; y)jy1=y1 ;y3=y3 and let wi(y2) denote w(I; i; y)jy1=y1 ;y3=y3 for each agent i.
Claim 1: For each agent i, the welfare function wi(y2) with y2 2 [y1 ; y3 ] satis es at least one of the following two properties: 1. wi(y2) = jy2 xij; 2. wi(y1 ) = wi(y3 ) = maxy2[y1 ;y3 ] wi(y).
Proof: Consider an agent i. We consider ve cases.
Case 1: F2 2= ai. Since the welfare of agent i is independent of the location of F2, wi is a constant function. Hence property 2 is satis ed.
Case 2: ai = fF2g. By de nition, we have wi(y2) = jy2 xij. Hence property 1 is satis ed.
Case 3: ai = fF1; F2g. By de nition, we have wi(y2) = min(jy1 xij; jy2 xij). Notice that wi(y1 ) = min(jy1 xij; jy1 xij) = jy1 xij = maxy2[y1 ;y3 ] wi(y). Moreover, wi(y3 ) = min(jy1 xij; jy3 xij). We consider two cases.
Case 3.1: jy1 xij > jy3 xij. Then wi(y3 ) = jy3 xij and hence wi(y2) = jy2 xij for all y2 in [y1 ; y3 ], that is, wi(y2) satis es property 1.
Case 3.2: jy1 xij jy3 xij. Then wi(y3 ) = jy1 xij = maxy2[y1 ;y3 ] wi(y) = wi(y1 ) and hence wi(y2) satis es property 2.
Case 4: ai = fF2; F3g. This case is symmetric to Case 3 and can be handled similarly.
Case 5: ai = fF1; F2; F3g. By de nition, we have wi(y2) = min(jy1 xij; jy2 xij; jy3 xij). Notice that wi(y1 ) = wi(y3 ) = min(jy1 xij; jy3 xij). Also notice that for any y2 in [y1 ; y3 ], wi(y2) = min(jy1 xij; jy2 xij; jy3 xij) min(jy1 xij; jy3 xij) = 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 facilities 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) satis es property 1 for all i in S, and wi(y2) satis es property 2 for all i in S. Thus, we have SW(y2) = Pi2[n] wi(y2) = P Pi2S wi(y2). By Lemma 3.1, there is a b in fy1 ; y3 g such that Pi2S wi(y2)+ P i2S wi(b) i2S 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 e cient solution. Now if (0; y2 ; y2 ) is e cient, then one can use a similar argument to prove that either (0; 0; 0) or (0; 1; 1) is e cient. And if (y2 ; y2 ; y2 ) is e cient, then by applying Lemma 3.2 with k = 3, we deduce that either (0; 0; 0) or (1; 1; 1) is e cient. Thus, there is a 0-1 e cient solution. The e ciency of Mechanism 2 follows. tu
When k = 2 (resp., 1), we can add one (resp., two) dummy facilities and use Theorem 3.3 to establish that Mechanism 2 is e cient for k = 2 (resp., 1). Theorem 3.4 below provides a lower bound on the approximation ratio of any SGSP e cient mechanism; this result implies that Mechanism 2 is not SGSP.
< 5=4.
Proof. Let n be a large even integer. We construct two 32n + 1 -agent singlefacility DOFLG instances (I; I) and (I; I0). In both (I; I) and (I; I0), agent 1 is located at 0 and dislikes fF1g, n=2 agents are located at 1 and dislike fF1g, 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 I0, all agents in U report fF1g and the remaining agents report truthfully.
Let the maximum social welfare for instances I and I0 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.
Let M build F1 at y on I. It follows that ALG = y + 32n n2y . If the agents in U and agent 1 form a coalition in I and the agents in U report fF1g, then the instance becomes I0. Thus, as M is SGSP, M cannot build F1 to the right of y in I0. Using this fact, it is easy to see that ALG0 (n + 1)y + n2 (1 y) = n2y + n2 + y.
Using OPT = 32n and ALG = y + 32n n2y , we obtain Let f (y) denote max From (1) and (2) we deduce that f (y). Let y denote a value of y in [0; 1] minimizing f (y). It is easy to verify that y satis es f (y ) = 54nn2+(n4+n1)4 . Thus, f (y ). As n approaches in nity, f (y ) approaches 5=4. Thus, for any SGSP -e cient mechanism, we have 5=4.
In view of Theorem 3.4, it is natural to try to determine the minimum value of for which an SGSP -e cient DOFLG mechanism exists. Below we present a 2-e cient SGSP mechanism. It remains an interesting open problem to improve the approximation ratio of 2, or to establish a tighter lower bound for the approximation ratio.
Mechanism 3 Let I = (n; k; x; a) denote the reported DOFL instance. Build all facilities at 0 if Pi2[n] xi Pi2[n](1 xi); otherwise, build all facilities at 1.
Proof. Reported dislikes do not a ect the locations at which the facilities are built. Hence the theorem follows.
(1) (2) tu tu
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). Then the welfare of an agent i not in indi (I) is xi and the welfare of an agent i0 in indi (I) is max(xi0 ; 1 xi0 ) xi0 . Thus, ALG Pi2[n] xi. As Mechanism 3 builds the facilities at 0 and not 1, we have Pi2[n] xi Pi2[n](1 xi), which implies that Pi2[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. tu
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-e cient when the agents are located on a cycle or square. 4
We now design egalitarian mechanisms for DOFLG when the agents are located on an interval, circle, or square.
In De nition 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 equivalent to specifying (n; 1; x; haters(I; 1)).
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 facility 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.
4.1
We begin by describing a SP egalitarian mechanism for single-facility DOFLG when the agents are located in the unit interval. 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 = maxj2[` 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.
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] 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 su cient 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 y0 denote the location where Mechanism 4 builds the facility and let ALG denote MW(I; y0). 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 = jy xij. Similarly , ALG is the distance between y0 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 f0; 1g. Assume 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.
We de ne 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.
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. is (pn),
Proof. Let q be a large even integer, let p denote q2 + 1, and let U (resp., V ) denote the set of all integers i such that 0 < i < q2=2 (resp., q2=2 < i < q2). We construct two (p + 3)-agent two-facility DOFLG instances (I; I) and (I; I0). In both (I; I) and (I; I0), there is an agent located at i=q2, 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 fF2g, each agent i such that i is in V dislikes fF1g, one agent at 0 (resp., 1=2, 1) dislikes fF1g, and the other agent at 0 (resp., 1=2, 1) dislikes fF2g. In I0, agents i such that i is in U n f1; : : : ; q 1g, have alternating reports: agent q reports fF1g, agent q + 1 reports fF2g, agent q + 2 reports fF1g, and so on. Symmetrically, the agents i such that i is in V nfq2 q +1; : : : ; q2 1g, have alternating reports: agent q2 q reports fF2g, agent q2 q 1 reports fF1g, agent q2 q 2 reports fF2g, and so on. All other agents in I0 report truthfully.
Let the optimal minimum welfare for DOFL instance I (resp., I0) be OPT (resp., OPT0). It is easy to see that OPT = 1=4 and OPT0 = 21q (obtained by building the facilities at (1=4; 3=4) and ( 21q ; 1 21q ), respectively). Let ALG (resp., ALG0) denote the minimum welfare achieved by M on instance I (resp., I0). 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., I0). 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 I0. If y10 < y1 and y20 > y2, then all agents in S bene t 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 fF1g. 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=q2 of y10 reported fF1g in I0. A similar observation holds for the case y20 1 1=q. Thus ALG0 1=q2. Hence OPT0=ALG0 q=2.
The preceding case analysis shows that q=4. Since q = pp 1 = pn 4, the theorem holds. tu
The following variant of Mechanism 5 is SGSP. In this variant, we rst replace the reported dislikes of all agents with fF1g and use Mechanism 4 to determine where to build F1. Then we build all of the remaining facilities at the same location as F1. This mechanism is SGSP because it disregards the reported aversion pro le. We claim that this mechanism is 2(n+1)-egalitarian, where n denotes the number of agents. To prove this claim, we rst observe that when Mechanism 4 is run as a subroutine within this mechanism, we have max(d1; 2d2; d3) 1=(n+1). 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
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
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 rst by x-coordinate and then by y-coordinate.
Toussaint presents an e cient O(n log n) algorithm to nd the optimal v in
Mechanism 6 [
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.
We de ne 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.
In this paper, we studied the obnoxious facility location game with dichotomous preferences. This game generalizes obnoxious facility location game to more realistic 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 e cient for k 3. Properties 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 e cient for all k. It remains an interesting open problem to reduce the gap between the (pn) and O(n) bounds on the approximation ratio of WGSP -egalitarian mechanisms.