# facility_location_games_with_fractional_preferences__0180d6a1.pdf

Facility Location Games with Fractional Preferences

Ken C.K. Fong, Minming Li, Pinyan Lu, Taiki Todo, Makoto Yokoo a a b c c

a Department of Computer Science, City University of Hong Kong, Hong Kong. b Shanghai University of Finance and Economics, Shanghai, China. c Department of Informatics, Kyushu University, Motooka 744, Fukuoka, Japan.

In this paper, we propose a fractional preference model for the facility location game with two facilities that serve the similar purpose on a line where each agent has his location information as well as fractional preference to indicate how well they prefer the facilities. The preference for each facility is in the range of [0, L] such that the sum of the preference for all facilities is equal to 1. The utility is measured by subtracting the sum of the cost of both facilities from the total length L where the cost of facilities is defined as the multiplication of the fractional preference and the distance between the agent and the facilities. We first show that the lower bound for the objective of minimizing total cost is at least Ω(n 1 3 ). Hence, we use the utility function to analyze the agents satification. Our objective is to place two facilities on [0, L] to maximize the social utility or the minimum utility. For each objective function, we propose deterministic strategy-proof mechanisms. For the objective of maximizing the social utility, we present an optimal deterministic strategy-proof mechanism in the case where agents can only misreport their locations. In the case where agents can only misreport their preferences, we present a 2approximation deterministic strategy-proof mechanism. Finally, we present a 4-approximation deterministic strategyproof mechanism and a randomized strategy-proof mechanism with an approximation ratio of 2 where agents can misreport both the preference and location information. Moreover, we also give a lower-bound of 1.06. For the objective of maximizing the minimum utility, we give a lower-bound of 1.5 and present a 2-approximation deterministic strategyproof mechanism where agents can misreport both the preference and location.

1 Introduction In recent years, designing mechanisms to achieve desirable properties under various constraints is a key research topic in the literature of mechanism design and social choice theory. AI researchers and computer scientists are interested in designing mechanisms for various mechanism design problems such as voting, auctions and matching. The facility location game is known as a special case of voting1, where the location and preference information of

Copyright c 2018, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. 1It is generally true that the facility loation is known as a special

agents are restricted so that well-known impossibility results do not hold. For example, in the traditional model of locating one facility on a continuous line, there exists a class of strategyproof and anonymous mechanisms called generalized median voter schemes (Moulin 1980), while in general voting situations any strategy-proof mechanism must be dictatorial, under some natural assumptions, by the Gibbard Satterthwaite theorem (Gibbard 1973; Satterthwaite 1975). By changing agents preferences on facilities as well as the nature of facilities, the traditional facility location game is extended to two facility location games, where researchers have studied heterogeneous facilities or homogeneous facilities on a line. To the best of our knowledge, there does not exist any studies of facility location games between heterogeneous and homogeneous versions. However, in reality there are indeed facilities which are different but serving a similar purpose, such as the supermarket along with the convenience store, the hospital along with the clinic, etc. In order to capture this scenario, we introduce the fractional preference model in this paper. Besides only zero and one on agents preferences, the fractional preference model allows agents to report a fractional preference on both facilities to indicate how often they require for both facilities. The fractional preference model complements the study on two facility location games. We further formulate the fractional preference model into three cases.

Case 1: the preference information is public whereas the location information is private. A university town is a community that the population is dominated by university students. Within the university town, it contains various facilities to support the daily lives of university students. We can find those famous university towns in Europe like Oxford in UK, Heidelberg in Germany, Salamanca in Spain, etc. Suppose the university plans to build one data-science laboratory and one multimedia laboratory in the university town. Students have

case of voting, but voting is usually assumed to be over a finite set of alternatives whereas in facility location, that set in infinite. The work described in this paper was supported by a grant from Research Grants Council of the Hong Kong Special Administrative Region, China (Project No. City U 11268616) and JSPS KAKENHI (Grant No. JP17H00761).

The Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18)

different preferences on both laboratories based on their course registration records. For example, if one student is enrolled in the course of data-science but not enrolled in the multimedia course such as computer graphics, then he may prefer 100% on the data-science laboratory and 0% on the multimedia laboratory. However, some students may be enrolled in the course of data-science as well as computer graphics, then he may need to visit the datascience laboratory for half of the week and the multimedia laboratory for the remaining half of the week. Therefore, he may prefer 50% on the data-science laboratory and 50% on the multimedia laboratory. Since the course registration records for each student are known by the university, the preference information is public. However, it is not necessary for students to report their living addresses to the university. Therefore the location information is private. Case 2: the location information is public whereas the preference information is private. Suppose the government wants to build one hospital and one clinic in a city. As the government maintains the addresses of all citizens, the location information of the patients is public. Patients may not always go to the hospital or clinic. It is based on the the severity of the illness. If one patient only catches a cold, clinic is good enough for him. Therefore he may prefer 100% on the clinic and 0% on the hospital. However, if the severity of illness is higher, for example if they need to visit the doctor in the hospital twice a week, and visit the clinic once a week, then they may prefer 67% on the hospital and 33% on the clinic. Due to the privacy and the patient protection concerns, the government does not know the severity of illness of patients. Therefore, the preference information is private. Case 3: both the location and preference information are private. One scenario is building two bus stops, with different bus lines on it. The preference on bus stops depends on the bus lines agents require for transportation. For example, if one agent only requires the bus lines on bus stop A, he may prefer 100% on bus stop A and 0% on bus stop B. If he needs the bus at bus stop A to go to work in weekdays, and requires the bus lines at bus stop B for leisure activity in the weekends/holidays, then he may prefer 70% on bus stop A, and 30% on bus stop B.

Related Work. The classicial facility location game was first studied by (Moulin 1980). They characterized strategyproof, Pareto efficient, and anonymous facility location mechanisms on a line. (Miyagawa 2001; Heo 2013; Fotakis and Tzamos 2014) extended this model for locating two facilities on a line. (Schummer and Vohra 2002) studied the characterizations of all the strategy-proof mechanisms on other networks. In addition, (Todo et al. 2011) also extended the original model by fully characterizing the deterministic false-nameproof facility location mechanisms for locating single facility on a line. Then, (Sonoda et al. 2016) extended the model by characterizing the possible outcomes of false-name-proof

mechanisms on a line for locating two facilities on a line as well as on a circle. Besides characterization of facility location games, researchers are also interested in analyzing the approximation ratios of strategy-proof mechanisms in facility location games. This problem was first studied by (Procaccia and Tennenholtz 2013). They also extended the facility location game to the scenario with two homogeneous facilities or with one agent possessing multiple locations. Lu et al. (Lu et al. 2009) improved the bounds for both the two homogeneous facilities scenario and one agent possessing multiple locations case. Fotakis and Tzamos (Fotakis and Tzamos 2014) explored the facility location game with k facilities and showed that the strategy-proofness can be achieved by adding winner-imposing constraints. Filos-Ratsikas et al. (Filos-Ratsikas et al. 2015) extended the single-peaked preference to the double-peaked preference where every agent has two ideal places for the facility on his two sides. Serafino and Ventre (Serafino and Ventre 2014; 2015) initiated the study on two heterogeneous facility location games where the cost of the agent is the summation of the distances to both facilities. Yuan et. al. (Yuan et al. 2016) extended the study on two heterogeneous facility location games by proposing the optional preference model. Other extensions of the classic facility location game can be found at (Alon et al. 2010; Dokow et al. 2012; Feldman and Wilf 2013; Fotakis and Tzamos 2014; Escoffier et al. 2011; Zhang and Li 2014). On the other hand, Cheng et al. (Cheng et al. 2011) introduced obnoxious facility games where the facility to be built is undesirable and all agents would like to get away from it. After that, they extend the model into trees and circles (Cheng et al. 2013). Ye et al. (Ye et al. 2015) considered the same model with the objective of maximizing the sum of squares of distances and the sum of distances, gave lower bounds and proposed both deterministic and randomized strategy-proof mechanisms. Another variant of the model is introduced by combining the classical facility location game and the obnoxious facility location game, named as dual preference model or hybrid model which was independently studied in (Zou and Li 2015; Feigenbaum and Sethuraman 2014). In that model, some agents would like to stay close to the facility while other agents want to stay far away from the facility.

Our contributions. We first show that the lower bound for the objective of minimizing total cost is at least Ω(n 1 3 ). Then we present our results for maximizing the social utility and maximizing the minimum utility as follows.

Results for maximizing the social utility: When we restrict the power of misreport to location only, we present an optimal deterministic strategyproof mechanism. When we restrict the power of misreport to preference only, we present a deterministic strategy-proof mechanism with an approximation ratio of 2 and also a lower bound of 1.06 for any deterministic strategyproof mechanism.

When we do not restrict the power of misreport: A 4-approximation deterministic strategy-proof mechanism. The lower bound of 1.06 carries over to this case. A 2-approximation randomized strategy-proof mechanism. A lower bound of 1.06 for any randomized strategyproof mechanism.

Results for maximizing the minimum utility:

We present a 2-approximation deterministic strategyproof mechanism. We give a lower bound of 1.5 for any deterministic strategy-proof mechanism.

The remainder of the paper is organized as follows. We first define the formulation of the problem in Section 2. Then, we study the case for the objective of maximizing the social utility and maximizing the minimum utility in Section 3 and Section 4 respectively. Finally, we conclude our work in Section 5 and discuss the open questions in Section 6.

2 Preliminaries We are given a collection of agents, N = {1, 2, . . . , n} where each agent i has the profile ci = {xi, pi} containing the agent location xi and a list of fractional preferences pi = {pi,1, pi,2} on facilities F1 and F2 where 0 pi,1, pi,2 1 and pi,1+pi,2 = 1. The agents are sorted in increasing order of location, i.e. x1 x2 . . . xn and we are only focusing on the one dimensional spaces. A profile c is a collection of the location and preference reported by all agents, c = {c1, c2, . . . , cn}. A mechanism is a function f which maps profile c to an output (y1, y2) containing the locations of F1 and F2 (0 y1, y2 L). Let d(a, b) = |a b| be the distance between a and b. The cost of agent i is defined as cost(f(c), ci) = d(xi, y1) pi,1 + d(xi, y2) pi,2. The social cost is defined as sc(f, c) = n i=1 cost(f(c), ci) and the minimum cost is defined as mc(f, c) = min1 i ncost(f(c), ci). However, in Theorem 1, we show that if the cost function is used as the measurement of agents satisfaction, the approximation ratio of any strategy-proof mechanism is Ω(n 1 3 ).

Theorem 1. For the objective of minimizing social cost, the approximation ratio for any strategy-proof mechanism is at least Ω(n 1 3 ).

Before the proof, note that the partial group strategyproofness defined in (Lu et al. 2010) also applies here.

Lemma 1. In a strategy-proof mechanism, a group of agents with the same location and preference cannot benefit even if they misreport simultaneously.

Its proof is similar to that of (Lu et al. 2010), which is omitted here. Now we are ready to prove the lower bound.

Proof. Consider a profile c with n agents at 0 with preference of (1, 0), n 1 3 agents at 0 with preference of (0, 1), and an agent at 1 with preference of (0, 1). The allocations for both facilites is (y1, y2). We shall prove that there is no

Figure 1: Example to prove the lower bound of cost.

strategy-proof mechanism with an approximation ratio of 1 4n 1 3 . Assume for contradiction that there is such a mechanism. For the profile c, the optimal mechanism will place both facilities in the left extreme point, which is 0 with the costs of 1 as illustrated in Fig. 1a. So the cost for (y1, y2) is at most 1

4n 1 3 . Therefore, we can conclude that n|y1|+n 1 3 |y2| 1 4n 1 3 . From this, we can further conclude that |y1| 1

3 and |y2| 1

4. Then we consider another profile c where the n 1 3 agents located in the left extreme point misreport their preferences to (1 ϵ, ϵ) simulataneously where ϵ = n 2

3 . The allocations for both facilites is (y 1, y 2) for profile c . In this profile, the optimal mechanism will place F1 at 0 and place F2 at 1 with the cost of n 1 3 ϵ = n 1

3 as illustrated in Fig. 1b. So the cost for (y 1, y 2) is at most 1

3 = 1 4. Therefore, we can conclude that |y 2 1| 1

4. From this, we can further conclude that |y 2| 3

4. Now we can reach a contradiction to the partial group strategy-proofness since the group of n 1 3 agents at point of 0 with preference of p = {1 ϵ, ϵ} can be better off by lying to the preference of p = {0, 1}:

(1 ϵ)|y1| + ϵ|y2| 2

(1 ϵ)|y 1| + ϵ|y 2| ϵ|y 2| 3

This completes the proof (The number of agents can be scaled down to n without affecting the asymptotic bound).

Since we showed that the ratio is at least Ω(n 1 3 ) if the cost function is used, in the following, we will use the utility function defined as follows. The utility of agent i is defined as u(f(c), ci) = L d(xi, y1) pi,1 d(xi, y2) pi,2. The social utility is defined as su(f, c) = n i=1 u(f(c), ci) and the minimum utility is defined as mu(f, c) = min1 i nu(f(c), ci).

Let OPTSU(c) and OPTMU(c) be the optimal solution for maximizing the social utility and the optimal solution for maximizing the minimum utility respectively. A mechanism f is strategy-proof if an agent can never benefit by reporting a false profile. More formally, let c i be the false profile reported by agent i. We have u(f(c), ci) u(f(c i, c i), ci) where c i is a collection of profile reported by n agents except agent i. We can further discuss three cases shown below. 1. restrict the power of misreport to locations only. 2. restrict the power of misreport to preferences only. 3. do not restrict the power of misreport. We measure the performance of a mechanism f by comparing the social utility that f obtains and the social utility of the optimal solution. For a mechanism f, if there exists a number α such that for any profile c, the output from f satisfies OP TSU(c)

su(f,c) α, then we say the approximation ratio for the social utility of f is α. Similarly, if there exists a number β such that for any profile c, the output from f satisfies OP TMU (c)

mu(f,c) β, then we say the approximation ratio for the minimum utility of f is β.

3 Maximizing the Social Utility 3.1 Misreport only the location In this subsection, we restrict the power of misreport to locations only. Mechanism 1. Let wj = n i=1 pi,j and define midj = 1 2wj. Put Fj at the location of agent mj where mj = arg mink{midj k i=1 pi,j}. Theorem 2. Mechanism 1 is an optimal deterministic strategy-proof mechanism.

Proof. Firstly, we consider agents which are not m1 or m2, if they are on the left hand side of agent mj, they cannot influence the location of Fj if they move to be still on the left of mj and it will possibly make Fj move away from them if they move to the right of agent mj. Therefore they have no incentive to misreport their locations. For the agents on the right hand side of agent mj, the analysis is similar. For agent mj, he cannot move facility F3 j towards him by misreporting due to the discussion above and on the other hand, Fj is already at the best position for agent mj. Hence, he has no incentive to misreport his location. Therefore, Mechanism 1 is strategy-proof if only the location can be misreported. Moreover, it can be proved optimal using the similar way as how the median mechanism is proved to be optimal.

3.2 Misreport only the preference In this subsection, we restrict the power of misreport to preferences only. Firstly, we show a lower bound of approximation ratios for deterministic strategy-proof mechanisms. Theorem 3. There does not exist any strategy-proof deterministic mechanism with an approximation ratio less than 1.06.

Figure 2: Example to prove the lower bound of social utility.

Proof. Let the length of the line segment be equal to 1, i.e. L = 1. Consider a profile c with one agent at 0 with preference of (1, 0), another two agents at 0 with the preference of (0, 1), and an agent at 1 with preference of (0, 1). The allocations for both facilites is (y1, y2). We shall prove that there is no strategy-proof mechanism with an approximation ratio of 1.06 for social utility. Assume for contradiction that there is such a mechanism. For the profile c, the optimal mechanism will place both facilities in the left extreme point 0 with the social utility of 3 as illustrated in Fig. 2a. Hence, the social utility for (y1, y2) is at least 3 1.06 > 2.83. Therefore, we can conclude that 3 y1 y2 > 2.83. From this, we can further conclude that y1 + y2 < 0.17 and y1 < 0.17. Then we consider another profile c where the two agents located at 0 misreport their preferences to (0.7, 0.3) simultaneously. The allocations for both facilities is (y 1, y 2) for profile c . In this profile, the optimal mechanism will place F1 at 0 and place F2 at 1 with the social utility of 3.4 as illustrated in Fig. 2b. Hence, the social utility for (y 1, y 2) is at least 3.4 1.06 > 3.2. The social utility for (y 1, y 2) is

1 y 1 + y 2 + 2(1 0.7y 1 0.3y 2) = 3 2.4y 1 + 0.4y 2 3 + 0.4y 2.

Therefore, we can conclude that 3 + 0.4y 2 > 3.2. From this, we can further conclude that y 2 > 0.5. Now we can reach a contradiction to the partial group strategy-proofness since the group of two agents at 0 with preference of (0.7, 0.3) can be better off by lying to the preference of (0, 1):

0.7y1 + 0.3y2 = 0.4y1 + 0.3(y1 + y2) < 0.119,

0.7y 1 + 0.3y 2 0.3y 2 > 0.15 > 0.119. This completes the proof.

Next, we propose the following mechanism. Mechanism 2. Given a profile c = (x, p), for Fj, we denote the left most agent with pj > 0 as lj and denote the right most agent with pj > 0 as rj. Put Fj at (xlj + xrj)/2.

Theorem 4. Mechanism 2 is a deterministic strategy-proof mechanism with an approximation ratio of 2.

Proof. In Mechanism 2, in order to influence the output location of Fj, there are three cases. Case 1: lj changes his preference on Fj to zero. Case 2: rj changes his preference on Fj to zero. Case 3: An agent k with xk < xlj or xk > xrj misreports the preference from zero to non-zero. For Case 1, since the output location of Fj is (xlj + xrj)/2, if lj misreports his preference to zero, lj will become the agent i on his right with pi,j > 0, which makes the facility move away from him. Hence, he has no incentive to misreport his preference in this case. Case 2 is symmetric to Case 1. For Case 3, although the agents can pull Fj towards them by misreporting the preference from zero to non-zero, as they have pi,j = 0, they have no incentive to misreport their preferences. Therefore, Mechanism 2 is strategy-proof. Let αlen = xr1 xl1 and βlen = xr2 xl2. The utility of each agent is

u(f(c), ci) = L d(xi, y1) pi,1 d(xi, y2) pi,2

2 pi,1 βlen

With n agents, the social utility of Mechanism 2 is at least 1

2n L. On the other hand, the optimal social utility is OPTSU(c) = n L. Hence, OPTSU(c)/su(f, c) n L/ 1

Moreover, we have a nearly tight example below to show that our analysis in Theorem 4 is tight. Suppose we have (n 2)/2 agents with preference of (1, 0) and (0, 1) in both extreme points. Then we have a single agent with preference of (0, 1) located at 0 and a single agent with preference of (1, 0) located at L. The optimal mechanism will place F1 at 0 and F2 at L. However, Mechanism 2 places both F1 and F2 at L/2. Hence, the optimal social utility will be (n 2)L, whereas Mechanism 2 has the social utility of n L/2 as both F1 and F2 are at L/2. Hence, the approximation ratio OP TSU(c)

su(f,c) = (n 2)L

n L/2 = 2 4

3.3 Misreport both the preference and location In this subsection, we do not restrict the power of misreport. Firstly, we can see that Mechanism 2 is not strategyproof if location information can be misreported. Consider the profile c = (x, p) with x = {0.5, 1} and p = {(0.5, 0.5), (0.5, 0.5)}. Since Mechanism 2 puts Fj at (lj + rj)/2, Fj is located at 0.75 in this situation. However, if agent 1 misreports his location as x 1 = 0, then the location of F1 will become 0.5 which is his real location. Therefore, agent 1 can gain by misreporting his location, and Mechanism 2 is not strategy-proof.

Mechanism 3. Given a profile c = (x, p), let A and B be a set of agents k with pk,1 > 0 and pk,2 > 0 respectively. Set A may intersect set B if some agent i has pi,1 > 0 and pi,2 > 0. Let med(A) be the median agent in A and med(B) be the median agent in B. If the set has an even number of

agents, we refer the left median as the median agent. Place F1 at med(A) and F2 at med(B).

Theorem 5. Mechanism 3 is a deterministic strategy-proof mechanism with an approximation ratio of n.

Proof. Firstly, an agent with preference (0,1) or (1,0) will not misreport since the median mechanism guarantees that truth telling (for both location and preference) is the best strategy for the facility he likes and he also will not misreport the preference for the other facility since his preference for that facility is 0. For other agents, if they only misreport locations or change their preferences to other non-zero values for both facilities, they will not gain due to the property of the median mechanism since any non-zero value is treated the same way. The only possibility left is to misreport preferences to (0,1) or (1,0) and misreport locations. However, in this case, they will only influence one facility instead of two. Again, the property of the median mechanism guarantees that no facility will move closer to them after the misreport. Then, we are going to show that the social utility of Mechanism 3 is at least L which implies an approximation ratio of n. If the two medians coincide, then the agent at that location can achieve a utility L and therefore the ratio holds. Otherwise, the two locations are different, then there must be some agents whose preferences are (0, 1) or (1, 0). Suppose that F1 is on the left of F2, then there are more agents with preference (1, 0) than agents with preference (0, 1) on the left of F2. Similarly, there are more agents with preference (0, 1) than agents with preference (1, 0) on the right of F1. Therefore, there must be some agents with preference (1, 0) on the left of F1 (or on F1) or some agents with preference (0, 1) on the right of F2 (or on F2). Suppose there is some agent with preference (1, 0) on the left of F1, as illustrated in Fig. 3, his utility together with F1 median s utility is at least L a + L b L, where a is the distance from 0 to F1 and b is the distance from F1 to F2 (so a + b L). Hence, we have su(f, c) L and OPTSU(c)/su(f, c) n L

Figure 3: Illustriation of Theorem 5.

Moreover, we have a nearly tight example below to show that our analysis in Theorem 5 is tight. Consider a profile c with (n 1)/2 agents at 0 with preference of (1 ϵ, ϵ), (n 1)/2 agents at L with preference of (ϵ, 1 ϵ), as well as an agent at L with preference of (1, 0). The optimal solution will place F1 at 0 and F2 at L. However, Mechanism 3 places F1 at L and F2 at 0.

Hence, we have Mechanism 3 computes the location of F1 and F2 separately and therefore results in a large approximation ratio. In order to improve the performance of the approximation ratio as well as maintain the strategy-proofness, we need to consider F1 and F2 together. Therefore we propose Mechanism 4. We first classify agents into three categories below. 1. F1 agent if pi,1 > 0.5. 2. F2 agent if pi,2 > 0.5. 3. F1F2 agent if pi,1 = pi,2 = 0.5. We say that agent i prefers Fj if pi,j > 0.5. For ease of presentation, we denote the left segment as the range of [0, L/2], the right segment as the range of (L/2, L]. Observe that if the solution is on the two extreme points, either (0, L) or (L, 0), then we have only two kinds of agents whereas the F1F2 agents can be ignored, as their utilities will not change no matter whether (0, L) or (L, 0) is returned.

1. LF1 agents: the agents who prefer F1 located in the left extreme point and prefer F2 located in the right extreme point. (F1 agents in the left segment and F2 agents in the right segment). 2. RF1 agents: the agents who prefer F2 located in the left extreme point and prefer F1 located in the right extreme point. (F1 agents in the right segment and F2 agents in the left segment).

Mechanism 4. Let |LF1| and |RF1| be the number of LF1 agents and RF1 agents respectively. If |LF1| |RF1|, output (0, L), otherwise, output (L, 0). Theorem 6. Mechanism 4 is strategy-proof.

Proof. First, we consider the F1F2 agents. As they prefer both facilities with the same ratio, i.e. pi,1 = pi,2 = 0.5 and the mechanism will only consider the two extreme points as the solution, no matter it is (0, L) or (L, 0) , their utilities are the same. Hence, they do not have incentive to misreport. Secondly, we consider LF1 agents and RF1 agents. Without loss of generality, suppose the output (0, L) is returned. We have |LF1| |RF1|. Since the facility F1 is already located at the left extreme point, LF1 agents do not have incentive to lie. For an RF1 agent, misreporting as an LF1 agent would increase |LF1| and decrease |RF2| which keeps the result the same. If he misreports as an F1F2 agent, then |RF1| will decrease by 1, and the result will also remain the same. Note that this already includes the possibility of misreporting both location and preference. Hence, RF1 agent does not have incentive to misreport. Outputting (L, 0) is symmetric to the case above. Hence, Mechanism 4 is strategy-proof.

Theorem 7. Mechanism 4 has an approximation ratio of 4.

Proof. We first assume Mechanism 4 outputs (y1, y2) = (0, L). We have |LF1| |RF1|. Observe that LF1 consists of two types of agents:

1. F1 agents: agents located in the left segment [0, L/2] who prefer facility 1 more than facility 2, i.e. pi,1 > pi,2.

2. F2 agents: agents located in the right segment (L/2, L] who prefer facility 2 more than facility 1, i.e. pi,1 < pi,2.

If an F1 agent moves to the right / F2 agent moves to the left, his utility will decrease, and his utility will reach the minimum if he moves to the center of the segment achieving utility of

L pi,1(0.5) pi,2(0.5) = 0.5L.

Similarly, for the RF1 agents, they are the agents located in the left segment who prefer F2, or the agents located in the right segment who prefer F1. Hence, their minimum utility will be zero in this case. For F1F2 agents, as their preferences are {0.5, 0.5}, their utilities are always

u(f(c), ci) = L (0.5) d(xi, y1) (0.5) d(xi, y2) = L 0.5L = 0.5L.

As |LF1| |RF1|, we have |RF1| |LF1|+|RF1|

2 . Therefore, we can conclude that

su(f, c) 0.5L(n |RF1|)

0.5L(n |LF1| + |RF1|

Then we have OPTSU(c)/su(f, c) n L/ 1

4n L = 4, since each agent can have utility at most L.

Notice that the lower bound 1.06 proved in subsection 3.2 is also a lower bound here. Besides deterministic mechanisms presented above, we also present a randomized strategy-proof mechanism which can further improve the approximation ratio (thanks to an anonymous reviewer).

Mechanism 5. Place the facilities F1 and F2 at (0, L) and (L, 0) with 1/2 probability.

Theorem 8. Mechanism 5 is a randomized strategy-proof mechanism with an approximation ratio of 2.

Proof. In Mechanism 5, the expected utility for each agent is

u(f(c), ci) = L 1/2 d(xi, y1) pi,1 1/2 d(xi, y2) pi,2 L 1/2L = L/2

Then we have OPTSU(c)/su(f, c) n L/ 1

2n L = 2 since each agent can have utility at most L. As the mechanism places the facilities in two extreme points with equal probability, the agents do not have incentive to misreport, and Mechanism 5 is strategy-proof.

Theorem 9. There does not exist any strategy-proof randomized mechanism with an approximation ratio less than 1.06.

Proof. For the proof, we can reuse the example in Theorem 3 to prove the lower bound for randomized mechanisms. The reason is that we are using profiles where agents are at two extreme points, where the agent s expected cost is equal to its distance to the expected location for the randomized mechanism (the possible positions for the facilities are only on one side of the agent). Therefore, we could treat the expected location of a facility as the output for a deterministic mechanism and thus the lower bound we proved for the deterministic mechanisms also works here.

4 Maximizing the Minimum Utility In this section, we do not restrict the power of misreport. Lemma 2. There does not exist any strategy-proof deterministic mechanism with an approximation ratio less than 1.5.

Proof. The proof below is inspired by (Procaccia and Tennenholtz 2013). We assume there exists a strategy-proof deterministic mechanism with an approximation ratio less than 1.5 for maximizing the minimum utility. Consider the profile of c = (x, p) where x = {0, 1} and p = {(1, 0), (1, 0)}. Without loss of generality, we assume mu(f, c) = L/2 + ϵ, where ϵ 0. Now consider another profile c = (x , p) where x = {0, L

2 }. The optimal solution has the minimum utility of 3

4L + ϵ, then in order to obtain an approximation ratio less than 1.5, we need to place F1 in the range of (0, L/2). Then in this case, agent 2 can gain by misreporting x = 1 in order to move F1 to L/2 + ϵ, in contradiction to strategy-proofness.

Mechanism 6. Place both facilities F1 and F2 at L/2. Theorem 10. Mechanism 6 is a deterministic strategy-proof mechanism with an approximation ratio of 2.

Proof. As Mechanism 6 places both facilities at the fixed center point, agents cannot influence the result by misreporting their location and preference information. Therefore, Mechanism 6 is strategy-proof. No matter where the facilities are placed, the minimum utility is at least

mu(f, c) = L d(xi, y1) pi,1 d(xi, y2) pi,2

2 (pi,1 + pi,2) = L

The optimal minimum utility is OPTMU(c) = L. Hence, OPTMU(c)/mu(f, c) L L/2 = 2.

5 Conclusion To conclude, we proposed a new variant of the facility location game, named as the fractional preference model and we mainly focused on deterministic mechanisms. The fractional preference model allows agents to state their preferences in a fractional form to distinguish the severity that they prefer on the similar facilities which can cover more real life scenarios in comparison with the zero and one preferences in the existing heterogenous facility location game. In this model, we further categorized the problem into different cases by restricting the power of misreports. In each

case, we achieved different results in both objectives of maximizing the social utility and maximizing the minimum utility. The results are summarized in Table 1 below.

Table 1: A summary of our results.

Objective Restrict the Power of Misreport Loc only Pref only No Restriction

Social Utility UB: 1 UB: 2

UB: 4 Rand UB: 2 LB:1.06 LB: 1.06 Rand LB: 1.06

Min Utility UB: 2 UB: 2 UB: 2 LB:1.5 LB: 1.5

6 Future Work We obtained the upper bound of 4 and lower bound of 1.06 for maximizing the social utility in the general case. The results can be further strengthened if the mechanism with a better approximation ratio can be found. Moreover, for maximizing the minimum utility, it is unknown whether a randomized mechanism could further improve the approximation ratio. On the other hand, extending our results to n facilities would also be an interesting direction. Based on our current result, Mechanism 2 and Mechanism 3 are possible to be extended to multiple facilities, since we choose the agents with positive preference on facilities i and pick the center point or median point to place facility i. In other words, the positions of facilities are independently decided. Therefore, when we have multiple facilities, the utilities are also independently calculated. Hence, strategyproofness can still be guaranteed and the ratio also does not change. However, it is unknown whether Mechanism 4 can be extended for multiple facilities since it uses the two end points of the line segment to place two facilities. When we have more than two facilities, there are not so many special points to choose from. Therefore, it is more challenging to design strategyproof mechanisms with good approximation ratios.

References Noga Alon, Michal Feldman, Ariel D. Procaccia, and Moshe Tennenholtz. Strategyproof approximation of the minimax on networks. Math. Oper. Res., 35(3):513 526, 2010. Yukun Cheng, Wei Yu, and Guochuan Zhang. Mechanisms for obnoxious facility game on a path. In Combinatorial Optimization and Applications - 5th International Conference, COCOA 2011, Zhangjiajie, China, August 4-6, 2011. Proceedings, pages 262 271, 2011. Yukun Cheng, Wei Yu, and Guochuan Zhang. Strategyproof approximation mechanisms for an obnoxious facility game on networks. Theor. Comput. Sci., 497:154 163, 2013. Elad Dokow, Michal Feldman, Reshef Meir, and Ilan Nehama. Mechanism design on discrete lines and cycles. In ACM Conference on Electronic Commerce, EC 2012, Valencia, Spain, June 4-8, 2012, pages 423 440, 2012.

Bruno Escoffier, Laurent Gourv es, Nguyen Kim Thang, Fanny Pascual, and Olivier Spanjaard. Strategy-proof mechanisms for facility location games with many facilities. In Algorithmic Decision Theory - Second International Conference, ADT 2011, Piscataway, NJ, USA, October 26-28, 2011. Proceedings, pages 67 81, 2011. Itai Feigenbaum and Jay Sethuraman. Strategyproof mechanisms for one-dimensional hybrid and obnoxious facility location. Co RR, abs/1412.3414, 2014. Michal Feldman and Yoav Wilf. Strategyproof facility location and the least squares objective. In ACM Conference on Electronic Commerce, EC 2013, Philadelphia, PA, USA, June 16-20, 2013, pages 873 890, 2013. Aris Filos-Ratsikas, Minming Li, Jie Zhang, and Qiang Zhang. Facility location with double-peaked preferences. In Blai Bonet and Sven Koenig, editors, Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25-30, 2015, Austin, Texas, USA., pages 893 899. AAAI Press, 2015. Dimitris Fotakis and Christos Tzamos. On the power of deterministic mechanisms for facility location games. ACM Trans. Economics and Comput., 2(4):15:1 15:37, 2014. Allan Gibbard. Manipulation of voting schemes: a general result. Econometrica: journal of the Econometric Society, pages 587 601, 1973. Eun Jeong Heo. Strategy-proof rules for two public goods: double median rules. Social Choice and Welfare, 41(4):895 922, 2013. Pinyan Lu, Yajun Wang, and Yuan Zhou. Tighter bounds for facility games. In Internet and Network Economics, pages 137 148. Springer, 2009. Pinyan Lu, Xiaorui Sun, Yajun Wang, and Zeyuan Allen Zhu. Asymptotically optimal strategy-proof mechanisms for two-facility games. In Proceedings of the 11th ACM Conference on Electronic Commerce, EC 10, pages 315 324, New York, NY, USA, 2010. ACM. Eiichi Miyagawa. Locating libraries on a street. Social Choice and Welfare, 18(3):527 541, 2001. Herv e Moulin. On strategy-proofness and single peakedness. Public Choice, 35(4):437 455, 1980. Ariel D. Procaccia and Moshe Tennenholtz. Approximate mechanism design without money. ACM Trans. Economics and Comput., 1(4):18:1 18:26, 2013. Mark Allen Satterthwaite. Strategy-proofness and arrow s conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of economic theory, 10(2):187 217, 1975. James Schummer and Rakesh V Vohra. Strategy-proof location on a network. Journal of Economic Theory, 104(2):405 428, 2002. Paolo Serafino and Carmine Ventre. Heterogeneous facility location without money on the line. In ECAI 2014 - 21st European Conference on Artificial Intelligence, 18-22 August 2014, Prague, Czech Republic - Including Prestigious Applications of Intelligent Systems (PAIS 2014), pages 807 812, 2014.

Paolo Serafino and Carmine Ventre. Truthful mechanisms without money for non-utilitarian heterogeneous facility location. In Blai Bonet and Sven Koenig, editors, Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25-30, 2015, Austin, Texas, USA., pages 1029 1035. AAAI Press, 2015. Akihisa Sonoda, Taiki Todo, and Makoto Yokoo. Falsename-proof locations of two facilities: Economic and algorithmic approaches. In AAAI, pages 615 621, 2016. Taiki Todo, Atsushi Iwasaki, and Makoto Yokoo. Falsename-proof mechanism design without money. In 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011), Taipei, Taiwan, May 2-6, 2011, Volume 1-3, pages 651 658, 2011. Deshi Ye, Lili Mei, and Yong Zhang. Strategy-proof mechanism for obnoxious facility location on a line. In Computing and Combinatorics - 21st International Conference,COCOON 2015, Beijing, China, August 4-6, 2015, Proceedings, pages 45 56, 2015. Hongning Yuan, Kai Wang, Ken C. K. Fong, Yong Zhang, and Minming Li. Facility location games with optional preference. In ECAI 2016 - 22nd European Conference on Artificial Intelligence, 29 August-2 September 2016, The Hague, The Netherlands - Including Prestigious Applications of Artificial Intelligence, PAIS 2016, pages 1520 1527, 2016. Qiang Zhang and Minming Li. Strategyproof mechanism design for facility location games with weighted agents on a line. J. Comb. Optim., 28(4):756 773, 2014. Shaokun Zou and Minming Li. Facility location games with dual preference. In Gerhard Weiss, Pinar Yolum, Rafael H. Bordini, and Edith Elkind, editors, Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2015, Istanbul, Turkey, May 4-8, 2015, pages 615 623. ACM, 2015.