Facility Location with Minimax Envy

1 Introduction

Over the past years, facility location has been a topic of intensive study at the intersection of AI and game theory. In the basic version of the problem [Procaccia and Tennenholtz, 2009], a central planner is asked to locate a facility on a real line, based on the reported preferences of self-interested agents. Agents' preferences are single-peaked and are expressed through cost functions; an agent's cost is the distance between her most-preferred position (her "peak") and the location of the facility [Procaccia and Tennenholtz, 2009].

Our work falls under the umbrella of approximate mechanism design without money, a term coined in [Procaccia and Tennenholtz, 2009] to describe problems where some objective function is approximately maximized under the constraint that the truthful behavior of the participants must

Pingzhong Tang

Tsinghua University, China kenshinping@gmail.com

be ensured. In fact, the setting in [Procaccia and Tennenholtz, 2009] is the very same facility location setting presented above. The objectives studied in [Procaccia and Tennenholtz, 2009], as well as in a large body of subsequent literature [Alon et al., 2009; Lu et al., 2009; 2010; Fotakis and Tzamos, 2013b] are minimizing the social cost, or the maximum cost, The social cost is the equivalent to the utilitarian objective from economics, whereas the maximum cost is often referred to the egalitarian solution and is in general interpreted as a more "fair" outcome, in comparison to its utilitarian counterpart.

In this paper, we adopt a different fairness criterion from the fair division literature [Caragiannis et al., 2009; Lipton et al., 2004; Netzer and Meisels, 2013], that of minimax envy. Since in the standard facility location setting in computer science agents' preferences are expressed through cost functions, quantifying comparisons between costs are possible and in fact, such comparisons are inherent in both the social cost and the maximum cost objectives. In a similar spirit, we can define a quantified version of envy; the envy of an agent with respect to another agent, is simply their difference in distance from the facility (normalized by the length of the location profile). For example, when there are two agents, placing the facility on either agent's most preferred point generates an envy of 1, while placing it in the middle of the interval defined by their most preferred locations generates an envy of 0. The goal is to find the location that minimizes the maximum envy of any agent, while at the same time making sure that agents will report their most preferred locations truthfully.

1.1 Our contributions

We study two versions of the problem, when the facility can be placed anywhere on a real line and when the space of allowed facility locations is restricted to an interval. As we will argue later on, the usual notion of the (multiplicative) approximation ratio used typically in facility location problems is not fit for the minimax envy objective. In fact, it is not hard to see that no truthful-in-expectation mechanism can achieve a finite approximation ratio, the reason being that there are inputs where the minimum envy is 0, which is not however achievable by any truthful mechanism. For that reason, we will employ an additive approximation to quantify the performance of truthful mechanisms. Additive approximations are quite common in the literature of approximation algorithms [Alon et al., 2005; Goemans, 2006; Williamson and Shmoys, 2011] as well as the mechanism design literature [Roughgarden and Sundararajan, 2009; Cohler et al., 2011], even for facility location [Nissim et al., 2012].

First, we study the version where the facility can be placed anywhere on the real line. We design a class of truthfulin-expectation mechanisms, that we will call ↵-LRM. which generalizes the well-known LRM ("left-right-median") mechanism introduced in [Procaccia and Tennenholtz, 2009] and named in [Alon et al., 2009]. We prove that there exists a mechanism in the ↵-LRM class that is near-optimal, i.e. it achieves an ✏ additive approximation, for any ✏ > 0.

Next, we consider the variant of the problem where the facility is restricted to an interval. This case captures most real-life scenarios and is often implicit in the motivation of the problem; when we locate a library in a university, the candidate locations are clearly constrained to be within the university premises or when choosing the ideal temperature in a room, it might not be sensible to consider temperatures much higher or lower than what any agent would ideally prefer. The reason why this restriction was not discussed explicitly in previous work is that the best performance guarantees for other objective functions are achievable even if we restrict our attention to the interval defined by the reported locations of the agents. As we will show, this is no longer the case for the minimax objective.

When the interval is defined by the report of the agents, we prove that for any choice of such an interval, there exists a mechanism in the class ↵-LRM with additive approximation that is arbitrarily close to the approximation achieved by the best truthful-in-expectation mechanism. For the case when all reports lie withing fixed intervals, we prove that the approximation of the best truthful-in-expectation mechanism is between 1◁3 - ✏ and 1◁2, for any ✏ > 0. For both the realline and the restriction to the interval, we prove that any truthful deterministic mechanism has a minimum maximum envy of 1, which shows that without randomization, making some agent maximally envious is unavoidable.

1.2 Related work

The facility location problem has been studied extensively in the computer science literature. [Procaccia and Tennenholtz, 2009; Alon et al., 2009; Lu et al., 2009; 2010; Fotakis and Tzamos, 2013a; 2013b]. Crucially however, most of the rich literature on facility location in computer science considers either the social cost or the maximum cost objective. It is only recently that different objectives have been considered. Feigenbaum et al. [Feigenbaum et al., 2013] consider facility location on a real line for minimizing the Lp norm of agents' costs, while Feldman et al. [Feldman and Wilf, 2013] design truthful mechanisms for approximating the least squares objective on tree networks. Our work introduces a different objective which is not based on aggregate measures, but rather on a quantitative notion of individual fairness.

The objective of envy minimization has attracted considerable attention in the recent literature of fair division and mechanism design. Lipton at al. [Lipton et al., 2004] and Caragiannis et al. [Caragiannis et al., 2009] study indivisible item allocation for the minimax envy criterion and bound the performance of truthful mechanisms. For the same problem, Nguyen and Rothe [Nguyen and Rothe, 2013] study the minimization of the maximum envy as well as the total envy, but from a computational standpoint and in the absence of incentives. Netzer and Meisels employ the minimax envy criterion to resource allocation problems in a distributed framework. It is worth noting that relaxations of envy-freeness and the goals of envy minimization have also been considered in the past in economics [Zeckhauser, 1991].

2 Preliminaries

In the facility location problem, a set N = ¶1↪ ▷ ▷ ▷ ↪ n♦ of agents have to decide collectively on the location of a facility y 2 R. Each agent i is associated with a location xi 2 R, which is her most preferred point on the real line. Let x = (x1↪ ▷ ▷ ▷ ↪ xn) be the vector of agents' locations, that we will refer to as a location profile. Given a location of the facility y, the cost of an agent is simply the distance between her location and the location of the facility, i.e. costi(y) = ♣y - xi♣. For a given location profile x, we will use lm(x) and rm(x) to denote the locations of the leftmost and the rightmost agents respectively. We will let mid(x) = (rm(x) + lm(x))◁2. Finally, we will let L(x) = rm(x) - lm(x) denote the length of profile x.

A mechanism is a function f : Rn ! R mapping location profiles to locations of the facility. The cost of an agent from mechanism f is defined as costi(f) = costi(f(x)). In this paper, we will also consider randomized mechanisms; a randomized mechanism f is a random variable X, with probability density function

Informally, randomized mechanisms output different locations with different probabilities. The cost of agent i from a randomized mechanism f is defined as

We will be interested in truthful mechanisms, i.e. mechanisms that do not incentivize agents to misreport their locations. Formally, a mechanism f is truthful if for every agent i 2 N and for any δ 2 R, it holds that

where x-i is the vector of reported locations of agents in N∩¶i♦. For randomized mechanisms, the notion of truthfulness is truthfulness-in-expectation and the definition is similar, with respect to the expected cost of an agent.

We will aim to minimize the maximum envy of all agents. For a given location of the facility y, the envy of agent i with respect to agent j is defined as costi(y)-costj(y). The maximum envy is defined as

where without loss of generality we can assume that L(x) 6= 0 (otherwise outputting lm(x) trivially minimizes the maximum envy). We define the maximum envy of a mechanism f on input profile x to be F(f(x)) = F(f↪ x). For randomized mechanisms, the maximum envy is defined with respect to the expected costs and given the definition of a randomized mechanism as a random variable can be written as

Our objective will be to find mechanisms that minimize the quantity F(f↪ x) over all location profiles. Note that by the definitions above, the maximum envy of any mechanism is 1 and the minimum envy is 0.

In a location profile with two agents, the location that minimizes the envy of any agent is the midpoint of the location interval. Furthermore, the minimum envy at that location is 0. On the other hand, it is not hard to see that a mechanism that outputs the midpoint of the location interval is not truthful while at the same time, assigning positive probabilities to other locations renders the minimum envy strictly positive. This means that if we employ the commonly used notion of multiplicative approximation (the approximation ratio) [Procaccia and Tennenholtz, 2009], the ratio of any truthful mechanism is infinite and hence this measure of efficiency is not appropriate for the problem that we study here.

We will instead consider an additive approximation: a mechanism achieves an approximation of ⇢ 2 [0↪ 1] if the maximum envy that it generates for any location profile x is at most O(x) + ⇢, where O(x) is the minimum possible envy achievable on profile x. We will be interested in truthful mechanisms with good additive approximations.

The following lemma will be very useful for analyzing the approximations of our mechanisms. The lemma implies that for any number of agents, we can assume that the location that minimizes the envy is in fact the midpoint of the location profile. The proof is based on a case analysis, and is omitted due to lack of space.

Lemma 1. Given a location profile x, the location mid(x) of the facility minimizes the maximum envy over all agents.

3 Location on the real line

In this section, we consider the variant of the problem where the location of the facility can be any point y 2 R on the real line. We start with the following theorem, which implies that deterministic truthful mechanisms are bound to perform poorly; the proof is not very involved and is omitted due to lack of space.

Theorem 1. The approximation of any truthful deterministic mechanism is 1.

Theorem 1 suggests that in order to any reasonable minimax envy guarantees, we need to resort to randomization. Next, we define a class of truthful-in-expectation mechanisms, parametrized by a constant ↵ 2 (0↪ 1◁4], that we will call ↵-LRM.

Mechanism↵-LRM. For any location profile x, let

Place the facility at mid(x) with probability 1 - 2↵, at lm(x) - L↵(x) with probability ↵, and at rm(x) + L↵(x) with probability ↵.

Note that the class ↵-LRM generalizes the well-known LRM mechanism [Procaccia and Tennenholtz, 2009; Alon et al., 2009], since the LRM mechanism can be obtained from the above definition by setting ↵ = 1◁4. We prove the following:

Theorem 2. Any mechanism in the class ↵-LRM is truthfulin-expectation.

Proof. Let x = (x1↪ x2↪ ▷ ▷ ▷ ↪ xn) be any location profile. For ease of notation and without loss of generality, assume that x1  x2  ▷ ▷ ▷  xn. Agents 1 and n can change the location of the facility by misreporting their locations, but any other agent j can not impact the output unless the misreported location x0j is such that x0j < x1 or x0j > xn. We consider two main cases.

Case 1: The deviating agent is either agent 1 or agent n. We only need to prove that agent 1 can not benefit from misreporting; the argument for agent n is completely symmetric. We will consider the cases when agent 1 reports x1 + δ and x1 - δ, for δ > 0 separately.

• ÷ First consider the case when agent 1 reports x1 + δ for δ > 0. Without loss of generality, we can assume that lm(x1 + δ↪ x-1) = x1 + δ, because any misreport x1 + δ 2 (x2↪ xn] gives agent 1 the same expected cost as the misreport x1 + δ = x2 (and any misreport x1 + δ > xn is obviously worse for the agent). By this discussion, it holds that mid(x1 + δ↪ x-1) = (x1 + xn + δ)◁2. Then the contribution to the cost of agent 1 by mid(x1+ δ↪ x-1) is larger by (1 - 2↵)δ◁2, when compared to the contribution to the cost of the agent from mid(x). The total contribution to the cost of the agent from lm(x) - L↵(x) and rm(x) + L↵(x) is

When agent 1 reports x1 + δ, the corresponding contribution to the cost of the agent from lm(x1 + δ↪ x-1) - L↵(x1+δ↪ x-1) and rm(x1+δ↪ x-1)+L↵(x1+δ↪ x-1) is (1 - 2↵)(L(x) - δ)◁2 which is smaller than the contribution to the cost of the agent from locations lm(x) - L↵(x) and rm(x) + L↵(x) by (1 - 2↵)δ◁2 and hence agent 1 can not benefit by misreporting.

• ÷ If agent 1 reports x1-δ, for δ > 0 it holds that mid(x1δ↪ x-1)(x1 + xn - δ)◁2. Then the contribution to the cost of the agent from mid(x1 - δ↪ x-1) is smaller by (1 - 2↵)δ◁2, when compared to the contribution to the cost from mid(x). Again, the contribution to the cost from locations lm(x) - L↵(x) and rm(x) + L↵(x) is

When agent 1 reports x1 - δ, the corresponding contribution from lm(x1 - δ↪ x-1) - L↵(x1 - δ↪ x-1) and rm(x1 - δ↪ x-1) + L↵(x1 - δ↪ x-1) is (L(x) + δ)(1 - 2↵)◁2, which is larger than the contribution to the cost of the agent from locations lm(x) -L↵(x) and rm(x)+L↵(x) by (1-2↵)δ◁2 and hence agent 1 cannot benefit frommisreporting.

Case 2: The deviating agent is some agent i ◁2 ¶1↪ n♦. From the earlier discussion, in order to affect the location of the facility, it has to be the case that for any misreport x0i of agent i, it holds that x0i < x1 or x0i > xn. We will only consider the case when x0i < x1; the other case is completely symmetric. Let δ > 0 be such that x0i = x1 - δ. Since x1 - δ is now the leftmost point of the location interval, it holds that mid(x1 - δ↪ x-i) = (x1 - δ + xn)◁2. Then the contribution to the cost of agent i from mid(x1 - δ↪ x-i) is smaller by at most ((1-2↵)δ)◁2, compared to the contribution to the cost from mid(x). On the other hand, the contribution to the cost of the agent by lm(x1 - δ↪ x-i) - L↵(x1 - δ↪ x-i) and rm(x1 - δ↪ x-i)-L↵(x1 -δ↪ x-i) when compared to the contribution from lm(x)-L↵(x) and rm(x)-L↵(x) is larger by at least ↵(δ +(1-4↵)δ◁2↵) = (1-2↵)δ◁2 and thus agent i cannot benefit frommisreporting her location.

Next, we prove that a mechanism in this class is arbitrarily close to the optimal assignment, that minimizes the maximum envy.

Theorem 3. For any ✏ > 0, there exists a mechanism in the class ↵-LRM with additive approximation ✏.

Proof. Recall that O(x) is the minimum maximum envy on profile x. By Lemma 1, it holds that O(x) = F(mid(x)↪ x) and hence the maximum envy achieved by a mechanism ↵- LRM, for some ↵ 2 (0↪ 1◁4] is at most (1-2↵)O(x)+2↵ and the approximation of the mechanism is at most 2↵-2↵O(x). For any ✏ > 0, we can choose ↵ small enough to achieve an approximation of ✏.

4 Location on an interval

In real-world applications, the designer might not have the freedom to place the facility anywhere he wants; the allowed locations might be constrained by physical borders (like a university campus) or practicality constraints (placing the library to far away even with a small probability is impractical).

We will consider the minimax envy when the facility is restricted to some interval [a↪ b], and consider two cases; when the interval is relative, i.e. determined by the reports of the agents or fixed in advance, with all the reports lying within the interval. Again, we have the following theorem, the proof of which is omitted due to lack of space.

Theorem 4. The approximation of any deterministic truthful mechanism for facility location on an interval is 1.

Next, we state some useful lemmas that will allow us to first consider profiles with two agents and then generalize the results to any number of agents. We start with a lemma that uses a mechanism for n agents to simulate a mechanism for two agents. Similar lemmas in spirit have been proven before in the literature [Lu et al., 2010; Filos-Ratsikas et al., 2015]; we omit the proof due to lack of space.

Lemma 2. Let f be a truthful mechanism for n agents with locations x1↪ ▷ ▷ ▷ ↪ xn. Let fk be the mechanism for two agents with locations x01 ↪ x02 such that

whenever x1 = x2 = ▷ ▷ ▷ = xk = x01 and xk+1 = xk+2 = ▷ ▷ ▷ = xn = x02 . Then, fk is truthful. Furthermore, if the output of f is restricted to an interval [a↪ b], the output of fk is restricted to the interval [a↪ b] as well.

Using Lemma 2, we prove the following lemma that allows us to bound the approximation of truthful mechanisms by only considering the case of two agents.

Lemma 3. Let f be a truthful mechanism for n players with approximation ⇢. Then, there exists a truthful mechanism g for two agents with approximation at most ⇢.

Proof. Let f be such a mechanism as above and let g be some mechanism fk for two agents constructed as in Lemma 2, for some value of k. Since the approximation of f is the worst case approximation over all input profiles, the achieved approximation of f (i.e. the difference between the minimax envy of the mechanism and the minimum maximum envy) on some input of the form x = (x1↪ x2↪ ▷ ▷ ▷ ↪ xk↪ xk+1↪ ▷ ▷ ▷ ↪ xn), with x1 = · · · = xk and xk+1 = · · · = xn is at most ⇢. By the construction of mechanism g and given that costi(f(x)) = costi0(f(x)) for all i↪ i0 = 1↪ ▷ ▷ ▷ ↪ k and that costj(f(x)) = cost0j 0 (f(x)) for all j↪ j 0 = k + 1↪ ▷ ▷ ▷ ↪ n, the approximation of g on any profile (x01 ↪ x02 ) is at most ⇢.

4.1 Relative Interval

Here, we consider the case where the allowed interval is determined by the reports of the extremal (leftmost and rightmost) agents. This setting corresponds to scenarios where the designer aims to balance the quality of the solution with the set of reports, in order to meet some natural restrictions expost. For example, the designer might want to make sure that in every possible run of the mechanism, the facility does not lie too far away from any agent, no matter how small the probability of that happening is. In the following, we will prove that for any choice of such an interval, there is a mechanism in the class ↵-LRM that achieves the best possible approximation among all truthful-in-expectation mechanisms.

First, we consider the case when the allowed interval is (strictly) contained in the interval defined by the profile.

Lemma 4. Let (x1↪ x2) be any location profile with two agents and assume without loss of generality that x1  x2. For any k 2 [0↪ 1), there does not exist a truthful mechanism such that it always holds that

i.e. the length of the allowed interval is r = k(x2 -x1).

Proof. Assume for contradiction that there exists a truthful mechanism f in this setting. For ease of notation, let (x↪ y) denote the location profile (x1↪ x2) and for any such profile, let

denote the endpoints of the allowed interval and let gx↪y = E[♣Xx↪y - lx↪y]♣ denote the expected distance between the facility and the left endpoint lx↪y of the allowed interval. It is easy to see that

Next, consider a location profile (x0↪ y0) (with x0 < y0) and observe that since k < 1, the expected cost of agent with location x0 is gx0↪y0 +(1-k)(y0 -x0)◁2. Now consider the case when the agent with location x0 reports z0 such that

i.e. her report sets x0 as the left endpoint of the allowed interval. In that case, her cost is x0 is gz0↪y0 and since mechanism f is truthful-in-expectation, we have that

Combining (1) and (2), we obtain

Since for any location profile (x0↪ y0), there exists some z0 such that (1+k)z0◁2+(1-k)y0◁2 = x0, Inequality (3) holds for all location profiles. By applying the same argument on the interval (z0↪ y0) and repeating this process by combining the new upper bound with Inequality (3), we obtain gx0↪y0  ai(y0 - x0), where an is given by the recursive relation:

By Equation (4), we have that

As 0  k < 1, there exist some m such that am < 0 and hence gx0↪y0 < 0, contradicting Inequality (1). We conclude that a truthful mechanism for this case does not exist.

By Lemma 4 and Lemma 2, we obtain the following theorem. The proof is simple and omitted due to lack of space.

Theorem 5. Let x be any location profile with n agents and assume without loss of generality that x1  x2  ▷▷▷  xn. For any k 2 [0↪ 1), there does not exist a truthful mechanism such that it always holds that

Next, we consider intervals that are the same with the interval defined by the agents' reports.

Lemma 5. Let (x1↪ x2) be any location profile with two agents and assume without loss of generality that x1  x2. For any k > 1, and for any truthful mechanism f such that

i.e. the length of the allowed interval is r = k(x2 -x1), the approximation of f is at least 1◁(1 + k) - ✏ for any ✏ > 0.

Proof. Since O(x) = 0 in the case of two agents, it suffices to prove that for any truthful mechanism f, the worst case maximum envy of the mechanism over all profiles is at least 1◁(1 + k) - ✏, for any ✏ > 0. Assume by contradiction that there exists a truthful mechanism f such that for any input profile (x1↪ x2), it holds that

Again, we will denote the profile (x1↪ x2) by (x↪ y). Let

denote the expected distance between the facility and the midpoint of the interval [xi↪ yi] for some location profile (xi↪ yi).

First, we argue that there exists a profile (x0↪ y0) (with x0 < y0), for which A0 ≥ (y0 - x0)◁4. Let (x↪ y) be any profile and observe that one agent (say the agent at location y) has cost at least (y -x)◁2. Then, consider the profile (x↪ y0 ), with y0 = 2y - x, i.e. y is the midpoint of the new interval; by truthfulness, the expected distance between the facility and the midpoint should be at least (y - x)◁2 = (y0 - x)◁4. A similar argument also appears in [Procaccia and Tennenholtz, 2009] (Theorem 3.4).

Let pi = Pr(Xxi↪yi 62 [xi↪ yi]) denote the probability that the facility is placed outside the interval [xi↪ yi] and let

denote the expected distance between the facility and the midpoint of the interval [xi↪ yi], conditioned on the fact that Xxi↪yi lies in the interval. Similarly, let

denote the expected distance between the facility and the midpoint of the interval, conditioned on Xxi↪yi lying outside the interval. By the definition of the maximum envy, it holds that

By the restriction of the facility location to the allowed interval, we have Eout 0  k(y0 -x0)◁2. Then

Let Ex i = E[(♣Xxi↪yi -xi♣ ♣ Xxi↪yi 62 [xi↪ yi])] denote the expected distance between the facility and xi conditioned on the fact that Xxi↪yi lies outside the interval and also let Ey i = E[(♣Xxi↪yi - yi♣ ♣ Xxi↪yi 62 [xi↪ yi])] denote the expected distance between the facility and yi conditioned on that Xxi↪yi lies outside the interval. We have that

By (7) and (8), we get that

Without loss of generality, we can assume that

By (6) and (9), we have

Now consider the location profile (x1↪ y1), with x1 = 2x0 - y0 and y1 = y0. Then, by truthfulness of mechanism f, it must hold that

By steps similar to the ones above, we get that

We can use this method to obtain the sequence (x0↪ y0)↪ (x1↪ y1)↪ ▷▷▷↪ (xm↪ ym)▷ For each input profile,

By (10) and (11), we get that

Note that bi is an increasing and bounded sequence, and the limit of bi is k◁2. By the same argument, we conclude that the limit of ai is 1◁(1 + k). Thus, there exists m such that

truthful-in-expectation mechanism f with worst case maximal envy less than 1◁(1 + k) - ✏.

When the allowed interval is the location profile, we have the following lemma and the following theorem.

Lemma 6. Let (x1↪ x2) be any location profile with two agents and assume without loss of generality that x1  x2. For any truthful mechanism f such that it is always the case that f(x) 2 [x1↪ x2], the approximation of f is at least 1◁2.

Theorem 6. Let x be any location profile with n agents and assume without loss of generality that x1  x2  ▷▷▷  xn. For any k > 1 and any truthful mechanism f such that it always holds that

the approximation of f is at least 1◁(1 + k) - ✏ for any ✏ > 0. Furthermore, for any truthful mechanism g such that g(x) 2 [x1↪ xn], the approximation of g is at least 1◁2.

We omit the proofs due to lack of space. For an appropriate choice of ↵, we can construct a mechanism in the class ↵- LRM that always outputs a valid location within the interval; for k ≥ 1, we can set ↵ = 1◁2(1 + k) and the approximation of f will then be at most 1◁(1+k)-O(x)◁(1+k)  1◁(1+ k). By Theorem 6, the mechanism is optimal among truthful mechanisms.

4.2 Fixed interval

In this subsection, we consider the setting where the allowed interval is fixed and the most preferred positions of the agents, as well as the set of their reports lie in this interval. This corresponds to scenarios where the facility location is constrained by physical borders and agents are asked to choose their most preferred points within these restrictions. For example, when planning to build a university library, it makes sense to assume that the library will be built within the university campus and the participants should only specify their preferences over locations present within the premises.

Recall that the approximation of any mechanism in the class ↵-LRM is at most 2↵ - 2↵O(x). For ↵ = 1◁4, we obtained the LRM mechanism which has an approximation of at most 1◁2. Due to lack of space, we only state the theorem that establishes the upper bound on any truthful mechanism.

Theorem 7. Let f be any truthful-in-expectation mechanism for n agents and let I = [0↪ 1] be the fixed interval. Then the approximation of f is at least 1◁3 - ", for any " > 0.

5 Conclusion

The minimax envy is an alternative criterion for the quality of truthful facility location mechanisms and future work could adopt the same approaches that have be popularized in other objectives in facility location literature, like studying more general metric spaces or multiple facilities. Finally, our work adds to the existing work on fair division on the minimax objective and offers a new natural setting on which the objective can be applied. It would be interesting to apply the same objective to other domains, in combination with truthfulness.

Acknowledgments

Qingpeng Cai and Pingzhong Tang were supported by the National Basic Research Program of China Grant 2011CBA00300, 2011CBA00301, the NSFC Grant 61033001, 61361136003, 61303077, a Tsinghua Initiative Scientific Research Grant and a National Youth 1000-talent program. Aris Filos-Ratsikas was supported by the ERC Advanced Grant 321171 (ALGAME) and acknowledges support from the Danish National Research Foundation and The National Science Foundation of China (under the grant 61061130540) for the Sino-Danish Center for the Theory of Interactive Computation, within which this work was performed and the Center for Research in Foundations of Electronic Markets (CFEM), supported by the Danish Strategic Research Council.