Strategy Proof Mechanisms for Facility Location
in Euclidean and Manhattan Space

The facility location problem captures many real world problems such as locating hospitals, telephone exchanges, ambulances, post offices or playgrounds. Beyond geographical domains, there are a range of other real world problems modeled by facility location problems such as choosing tax-rates, room temperatures, or members of a committee. The facility location problem has attracted researchers from a range of areas including AI, operations research and social choice (e.g. (Drezner and Hamacher 2002; Escoffier et al. 2011; Procaccia and Tennenholtz 2013; Feigenbaum and Sethuraman 2015; Golowich, Narasimhan, and Parkes 2018)). Our goal here is to design strategy proof mechanisms that elicit the true locations of a set of agents and use this information to locate one or more facilities to serve the agents fairly and efficiently. In particular, we look to minimize the total or maximum distance of the agents from the facility serving them. These are respectively an utilitarian or egalitarian welfare objective.

In previous work on mechanism design for facility location problems, researchers have often limited their attention to the one dimensional problem, locating facilities on a line (e.g. (Procaccia and Tennenholtz 2013)). This captures a number of real world settings such as locating distribution centres along a motorway, or sewage plants along a river. However, many real world problems have two (or more) dimensions, and use metrics such as Euclidean or Manhattan distances. This focus on one dimensional problems has been justified as a starting point to consider more complex settings (e.g., trees and networks), and as it may provide insight into these more complex settings (e.g. lower bounds for 1-d problem are inherited by 2-d problem). Our contribution here is to suggest caution in such arguments. We show, for example, that many Pareto optimal and strategy proof mechanisms do not lift from 1-d to 2-d space. The extra freedom provided by an additional dimension can make it harder to achieve desirable axiomatic properties like Pareto optimality and strategy proofness.

We have $n$ agents located in 2-d space, and want to locate $m$ facilities to serve all $n$ agents. Agent $i$ is at location $(x_{i},y_{i})$. Distances are either Euclidean or Manhattan: $d((x,y),(u,v))=\sqrt{(x-u)^{2}+(y-v)^{2}}$ or $d((x,y),(u,v))=|x-u|+|y-v|$. The extension of the problem to higher dimensions is straightforward, while the restriction to 1-d space simply requires setting all y-coordinates to zero. In this case, we suppose agents are ordered so that $x_{1}\leq\ldots\leq x_{n}$. An agent is served by the nearest facility, and a solution is a location $(u_{j},v_{j})$ for each facility $j$. We let $a_{i}\in[1,m]$ be the facility serving agent $i$. We consider an utilitarian welfare objective of the total distance, $\sum_{i=1}^{n}d((x_{i},y_{i}),(u_{a_{i}},v_{a_{i}}))$ and an egalitarian welfare objective of the maximum distance, $\mbox{\rm max}_{i=1}^{n}d((x_{i},y_{i}),(u_{a_{i}},v_{a_{i}}))$. The goal is to locate facilities to minimize one of these two distances.

We consider a number of mechanisms for the facility location problem. Given a fixed order over the agents, the SD mechanism is a serial dictatorship that allocates the first facility to the location of the first agent, and subsequent facilities to the next agent in order at a new location. In the 1-d problem, the Percentile mechanism is a family of mechanisms with parameters $p_{1}$ to $p_{m}$ that locate facility $j$ at $x_{1+\lfloor p_{j}(n-1)\rfloor}$ for $j\in[1,m]$. For instance, with $m=1$, the Leftmost mechanism has $p_{1}=0$, the Median mechanism has $p_{1}=\frac{1}{2}$, and the Rightmost mechanism has $p_{1}=1$. And, with $m=2$, the EndPoint mechanism, which locates facilities at the left and rightmost agents, has $p_{1}=0$ and $p_{2}=1$. The $d$-dimensional Percentile mechanism picks an orthogonal set of $d$ axes and applies a Percentile mechanism to each axis. For example, the 2-dimensional Median mechanism picks an orthogonal set of axes, and applies the Median mechanism to each axis.

In many facility location problems, facilities may also have capacity constraints (e.g. (Brimberg et al. 2001; Aziz et al. 2019, 2020)). A telephone exchange can connect at most a fixed number of houses, a kindergarten has places for only a given number of children, a doctor’s practice can serve just a limited number of patients, etc. Therefore, we also consider an extension of the facility location problem that includes capacity constraints. This extension was previously studied in (Aziz et al. 2019, 2020). In this capacitated setting, the $j$th facility can serve up to $c_{j}$ agents. We assume that $n\leq\sum_{j=1}^{m}c_{i}$ so that every agent can be served. One special setting we consider is when there is no spare capacity (i.e. $\sum_{j=1}^{m}c_{j}=n$). Another special setting we consider is when facilities are identical (i.e. $c_{i}=c_{j}$ for all $i<j)$. A solution in the capacitated setting is now both a location $(u_{j},v_{j})$ for each facility $j$, and an assignment of agents to facilities such that the capacity constraint on each facility is not exceeded. Agents no longer have to be served by their nearest facility. Let $N_{j}$ denote the set of agents assigned to facility $j$, i.e., $N_{j}=\{i|a_{i}=j\}$. Then the capacity constraints ensure $|N_{j}|\leq c_{j}$ for all $j\in[1,m]$. The goal in the capacitated setting is to locate facilities and assign agents to facilities to minimize either the total or maximum distance.

We consider three desirable axiomatic properties of mechanisms for facility location: anonymity, strategy proofness and Pareto optimality. Anonymity is a simple but fundamental fairness property that requires all agents to be treated the same. Pareto optimality is a simple efficiency property that is one of the most fundamental normative properties in the whole of economics. It demands that we cannot make one agent better off without making other agents worse off. Finally, strategy proofness is a fundamental game theoretic property that ensures there is no incentive for agents to act strategically by mis-reporting their location.

More formally, a mechanism is anonymous iff permuting the agents does not change the solution. It is not hard to see that the SD mechanism is not anonymous, but that any Percentile mechanism is. A mechanism is Pareto optimal iff it returns solutions that are always Pareto optimal. A solution is Pareto optimal iff there is no other solution in which one agent travels a strictly shorter distance, and every other agent travels the same or shorter distance to the facility serving them. For example, the SD mechanism is Pareto optimal. A mechanism is strategy proof iff agents cannot improve the solution by mis-reporting their location (i.e. no agent can mis-report and reduce the distance to travel to the facility serving them). For example, the $d$-dimensional Percentile mechanism is strategy proof with any parameters (Theorem 3 in (Sui, Boutilier, and Sandholm 2013)).

Finally, we will consider how well a mechanism approximates the optimal possible welfare. A mechanism achieves an approximation ratio $\rho$ for the total (maximum) distance iff the total (maximum) distance in any solution it returns is at most $\rho$ times the optimal. In this case, we say that the mechanism $\rho$-approximates the optimal total (maximum) distance. For example, in 1-d space, any Percentile mechanism such as the Leftmost  mechanism 2-approximates the optimal maximum distance (Procaccia and Tennenholtz 2013).

We begin with one of the simplest possible settings: a single uncapacitated facility in Euclidean space. This is a setting in which several insightful results are already known about strategy proof mechanisms.

We next consider strategy proof mechanisms for locating two or more uncapacitated facilities in Euclidean space. There is less known about this setting than about two or more facilities in one dimensional Euclidean space, or about a single facility in an Euclidean space of two or more dimensions. Our results here are somewhat negative. We first prove a strong impossibility theorem: when locating two or more facilities in Euclidean space, we cannot simultaneously achieve anonymity, Pareto optimality and strategy proofness.

We contrast this impossibility result with the 1-d setting where anonymity, Pareto optimality, strategy proofness and good approximation ratios are all simultaneously achievable. In particular, when locating two facilities on the line, the EndPoint mechanism is anonymous, Pareto optimal and strategy proof, and has good approximation ratios for the total and maximum distances (Procaccia and Tennenholtz 2013). It is somewhat disappointing then that, when we move from two facilities in 1-d Euclidean space to two facilities in 2-d Euclidean space, we can no longer simultaneously achieve these desirable axiomatic properties.

We also contrast this impossibility result with the setting of a single facility in the Euclidean plane where anonymity, Pareto optimality, strategy proofness and good approximation ratios are again all simultaneously achievable provided we have an odd number of agents. In particular, the two-dimensional Median mechanism satisfies all these desirable axiomatic properties. Note that Theorem 3 continues to hold in the Euclidean plane with just an odd (or just an even) number of agents. It is again somewhat disappointing then that, when we move from one facility in the Euclidean plane to two facilities in the Euclidean plane, we can no longer simultaneously achieve these desirable axiomatic properties.

We next consider dropping in turn anonymity, Pareto optimality and strategy proofness. If we drop anonymity, there are multiple mechanisms for locating two or more facilities in Euclidean space that are Pareto optimal and strategy proof but not anonymous. For example, any SD mechanism is Pareto optimal and strategy proof but not anonymous. Similarly, if we drop Pareto optimality, there are multiple mechanisms that are anonymous and strategy proof but not Pareto optimal (e.g. any multi-dimensional Percentile  mechanism with parameters $p_{i}=p_{j}$ for all $i$ and $j$). And if we drop strategy proofness, there are multiple mechanisms that are anonymous and Pareto optimal but not strategy proof. Consider, for example, the mechanism that picks some orthogonal set of coordinate axes, then orders agents by $x$-coordinate, tie-breaking by $y$-coordinate, and locates the first facility at the position of the first agent in this order, and subsequent facilities at the position of the next agent in the order at a new location. We therefore conclude that anonymity, Pareto optimality and strategy proofness are a minimal combination of incompatible axioms for locating two or more facilities in Euclidean space.

We now consider how well strategy proof mechanisms can approximate the optimal welfare when locating multiple facilities in Euclidean space. For instance, can we bound the approximation ratio for the maximum or total distance?

When locating two facilities on the line, the only deterministic, anonymous and strategy proof mechanism with a bounded approximation ratio for the total distance is the EndPoint mechanism (Theorem 3.1 in (Fotakis and Tzamos 2013)). Recall that the EndPoint mechanism is an instance of the Percentile mechanism with $m=2$, $p_{1}=0$ and $p_{2}=1$. The EndPoint mechanism also provides a 2-approximation of the optimal maximum distance. Again, this is optimal as no deterministic and strategy proof mechanism can have a better approximation ratio (Corollary 4.4 of (Procaccia and Tennenholtz 2013)). In fact, the EndPoint mechanism is not just optimal in terms of the approximation ratio of the maximum distance. It is the only Percentile mechanism for locating two uncapacitated facilities on the line with a bounded approximation ratio for the maximum distance (Anonymous 2021).

We therefore consider next welfare bounds for multi-dimensional Percentile mechanism when locating two or more facilities in Euclidean space. It is known that in Euclidean space the multi-dimensional Percentile mechanism for two or more uncapacitated facilities has an unbounded approximation ratio for the total distance (Theorem 4 in (Sui, Boutilier, and Sandholm 2013)). Can we do better in approximating the maximum distance? This is certainly the case in 1-dimension where we can approximate the maximum distance better than the total distance. Specifically, with any mechanism on the line that is deterministic and strategy proof, the optimal approximation ratio for the total distance is $n-2$, but for the maximum distance is just 2 (Fotakis and Tzamos 2013). We prove next that, in Euclidean space, multi-dimensional Percentile mechanisms cannot do better at approximating the maximum distance than they can at approximating the total distance.

We consider two facilities in two dimensions. The proof easily generalizes to more facilities and more dimensions. There are three cases. In the first case, neither of the two facilities is at a location corresponding to parameters $(1,1)$. That is, neither of the two facilities is at $(x_{max},y_{max})$ where $x_{max}$ and $y_{max}$ are the maximum reported $x$ and $y$ coordinates. Let $p_{max}$ be the largest parameter less than 1, and $n=\lceil\frac{3}{1-p_{max}}\rceil$. Consider $n-1$ agents at $(0,0)$ and one at $(1,1)$. The optimal maximum distance is zero with a facility at $(0,0)$ and one at $(1,1)$. However, the Percentile mechanism returns a solution with both facilities at $(0,0)$, and maximum distance of $\sqrt{2}$. In the second case, one of the facilities is at a location corresponding to parameters $(1,1)$ and the other is at a location corresponding to $(p_{1},p_{2})$ where at least one $p_{i}$ is non-zero. Let $p_{max}$ be the maximum of $p_{1}$ and $p_{2}$, and $n=\lceil\frac{3}{p_{max}}\rceil$. Consider $n-1$ agents at $(1,1)$ and one at $(0,0)$. The optimal maximum distance is zero with a facility at $(0,0)$ and one at $(1,1)$. However, the Percentile mechanism returns a solution with one facility at $(1,1)$, and the other not at $(0,0)$. This solution has a maximum distance of $\sqrt{2}$. In the third case, one of the facilities is at a location corresponding to parameters $(0,0)$ and the other is at a location corresponding to parameters $(1,1)$. Consider one agent at $(0,1)$ and the other at $(1,0)$. The optimal maximum distance is zero with a facility at each agent, but the Percentile mechanism returns a solution with a maximum distance of 1. $\diamond$

We next consider the impact of capacity constraints on facility location in Euclidean space. We might hope to design mechanisms with stronger axiomatic properties in the capacitated setting than the uncapacitated setting for at least two reasons. The first reason is that adding capacity limits requires us to allocate agents to particular facilities, and this may reduce the opportunity for agents to be strategic. For example, in a general metric space, the randomized Proportional mechanism is not strategy proof with three or more agents but becomes so when we make it winner imposing (Fotakis and Tzamos 2010).

A second reason we might do better in the capacitated setting in Euclidean space is that, with multiple uncapacitated facilities, irrespective of whether the total number of agents is even or odd, one facility might need to serve an even number of agents, and no mechanism in Euclidean space is anonymous, Pareto optimal and strategy proof with an even number of agents (Peters et al. 1992). On the other hand, in the capacitated setting, we can limit ourselves to situations in which the capacity of each facility is an odd number. Recall that in the Euclidean plane with an odd number of agents, there exists an unique mechanism to locate a single uncapacitated facility that is anonymous, Pareto optimal and strategy proof (Peters et al. 1992).

Unfortunately, this hope is not realized. We prove another strong impossibility theorem: no mechanism for locating two or more capacitated facilities in Euclidean space can simultaneously be anonymous, Pareto optimal and strategy proof even limited to facilities with an odd capacity.

We suppose that we have two facilities of capacity $c$. There are two cases. If $c$ is even, say $c=2k$ with $k>1$, we consider $2k$ agents in the box between $(0,0)$ and $(1,1)$, and another $2k$ agents at $(100,100)$. Any anonymous and Pareto optimal mechanism locates one facility at $(100,100)$ serving the agents at this location, and the other in the box between $(0,0)$ and $(1,1)$. Suppose the agents at $(100,100)$ are fixed. Then essentially we have a single facility location problem on the remaining $2k$ agents. Theorem 4.1 in (Peters et al. 1992) demonstrates that no mechanism is anonymous, Pareto optimal and strategy proof for an even number of agents in two dimensional Euclidean space. This proof continues to hold if the agents are limited to a small box such as between $(0,0)$ and $(1,1)$. Note that an agent cannot profitably mis-report their location as $(100,100)$. To ensure anonymity and Pareto optimality, the mechanism must then locate both facilities at $(100,100)$ which puts the facility serving this agent at a greater distance. A sincere report locates the facility within the convex hull of the leftmost $2k$ agents which is nearer to their true location than $(100,100)$. Hence, there is no mechanism for two facilities with even capacity in the Euclidean plane that is anonymous, and Pareto optimal and strategy proof.

If $c$ is odd, say $c=2k+1$ with $k\geq 1$, we consider $2k+1$ agents at $(0,0)$, and another $2k+1$ agents at $(100,100)$. Any anonymous and Pareto optimal mechanism locates one facility at $(0,0)$ and the other at $(100,100)$. Suppose the agents at $(100,100)$ are fixed. Then essentially we have a single facility location problem on the remaining $2k+1$ agents. Theorem 3.1 in (Peters et al. 1992) demonstrates that any mechanism in this setting that is anonymous, Pareto optimal and strategy proof is a multi-dimensional Median mechanism. Whatever orthogonal coordinate axes we take, this puts the leftmost facility at $(0,0)$. Suppose one agent at $(0,0)$ is moved along the diagonal towards the $2k+1$ agents at $(100,100)$. The two facilities remain immobile at $(0,0)$ and $(100,100)$. Consider now the agent arriving at $(100,100)$. By anonymity over the $2k+2$ agents now at $(100,100)$ and Pareto optimality, both facilities must be at $(100,100)$. This contradicts the leftmost facility remaining at $(0,0)$. This contradiction means that our initial assumption, that an anonymous, Pareto optimal and strategy proof mechanism exists, is false. For $m$ facilities with $m>2$, we consider an additional $(m-2)c$ agents at $(200,200)$. $\diamond$

An interesting open case is four agents and two identical facilities with no space capacity. Is there an anonymous, Pareto optimal and strategy proof mechanism for this setting?

We contrast this last impossibility result with the 1-d setting. For facility location on the line, anonymity, Pareto optimality and strategy proofness can simultaneously be achieved. In particular, with two identical and capacitated facilities on the line, provided there is no spare capacity, the InnerPoint mechanism is anonymous, Pareto optimal and strategy proof and has good approximation ratios for the total and maximum distance (Aziz et al. 2020).

Finally, we consider dropping in turn anonymity, Pareto optimality and strategy proofness. By similar arguments to case of strategy proof mechanisms for locating multiple uncapacitated facilities in Euclidean space, we can show that there are multiple mechanisms satisfying just two of these axioms. It follows then that anonymity, Pareto optimality and strategy proofness are a minimal combination of incompatible axioms for locating two or more capacitated facilities in two or more dimensional Euclidean space.

We conclude by switching from Euclidean to Manhattan distances. We might hope to achieve stronger axiomatic properties with Manhattan distances as these are somewhat “closer” to the one dimensional setting, and strategy proof mechanisms are somewhat “easier” to construct on the line. Unfortunately, this is not the case.

For a single facility on the line, any mechanism that is anonymous, Pareto optimal and strategy proof is a generalized median mechanism (Moulin 1980). Barbera et al. (Barberà, Gul, and Stacchetti 1993) lifted this result to Manhattan distances in two or more dimensions. In particular, they prove that any strategy proof mechanism on $m$ dimensions can be decomposed coordinate wise into strategy proof mechanisms that act on the $m$ coordinates individually. What if we additionally demand Pareto optimality? We prove a strong characterization result: with Manhattan distances and two or more dimensions, mechanisms can only be anonymous, strategy proof and Pareto optimal iff there are three or fewer agents.

For two agents, consider a mechanism which sets each coordinate of the facility to be the max (or the min) of the two reported coordinates of the two agents. This mechanism is anonymous and strategy proof. To show Pareto optimality, there are two cases. Either the facility is at the location of one of the agents which is clearly Pareto optimal, or it is at an empty vertex of the bounding hypercube around the two facilities. Moving along one coordinate direction towards one agent reduces the Manhattan distance to this agent, but increases the Manhattan distance to the other agent. Hence, the solution is Pareto optimal.

For three agents, consider a mechanism which sets each coordinate to be the median of the three reported coordinates of the three agents. This mechanism is anonymous and strategy proof. To show Pareto optimality, there are two cases. Either the facility is at the location of one of the agents which is clearly Pareto optimal. Or the facility is in the interior of the bounding hypercube around the three facilities. Moving along one coordinate direction towards one agent reduces the Manhattan distance to this agent, but increases the Manhattan distance to at least one of the two other agents. Hence, the solution is Pareto optimal. $\diamond$

We now consider a four agent problem made up of these three agents and one other. By Theorem 2 in (Barberà, Gul, and Stacchetti 1993), any strategy proof mechanism in two dimensions is a coordinate-wise combination of strategy proof mechanisms. By (Moulin 1980), it must be a coordinate-wise combination of generalized median voting schemes. We can shift our original three voters in the box bounded by $(0,0)$ and $(2,2)$ so that they are well away from any “phantom” voters. Hence, any strategy proof mechanism for our four agents picks out the $j$th ranked $x$-coordinate and the $k$th ranked $y$-coordinate for some $j,k\in[1,4]$. Suppose $j=1$ and $k=2$. Then place the fourth agent at $(3,0)$. Our strategy proof mechanism then locates the facility at the minimum $x$-coordinate and minimum $y$-coordinate of the original three agents. That is, it locates the facility at $(0,0)$. This is Pareto dominated by the mechanism that locates the facility at $(1,1)$. Similar constructions show that any other parameters $j$ and $k$ also return solutions that are Pareto dominated. Hence, no mechanism for four agents in two dimensions is anonymous, strategy proof and Pareto optimal. The proof extends to five or more agents by placing additional agents at appropriate boundary positions. $\diamond$

A similar impossibility result for locating multiple facilities in Manhattan space quickly follows: there is no anonymous, strategy proof and Pareto optimal mechanism for locating $m$ uncapacitated facilities ($m\geq 2$) and $m+3$ or more agents in Manhattan space.

We next consider dropping in turn anonymity, Pareto optimality and strategy proofness. If we drop anonymity, there are multiple mechanisms for locating one or more facilities in Manhattan space that are Pareto optimal and strategy proof but not anonymous. For example, any SD mechanism is Pareto optimal and strategy proof but not anonymous. Similarly, if we drop Pareto optimality, there are multiple mechanisms for Manhattan space that are anonymous and strategy proof but not Pareto optimal (e.g. any multi-dimensional Percentile  mechanism with parameters $p_{i}=0$ for all $i$). And if we drop strategy proofness, there are multiple mechanisms that are anonymous and Pareto optimal but not strategy proof. Consider again the mechanism that orders agents by $x$-coordinate, tie-breaking by $y$-coordinate, and locates the first facility at the position of the first agent in this order, and subsequent facilities at the position of the next agent in the order at a new location. We therefore conclude that anonymity, Pareto optimality and strategy proofness are a minimal combination of incompatible axioms for locating one or more facility in two or more dimensional Manhattan space.

We end with some discussion about welfare bounds. In particular, we consider welfare bounds for multi-dimensional Percentile mechanism when locating one or more facility in Manhattan space. Recall that such mechanisms are anonymous and strategy proof. We suppose the mechanism chooses axes that align with those used to compute Manhattan distances. We first observe that lower bounds on approximation ratios for facility location in Manhattan space can be inherited from lower bounds on approximation ratios for facility location on the line (e.g. those bounds in (Procaccia and Tennenholtz 2013)). Hence, with a single facility, no deterministic and strategy proof mechanism is better than a 2-approximation for the maximum Manhattan distance. In fact, with a single facility, the multi-dimensional Median mechanism is optimal with respect to both the total and the maximum Manhattan distances. No deterministic and strategy proof mechanism provides better approximation ratios.

When locating more facilities in Manhattan space, approximation becomes more challenging. In particular, with two or more uncapacitated facilities in two or more dimensions, no multi-dimensional Percentile mechanism has a bounded approximation ratio for the total Manhattan distance (Theorem 4 in (Sui, Boutilier, and Sandholm 2013)). It follows quickly that no multi-dimensional Percentile mechanism has a bounded approximation ratio for the maximum Manhattan distance (using the same argument as in the proof of Theorem 4).

We contrast these results with the 1-d setting. With a single facility, approximation ratios are the same in 1-d as 2-d Manhattan space. With two facilities on the line, the EndPoint mechanism has bounded approximation ratios for the total and maximum distances. When we move to 2-d Manhattan space, the approximation ratios become unbounded. With three or more facilities, approximation ratios are unbounded whether we are in 1-d or 2-d Manhattan space. In general, moving from 1-d to 2-d Manhattan space, tends to increase approximation ratios for the total or maximum distance. We also contrast results for Manhattan space with those for Euclidean space. With a single facility, the 2-dimensional Median mechanism is optimal with respect to the total Manhattan distance but is just a $\sqrt{2}$-approximation of the optimal Euclidean distance. In other settings we observe similar approximation ratios for Manhattan as Euclidean distances (e.g. with two or more facilities and multi-dimensional Percentile  mechanisms, approximation ratios are unbounded in both Euclidean and Manhattan space).

A number of specific mechanisms have been proposed with good axiomatic properties that will locate multiple facilities in two or higher dimensional space. With two facilities and any type of metric space, Lu et al. prove that the randomized Proportional mechanism is strategy proof and 4-approximates the total distance (proportional). With three or more facilities, they note that this mechanism is no longer strategy proof. With any fixed number $m$ of facilities ($m\geq 1)$ and any type of metric space, Fotakis and Tzamos prove that the winner imposing version of the Proportional  mechanism is strategy proof and achieves an approximation ratio for the total distance of at most $4m$ (Fotakis and Tzamos 2010). Finally, with $n-1$ facilities and $n$ agents and any type of metric space, Escoffier et al. prove that the randomized InverselyProportional  mechanism is strategy proof and an $n/2$-approximation for the total distance and an $n$-approximation for the maximum distance (Escoffier et al. 2011).

We have studied the impact on strategy proof mechanisms for facility location when moving from one dimension to two (or more) dimensions with Euclidean or Manhattan distances. We considered two additional axiomatic properties: anonymity which is a fundamental fairness property, and Pareto optimality which is a fundamental efficiency property. We also consider how well such mechanisms can approximate the optimal welfare. Our results are somewhat negative. Moving from one dimension to two (or more) dimensions often makes these axiomatic properties more difficult to achieve. For example, with two facilities in Euclidean space or with just a single facility in Manhattan space, no mechanism is anonymous, Pareto optimal and strategy proof. By contrast, in one dimension when locating up to two facilities on the line, there exists mechanisms that are anonymous, Pareto optimal and strategy proof. As a second example, with two facilities in Euclidean space no Percentile mechanism has a bounded approximation ratio for the total or maximum distance. By contrast, when locating up to two facilities on the line, there exists Percentile mechanisms that bound these approximation ratios. Indeed, such mechanisms can have optimal approximation ratios. All our impossibility results are minimal. If we drop one of the three axioms (anonymity, Pareto optimality or strategy proofness) multiple mechanisms satisfy the other two axioms. For example, when locating two facilities in Euclidean space, there exist multiple mechanisms that are anonymous and Pareto optimal, that are anonymous and strategy proof, and that are Pareto optimal and strategy proof.