{'fraction_non_alphanumeric': 0.059628840888348036, 'fraction_numerical': 0.013203529053848494, 'mean_word_length': 3.892245869921119, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 14, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Coordinate-wise Median: Not Bad, Not Bad, Pretty Good

We consider the facility location problem in two dimensions. In particular, we consider a setting where agents have Euclidean preferences, defined by their ideal points, for a facility to be located in R2. For the minisum objective and an odd number of agents, we show that the coordinate-wise median mechanism (CM) has a worst-case approximation ratio (AR) of √ 2 √ n+1 n+1 . Further, we show that CM has the lowest AR for this objective in the class of deterministic, anonymous, and strategyproof mechanisms. For the p − norm social welfare objective, we find that the AR for CM is bounded above by 2 3 2 − 2 p for p ≥ 2. Since any deterministic strategyproof mechanism must have AR at least 2 1− 1 p (Feigenbaum et al. [12]), our upper bound suggests that the CM is (at worst) very nearly optimal. We conjecture that the approximation ratio of coordinate-wise median is actually equal to the lower bound 21− 1 p (as is the case for p = 2 and p = ∞) for any p ≥ 2.


Introduction
We consider the problem of locating a facility on a plane where a set of strategic agents have private preferences over the facility location. Each agent's preferences are defined by their ideal point so that the cost incurred by an agent equals the Euclidean distance between the facility location and the ideal point. A central planner wishes to locate the facility to minimize the social cost. Since agents may lie about their ideal points if it benefits them, the planner is constrained to choose a mechanism that is strategyproof. In this environment, the only mechanism that is strategyproof and satisfies some other desirable properties like anonymity and Pareto optimality is the coordinate-wise median mechanism [Peters et al. [26]]. This paper investigates how well the coordinate-wise median mechanism approximates the optimal social cost for the p-norm objective and if it is the best deterministic strategyproof mechanism using the measure of worst-case approximation ratio.
For the utilitarian social objective of minimizing the sum of individual costs and n odd, we show that the coordinate-wise median mechanism has an approximation ratio of √ 2 √ n 2 +1 n+1 . Using the simple structure of the worst case profile and a characterization by Peters et al. [24], we also show that no other deterministic, anonymous and SP mechanism has a better approximation ratio. For the case where the social cost function is the p-norm of individual costs, with p ≥ 2, we find that the AR for the coordinate-wise median mechanism is bounded above by 2 3 2 − 2 p . Since it follows from Feigenbaum et al. [12], who considers the facility location problem on a real line, that any strategyproof mechanism must have AR at least 2 1− 1 p , our upper bound suggests that the coordinate-wise median mechanism is (at worst) very nearly optimal. We conjecture that the approximation ratio of coordinate-wise median is actually equal to the lower bound 2 1− 1 p (as is the case when p = 2 or p = ∞). If the conjecture is true, it would imply that coordinate-wise median is the best deterministic strategyproof mechanism for p-norm objective.
This problem has been extensively studied in the literature known as Approximate Mechanism Design without money. It was first introduced by Procaccia and Tennenholtz [27] who studied the setting of locating a single facility on a real line under the utilitarian (sum of individual costs) and egalitarian (maximum of individual costs) objectives. Since then, the problem has received much attention, with extensions to alternative objective functions, multiple facilities, obnoxious facilities, different networks, etc. Cheng and Zhou [8] and more recently, Chan et al. [7] provide surveys of results in the last decade in several of these settings. In the class of deterministic strategyproof mechanisms for locating a facility, the median mechanism has been shown to be optimal under various objectives and domains [Procaccia and Tennenholtz [27], Feigenbaum et al. [12], Feldman and Wilf [14], Feldman et al. [13]].
There has been some related work in extending the problem to multiple dimensions. Meir [22] shows that in the d-dimensional Euclidean space, the approximation ratio of the coordinate-wise median mechanism for the utilitarian objective is bounded above by √ d. In the same setting, El-Mhamdi et al. [11] find that the mechanism choosing the optimal location (geometric median) is approximately strategyproof in a large economy. In two dimensions, Walsh [32] shows that there is a lower bound on the approximation ratio of any deterministic and strategyproof mechanism. Meir [22], using techniques different from ours, finds the AR of coordinate-wise median mechanism for the case of 3 agents. Gershkov et al. [17] shows that for some natural priors on the ideal points (that include i.i.d. marginals), taking the coordinate-wise median after a judicious rotation of the orthogonal axes can lead to welfare improvements under the least-squares objective. In other related work, Durocher and Kirkpatrick [10] and Bespamyatnikh et al. [3] analyse approximations to geometric median due to its instability and computational difficulty; Sui et al. [30] propose percentile mechanisms for locating multiple facilities in Euclidean space which are further analysed in Sui and Boutilier [29] and Walsh [32] for the minisum and the minimax objectives.
There is also a large literature in social choice theory on characterizing the set of strategyproof mechanisms under different assumptions on preference domains [Gibbard [18], Satterthwaite [28], Moulin [23]]. In multiple dimensions with Euclidean preferences, the characterizations typically include or are completely described by the coordinate-wise median mechanism [Kim and Roush [19], Border and Jordan [5], Peters et al. [24], Peters et al. [26]]. The strong axiomatic foundations of the coordinate-wise median mechanism, together with the nice properties of the median in one dimension, motivate our study of the coordinatewise median mechanism against the optimal mechanism in two dimensions under a variety of social cost functions.
The paper proceeds as follows. In section 2, we formally define the problem and state some characterisation results and approximation results from the literature that will be useful in our analysis. In section 3 and 4, we discuss the problem of finding the approximation ratio of coordinate-wise median mechanism for the utilitarian objective and the p-norm objective (p ≥ 2). In section 5, we investigate how the coordinate wise median mechanism compares against other deterministic SP mechanisms in terms of worst-case approximation ratio for the utilitarian and p norm objective. Section 6 concludes.
To measure how closely a mechanism approximates the optimal social cost, we use the worst-case approximation ratio. Definition 2.3. The worst-case approximation ratio (AR) of a mechanism f for the objective given by sc is the smallest γ such that for any x ∈ X n , Given a metric space (X, d) and a social cost function sc, the problem is to find a strategyproof mechanism that best approximates the optimal social cost.
In this paper, we consider the Euclidean metric space with X = R 2 . The social cost function is the L p norm of the vector of distances sc(y, We refer to the coordinates of points in R 2 by a and b. We refer to the sets R × {0} and {0} × R as the a-axis and the b-axis, respectively. We refer to the sets ±R ≥0 ×{0} and {0} ×±R ≥0 as the ±a-axes and ±b-axes, respectively. We use the notation [yz] to denote the line segment joining y and z: {ty+(1−t)z : t ∈ [0, 1]}. Similarly, we denote by (y, z) the set [yz]\{y, z}.
Our analysis makes use of some previous results regarding characterization of strategyproof mechanisms and bounds on approximation ratios in the Euclidean domain. We collect those results here.

Characterisation results in two dimensions
First, let's define an important class of mechanisms in this domain.
Definition 2.4. In the Euclidean metric space with X = R m , a mechanism f is called a generalized coordinatewise median voting scheme with k constant points if there exists a coordinate system and points c 1 , c 2 , . . . , c k ∈ (R ∪ {−∞, ∞}) m so that for every profile x ∈ (R m ) n and every j = 1, 2, . . . , m, f j (x) := med x j 1 , x j 2 , . . . , x j n , c j 1 , . . . , c j k where"med" denotes the median of the subsequent real numbers, and all coordinates are expressed with respect to the given coordinate system.
This class of mechanisms has strong axiomatic foundations in the literature as illustrated in the following lemma: Lemma 1 (Kim and Roush [19], Peters et al. [26,24]). In the Euclidean metric space with X = R 2 and an odd number of agents, a mechanism f : (R 2 ) n → R 2 is • [19] continuous, anonymous, and strategyproof if, and only if, f is a coordinate-wise median voting scheme with n + 1 constant points.
• [24] unanimous, anonymous, and strategyproof if, and only if, f is a coordinate-wise median voting scheme with n − 1 constant points.
• [26] Pareto optimal, anonymous, and strategyproof if, and only if, it is a coordinatewise median voting scheme with 0 constant points.
We refer to the coordinate-wise median voting scheme with 0 constant points and the standard coordinate-system as the coordinate-wise median mechanism and denote it by c(x). We denote by a c (·) and b c (·) the coordinates of c(·), so that c(x) = (a c (x), b c (x)).

Approximation results in two-dimensions
For the case of X = R 2 with the Euclidean metric, there has been some work in finding bounds on AR for the utilitarian objective sc(y, x) = y − x i . We discuss those findings here.
A point minimizing the sum of distances from a finite set of points in R 2 is known as a geometric median for that set of points. The geometric median is characterised by the following result: Lemma 2. Given x ∈ (R 2 ) n , a point y ∈ R 2 is a geometric median for x if and only if there are vectors u 1 , . . . , u n such that where for x i = y, u i = x i −y x i −y and for x i = y, u i ≤ 1. This characterisation yields conditions under which changing a profile of points does not change the geometric median, as summarized in the following corollary: Corollary 3. Let x ∈ X n , and denote by y the geometric median of x. For any i, if x i = y and if x ′ i ∈ {y + t(x i − y) | t ∈ R ≥0 }, then the geometric median for the profile (x ′ i , x −i ) is also y.
Informally, moving a point directly away from or directly towards (but not past) the geometric median leaves the geometric median unchanged. We will use this observation repeatedly in the sequel and note here that in fact it will be the only characteristic of the geometric median that we use for much of the paper. We refer to the geometric median by g(x). We use the notation a g (x) and b g (x) to denote the first and second coordinates of g(x), respectively.
It follows from Lemma 1 that the geometric median mechanism is not strategyproof. Meir [22] finds an upper bound on the AR of coordinate-wise median in the m dimensional problem: Lemma 4 (Meir [22]). For X = R m and the utilitarian objective sc(y, x) = y − x i , the coordinate-wise median mechanism has an approximation ratio of at most √ m for any number of agents n.
Feigenbaum et al. [12] consider the facility location problem for X = R and d( Lemma 5 (Feigenbaum et al. [12]). For X = R and the p norm objective sc(y, x) = [ |y − x i | p ] 1 p , the median mechanism has an approximation ratio of 2 1−1/p . Further, any strategyproof deterministic mechanism has approximation ratio of at least 2 1−1/p .
Since this case is included in our analysis of the facility location in a plane, we get a lower bound on the AR of any deterministic strategyproof mechanism: Corollary 6. For the Euclidean metric space with X = R 2 and the p norm objective p , any strategyproof deterministic mechanism has an approximation ratio of at least 2 1−1/p .

The minisum objective
In this section, we consider the objective sc(y, x) = ( n i=1 y − x i ). Assume that n is odd 1 and so the geometric median is unique. Consider the geometric median mechanism, which chooses the geometric median g(x) at any profile x. Since this mechanism is anonymous, pareto optimal, and not a coordinate-wise median voting scheme, it follows from Lemma 1 that it is not strategyproof.
This leads to the question of how well a strategyproof mechanism might approximate the geometric median. We consider the coordinate-wise median mechanism as a good candidate and investigate the problem of finding its approximation ratio.
Theorem 7. For n odd, the worst-case approximation ratio for the coordinate-wise median mechanism is given by: The argument for obtaining the exact value of AR(CM) is rather involved. We provide a full proof for the case that n = 3 as we find the approach taken in its proof to be simple enough to be digestible yet sufficiently similar to the more nuanced approach required for arbitrary odd n as to be illuminating. We then provide a sketch of the proof for all odd n, relegating the formal proof for this case to the appendix.
In both the n = 3 case and the general case, the key to the proof is to reduce the search space for the worst-case profile from (R 2 ) n to a much smaller space of profiles that have a simple structure. In many cases, this involves "transforming" one profile into another profile that has a higher approximation ratio and a simpler structure. One important transformation that helps in significantly reducing the search space involves moving a point x i directly towards g(x), getting as close as possible to g(x) without changing c(x). Because this transformation will be used repeatedly throughout this section, we provide here a proof that this transformation leads to a profile (x ′ i , x −i ) with a weakly higher approximation ratio.
Lemma 8 (Towards geometric median). Let x be a profile and i ∈ N, and let x ′ be any profile such that .
The change in optimal social cost is given by Thus, the sc(OP T (·), ·) reduces by a greater amount than sc(CM(·), ·) as we move x i to x ′ i . Since the ratio is always at least 1, it follows that AR(x ′ ) ≥ AR(x).
3.1 Proof for n = 3 case Corollary 9. For n = 3, the worst-case approximation ratio for the coordinate-wise median mechanism is given by: Remark 10. There is a more explicit characterisation of geometric median when n = 3. In this case, if any angle of the triangle formed by the three points is at least 120 o , g(x) lies on the vertex of that angle; otherwise, it is the unique point inside the triangle that subtends an angle of 120 o to all three pairs of vertices Proof of Theorem 7 for n = 3. Define the set of Centered perpendicular (CP) profiles as follows: In words, a profile is in CP if the coordinate-wise median is at the origin and all points in x are on the axes. Define the set of Isosceles-centered perpendicular (I-CP) profiles as follows: I − CP = {x ∈ CP : ∃t such that x = ((t, 0), (−t, 0), (0, 1)) and g(x) = (0, 1)} In words, a profile is in I − CP if there are two points on the a-axis equidistant from the origin and the third point is at (0, 1), which is also the geometric median.
We first show that we can reduce the search space for the worst-case profile from (R 2 ) 3 to CP .
. Then x ′ has the same approximation ratio as x and c(x ′ ) = (0, 0). Denote A = {i : a i = 0} and Proof. Let x be a profile in CP .
Without loss of generality, we may assume that all x i are weakly above the a-axis and there are at least two x i on the a-axis, since reflecting a profile in CP across the a-axis, the b-axis, or the line a = b gives a profile in CP with the same approximation ratio. Hence, we can label the points such that If c = 0, then AR(x) = 1, and so every profile has approximation ratio weakly greater than x. Hence, we may further assume that c > 0.
Since x 1 and x 2 are on the a-axis, it follows from the characterization of the geometric median for three points given in remark 10 that −a ≤ a g (x) ≤ b and 0 ∩ Γ is non-empty because g(x ′ ) cannot be in the same quadrant as x ′ i . Any point in the same quadrant as x ′ i subtends an angle of less than 90 o with the other two points and hence it cannot be the Torricelli point. moving x 3 to g(x) then (if necessary) translating all points by the same vector so that the coordinate-wise median is at the origin yields a profile in CP which has higher approximation ratio. Hence, we may further assume that g(x) = x 3 . Let x ′ be the profile where x ′ 1 = (−(a + b)/2, 0), x ′ 2 = ((a + b)/2, 0), and x ′ 3 = (0, c). By definition, sc(g(x ′ ), x ′ ) ≤ sc(g(x), x ′ ) and by an argument that exploits the convexity of the distance function, sc(g(x), x ′ ) ≤ sc(g(x), x). Combining these inequalities gives sc(g(x ′ ), x ′ ) ≤ sc (g(x), x), and a simple calculation shows that sc(c(x ′ ), Note that under x ′ , g(x ′ ) = (0, k) for some k ≤ c. Define x ′′ to be the profile with , 0), and x ′′′ 3 = (0, 1) for some t ≥ 0; in fact, it follows from the characterisation of the geometric median that t ≥ √ 3. Hence, x ′′′ ∈ I − CP , and so taking χ = x ′′′ completes the proof.
Denote by η t = ((t, 0), (−t, 0), (0, 1)). It follows from the arguments in the proof of In particular, it follows that the approximation ratio of coordinate-wise median mechanism is equal to sup t≥ √ 3 α(t). Since α(t) achieves its global

Proof sketch for general n
Proof sketch. We now consider the case of n = 2m + 1 agents. We begin by defining classes of profiles analogous to those used in the proof for n = 3. We define the class of Centered Perpendicular (CP) profiles as all profiles x ∈ (R 2 ) n such that Since the last condition is slightly more subtle than the others and will be important in the sequel, we describe it now in words. This condition says that any (nonzero) movement of any x i towards the geometric median would result in a change in the coordinate-wise median.
We define the class of Isosceles-Centered Perpendicular (I-CP) profiles as all x ∈ CP for which there exists t ≥ 0 such that The proof proceeds much as in the proof for n = 3. We first show that for every profile, there is some profile in CP with weakly higher approximation ratio. The approach used in the n = 3 case extends naturally here: first, translate the profile x ∈ (R 2 ) n so that coordinate-wise median moves to the origin; then, starting from i = 1 and going to i = n, move x i directly towards the geometric median until either it reaches the geometric median or moving it further would move the coordinate-wise median. The resulting profile is in CP and has an approximation ratio that is weakly greater than x's. Next, we show that for any profile in CP , there is some profile in I − CP with weakly higher approximation ratio. The approach used in the n = 3 case for this step does not extend in a straightforward manner to the general case-the main obstruction arises from the fact that for a profile x in CP , there may be i ∈ N such that x i = g(x), which may not be on either axis. The next subsection is devoted to giving an overview of the procedure used to transform a profile in CP to one in I − CP with weakly higher approximation ratio.
Finally, the approach used to calculate the worst-case approximation ratio for profiles in I − CP has much the same structure as in the n = 3 case. We define η t = (x t 1 , . . . , x t 2m+1 ), where 2m−1 , AR(η t ) = α(t), and that α(t) has a global maximum at t * = m+1 m > 2m+1 2m−1 , from which it follows that

Reduction from CP to ICP
In this subsection, we discuss informally some transformations that allow us to deal with the profiles in CP . Without loss of generality (using reflections if necessary as in the n = 3 case), we may restrict consideration to profiles x ∈ CP with g(x) = (a g , b g ) such that a g ≥ 0, b g ≥ 0, and b g ≥ a g .

1.
Reducing axes: In this step, we move all points on −b-axis to −a-axis while keeping them equidistant from c(x) = (0, 0). This works because the sc(c(·), ·) remains the same while sc(g(·), ·) reduces, as the points move closer to the old geometric median. Thus, we get a profile in which all points are either on one of the +a-, +b-, or −a-axes or at g(x).

2.
Convexity: Consider a profile obtained after applying step 1. Transform the profile so that all points on the +a-, +b-, and −a-axes are at their mean coordinates on the +a-, +b-, and −a-axes respectively. Again, sc(c(·), ·) remains the same while sc(g(·), ·) falls because of convexity of the distance function. Thus, we get a profile with weakly higher approximation ratio which has k points at (−b, 0), m + 1 − k points at (0, c), m + 1 − k points at (a, 0) and k − 1 points at g(x). Note that we are able to pin down the exact cardinalities of these sets because of the third condition in the definition of CP , which requires that if any of the points were to move towards g(x), then c(x) would change.
3. Double Rotation: Consider a profile obtained after applying step 2. Transform the profile by moving the k − 1 points at g(x) to (0, α), where α = d(c(x), g(x)), and moving k − 1 of the k points at (−b, 0) to (β, 0), where β is the unique positive number such that d(g(x), (β, 0)) = d(g(x), (−b, 0)). In this case, one can show that the increase in sc(c(·), ·) is at least √ 2 times the increase in sc(g(·), ·) and therefore, by Lemma 4, it follows that the approximation ratio weakly increases. Applying convexity again, we get a profile such that there is one point at (−b, 0), m points at (0, c) and m points at (a, 0). Note that g(x) may still not be on the axes. 4. Geometric to axis: Consider a profile obtained after applying step 3. Transform the profile so that the m points at (0, c) are at g(x), then translate all points by the same amount so that the coordinate-wise median is back to the origin. Doing so weakly increases the approximation ratio and yields a profile where one point is at (−b, 0), m points are at (0, c), m points are at (a, 0) and g(x) = (0, c).
From here, we apply a transformation similar to step 2 to get a profile in I − CP . Note that we have suppressed some details (especially when the same transformation must be used repeatedly) in order to make the exposition as clear as possible-see the appendix for a rigorous proof.

p-norm objective
In this section, we consider the problem of quantifying the approximation ratio for the coordinate-wise median mechanism under the p-norm objective sc(y, for p ≥ 2 when agents have ideal points in R 2 .
Theorem 13. For the p-norm objective with p ≥ 2, The lower bound follows directly from Corollary 6. For the upper bound, note that it follows from Lemma 5 that, if a c is the median of (a 1 , a 2 , . . . , a n ) and OP T (a) is the optimal location, then n i=1 a c − a i p ≤ 2 p−1 n i=1 OP T (a) − a i p . The upper bound is then obtained by using the following inequalities, together with Lemma 5: The proof is relegated to the appendix.

Is coordinate-wise median the best deterministic SP mechanism?
In this section, we aim to compare the performance of the coordinate-wise median mechanism against other strategyproof mechanisms. For the case p = 1, which corresponds to the minisum objective, we have the following result: Theorem 14. For X = R 2 and sc(yx) = y−x i (minisum objective), CM has the lowest approximation ratio among all deterministic, anonymous and strategyproof mechanisms.
We note that our proof of Theorem 14 makes heavy use of the worst case profile w derived in Theorem 7. Specifically, the proof uses the characterisation of Peters et al. [24] in Lemma 1 and shows that for any coordinate-wise median voting scheme with n − 1 constant points f , we can find a profile w ′ , where w ′ i = w i + θ for some fixed θ ∈ R 2 , such that Then, we show that for any of these six locations, we can find a profile which is the same as w up to translation and reflection, and whose AR for the mechanism under consideration is at least as high as AR(CM).
Proof. Suppose f is any deterministic, strategyproof, anonymous mechanism. If f is not unanimous, it follows that its AR is unbounded. So suppose it is unanimous. Using Lemma 1, we know then that f is defined by points p 1 , p 2 , . . . , p n−1 such that f (x) = c(x, p).
For p = 1, the worst case profile w defines six important points which are P figure 5.
Observe that if f (w) / ∈ P , there exists some θ ∈ R 2 such that f (w + θ) ∈ P + θ. Thus, without loss of generality, we restrict attention to the case where f (w) ∈ P and show that no matter which point f chooses under w in P , we can find a profile x ′ such that m , 0)}. This is same as the previous case and hence, we get that for p = 1, there is no deterministic, strategyproof, anonymous and unanimous mechanism with a better AR than the coordinatewise median mechanism. The result for the minisum case (p = 1) follows. For general p ≥ 2, we are able to show quantitatively that CM can not be much worse than the optimal deterministic strategyproof mechanism. As we show in Theorem 13, AR(CM) for the p-norm is bounded above by 2 Since the ratio of upper bound on AR(CM) and this lower bound on any deterministic SP mechanism is at most √ 2 for p ≥ 2, it follows that for such p no deterministic strategyproof mechanism has a worst-case approximation ratio that is better than CM by more than a factor of √ 2. This implies that the coordinate-wise median mechanism is already very close to being optimal. While Theorem 13 gives bounds on AR(CM) for arbitrary p, more precise results follow directly for p = 2 and p = ∞ from previous work in the one-dimensional setting [Procaccia and Tennenholtz [27], Feigenbaum et al. [12]]. Even though these results extend in a straightforward way, we are not aware of anyone stating them explicitly, and so we mention them here for completeness.
For p = 2, the upper and lower bound for CM mechanism in Theorem 13 coincide and together with Corollary 6, we get the following: 1 2 (miniSOS objective or p = 2 case), the worst case approximation ratio of coordinate-wise median mechanism is √ 2. In addition, any deterministic SP mechanism has AR at least √ 2.
For p = ∞, any deterministic strategyproof mechanism has AR ≥ 2. Also, any pareto optimal mechanism has AR ≤ 2. Together, we get Corollary 16. For X = R 2 and sc(y, x) = max i y −x i (minimax objective or p = ∞ case), the worst case approximation ratio of coordinate-wise median mechanism is 2. In addition, any deterministic SP mechanism has AR at least 2.
The last Corollary suggests that the upper bound in Theorem 13 is not tight. In fact, the AR of CM is actually equal to its lower bound in both cases p = 2 and p = ∞. This leads us to conjecture that: Conjecture 17. For X = R 2 , and the p-norm objective sc(y, p where p ≥ 2, the coordinate wise median mechanism has AR = 2 1− 1 p and no other deterministic strategyproof mechanism has a lower approximation ratio.
If it is indeed the case that for any p, the AR of CM is equal to its lower bound in theorem 13, it would follow from Corollary 6 that CM is actually the best deterministic SP mechanism for the p − norm objective for any p ≥ 2.

Conclusion
We show that the utilitarian cost of the coordinate-wise median is always within of the utilitarian cost obtained under the optimal mechanism. Using the worst-case profile, we further show that no deterministic, anonymous, and strategyproof mechanism can do better. For the p-norm objectives, we find that the worst-case approximation ratio for the coordinate-wise median mechanism is bounded above by 2 Since the worst-case approximation ratio for any deterministic strategyproof mechanism is bounded below by 2 1− 1 p (from Feigenbaum et al. [12]'s analysis in one dimension), it follows that the coordinate-wise median mechanism is within a factor of √ 2 of being optimal. For the case of p = 2 and p = ∞, the coordinate-wise median has AR equal to √ 2 and 2, respectively. This leads us to conjecture that the approximation ratio of CM is actually equal to 2 1− 1 p for any p ≥ 2. If the conjecture is true, it would imply that CM is the best deterministic SP mechanism for this objective.
We hope that the results and methods in this paper will encourage further research in this fundamental domain. The question of how well a randomized mechanism might approximate the social cost of the geometric median remains open. A potentially good candidate is the mechanism that chooses a coordinate-wise median after a uniform rotation of the orthogonal axes. While its analysis seems hard in general, finding its AR on the worst-case profile in Theorem 7 might give a useful lower bound. Another question is to close the gap between the upper bound on AR of the coordinate wise median mechanism and the lower bound on AR of any deterministic SP mechanism for the p norm objective. The analysis for more general single-peaked preferences in multi-dimensional domains also remains open.

A Proofs for Section 3 (The minisum objective)
Proof. of theorem 7 Define Centered Perpendicular (CP) profiles as all profiles x ∈ (R 2 ) n such that Lemma 18 (CP). For any profile x ∈ (R 2 ) n , there exists a profile χ ∈ CP such that AR(χ) ≥ AR(x).
Proof. Let x ∈ (R 2 ) n be a profile. Let x ′ be the profile where Define Isosceles-Centered Perpendicular (I-CP) profiles as all x ∈ CP for which there exists t ≥ 0 such that • g(x) = (0, 1).
Next, we prove some lemmas that will be useful in reducing the search space for the worst-case profile from CP to I − CP .
First, we show that we can reduce the number of half-axes that the points lie on from (at most) four to (at most) three. Proof. Again c(x ′ ) = c(x) and sc(c(x ′ ), x ′ ) = sc(c(x), x). Thus, it is sufficient to show that sc(g(x ′ ), x ′ ) ≤ sc(g(x), x). For this, we just need to show that d( ). This follows from the following simple calculation: Next, we show that we can combine points on each of the three half-axes while weakly increasing the approximation ratio.
Lemma 20 (Convexity). Let x ∈ CP and let S ⊆ N be such that for all i ∈ S, a i > 0 and b i = 0. Let x S be the mean of the x i across i ∈ S. Let x ′ be the profile where Then AR(x ′ ) ≥ AR(x).
Proof. It is immediate that c(x ′ ) = c(x). Hence, it will be sufficient to show that AR for x ′ with c(x) and g(x) instead of c(x ′ ) and g(x ′ ) is at least as big as AR(x). Indeed, sc(c(x), x ′ ) = sc(c(x), x)) and sc(g(x ′ ), x ′ ) < sc(g(x), x ′ ) < sc(g(x), x) where the last inequality follows from convexity of the distance function.
The same argument applies for any of the other strict half axes. Next, we show that we can move all the points that are on the geometric median to the axis in a way that weakly increases the approximation ratio.
Proof. The first claim is immediate. For the second claim, let By a previous result, Hence, it follows that . Hence, From this it follows that and hence Once we have all the points on the three half-axes, we now show that we can move the geometric median to the axis as well.
Finally, the following lemma shows that we can use convexity to make the triangle formed by the three groups of points isosceles. Proof. Note that c(x) = c(x ′ ) = (0, 0). Since m * a + b = m * (ma+b) m+1 + ma+b m+1 , we get that the numerator in AR(x) and AR(x ′ ) remains the same. Thus, we only need to argue that the denominator goes down as we go from AR(x) to AR(x ′ ).
Even though g(x ′ ) may not be equal to g(x) we have that sc(g(x), x ′ ) ≤ sc(g(x), x) by the convexity of the distance function which would imply sc(g(x ′ ), x ′ ) ≤ sc(g(x), x) by definition of g(x). Thus, we have that AR(x ′ ) ≥ AR(x). Now, we use above lemmas to reduce the search space to I-CP.
Proof. Without loss of generality, consider any profile x ∈ CP such that b g (x) ≥ a g (x) ≥ 0. Applying Lemma 19 to all points on the negative b axis gives a profile x ′ with a weakly higher approximation ratio. In x ′ , we have all points on positive a, negative a, positive b and the geometric median. Using lemma 20, we can combine the points on positive a, negative a, positive b to some (a, 0), (0, b), (−c, 0) while weakly increasing AR. Let this profile be x ′′ . Now, we use lemma 21 to move points on the geometric median to +b-axis. Using 20 again, we get a profile x ′′′ with m points on some (a, 0), 1 point on (−c, 0) and m points on (0, b). Now we use lemma 22 to move the geometric median to the axis. Then, we use lemma 23 which gives a profile x ′′′ such that x ′′′′ ∈ I − CP and AR(x ′′′′ ) ≥ AR(x). Setting χ = x ′′′′ completes the proof.
Thus, we get that the worst case approximation ratio is √ 2 √ n 2 + 1 n + 1 as required.

B Proofs for Section 4 (p-norm objective)
Proof. of Theorem 13 Consider any profile x = (a i , b i ) ∈ (R 2 ) n . Let g(x) = (a g (x), b g (x)) and c(x) = (a c (x), b c (x)). Then, we have that