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)