Proof. For any realized facility location \(y \in \mathbb{R}^d\), the sum of the Euclidean distances to the vertices of \(S\) is minimized at the geometric median, which for a regular simplex coincides with its circumcenter \(O\). Because the distance from \(O\) to each of the \(d+1\) vertices is \(1\), the minimum possible sum of distances is \(d+1\). Thus, for any \(y \in \mathbb{R}^d\), we have the bound: \[\label{eq:median95bound} \sum_{k=0}^d d(y, x_k) \ge \sum_{k=0}^d d(O, x_k) = d+1.\tag{1}\] Taking the expectation over the randomness of the mechanism \(\mathcal{M}\), by linearity of expectation we obtain: \[\sum_{k=0}^d \mathbb{E}\left[d(Y, x_k)\right] = \mathbb{E}\left[ \sum_{k=0}^d d(Y, x_k)\right] \ge d+1.\] Because the sum of these \(d+1\) expected distances is bounded below by \(d+1\), at least one term in the sum must be at least 1. Therefore, there exists an index \(j \in \{0, \dots, d\}\) such that \(\mathbb{E}[d(Y, x_j)] \ge 1\). ◻

Proof. We construct a sequence of profiles \(\boldsymbol{x} = \boldsymbol{x}^0, \boldsymbol{x}^1, \dots, \boldsymbol{x}^k = \boldsymbol{x}',\) where for each \(i \in \{1, \dots, k\}\), \(\boldsymbol{x}^i\) is the profile obtained after \(i\) agents have changed their report from \(u\) to their respective misreported location in \(\boldsymbol{x}'.\)

Consider the transition from profile \(\boldsymbol{x}^{i-1}\) to \(\boldsymbol{x}^i.\) The only difference between these two profiles is that a single agent, whose true location is \(u\), changes their reported location. Because the mechanism \(\mathcal{M}\) is strategyproof in expectation, this agent cannot decrease their expected distance to their true location \(u\) by misreporting, i.e., \(\mathbb{E}[d(\mathcal{M}(\boldsymbol{x}^i), u)] \ge \mathbb{E}[d(\mathcal{M}(\boldsymbol{x}^{i-1}), u)].\) Chaining these inequalities for all \(i \in \{1, 2, \dots, k\}\), we obtain: \[\mathbb{E}[d(\mathcal{M}(\boldsymbol{x}'), u)] = \mathbb{E}[d(\mathcal{M}(\boldsymbol{x}^k), u)] \ge \dots \ge \mathbb{E}[d(\mathcal{M}(\boldsymbol{x}^0), u)] = \mathbb{E}[d(\mathcal{M}(\boldsymbol{x}), u)].\] ◻

Proof. Consider the unit sphere \(C_O = S^{d-1}\) in \(\mathbb{R}^d\) centered at the origin \(O = (0, \dots, 0)\). Let \(S\) be a regular simplex inscribed in \(S^{d-1}\), defined by \(d+1\) vertices \(x_0, x_1, \dots, x_d\), where we orient the simplex such that \(x_0 = (1, 0, \dots, 0)\). Because the circumradius of \(S\) is \(1\), the distance from the origin to any vertex is \(d(O, x_k) = 1\) for all \(k \in \{0, 1, \dots, d\}\). The uniform side length of this regular simplex is given by \(a_d = \sqrt{2 + \frac{2}{d}}\). Therefore, the pairwise distance is \(d(x_j, x_k) = a_d\) for all \(j \neq k\). See Figure 1 for an illustration of the construction for \(d = 2\).

Let \(n\) be a multiple of \(d+1\). Consider an initial profile \(\boldsymbol{x}\) of \(n\) agents equally distributed among the \(d+1\) vertices of \(S\). Let \(Y = \mathcal{M}(\boldsymbol{x})\) denote the random facility location chosen by the mechanism. Applying Lemma 1 to the vertices of the regular simplex \(S\), the expected distance from the facility to at least one of these vertices is at least \(1\). Without loss of generality, assume this holds for \(x_0\), i.e., \[\label{eq:lower95bound95x0} \mathbb{E}\left[d(Y, x_0)\right] \ge 1.\tag{2}\]

We now construct a sequence of modified profiles \(\boldsymbol{x}'\) as \(n \to \infty\). Let \(C_{x_0}\) be the \((d-1)\)-sphere centered at \(x_0\) with radius \(a_d\). Observe that all other vertices \(x_1, \dots, x_d\) inherently lie on \(C_{x_0}\) because \(d(x_0, x_k) = a_d\). We modify the profile by having the agents originally located at \(x_0\) uniformly deviate over the surface of \(C_{x_0}\).

Let \(Y' = \mathcal{M}(\boldsymbol{x}')\). By Lemma 2, a simultaneous deviation by the subset of agents from their true location \(x_0\) to the boundary of \(C_{x_0}\) cannot decrease their expected distance to \(x_0\). Applying 2 , we obtain: \[\mathbb{E}[d(Y', x_0)] \geq \mathbb{E}[d(Y, x_0)] \geq 1.\]

To evaluate the egalitarian cost of \(\mathcal{M}\) on \(\boldsymbol{x}'\), consider any realized facility location \(y'\). The supremum distance from \(y'\) to any point on the sphere \(C_{x_0}\) is achieved by extending the line segment from \(y'\) through the center \(x_0\) to the far boundary. This supremum is exactly \(d(y', x_0) + a_d\). As \(n \to \infty\), the discretely distributed deviating agents densely populate \(C_{x_0}\), and the maximum distance to any agent in the profile converges to this supremum: \[\lim_{n \to \infty} \max_{i \in [n]} d(y', x'_i) = d(y', x_0) + a_d.\]

Taking the expectation, the asymptotic expected egalitarian cost of the mechanism is bounded below by:

\[\lim_{n \to \infty} \mathrm{MC}(\mathcal{M}(\boldsymbol{x}'), \boldsymbol{x}') = \lim_{n \to \infty} \mathbb{E}\left[\max_{i \in [n]} d(Y', x'_i)\right] = \mathbb{E}[d(Y', x_0)] + a_d \ge 1 + a_d.\]

Since the optimal egalitarian cost for the modified profile \(\boldsymbol{x}'\) is \(\mathrm{OPT}(\boldsymbol{x}') = a_d\), the asymptotic approximation ratio is at least: \[\frac{1 + a_d}{a_d} = 1 + \frac{1}{a_d} = 1 + \frac{1}{\sqrt{2 + \frac{2}{d}}} = 1 + \sqrt{\frac{d}{2(d+1)}}.\] ◻

Proof. Let \(\boldsymbol{x}\) and \(\boldsymbol{x}'\) be as defined above. By Lemma 1, the expected distance from the facility to at least one of these vertices is at least \(1\). Without loss of generality, assume \(\mathbb{E}[d(\mathcal{M}(\boldsymbol{x}), x_1)] \ge 1\).

Let \(R = d(\mathcal{M}(\boldsymbol{x}'), x_1)\) be the random variable corresponding to the distance from \(x_1\) to the facility location \(\mathcal{M}(\boldsymbol{x}')\). By strategyproofness, agent 1 cannot decrease their expected distance to their true location by misreporting: \[\mathbb{E}[R] \ge \mathbb{E}[d(\mathcal{M}(\boldsymbol{x}), x_1)] \ge 1.\]

By Lemma [lem:min95cost], for a fixed value of \(R\), the maximum distance from any realized facility to the agents in \(\boldsymbol{x}'\) is bounded below by \(L(R)\). Applying Jensen’s inequality to the convex function \(L\), the expected maximum cost for the reported profile \(\boldsymbol{x}'\) is bounded by: \[\mathrm{MC}(\mathcal{M}(\boldsymbol{x}'), \boldsymbol{x}') \ge \mathbb{E}[L(R)] \ge L(\mathbb{E}[R]) \ge L(1) = \sqrt{4 + \lambda}.\]

Dividing this expected cost by the optimal cost for \(\boldsymbol{x}'\) we obtain a lower bound of \(\frac{\sqrt{4 + \lambda}}{\sqrt{3}} \approx 1.277\) for the approximation ratio. This lower bound extends to \(n > 3\) by co-locating any additional agents at the origin and applying the same argument. ◻

Proof. We establish the two claims of the theorem separately.

Approximation Ratio. For any profile \(\boldsymbol{x} = (x_1, x_2)\), the mechanism outputs \(L = m + \boldsymbol{v}\), where \(m = \frac{x_1 + x_2}{2}\) and \(\|\boldsymbol{v}\| = h\). For any vector \(\boldsymbol{v}\) sampled from the orthogonal sphere \(S^\perp\), we have \(\langle m - x_1, \boldsymbol{v} \rangle = 0\). By the Pythagorean theorem, the distance from the facility to Agent 1 is: \[\|L - x_1\| = \sqrt{\|m - x_1\|^2 + \|\boldsymbol{v}\|^2} = \sqrt{h^2 + h^2} = h\sqrt{2}.\] By symmetry, the distance to Agent 2 is also \(\|L - x_2\| = h\sqrt{2}\). Since the optimal egalitarian cost is \(h\), the approximation ratio evaluates to exactly \(\frac{h\sqrt{2}}{h} = \sqrt{2}\).

Strategyproofness. Without loss of generality, by translating and rotating the coordinate system, we can set \(x_1 = (-R, 0, \dots, 0)\) and \(x_2 = (R, 0, \dots, 0)\) for \(R \ge 0\). This gives an expected distance of \(h\sqrt{2} = R\sqrt{2}\) to the facility for both agents. To establish strategyproofness, it suffices to show that any deviation by Agent 1 results in an expected distance of at least \(\sqrt{2}R\) from the facility to him.

Because the mechanism’s configuration is rotationally symmetric around the line between \(x_1\) and \(x_2\), any misreported location can be rotated into the \(xy\)-plane without loss of generality. Thus, we assume Agent 1 misreports to a location \[x_1' = (-R + \delta_x, \delta_y, 0, \dots, 0).\] The mechanism computes the reported midpoint \(m = (\frac{\delta_x}{2}, \frac{\delta_y}{2}, 0, \dots, 0)\) and a reported radius \(h\) satisfying \(h^2 = (R - \frac{\delta_x}{2})^2 + (\frac{\delta_y}{2})^2\). It then samples a vector \(\boldsymbol{v} = (v_x, v_y, \dots, v_d) \in S^\perp\). Since \(\boldsymbol{v}\) must be orthogonal to the vector \(x_2 - x_1' = (2R - \delta_x, -\delta_y, 0, \dots, 0)\), its components must satisfy: \[\label{eq:orthogonality95identity} v_y \delta_y = (2R - \delta_x)v_x.\tag{3}\]

Pairing every sampled vector \(\boldsymbol{v}\) with its antipodal counterpart \(-\boldsymbol{v}\), the corresponding squared distances from the true location \(x_1\) are: \[D_{\pm} = \|(m \pm \boldsymbol{v}) - x_1\|^2 = \|m - x_1\|^2 + \|\boldsymbol{v}\|^2 \pm 2\langle m - x_1, \boldsymbol{v} \rangle.\] Using \(m - x_1 = (R + \frac{\delta_x}{2}, \frac{\delta_y}{2}, 0, \dots, 0)\) and \(\|\boldsymbol{v}\|^2 = h^2\), expanding the norm gives: \[\|m - x_1\|^2 + h^2 = 2R^2 + \frac{\delta_x^2}{2} + \frac{\delta_y^2}{2}.\] For the inner product, substituting the identity 3 into the expression gives: \[\langle m - x_1, \boldsymbol{v} \rangle = v_x\left(R + \frac{\delta_x}{2}\right) + v_y\left(\frac{\delta_y}{2}\right) = v_x\left(R + \frac{\delta_x}{2}\right) + v_x\left(R - \frac{\delta_x}{2}\right) = 2Rv_x.\]

Combining these terms gives \(D_{\pm} = 2R^2 + \frac{\delta_x^2}{2} + \frac{\delta_y^2}{2} \pm 4R v_x\). This can be rewritten as: \[D_+ = 2\left[ (R + v_x)^2 + z^2 \right] \quad \text{and} \quad D_- = 2\left[ (R - v_x)^2 + z^2 \right],\] where \(z = \sqrt{\frac{\delta_x^2 + \delta_y^2}{4} - v_x^2}\). To guarantee that \(z\) is a well-defined real number, note that \(v_x^2 + v_y^2 \le h^2\). Isolating \(v_y\) via 3 results in \(v_x^2 [ 1 + (2R - \delta_x)^2/\delta_y^2 ] \le h^2\), which simplifies using the definition \(4h^2 = (2R - \delta_x)^2 + \delta_y^2\) to show that: \[v_x^2 \le \frac{\delta_y^2}{4} \le \frac{\delta_x^2 + \delta_y^2}{4}.\]

These expressions have a geometric interpretation in \(\mathbb{R}^2\). Consider the auxiliary points \(p = (v_x, z)\), \(F_1 = (-R, 0)\), and \(F_2 = (R, 0)\). Noting that \(\|p - F_1\|^2 = (R + v_x)^2 + z^2\) and \(\|p - F_2\|^2 = (R - v_x)^2 + z^2\), we can rewrite the paired distances as: \[\sqrt{D_+} = \sqrt{2}\|p - F_1\| \quad \text{and} \quad \sqrt{D_-} = \sqrt{2}\|p - F_2\|.\]

Applying the triangle inequality to these auxiliary points, the average distance of the antipodal pair \(\{\boldsymbol{v}, -\boldsymbol{v}\}\) to Agent 1’s true location is bounded as follows: \[\begin{align} \frac{d(m + \boldsymbol{v}, x_1) + d(m - \boldsymbol{v}, x_1)}{2} &= \frac{\sqrt{D_+} + \sqrt{D_-}}{2} \\ &= \frac{\sqrt{2}}{2} \left( \|p - F_1\| + \|p - F_2\| \right) \\ &\ge \frac{\sqrt{2}}{2} \|F_1 - F_2\| \\ &= \sqrt{2}R. \end{align}\] Because this lower bound holds pointwise for every antipodal pair on the sphere, taking the expectation over the uniform distribution of \(S^\perp\) preserves the inequality: \[\mathbb{E}[d(L, x_1)] = \mathbb{E}\left[\frac{\sqrt{D_+} + \sqrt{D_-}}{2}\right] \ge \sqrt{2}R,\] completing the proof. ◻

Proof. Let \(\mathcal{M}\) denote the mechanism. By translation and scale invariance of \(\mathcal{M}\), we can assume, without loss of generality, the extreme reports are \(l = -1\) and \(r = 1\). We establish the two properties of the mechanism separately:

• Approximation Ratio: The optimal facility location is the origin \((0,0)\), yielding a maximum cost of \(1\). The mechanism \(\mathcal{M}\) outputs \((0,1)\). For any agent \(i\) with \(x_i \in [-1, 1]\), the distance to the output is \(\sqrt{x_i^2 + 1}\), which is maximized at the extremes \(x_i = \pm 1\) with a value of \(\sqrt{2}\). Thus, the approximation ratio is \(\sqrt{2}\).

• Strategyproofness: By the strategyproofness of the 2-agent mechanism (4), the extreme agents \(l\) and \(r\) cannot profit by deviating. Therefore, we only need to consider an interior agent misreporting to become a new extreme.

  Suppose an interior agent is located at \((a, 0)\) with \(a \in [0, 1)\). If the agent reports a new extreme \(z < -1\), the facility shifts to the location \(\left(\frac{z+1}{2}, \frac{1-z}{2}\right)\). The distance from the agent to this new location is \(a - \frac{z+1}{2} > a\) along the \(x\)-axis and \(\frac{1-z}{2} > 1\) along the \(y\)-axis. Since both coordinate-wise distances are larger than the distances to the truthful output facility at \((0,1)\), this deviation is unprofitable. The agent can also define a new extreme by reporting \(z > 1\). This moves the facility to the coordinates \(\left(\frac{z-1}{2}, \frac{z+1}{2}\right)\). For this deviation to be profitable, the squared distance to this new position must be less than the squared distance to the truthful output which gives us the inequality: \[\left(\frac{z-1}{2} - a\right)^2 + \left(\frac{z+1}{2}\right)^2 < a^2 + 1.\] Simplifying reduces this inequality to \(z^2 - 2az + 2a - 1 < 0\), which only holds when \(z \in (2a - 1, 1)\). This contradicts our requirement that \(z > 1\). A symmetric argument holds for an interior agent located at \((a,0)\) with \(a<0\). Thus, \(\mathcal{M}\) is strategyproof.

 ◻

Proof. It suffices to prove the bound for \(n=2\), as it extends to any \(n \ge 2\) via [lem:population95extension2]. For the proof, fix \(x_1=0\) and let \(x_2 = x \in (0, \infty)\). The mechanism’s output defines a curve parameterized by \(x\): \[f(x) := \mathcal{M}(0, x) = (u(x), v(x)).\]

The optimal facility location for this profile is the midpoint \((x/2, 0)\), with a corresponding maximum cost of \(x/2\). Because \(\mathcal{M}\) guarantees a \(\lambda\)-approximation, the squared distance from \(\mathcal{M}(\boldsymbol{x})\) to either agent is bounded by \((\lambda x/2)^2\). For Agents 1 and 2 respectively, this implies: \[\begin{align} d(x_1, \mathcal{M}(\boldsymbol{x})) = u(x)^2 + v(x)^2 &\le \frac{\lambda^2 x^2}{4}, \tag{4} \\ D(x) := d(x_2, \mathcal{M}(\boldsymbol{x})) = (x - u(x))^2 + v(x)^2 &\le \frac{\lambda^2 x^2}{4},\tag{5} \end{align}\] where we defined \(D(x)\) as the squared distance from the point \(x_2 = (x,0)\) to the output of the mechanism \(\mathcal{M}(x_1, x)\).

By strategyproofness, Agent 2 located at \(x\) cannot improve their outcome by misreporting \(y \in (0, \infty)\), meaning \(D(x) \le (x - u(y))^2 + v(y)^2\). To express this in terms of \(D(y)\), we expand the squared term and substitute \(v(y)^2 = D(y) - (y - u(y))^2\): \[\begin{align} D(x) &\le x^2 - 2x u(y) + u(y)^2 + v(y)^2 \\ &= x^2 - 2x u(y) + D(y) - y^2 + 2y u(y) \\ &= D(y) + (x^2 - y^2) - 2u(y)(x - y). \end{align}\] Using the identity \(x^2 - y^2 = (x - y)^2 + 2y(x - y)\), we obtain the upper bound: \[\label{eq:sp95upper} D(x) - D(y) \le (x - y)^2 + 2(x - y)(y - u(y)).\tag{6}\]

Symmetrically, preventing an agent at \(y\) from misreporting \(x\) requires \(D(y) \le (y - u(x))^2 + v(x)^2\). Expanding this similarly yields: \[D(y) \le D(x) + (y^2 - x^2) - 2u(x)(y - x).\] In a similar way, by rearranging the inequality we obtain: \[\label{eq:sp95lower} D(x) - D(y) \ge -(x - y)^2 + 2(x - y)(x - u(x)).\tag{7}\]

Let \([a, b] \subset (0, \infty)\) be an arbitrary compact interval. For any \(z \in [a, b]\), inequality 4 ensures \(|u(z)| \le \frac{\lambda}{2}z \le \frac{\lambda}{2}b\). Dividing 6 and 7 by \(|x - y|\) we get that for any distinct \(x, y \in [a, b]\), the absolute difference quotient is bounded: \[\left| \frac{D(x) - D(y)}{x - y} \right| \le |x - y| + 2|x| + 2|y| + 2|u(x)| + 2|u(y)| \le (b - a) + 4b + 2\lambda b.\] Because for any fixed interval \([a,b] \subseteq (0, \infty)\) this upper bound is a constant, \(D(x)\) is locally Lipschitz on \((0, \infty)\). This implies that for any compact interval \([a,b] \subset (0, \infty)\), \(D(x)\) is absolutely continuous and therefore differentiable almost everywhere (a.e.).

Let \(x\) be a point of differentiability. Dividing 7 by \((x - y)\) and taking the limits as \(y \to x^+\) and \(y \to x^-\) we obtain: \[\label{derivative2} D'(x) = 2(x - u(x)) \quad \text{a.e.}\tag{8}\]

Expanding \(D(x)\) and applying 4 we obtain:

\[\label{stepineq} D(x) = x^2 - 2x u(x) + u(x)^2 + v(x)^2 \le x^2 - 2x u(x) + \frac{\lambda^2 x^2}{4}.\tag{9}\] By the derivative equation 8 , we substitute \(-2x u(x) = -x(2x - D'(x)) = -2x^2 + x D'(x)\) into inequality 9 and obtain: \[D(x) \le x^2 - 2x^2 + x D'(x) + \frac{\lambda^2 x^2}{4} = -x^2 + x D'(x) + \frac{\lambda^2 x^2}{4} \quad \text{a.e.}\] Rearranging terms to group \(D(x)\) and its derivative gives: \[x D'(x) - D(x) \ge x^2\left(1 - \frac{\lambda^2}{4}\right) \quad \text{a.e.}\] Dividing both sides by \(x^2 >0\) we obtain the derivative of a quotient on the left hand side: \[\frac{d}{dx} \left( \frac{D(x)}{x} \right) \ge 1 - \frac{\lambda^2}{4} \quad \text{a.e.}\]

Because \(D(x)\) is absolutely continuous on any compact subset of \((0, \infty)\), the quotient \(D(x)/x\) is absolutely continuous on any interval \([\epsilon, X] \subset (0, \infty)\). Integrating from \(\epsilon\) to \(X\) preserves the above inequality and we obtain: \[\label{integrated} \frac{D(X)}{X} - \frac{D(\epsilon)}{\epsilon} \ge \left( 1 - \frac{\lambda^2}{4} \right)(X - \epsilon).\tag{10}\]

From 5 , we know \(0 \le D(\epsilon) \le \lambda^2 \epsilon^2 / 4\), which implies \(0 \le \frac{D(\epsilon)}{\epsilon} \le \frac{\lambda^2}{4} \epsilon\). Thus, \(\lim_{\epsilon \to 0^+} \frac{D(\epsilon)}{\epsilon} = 0\). Taking this limit, multiplying the resulting inequality 10 by \(X\), and combining it with the original bound 5 we obtain: \[X^2\left(1 - \frac{\lambda^2}{4}\right) \le D(X) \le \frac{\lambda^2 X^2}{4}.\] Dividing by \(X^2\) simplifies to: \[1 - \frac{\lambda^2}{4} \le \frac{\lambda^2}{4},\] which establishes \(\lambda \ge \sqrt{2}\).

It remains to argue that the bound extends to any \(n > 2\). If an \(n\)-agent mechanism achieved an approximation ratio better than \(\lambda\), we could construct a strategyproof 2-agent mechanism preserving this improved bound by having it run the \(n\)-agent mechanism on a profile where the reports \((a,b)\) are padded with \(n-2\) dummy agents co-located at \(b\). The full formal argument for the extension to \(n>2\) can be found in [lem:population95extension2] in the appendix. ◻

Proof. By definition, the mechanism outputs the facility at \(\mathcal{M}(\boldsymbol{x}) = (m_1,\ldots,m_d,h)\) with \(h = \sqrt{\sum_{j \in [d]} r_j^2}\). The squared distance \(D_i^2\) from agent \(i\)’s true location \((x^i_1, \ldots, x^i_d, 0)\) to the facility is: \[D_i^2 = \sum_{j \in [d]} (m_j-x_j^i)^2 + \sum_{j \in [d]} r_j^2.\] We can decouple this into independent terms for each axis: \[D_i^2 = \sum_{j \in [d]} \left((m_j-x_j^i)^2 + r_j^2\right).\] Define \(D_i^2(j) = \left((m_j-x_j^i)^2 + r_j^2\right)\). The term \(D_i^2(j)\) is the squared cost that agent \(i\) would incur if we run the Augmented Midpoint Mechanism with \(\mathcal{I}= \mathbb{R}\) and \(\mathcal{O}= \mathbb{R}^2\) only for the \(j\)-coordinates.

Because the mechanism computes \(m_j, r_j\) using only the \(j\)-coordinates, each misreported coordinate of agent \(i\) independently only affects the corresponding \(D_i^2(j)\) term. By Theorem [thm:augmented:line], the Augmented Midpoint Mechanism is strategyproof, meaning a unilateral deviation cannot decrease the squared cost \(D_i^2(j)\) for each coordinate \(j\). That is \(D_i'^2(j) \ge D_i^2(j)\) where \(D_i'^2(j)\) is the squared cost of agent \(i\) in coordinate \(j\) after deviating. This immediately implies \(D_i^2 = \sum_{j \in [d]} D_i^2(j) \le \sum_{j \in [d]} D_i'^2(j) = D_i'^2\). Thus, the mechanism is strategyproof. ◻

Proof. Note that the optimal facility location \(z \in \mathbb{R}^{d+1}\) is of form \(z = (z_1,\ldots,z_d,0)\) as all reported locations \(x_i\) are of form \((x_1^i,\ldots x_d^i,0)\). Without loss of generality, let the optimal facility location be the origin \((0,\ldots,0)\). Let \(R = \mathrm{OPT}(\boldsymbol{x})\) denote the optimal radius. For every agent \(i\), we have \(\sum_{j \in [d]} (x_j^i)^2 \le R^2\).

Because all agents lie within the optimal ball of radius \(R\), the extreme reports on the axis \(j\) must satisfy \(r_j + |m_j| \le R\). Squaring both sides and rearranging yields \[m_j^2 + r_j^2 \le R^2 - 2r_j|m_j|.\]

The squared distance \(D_i^2\) from agent \(i\) to the facility \(\mathcal{M}(\boldsymbol{x}) = (m_1,\ldots,m_d,h)\) is \[\begin{align} D_i^2 &= \sum_{j \in [d]} (m_j-x_j^i)^2 + \sum_{j \in [d]} r_j^2\\ &= \sum_{j \in [d]} (x^i_j)^2 + \sum_{j \in [d]} (m_j^2 + r_j^2) - 2 \cdot \sum_{j \in [d]} x_j^i m_j. \end{align}\] Plugging in \(\sum_{j \in [d]} (x_j^i)^2 \le R^2\) and \(m_j^2 + r_j^2 \le R^2 - 2r_j|m_j|\) yields \[\label{eq:augmented:d} D_i^2 \le (d+1)R^2 - 2\sum_{j \in [d]} (x_j^i m_j + r_j|m_j|).\tag{11}\] Next, we argue that \((x_j^i m_j + r_j|m_j|) \ge 0\). For each agent \(i\) and coordinate \(j\), we have \(|x_j^i - m_j| \le r_j\) by choice of \(r_j\) and \(m_j\). Multiplying by \(|m_j|\) gives \[r_j|m_j| \ge |x_j^i - m_j||m_j| \ge -(x_j^i - m_j)m_j = m_j^2 - x_j^i m_j\] Rearranging this yields \(x_j^i m_j + r_j|m_j| \ge m_j^2 \ge 0\).

Since \((x_j^i m_j + r_j|m_j|) \ge 0\) for all agents \(i\) and coordinates \(j\), the inequality 11 implies \(D_i^2 \le (d+1)R^2\) and, thus, \(D_i \le \sqrt{d+1} \cdot R\). We can conclude that the mechanism is a \(\sqrt{d+1}\)-approximation.

We finish the proof by arguing that this bound is tight. Consider an instance with \(2d\) agents where, for each dimension \(j \in [d]\), two agents are placed on the \(j\)-th coordinate axis: one at \(R\) and one at \(-R\).

The optimal solution places the facility at the origin with a cost of \(\mathrm{OPT}(\boldsymbol{x}) = R\). The mechanism, on the other hand, places the facility at \(\mathcal{M}(\boldsymbol{x}) = (m_1,\ldots,m_d,h) = (0,\ldots,0,h)\).

Fix an arbitrary agent \(i\) with report \(x_i = (x_1^i, \dots, x_d^i,0)\). By construction, \(x_i\) has exactly one non-zero coordinate \(\pm R\). Since \(m_j = 0\) and \(r_j = R\) for all \(j \in [d]\), we have: \[d(\mathcal{M}(\boldsymbol{x}),x_i) = \sqrt{\sum_{j \in [d]} (x_j^i-m_j)^2 + h^2} = \sqrt{R^2 + d \cdot R^2} = \sqrt{d+1} \cdot R.\] ◻

Proof. Let \(\mathcal{D}_{\text{flipped}}\) be the distribution corresponding to the reflection of \(\mathcal{D}\) across the \(y\)-axis, i.e. a location \((a,b) \sim \mathcal{D}\) is mapped to a location \((-a,b) \sim \mathcal{D}_{\text{flipped}}\) with the same probability. We define the new symmetric distribution \(\mathcal{D}'\) as: \[\mathcal{D}' = \frac{1}{2}\mathcal{D} + \frac{1}{2}\mathcal{D}_{\text{flipped}}.\]

Let \(\mathcal{M}'\) be the mechanism corresponding to this distribution \(\mathcal{D}'\). Note that by symmetry, if \(\mathcal{M}\) is strategyproof then \(\mathcal{M}_{\text{flipped}}\) is also strategyproof. Furthermore, \(\mathcal{M}'(\boldsymbol{x}) = \frac{1}{2}\mathcal{M}(\boldsymbol{x}) + \frac{1}{2}\mathcal{M}_{\text{flipped}}(\boldsymbol{x})\). Thus, since \(\mathcal{M}'\) is a probability mixture of two scalar and translation invariant, strategyproof mechanisms, it is also scalar and translation invariant and strategyproof.

To evaluate the approximation ratio, we only need to consider the expected egalitarian cost on the profile \((x_1, x_2)= (-1,1)\). The cost for any realized facility location \((a,b)\) is the maximum distance to either agent: \(\max(d(x_1, (a,b)), d(x_2, (a,b)))\).

Note that reflecting a point across the \(y\)-axis swaps its individual distances to \(x_1\) and \(x_2\): \[d(x_1, (-a,b)) = d(x_2, (a,b)) \quad \text{and} \quad d(x_2, (-a,b)) = d(x_1, (a,b)).\]

Consequently, the maximum distance to the agents remains identical for a point and its reflection: \[\max(d(x_1, (-a,b)), d(x_2, (-a,b))) = \max(d(x_1, (a,b)), d(x_2, (a,b))).\]

Taking the expectation over the respective distributions, the expected egalitarian cost under \(\mathcal{M}'\) is equal to the cost under \(\mathcal{M}\) and we conclude \(\lambda' = \lambda\). ◻

Proof. Because \(d(x_1, \mathcal{M}(x_1',1))= \mathbb{E}_{(a,b)\sim\mathcal{D}}[d(x_1, T_{x_1', 1}(a,b))]\) is a convex function with respect to the report \(x_1'\), strategyproofness requires \(x_1' = -1\) to be a global minimum. Because of convexity, this is satisfied if and only if \(0\) lies in the subdifferential of this expected distance at \(x_1' = -1\).

For a reference point \((a,b)\), the distance from Agent 1’s location \(x_1 = (-1,0)\) to the mapped facility under misreport \(x_1' \le 1\) is: \[d(x_1, T_{x_1', 1}(a,b)) = \sqrt{\left( \frac{1-x_1'}{2}a + \frac{x_1'+3}{2} \right)^2 + \left( \frac{1-x_1'}{2}b \right)^2}.\]

For any point \((a,b) \neq (-1,0)\), the function \(d(x_1, T_{x_1', 1}(a,b))\) is differentiable with respect to \(x_1'\) at \(x_1' = -1\) with:

\[\label{derivative} \left. \frac{d}{dx_1'} d\bigl(x_1, T_{x_1', 1}(a,b)\bigr) \right|_{x_1'=-1} = \frac{1 - a^2 - b^2}{2\sqrt{(a+1)^2 + b^2}}.\tag{13}\]

For the point \((a,b) = (-1,0)\), the distance simplifies to \(|x_1'+1|\), which is not differentiable at \(x_1'=-1\) but has a subdifferential interval of \([-1, 1]\). Weighted by its probability \(p\), its contribution to the expected subdifferential at point \(x_1'=-1\) is \([-p, p]\).

Taking the expectation over the differentiable part \(\mathcal{D} \setminus \{(-1,0)\}\) and adding the subdifferential contribution of the point mass at \((-1,0)\), the condition for \(0\) to be in the subdifferential at \(x_1'=-1\) is: \[-p \;\le\; \mathbb{E}_{(a,b)\sim\mathcal{D} \setminus \{(-1,0)\}} \left[ \frac{1 - a^2 - b^2}{2\sqrt{(a+1)^2 + b^2}} \right] \;\le\; p.\]

By the \(y\)-axis symmetry of \(\mathcal{D}\), the same logic applies to Agent 2 concluding the proof. ◻

Proof. By translation and scale invariance, it is enough to analyze the profile \((x_1, x_2) = (-1, 1)\). Let \(p = \mathbb{P}_{\mathcal{D}}((-1,0))\), which by symmetry implies \(\mathbb{P}_{\mathcal{D}}((1,0)) = p\). Since the derivative contribution evaluated at \((1,0)\) is zero, Lemma 6 gives us the bound: \[\label{D95bound} \left|\mathbb{E}_{(a,b)\sim\mathcal{D} \setminus \{(-1,0), (1,0)\}} \left[ \frac{1 - a^2 - b^2}{2\sqrt{(a+1)^2 + b^2}} \right] \right| \leq p.\tag{14}\] We construct the new distribution \(\mathcal{D}'\) on the \(y\)-axis in two steps.

First, by symmetry, we group the remaining support into pairs of points \(\{(a,b), (-a,b)\}\) for \(a > 0\) (note each point carries the same probability mass). We map each pair to a single location \((0, b')\) on the \(y\)-axis with \(b' \ge 0\), assigning it their combined probability mass (see Figure 5). To preserve strategyproofness, we require the expected derivative contribution of the pair given by 13 to equal that of the new mapped location. Multiplying both sides by \(-1\) to rearrange the terms, we obtain: \[\frac{1}{2}\left[\frac{a^2 + b^2 - 1}{2\sqrt{(a+1)^2 + b^2}} + \frac{(-a)^2 + b^2 - 1}{2\sqrt{(-a+1)^2 + b^2}}\right] = \frac{(b')^2 - 1}{2\sqrt{1 + (b')^2}}.\] Simplifying, the above is equivalent to: \[\label{eq:projection95identity} \frac{1}{2}\left[\frac{a^2 + b^2 - 1}{\sqrt{(a+1)^2 + b^2}} + \frac{a^2 + b^2 - 1}{\sqrt{(a-1)^2 + b^2}}\right] = \sqrt{1 + (b')^2} - \frac{2}{\sqrt{1 + (b')^2}}.\tag{15}\]

The right-hand side takes the form \(f(x) = x - \frac{2}{x}\) for \(x = \sqrt{1 + (b')^2} \ge 1\). Note \(f(x)\) is strictly increasing on \([1, \infty)\), with range \([-1, \infty)\). The left-hand side of 15 is bounded below by \(-1\): it is non-negative when \(a^2+b^2 \ge 1\), and for \(a^2+b^2 < 1\), it is minimized when \(b=0\), where it evaluates to \(\frac{1}{2}(a^2-1)(\frac{1}{a+1} + \frac{1}{1-a}) = -1\). Thus, a unique solution \(x \ge 1\) always exists, determining \(b'\).

To show that this transformation does not increase the expected egalitarian cost, observe that under the profile \((-1,1)\), both facility locations \((a,b)\) and \((-a,b)\) share the same maximum cost \(\sqrt{(a+1)^2+b^2}\). Since \(a > 0\) implies \(\sqrt{(a+1)^2+b^2} \ge \sqrt{(a-1)^2+b^2}\), bounding the paired terms on the left-hand side of 15 ensures that: \[\sqrt{1 + (b')^2} - \frac{2}{\sqrt{1 + (b')^2}} \le \sqrt{(a+1)^2 + b^2} - \frac{2}{\sqrt{(a+1)^2 + b^2}}.\] Because \(f(x)\) is strictly increasing, this inequality implies \(\sqrt{1 + (b')^2} \le \sqrt{(a+1)^2 + b^2}\), confirming that the new mapped maximum cost is never higher than the original.

Second, we map the total probability mass \(2p\) from the points \((\pm 1,0)\) to a single point \((0,b_0)\) on the \(y\)-axis. By applying linearity of expectation, the definition of \(\mathcal{D}'\), and Lemma  12 , the underlying mechanism \(\mathcal{M}\) is strategyproof in expectation if: \[\label{aaaaa} \begin{align} 0 &= \mathbb{E}_{(a,b)\sim\mathcal{D}'} \left[ \frac{1 - a^2 - b^2}{2\sqrt{(a+1)^2 + b^2}} \right] \\ &= 2p \left( \frac{1 - b_0^2}{2\sqrt{1 + b_0^2}} \right) + \mathbb{E}_{(a,b)\sim\mathcal{D} \setminus \{(-1,0), (1,0)\}} \left[ \frac{1 - a^2 - b^2}{2\sqrt{(a+1)^2 + b^2}} \right]. \end{align}\tag{16}\]

To solve for \(b_0\), let \(Z_0 := \sqrt{1 + b_0^2}\) and let \(D\) denote the remaining expected value term: \[D := \mathbb{E}_{(a,b)\sim\mathcal{D} \setminus \{(-1,0), (1,0)\}} \left[ \frac{1 - a^2 - b^2}{2\sqrt{(a+1)^2 + b^2}} \right].\] Under these assignments, equality 16 is equivalent to \(f(Z_0) = \frac{D}{p}\). By 14 , we obtain \(|D| \leq p\), implying the right-hand side is bounded within \([-1, 1]\). Since \(f(1) = -1\), \(f(2) = 1\), and \(f(x)\) is continuous and strictly increasing, there exists a unique solution \(Z_0 \in [1, 2]\), which defines \(b_0 \ge 0\). Because the egalitarian cost of the mapped location \((0, b_0)\) is \(\sqrt{1+b_0^2} = Z_0 \le 2\), this transformation does not increase the original egalitarian cost of \(2\) associated with the points \((\pm 1, 0)\).

Since this construction preserves the pointwise probability weights and ensures that the egalitarian cost contributions never increase, the expected approximation ratio of \(\mathcal{M}'\) under \(\mathcal{D}'\) is at most that of \(\mathcal{M}\), and \(\mathcal{M}'\) is strategyproof. ◻

Proof. We first establish the lower bound for the case of \(n = 2\) agents.

By Lemma 7, it suffices to consider mechanisms whose output distribution \(\mathcal{D}\) on the profile \(\boldsymbol{x} = (-1, 1)\) is supported entirely on the \(y\)-axis, meaning any realized facility location is of the form \((0, b) \sim \mathcal{D}\).

Because the agents are located at \(x_1 = (-1,0)\) and \(x_2 = (1,0)\), their distances to any point on the \(y\)-axis are identical. We define the random variable \(Z := d(x_1, \mathcal{M}(\boldsymbol{x})) = \sqrt{1 + b^2}\) to represent this distance. Note that its expectation \(\mathbb{E}_{\mathcal{D}}[Z]\) corresponds to the expected egalitarian cost. Rearranging this identity we obtain \(b^2 = Z^2 - 1\).

Applying Lemma 6 with \(a=0\), the strategyproofness condition simplifies to: \[\mathbb{E}_{\mathcal{D}} \left[ \frac{1 - b^2}{2\sqrt{1 + b^2}} \right] = 0\]

Substituting \(b^2 = Z^2 - 1\) and \(\sqrt{1+b^2} = Z\) yields: \[\mathbb{E}_{\mathcal{D}} \left[ \frac{1 - (Z^2 - 1)}{2Z} \right] = \mathbb{E}_{\mathcal{D}} \left[ \frac{2 - Z^2}{2Z} \right] = 0\]

By linearity of expectation, this expression separates into: \[\mathbb{E}_{\mathcal{D}} \left[ \frac{1}{Z} - \frac{Z}{2} \right] = 0 \implies \mathbb{E}_{\mathcal{D}}[Z] = 2\mathbb{E}_{\mathcal{D}}\left[\frac{1}{Z}\right]\]

Since \(f(t) = 1/t\) is convex for \(t > 0\), Jensen’s inequality implies \(\mathbb{E}_{\mathcal{D}}\left[\frac{1}{Z}\right] \ge \frac{1}{\mathbb{E}_{\mathcal{D}}[Z]}\). Substituting this inequality gives us: \[\mathbb{E}_{\mathcal{D}}[Z] \ge \frac{2}{\mathbb{E}_{\mathcal{D}}[Z]}\]

This implies \(\mathrm{MC}(\boldsymbol{x},\mathcal{M}) = \mathbb{E}_{\mathcal{D}}[Z] \ge \sqrt{2}\). Because the optimal maximum cost for this profile is \(\mathrm{OPT}= 1\), the expected approximation ratio is at least \(\sqrt{2}\).

By Lemma [lem:population95extension2], the lower bound extends to an arbitrary number of agents. ◻

Proof. We rely on the optimal configurations established in the preliminaries and distinguish between the two configurations of the spanning arc.

• Case 1 (\(\alpha \ge \pi\)): The profile spans at least a semicircle, so \(\mathrm{OPT}= 1\). The mechanism outputs the origin, yielding a distance of \(1\) for all agents \(x_i \in S^1\). Thus, \(\mathrm{MC}(\mathcal{M},\boldsymbol{x}) = 1 \le 1.5 \cdot \mathrm{OPT}\).

• Case 2 (\(\alpha < \pi\)): Let A and B be the locations of the extreme agents of the arc that span an angle of \(\alpha\) and let \(z\) be the midpoint of the arc between them. The optimal cost is \(\mathrm{OPT}= \sin(\alpha/2)\), and the mechanism outputs a facility \(Y \in \{A, B, z\}\). Because all agents lie inside the arc bounded by \(A\) and \(B\), the maximum distance \(d^*\) from \(Y\) to any agent is achieved at one of the endpoints. If \(Y = A\) or \(Y = B\), then \(d^* = \|A-B\| = 2\sin(\alpha/2)\). If \(Y = z\), then \(d^* = \|z-A\| = \sin(\alpha/2)\).

Taking the expectation over the mechanism’s randomness, the expected maximum cost is: \[\begin{align} \mathrm{MC}(\mathcal{M},\boldsymbol{x}) &= \lambda(\alpha)\cdot(2\sin(\alpha/2)) + \lambda(\alpha)\cdot(2\sin(\alpha/2)) + (1-2\lambda(\alpha))\cdot\sin(\alpha/2) \\ &= 4\lambda(\alpha)\cdot\sin(\alpha/2) + \sin(\alpha/2) - 2\lambda(\alpha)\cdot\sin(\alpha/2) \\ &= \sin(\alpha/2)\cdot(1 + 2\lambda(\alpha)) \\ &= \sin(\alpha/2) \cdot\left[ 1 + \frac{\cos(\alpha/2)}{1+\cos(\alpha/2)} \right] \\ &= \sin(\alpha/2)\cdot \left[ \frac{1 + 2\cos(\alpha/2)}{1+\cos(\alpha/2)} \right]. \end{align}\]

Thus, the approximation ratio is \(\frac{\mathrm{MC}(\mathcal{M},\boldsymbol{x})}{\mathrm{OPT}} = \frac{1 + 2\cos(\alpha/2)}{1+\cos(\alpha/2)}\). For \(\alpha \in (0, \pi)\), this expression is decreasing in \(\alpha\) so: \[\frac{\mathrm{MC}(\mathcal{M},\boldsymbol{x})}{\mathrm{OPT}} \le \lim_{\alpha \to 0} \frac{1 + 2\cos(\alpha/2)}{1+\cos(\alpha/2)} = \frac{3}{2}.\] ◻

Proof. Fix an arbitrary agent \(x_i\) at true angle \(\beta \in [0, \alpha]\) and assume that the manipulated profile \(\boldsymbol{x'}\) spans the arc \([0,\gamma]\) with \(\gamma < \pi\). By Lemma [lem:internal95cost95simplification], the expected distance of \(x_i\) for profile \(\boldsymbol{x'}\) is \[\mathbb{E}[d(\mathcal{M}(\boldsymbol{x'}),x_i)] = \sin\left(\frac{\beta}{2}\right) + \frac{D(\beta, \gamma) - g(\beta, \gamma)}{1+\cos(\gamma/2)}.\] Applying the same logic for the truthful profile \(\boldsymbol{x}\) gives \[\mathbb{E}[d(\mathcal{M}(\boldsymbol{x}),x_i)] = \sin\left(\frac{\beta}{2}\right) + \frac{D(\beta, \alpha) - g(\beta, \alpha)}{1+\cos(\alpha/2)}.\] Since \(\alpha < \gamma < \pi\), by Lemma [lem:internal95monotonicity], \(\mathbb{E}[d(\mathcal{M}(\boldsymbol{x'})), x_i] > \mathbb{E}[d(\mathcal{M}(\boldsymbol{x})), x_i]\).

If \(\boldsymbol{x'}\) instead spans an arc of angle \(\ge \pi\), then \(\mathbb{E}[d(\mathcal{M}(\boldsymbol{x'}),x_i)] = 1\) because the mechanism outputs the origin. However, as shown in Lemma [lem:internal95monotonicity], the expected distance is strictly increasing with the span angle. The limit as the span approaches \(\pi\) evaluates to one. Since \(\alpha < \pi\) by assumption, this implies \(\mathbb{E}[d(\mathcal{M}(\boldsymbol{x}),x_i)] < 1\). ◻

Proof. Profile \(\boldsymbol{x}\) obtains an expected egalitarian cost of \(1\). Without loss of generality, assume the profile \(\boldsymbol{x'}\) spans the arc \(W' = [-\theta/2, \theta/2]\). Let \(z' = (\cos(\theta/2), 0)\) be the chord midpoint of its extreme agents.

Because the truthful profile \(\boldsymbol{x}\) has a span \(\ge \pi\) and all non-deviating agents lie within \(W'\), the true location \(x_i\) must correspond to an angle \(\gamma \in [\pi - \theta/2, \pi + \theta/2]\) to satisfy the true spanning condition. Consequently, we get

\[\label{cosineq} \cos\gamma \le \cos(\pi - \theta/2) =-\cos(\theta/2).\tag{17}\]

Let \(f(X) = \|x_i - X\|\) be the distance from the mechanism’s output \(X\) to \(x_i\). Since \(f\) is convex, by Jensen’s inequality: \(\mathbb{E}[d(\mathcal{M}(\boldsymbol{x'}), x_i)] = \mathbb{E}[\|x_i - X\|] \geq \|x_i - \mathbb{E}[X]\| = \|x_i - z'\|\). Applying the Law of Cosines to the triangle formed by the origin \(O\), the agent location \(x_i\), and the chord midpoint \(z'\), and using \(\|x_i\|=1\) and \(\|z'\|=\cos(\theta/2)\) we obtain: \[\begin{align} \|x_i - z'\|^2 &= 1^2 + \cos^2(\theta/2) - 2\cdot\cos(\theta/2)\cdot\cos(\gamma) \\ &\ge 1 + \cos^2(\theta/2) - 2\cdot\cos(\theta/2)\cdot(-\cos(\theta/2)) \\ &= 1 + 3\cdot\cos^2(\theta/2) > 1, \end{align}\] where we used 17 for the inequality step.

Thus, \(\mathbb{E}[d(\mathcal{M}(\boldsymbol{x'}), x_i)] > 1 = \mathbb{E}[d(\mathcal{M}(\boldsymbol{x}), x_i)]\). ◻

Proof. Since the deviation shrinks the minimum spanning arc, it must be done by one of the extreme points. By our established setup, the stationary extreme \(B\) is located at angle \(0\), agent \(A\) is at angle \(\alpha\). Without loss of generality, let \(A\) be the deviating agent to a location \(A'\). Thus, the manipulated profile \(\boldsymbol{x'}\) spans the smaller arc \([0, \gamma]\) with the new extreme \(A'\) at angle \(\gamma\).

The expected cost for agent \(A\) under the truthful profile \(\boldsymbol{x}\) is \(\mathbb{E}[d(A,\mathcal{M}(\boldsymbol{x}))] = 2\lambda(\alpha) \cdot\sin(\alpha/2) + (1-2\lambda(\alpha))\cdot \sin(\alpha/2) = \sin(\alpha/2)\). Therefore, it only remains to show that \(\mathbb{E}[d(\mathcal{M}(\boldsymbol{x'}),A)] > \sin(\alpha/2)\).

Let \(z'\) be the chord midpoint of the reported arc \([0, \gamma]\). Given that agent \(A\) is at angle \(\alpha\) and the new reported extreme \(A'\) is at angle \(\gamma\), the distances from \(A\) to the possible output locations \(B\), \(A'\), and \(z'\) are \(2\sin(\alpha/2)\), \(2\sin\left(\frac{\alpha - \gamma}{2}\right)\), and \(D(\alpha, \gamma)\), respectively. Applying Lemma [lem:distance95factorization] and dropping the non-negative second squared term yields the lower bound: \[\begin{align} D(\alpha, \gamma) &\ge \sin(\alpha/2) - \cos(\gamma/2)\sin\left(\frac{\gamma-\alpha}{2}\right) \\ &=\sin(\alpha/2) + \cos(\gamma/2)\sin\left(\frac{\alpha-\gamma}{2}\right). \end{align}\]

The expected cost for agent \(A\) under the reported profile \(\boldsymbol{x'}\) is given by: \[\mathbb{E}[d(\mathcal{M}(\boldsymbol{x'}),A)] = \lambda(\gamma)\|A-B\| + \lambda(\gamma)\|A-A'\| + (1-2\lambda(\gamma))D(\alpha, \gamma).\]

Substituting the respective distances and our lower bound for \(D(\alpha, \gamma)\) gives: \[\begin{align} \mathbb{E}[d(\mathcal{M}(\boldsymbol{x'},A))] &\ge \frac{\cos(\gamma/2)\left[\sin(\alpha/2) + \sin\left(\frac{\alpha-\gamma}{2}\right)\right] + \sin(\alpha/2) + \cos(\gamma/2)\sin\left(\frac{\alpha-\gamma}{2}\right)}{1+\cos(\gamma/2)} \\ &= \sin(\alpha/2) + \frac{2\cos(\gamma/2)\sin\left(\frac{\alpha-\gamma}{2}\right)}{1+\cos(\gamma/2)} > \sin(\alpha/2), \end{align}\] where the strict inequality relies on our assumption \(\gamma < \alpha\). ◻

Proof. Without loss of generality let the deviating agent be agent \(A\) corresponding to a true location at angle \(\alpha\).

We can decompose this deviation into two steps via an intermediate span \([-\gamma, \alpha]\):

1. Expansion Step: First, consider the arc expanding from the truthful \([0, \alpha]\) to \([-\gamma, \alpha]\). By Lemma 9, expanding the minimal spanning arc increases the expected cost for all agents located within the original arc.

2. Shrinking Step: Second, consider the arc shrinking from \([-\gamma, \alpha]\) down to \([-\gamma, \beta]\) (since \(A\)’s true location \(\alpha\) is no longer reported). As we prove in Lemma 11, when a spanning arc shrinks away from an extreme agent’s true location, that agent’s expected cost increases.

Because both intermediate operations penalize agent \(A\), the combined deviation to \(-\gamma\) increases \(A\)’s expected cost. ◻

Proof. Let the truthful profile \(\boldsymbol{x}\) span a minimal arc \(W\), and a coalition \(S\) deviate to a reported profile \(\boldsymbol{x'}\) spanning \(W'\). To prove group-strategyproofness, we must show that if \(W \neq W'\), at least one agent in \(S\) increases their expected cost. By the logic of Lemma 9 and Lemma 10, any deviation that transitions the spanning arc between the \(<\pi\) and the \(\ge\pi\) cases, in either direction, increases the expected cost for at least one deviating agent.

Therefore, we restrict our analysis to the case where both \(W\) and \(W'\) have spanning angles smaller than \(\pi\). Without loss of generality, let \(W = [0, \alpha]\) with an agent \(B\) at angle \(0\) and an agent \(A\) at angle \(\alpha\). Let \(z\) be the midpoint of the arc connecting \(A\) and \(B\).

We partition the analysis based on how many of the extreme agents belong to the coalition \(S\):

Case 1: Both extreme agents are in \(S\).

Under truthful reporting, the mechanism \(\mathcal{M}(\boldsymbol{x})\) restricts its outputs to the set \(\{A, B, z\}\), where \(z\) is the chord midpoint of the extremes \(A\) and \(B\). The expected distance from each extreme agent to the facility is given by: \[\mathbb{E}[d(\mathcal{M}(\boldsymbol{x}), A)] = \mathbb{E}[d(\mathcal{M}(\boldsymbol{x}), B)] = \sin(\alpha/2).\] Notice that, by the triangle inequality, for any point \(y \in \mathbb{R}^2\) we have: \[\|A - y\| + \|B - y\| \geq \|A - B\| = 2\sin(\alpha/2).\] By linearity of expectation, for any random variable \(Y\), the sum of the expected costs is also lower bounded by \(2\sin(\alpha/2)\): \[\mathbb{E}[d(Y, A)] + \mathbb{E}[d(Y, B)] \geq 2\sin(\alpha/2).\]

Now consider a manipulated profile \(\boldsymbol{x}'\) with a modified spanning arc \(W' \neq W\), with extreme agents \(A'\) and \(B'\) and midpoint \(z'\) between them. This implies that at least one of the new candidate facility locations in \(\{A', B', z'\}\) must lie off the line segment connecting the extremes \(A\) and \(B\). Consequently, the mechanism’s probability support for \(\boldsymbol{x}'\) must place a strictly positive probability \(p > 0\) on at least one realization \(y^*\) that does not lie on the original segment between \(A\) and \(B\).

By the strict triangle inequality, this specific point \(y^*\) satisfies: \[\|A - y^*\| + \|B - y^*\| > 2\sin(\alpha/2),\] while all other possible outputs \(y \in \{A', B', z'\}\) still satisfy the lower bound \(\|A - y\| + \|B - y\| \geq 2\sin(\alpha/2)\). Taking the expectation over the entire distribution we obtain: \[\mathbb{E}[d(\mathcal{M}(\boldsymbol{x}'), A)] + \mathbb{E}[d(\mathcal{M}(\boldsymbol{x}'), B)] > 2\sin(\alpha/2).\] By the pigeonhole principle, it follows that the bounds \(\mathbb{E}[d(\mathcal{M}(\boldsymbol{x}'), A)] \le \sin(\alpha/2)\) and \(\mathbb{E}[d(\mathcal{M}(\boldsymbol{x}'), B)] \le \sin(\alpha/2)\) cannot both hold simultaneously. At least one of the two deviating extreme agents must incur an expected cost greater than \(\sin(\alpha/2)\), which ensures the deviation fails.

Case 2: At least one extreme agent is not in \(S\).

We formalize the deviation of \(S\) in two sequential steps by constructing an intermediate profile \(\boldsymbol{y}\). In profile \(\boldsymbol{y}\), only the deviating agents located in the interior of \(W\) report their altered locations from \(\boldsymbol{x}'\), while all other agents-including any deviating extreme agents-report truthfully according to \(\boldsymbol{x}\). Because the extreme agents continue to anchor the boundaries, this interior deviation gives an intermediate spanning arc \(W_y\) that either expands or remains equal to \(W\).

By Lemma 9, if this intermediate arc expands, the expected cost for every agent in the interval \([0, \alpha]\) increases. If the coalition \(S\) contains no extreme agents, then the intermediate profile constitutes the final reported profile (\(\boldsymbol{y} = \boldsymbol{x}'\)). The resulting expansion means that every agent in \(S\) incurs a higher expected cost, so the deviation fails.

Alternatively, if exactly one extreme agent is in \(S\), we assume without loss of generality that it is agent \(A\). We then evaluate the final deviation from the intermediate profile \(\boldsymbol{y}\) based on the intermediate arc \(W_y\):

• If \(W_y\) expands: The transition from \(\boldsymbol{x}\) to \(\boldsymbol{y}\) increases the expected cost for agent \(A\), meaning \(\mathbb{E}[d(\mathcal{M}(\boldsymbol{y}), A)] > \mathbb{E}[d(\mathcal{M}(\boldsymbol{x}), A)]\). In the subsequent step from \(\boldsymbol{y}\) to \(\boldsymbol{x}'\), agent \(A\) unilaterally deviates while all other agents maintain their reports from \(\boldsymbol{y}\). Because agent \(A\) reports truthfully in \(\boldsymbol{y}\), individual strategyproofness (Theorem 13) implies that this unilateral deviation cannot decrease their expected cost, ensuring \(\mathbb{E}[d(\mathcal{M}(\boldsymbol{x}'), A)] \geq \mathbb{E}[d(\mathcal{M}(\boldsymbol{y}), A)]\). Combining these inequalities gives \(\mathbb{E}[d(\mathcal{M}(\boldsymbol{x}'), A)] > \mathbb{E}[d(\mathcal{M}(\boldsymbol{x}), A)]\).

• If \(W_y = W\): The intermediate transition preserves the expected cost for agent \(A\), so \(\mathbb{E}[d(\mathcal{M}(\boldsymbol{y}), A)] = \mathbb{E}[d(\mathcal{M}(\boldsymbol{x}), A)]\). However, because the final configuration satisfies \(W' \neq W\), the step from \(\boldsymbol{y}\) to \(\boldsymbol{x}'\) represents a unilateral deviation by agent \(A\) that alters the minimal spanning arc. As established by our boundary lemmas (Lemmas 9 and 11), any unilateral deviation by a boundary agent that changes the minimal spanning arc increases that agent’s expected cost, giving \(\mathbb{E}[d(\mathcal{M}(\boldsymbol{x}'), A)] > \mathbb{E}[d(\mathcal{M}(\boldsymbol{y}), A)]\).

Thus, in both subcases, the deviating extreme agent does not profit, ensuring that any coalition is never profitable. ◻

Proof. Suppose for contradiction there exists a GSP and unanimous mechanism \(\mathcal{M}\) with an approximation ratio of \(2 - \epsilon\) for some \(\epsilon > 0\).

Let \(x_1, x_2 \in S^1\) be two agent locations separated by an angle \(\theta \in (0, \pi]\). By GSP and unanimity, the output \(y = \mathcal{M}(x_1, x_2)\) is constrained to the lens-shaped region \(L(x_1, x_2)\) bounded by the circle’s arc connecting \(x_1\) and \(x_2\) and its reflection across the chord between them (see Figure 12). Otherwise, there would exist a point \(z \in S^1\) closer to both agents than \(y\). Since the mechanism is unanimous, the agents could profitably deviate by jointly reporting \(z\), forcing the output to be \(z\) and violating group-strategyproofness.

Without loss of generality, assume \(\|y - x_2\| \le \|y - x_1\|\). Let \(x_2'\) be the radial projection of \(y\) onto the circle’s arc connecting \(x_1\) and \(x_2\), and let \(\delta = \|y - x_2'\|\).

The distance from a point \(y\) inside the lens to its projection \(x_2'\) is at most twice the maximum distance from the chord to the arc. This maximum distance equals \(h = 1 - d(O, m) = 1 - \cos(\theta/2)\), where \(O\) is the center of the circle and \(m\) is the midpoint of the chord. Using the identity \(\cos(2x) = 1 - 2\sin^2(x)\), this can be rewritten as \(2\sin^2(\theta/4)\), implying the upper bound: \[\label{eq:delta95upper95bound} \delta \le 2(1 - \cos(\theta/2)) = 4\sin^2(\theta/4).\tag{18}\]

Fix \(\theta > 0\) sufficiently small such that \(4\sin(\theta/4) < \epsilon\).

Consider the profile \((x_1, x_2')\), and let \(y' = \mathcal{M}(x_1, x_2')\). By strategyproofness, an agent at \(x_2'\) must not benefit by falsely reporting \(x_2\): \[\label{eq:sp95bound} \|y' - x_2'\| \le \|\mathcal{M}(x_1, x_2) - x_2'\| = \|y - x_2'\| = \delta.\tag{19}\]

For the profile \((x_1, x_2')\), the optimal maximum cost is \(\mathrm{OPT}(x_1, x_2') = \frac{1}{2}\|x_1 - x_2'\|\). By the triangle inequality and 19 , the cost to agent 1 is bounded by: \[\label{eq:agent195bound} \|y' - x_1\| \ge \|x_1 - x_2'\| - \|y' - x_2'\| \ge \|x_1 - x_2'\| - \delta.\tag{20}\]

The approximation ratio \(\rho\) for the profile \((x_1, x_2')\) must satisfy, by using 20 : \[\label{eq:rho95lower95bound} \rho \ge \frac{\|y' - x_1\|}{\mathrm{OPT}(x_1, x_2')} \ge \frac{\|x_1 - x_2'\| - \delta}{\frac{1}{2}\|x_1 - x_2'\|} = 2 - \frac{2\delta}{\|x_1 - x_2'\|}.\tag{21}\]

Because we assumed \(\|y - x_2\| \le \|y - x_1\|\), the facility \(y\) lies on the \(x_2\) side of the perpendicular bisector between \(x_1\) and \(x_2\). Consequently, its radial projection \(x_2'\) also lies on the \(x_2\) side of the arc. This means \(x_2'\) is further from \(x_1\) than the arc’s midpoint. The angle between \(x_1\) and this midpoint is \(\theta/2\), which on the unit circle corresponds to a chord length of \(2\sin(\frac{\theta/2}{2}) = 2\sin(\theta/4)\). Therefore, we obtain the lower bound: \[\label{eq:distance95lower95bound} \|x_1 - x_2'\| \ge 2\sin(\theta/4).\tag{22}\]

Substituting the upper bound for \(\delta\) from 18 and the lower bound for \(\|x_1 - x_2'\|\) from 22 into inequality 21 gives: \[\rho \ge 2 - \frac{2(4\sin^2(\theta/4))}{2\sin(\theta/4)} = 2 - 4\sin(\theta/4).\]

By our choice of \(\theta\), we have \(4\sin(\theta/4) < \epsilon\), which implies \(\rho > 2 - \epsilon\). This contradicts the assumption that \(\mathcal{M}\) achieves an approximation ratio of \(2 - \epsilon\), establishing the lower bound of \(2\). ◻

Proof. Without loss of generality, translate every point so that \(x_0 = O\) is the origin. Let \(y = \rho(\cos\alpha, \sin\alpha)\) for some angle \(\alpha \in [0, 2\pi)\), where \(\rho = d(y, x_0) = \|y\|> 0\). Then \(y' = r \cdot (-\cos\alpha, -\sin\alpha)\), the point on \(S^1\) in the direction from \(y\) through \(x_0\).

The \(k\) boundary points are at angles \(\theta_i = 2\pi i/k\). The closest boundary point \(x'\) to \(y'\) is at angle \(\theta_{i^*}\), where \(\theta_{i^*}\) is the angle nearest to \(\alpha + \pi\). The angular deviation \(\delta = \theta_{i^*} - (\alpha + \pi)\) satisfies \(|\delta| \leq \pi/k\). Thus: \[x' = r(-\cos(\alpha + \delta), -\sin(\alpha + \delta)) \quad \text{for some |\delta| \leq \pi/k. }\] Expanding the squared Euclidean distance between \(y\) and \(x'\) we obtain: \[\begin{align} d(y, x')^2 &= \|\rho \cdot(\cos\alpha, \sin\alpha) + r \cdot(\cos(\alpha+\delta), \sin(\alpha+\delta))\|^2 = \rho^2 + r^2 + 2\rho r\cos\delta. \end{align}\] Since \(\cos(.)\) is decreasing on \([0, \pi]\) and \(|\delta| \leq \pi/k\), we have \(\cos\delta \geq \cos(\pi/k)\), and thus: \[d(y, x')^2 \geq \rho^2 + r^2 + 2\rho r\cos\!\left(\frac{\pi}{k}\right) = d(y,x_0)^2 + r^2 + 2\,d(y,x_0)\,r\cos\!\left(\frac{\pi}{k}\right).\] Taking the square root completes the proof. ◻

Proof. We follow the same line of arguments as in the proof of Theorem [lowerboundtheorem]. The key difference is that we cannot simply lower bound the maximum distance from the facility location \(y'\) to any point on the sphere \(C_{x_0}\) by \(d(y', x_0) + a_2\) since we only have a finite number of agents deviating from \(x_0\), meaning they cannot densely cover the circumference.

Suppose we distribute the \(k = n/3\) agents, initially located at \(x_0\), equidistantly over the circle \(C_{x_0} = S^1\) as defined in Lemma 13. Let the resulting location profile be \(\boldsymbol{x}'\). Consider any realized facility location \(y'\). Using Lemma 13 with \(y = y'\) and \(r = a_2 = \sqrt{3}\), there exists a boundary point \(x'\) on \(C_{x_0}\) such that \[d(y', x') \geq \sqrt{d(y',x_0)^2 + 3 + 2\sqrt{3} \, d(y',x_0)\, \cos\!\left(\frac{\pi}{k}\right)}.\] The expression on the right-hand side is convex in \(d(y',x_0)\) for all \(k \ge 2\). We can thus apply Jensen’s inequality to conclude that: \[\begin{align} \mathrm{MC}(\mathcal{M}(\boldsymbol{x}'), \boldsymbol{x}') & \ge \mathbb{E}\left[\sqrt{d(Y',x_0)^2 + 3 + 2\sqrt{3} \, d(Y',x_0)\, \cos\!\left(\frac{\pi}{k}\right)} \; \right] \\ & \ge \sqrt{\mathbb{E}[d(Y',x_0)]^2 + 3 + 2\sqrt{3} \, \mathbb{E}[d(Y',x_0)]\, \cos\!\left(\frac{\pi}{k}\right)} \\ & \ge \sqrt{4 + 2\sqrt{3} \, \cos\!\left(\frac{\pi}{k}\right)}, \end{align}\] where the final inequality holds because \(\mathbb{E}[d(Y',x_0)] \ge 1\) and the underlying function is increasing over this domain. The claim follows by dividing this final expression by the optimal cost \(\mathrm{OPT}(\boldsymbol{x}') = \sqrt{3}\). ◻

Proof. Without loss of generality, translate every point so that \(x_0 = O\) is now the origin. Let \(y = \rho u\) with \(\rho = d(y, x_0) = \|y\| > 0\) and \(\|u\| = 1\). The projection is \(y' = -ru\). Let the closest grid point be \(x' = rv\) with \(\|v\| = 1\).

The grid divides each angular axis into \(m = k^{1/(d-1)}\) equidistant intervals. Therefore, in each of the \(d-1\) angular coordinates, the distance between the coordinates of \(y'\) and the closest grid point \(x'\) is at most \(\frac{\pi}{m}\).

We can bound the angle \(\delta\) that \(-u\) and \(v\) make with the origin by the Euclidean distance of these coordinate differences. Summing over the \(d-1\) coordinates, we have: \[\delta \le \sqrt{ \sum_{i=1}^{d-1} \left(\frac{\pi}{m}\right)^2 } = \frac{\pi\sqrt{d-1}}{m} = \gamma.\]

Expanding the squared Euclidean distance between \(y\) and \(x'\) we obtain: \[d(y, x')^2 = \|\rho u - r v\|^2 = \rho^2 + r^2 + 2\rho r \cos\delta\] By our assumption that \(k \ge (\sqrt{d-1})^{d-1}\), we obtain \(\gamma \le \pi\). Since \(\cos(\cdot)\) is decreasing on \([0, \pi]\) and we established \(\delta \le \gamma \le \pi\), it follows that \(\cos\delta \ge \cos\gamma\) and thus: \[d(y, x')^2 \ge d(y, x_0)^2 + r^2 + 2 d(y, x_0) r \cos\gamma.\]

Taking the square root completes the proof. ◻

Proof. The proof follows the argument of the \(\mathbb{R}^2\) case, substituting the circle discretization with the spherical coordinate grid. We distribute \(k = n/(d+1)\) agents over the sphere of radius \(r = \sqrt{\frac{2(d+1)}{d}}\) centered at \(x_0\).

Let \(y'\) be the realized facility location. By Lemma 14, there exists a grid point \(x'\) such that: \[d(y', x') \geq \sqrt{d(y',x_0)^2 + r^2 + 2r \, d(y',x_0)\, \cos\gamma},\] where \(\gamma = \frac{\pi\sqrt{d-1}}{(n/(d+1))^{1/(d-1)}}\).

The function \(f(z) = \sqrt{z^2 + r^2 + 2rz\cos\gamma}\) is convex for \(z \ge 0\). Applying Jensen’s Inequality to the expected social cost \(\mathrm{MC}(\mathcal{M}(\boldsymbol{x}'), \boldsymbol{x}')\): \[\begin{align} \mathrm{MC}(\mathcal{M}(\boldsymbol{x}'), \boldsymbol{x}') &\ge \mathbb{E}\left[\sqrt{d(Y',x_0)^2 + r^2 + 2r \, d(Y',x_0)\, \cos\gamma} \right] \\ &\ge \sqrt{\mathbb{E}[d(Y',x_0)]^2 + r^2 + 2r \, \mathbb{E}[d(Y',x_0)]\, \cos\gamma}. \end{align}\] Using \(\mathbb{E}[d(Y',x_0)] \ge 1\) and substituting \(r = \sqrt{\frac{2(d+1)}{d}}\), the maximum cost is lower bounded by: \[\sqrt{1 + \frac{2(d+1)}{d} + 2\sqrt{\frac{2(d+1)}{d}} \cos\gamma}.\] The theorem follows by dividing by the optimal cost \(\mathrm{OPT}(\boldsymbol{x}') = r = \sqrt{\frac{2(d+1)}{d}}\). ◻

Proof. We parameterize the facility location as \(y = (u, 1+v)\) subject to the distance constraint \(u^2 + v^2 = r^2\). The squared distances \(D_i\) to the locations in \(\boldsymbol{x}'\) simplify to: \[\begin{align} D_1 &= d(x_1', y)^2= u^2 + (v - \sqrt{3})^2 = r^2 - 2\sqrt{3}v + 3, \\ D_2 &= d(x_2, y)^2= (u - \tfrac{\sqrt{3}}{2})^2 + (v + 1.5)^2 = r^2 - \sqrt{3}u + 3v + 3, \\ D_3 &= d(x_3, y)^2= (u + \tfrac{\sqrt{3}}{2})^2 + (v + 1.5)^2 = r^2 + \sqrt{3}u + 3v + 3. \end{align}\]

By symmetry, we may assume \(u \ge 0\), ensuring \(D_3 \ge D_2\). The egalitarian cost is defined by \(\max(\sqrt{D_1}, \sqrt{D_3})\), which is minimized when \(D_1 = D_3\). Setting \(D_1 = D_3\) gives: \[-2\sqrt{3}v = \sqrt{3}u + 3v \implies \sqrt{3}u = -(2\sqrt{3}+3)v.\] Since \(u \ge 0\), we must have \(v \le 0\). Substituting \(u^2 = r^2 - v^2\) and squaring both sides gives \(3(r^2 - v^2) = (21 + 12\sqrt{3})v^2\), which simplifies to \(3r^2 = (24 + 12\sqrt{3})v^2\). Thus, the minimizer is \(v = -r / \sqrt{8+4\sqrt{3}}\).

Substituting \(v\) into \(D_1\) we obtain the minimal squared cost \(L(r)^2\): \[L(r)^2 = r^2 - 2\sqrt{3}v + 3 = r^2 + \left( \frac{2\sqrt{3}}{\sqrt{8+4\sqrt{3}}} \right) r + 3 = r^2 + \lambda r + 3.\] Because \(\lambda > 0\), the function \(L(r) = \sqrt{r^2 + \lambda r + 3}\) is increasing for \(r \ge 0\). Also, its second derivative is positive, establishing strict convexity for \(r\geq0\). ◻

Proof. Suppose for contradiction there exists a randomized strategyproof \(n\)-agent mechanism \(\mathcal{M}\) with an approximation ratio \(\lambda' < \lambda\). We construct a 2-agent mechanism \(\mathcal{M}'\) that on input \((x_1, x_2)\) runs the \(n\)-agent mechanism on the profile with the first agent at \(x_1\) and the remaining \(n-1\) agents co-located at \(x_2\):

\[\mathcal{M}'(x_1,x_2) = \mathcal{M}(x_1,x_2,\dots, x_2).\]Because \(\mathcal{M}'\) evaluates \(\mathcal{M}\) on a restricted subdomain, the approximation ratio of \(\mathcal{M}'\) is at most \(\lambda'\).

We show that \(\mathcal{M}'\) inherits strategyproofness from \(\mathcal{M}\) by examining potential deviations by either agent.

• Case 1: The first agent deviates. A deviation by the first agent from \(x_1\) to \(x_1'\) in \(\mathcal{M}'\) corresponds to a single, unilateral deviation in \(\mathcal{M}\). By the strategyproofness of \(\mathcal{M}\), this agent cannot decrease their expected distance to the facility: \[\mathbb{E}[d(\mathcal{M}'(x_1', x_2), x_1)] \ge \mathbb{E}[d(\mathcal{M}'(x_1,x_2), x_1)].\]

• Case 2: The second agent deviates. A deviation by the second agent from \(x_2\) to \(x_2'\) in \(\mathcal{M}'\) corresponds to a simultaneous deviation by a cluster of \(n-1\) co-located agents in \(\mathcal{M}\) from their shared true location \(x_2\) to \(x_2'\). By 2, this joint deviation cannot decrease the expected distance to their true location \(b\). Thus, \[\mathbb{E}[d(\mathcal{M}'(x_1, x_2'), x_2)] \ge \mathbb{E}[d(\mathcal{M}'(x_1,x_2), x_2)],\] meaning the second agent cannot profit.

Since neither agent has a profitable deviation, the randomized mechanism \(\mathcal{M}'\) is strategyproof. This contradicts the assumption that \(\lambda\) was a lower bound for the approximation ratio of 2-agent mechanisms, completing the proof. ◻

Proof. By unanimity, if Agent 1 reports \(x_1'=1\), both agents report the same location \(1\), forcing the mechanism to output the facility at \((1,0)\). The true distance from Agent 1’s location \(x_1 = (-1,0)\) to this facility makes the expected distance \(2\).

For any misreport \(x_1' \ge 1\), the sorted reported profile is \(\{1, x_1'\}\). By the translation and scale invariance, an arbitrary reference point \((a,b) \sim \mathcal{D}\) is mapped to the facility location \(T_{1, x_1'}(a,b)\) given by: \[T_{1, x_1'}(a,b) = \left( \frac{x_1'-1}{2}a + \frac{x_1'+1}{2}, \; \frac{x_1'-1}{2}b \right).\] The function \(f_{(a,b)}(x_1')\) representing the distance from Agent 1’s true location \(x_1 = (-1,0)\) to this mapped facility is \(d(x_1, T_{1, x_1'}(a,b))\). Expanding, we obtain: \[\label{eq:f95u95def} f_{(a,b)}(x_1') = \sqrt{\left( \frac{x_1'-1}{2}a + \frac{x_1'+3}{2} \right)^2 + \left( \frac{x_1'-1}{2}b \right)^2},\tag{23}\] and its derivative with respect to \(x_1'\) is given by: \[f'_{(a,b)}(x_1') = \frac{\left( \frac{x_1'-1}{2}a + \frac{x_1'+3}{2} \right)\left( \frac{a+1}{2} \right) + \left( \frac{x_1'-1}{2}b \right)\left( \frac{b}{2} \right)}{\sqrt{\left( \frac{x_1'-1}{2}a + \frac{x_1'+3}{2} \right)^2 + \left( \frac{x_1'-1}{2}b \right)^2}}.\]

Evaluating this derivative at the boundary \(x_1' = 1\), we obtain: \[f'_{(a,b)}(1) = \frac{\left( 0 + \frac{4}{2} \right)\left( \frac{a+1}{2} \right) + (0)\left( \frac{b}{2} \right)}{\sqrt{\left( 0 + \frac{4}{2} \right)^2 + 0^2}} = \frac{a+1}{2}.\] Taking the expectation over \(\mathcal{D}\) and applying \(y\)-axis symmetry (\(\mathbb{E}_{(a,b)\sim\mathcal{D}}[a] = 0\)), the derivative of the expected distance to \(x_1\) at the boundary \(x_1'=1\) evaluates to: \[\mathbb{E}_{(a,b)\sim\mathcal{D}}\left[ f'_{(a,b)}(1) \right] = \frac{\mathbb{E}_{(a,b)\sim\mathcal{D}}[a] + 1}{2} = \frac{1}{2} > 0.\]

Because the mapped coordinates are affine functions of \(x_1'\) and the Euclidean norm is convex, the composite function \(\mathbb{E}_{(a,b)\sim\mathcal{D}}\left[ f_{(a,b)}(x_1') \right]\) is convex with respect to \(x_1'\) on \([1, \infty)\). A convex function with a strictly positive derivative at its left boundary is increasing across its entire domain. Since the expected distance at the boundary \(x_1'=1\) is \(2\), we conclude that the expected distance remains at least \(2\) for all \(x_1' \ge 1\). ◻

Proof. Let \(z'\) be the chord midpoint of the arc \([0, \phi]\), and let the agent be at \(x_i\). Applying the Law of Cosines to the triangle defined by the three points \(x_i\), \(z'\), and \(O\), we have \[\begin{align} D(\theta, \phi)^2 &= \|x_i - O\|^2 + \|O - z'\|^2 - 2 \cdot \|x_i - O\| \cdot \|O - z'\| \cdot \cos\left(\theta - \frac{\phi}{2}\right) \\ &= 1 + \cos^2\left(\frac{\phi}{2}\right) - 2\cos\left(\frac{\phi}{2}\right)\cos\left(\frac{2\theta - \phi}{2}\right). \end{align}\] Expanding the cross-term using the cosine difference formula, noting \(\cos\left(\frac{2\theta - \phi}{2}\right) = \cos\left(\frac{\theta}{2} - \frac{\phi-\theta}{2}\right)\), we obtain: \[\cos\left(\frac{2\theta - \phi}{2}\right) = \cos\left(\frac{\theta}{2}\right)\cos\left(\frac{\phi-\theta}{2}\right) + \sin\left(\frac{\theta}{2}\right)\sin\left(\frac{\phi-\theta}{2}\right).\] Substituting this into the equation for \(D(\theta, \phi)^2\) yields: \[D(\theta, \phi)^2 = 1 + \cos^2\left(\frac{\phi}{2}\right) - 2\cos\left(\frac{\phi}{2}\right)\left[\cos\left(\frac{\theta}{2}\right)\cos\left(\frac{\phi-\theta}{2}\right) + \sin\left(\frac{\theta}{2}\right)\sin\left(\frac{\phi-\theta}{2}\right)\right].\] To factor this into perfect squares, we substitute \(1 = \sin^2\left(\frac{\theta}{2}\right) + \cos^2\left(\frac{\theta}{2}\right)\) and expand \(\cos^2\left(\frac{\phi}{2}\right) = \cos^2\left(\frac{\phi}{2}\right)\left[\sin^2\left(\frac{\phi-\theta}{2}\right) + \cos^2\left(\frac{\phi-\theta}{2}\right)\right]\). Grouping the respective sine and cosine components of \(\frac{\theta}{2}\) gives the stated sum of perfect squares. ◻

Proof. Let \(v = \frac{\theta}{2}\) and \(u = \frac{\phi}{2}\). Applying Lemma [lem:distance95factorization] with angles \(2v\) and \(2u\) we obtain: \[\begin{align} D(v, u)^2 &= \big(\sin v - \cos u \sin(u-v)\big)^2 + \big(\cos v - \cos u \cos(u-v)\big)^2\\ &= g(v, u)^2 + \big(\cos v - \cos u \cos(u-v)\big)^2. \end{align}\] The second term of this expression expands to: \[\begin{align} &\big(\cos v - \cos u \cos(u - v)\big)^2\\ &= \cos^2 v - 2\cos v \cos u \cos(u-v) + \cos^2 u \cos^2(u-v). \end{align}\] Applying the product-to-sum identity, \(2\cos u \cos(u-v) = \cos v + \cos(2u-v)\), allows us to simplify the expression to: \[\begin{align} \cos^2 v - \cos v\left[\cos v + \cos(2u-v)\right] + \cos^2 u \cos^2(u-v) = \sin^2 u \sin^2(u-v). \end{align}\] Finally, using that \(\sin^2 u = (1 - \cos u)(1 + \cos u)\), the term simplifies to \((1 + \cos u)h(v, u)\). ◻

Proof. Let \(v = \frac{\theta}{2}\) and \(u = \frac{\phi}{2}\). Let \(A'\) be the new extreme point at angle \(\phi = 2u\). The selection probability of the extremes \(B\) and \(A'\) is \(\lambda(2u) = \frac{\cos(u)}{2(1+\cos(u))}\), while the selection probability of the new chord midpoint \(z'\) is: \[1-2\cdot\lambda(2u) = 1- \frac{\cos(u)}{1+\cos(u)} = \frac{1}{1+\cos(u)}.\] Direct substitution of these probabilities and the distances to the outputs (\(\|x_i-B\| = 2\cdot\sin(v)\) and \(\|x_i-A'\| = 2\cdot\sin(u-v)\)) into \(\mathbb{E}[d(\mathcal{M}(\boldsymbol{x'}),x_i)]\) we obtain: \[\begin{align} \mathbb{E}[d(\mathcal{M}(\boldsymbol{x'}),x_i)] &= \lambda(2u)\cdot\|x_i-B\| + \lambda(2u)\cdot\|x_i-A'\| + (1-2\cdot\lambda(2u))\cdot\|x_i-z'\|\\ &= \frac{\cos(u)\cdot\sin(v) + \cos(u)\cdot\sin(u-v) + D(v,u)}{1+\cos(u)} \\ &= \sin(v) + \frac{D(v,u) - \big(\sin(v) - \cos(u)\cdot\sin(u-v)\big)}{1+\cos(u)}\\ &= \sin\left(\frac{\theta}{2}\right) + \frac{D(\theta, \phi) - g(\theta, \phi)}{1+\cos\left(\frac{\phi}{2}\right)}. \end{align}\] ◻

Proof. To prove the lemma, it suffices to show that the derivative of \(w(\phi)\) with respect to \(\phi\) is positive for \(\phi \in (\theta, \pi)\). Let \(u = \frac{\phi}{2}\) and \(v = \frac{\theta}{2}\). By the chain rule, we need \(\frac{dw}{du} > 0\) for all \(u \in (v, \pi/2)\).

Differentiating \(w(u)\) using the quotient rule is inconvenient due to the complexity of the derivatives. Instead, we will find \(\frac{dw}{du}\) using the Implicit Function Theorem.

By the definition of \(w(u)\), we have: \[\label{eq:dist95w} D(v,u) = w(u)\cdot(1+\cos(u)) + g(v,u).\tag{24}\] Lemma [lem:internal95identities] gives the identity: \[\label{eq:dist95sq} D(v,u)^2 - g(v,u)^2 = (1+\cos(u))\cdot h(v,u).\tag{25}\] Substituting 24 into 25 and expanding gives: \[\begin{align} w(u)^2\cdot(1+\cos(u))^2 + 2 w(u)\cdot(1+\cos(u))\cdot g(v,u) &= (1+\cos(u))\cdot h(v,u). \end{align}\] Because \(u \in (v, \pi/2)\), we know \(1+\cos(u) > 0\). Dividing by this factor we obtain: \[\label{eq:curve95zero} w(u)^2\cdot(1+\cos(u)) + 2 w(u)\cdot g(v,u) - h(v,u) = 0.\tag{26}\]

To apply the Implicit Function Theorem, we define the continuously differentiable function \(F\): \[\label{eq:implicit95F} F(x, y) := y^2\cdot(1+\cos(x)) + 2y\cdot g(v,x) - h(v,x).\tag{27}\] Equation 26 implies that \(F(u, w(u)) = 0\). We evaluate the partial derivative of \(F\) with respect to \(y\) at the point \((u, w(u))\): \[\label{eq:partial95y} \frac{\partial F}{\partial y}(u, w(u)) = 2 w(u)\cdot(1+\cos(u)) + 2\cdot g(v,u) = 2D(v,u).\tag{28}\] Because the agent and the chord midpoint are distinct points when \(u > v \ge 0\), the distance \(D(v,u)\) is positive. Since \(\frac{\partial F}{\partial y} > 0\), the Implicit Function Theorem guarantees that \(w(u)\) is a \(\mathcal{C}^1\) function on this domain, and its derivative is: \[\frac{dw}{du} = -\frac{\frac{\partial F}{\partial x}(u, w(u))}{\frac{\partial F}{\partial y}(u, w(u))}.\] Because the denominator is positive, the sign of \(\frac{dw}{du}\) is determined by the numerator. Evaluating \(-\frac{\partial F}{\partial x}\) at \((u, w(u))\) we obtain a quadratic expression in \(w(u)\), which we abbreviate as \(w\) for readability: \[\label{eq:partial95u} -\frac{\partial F}{\partial x}(u, w(u)) = w^2\cdot\sin(u) - 2 w\cdot\frac{\partial g}{\partial u} + \frac{\partial h}{\partial u}.\tag{29}\]

Computing the partial derivatives of \(g(v,u)\) and \(h(v,u)\) gives \(\frac{\partial g}{\partial u} = -\cos(2 u - v)\) and \(\frac{\partial h}{\partial u} = \sin(u)\cdot\sin^2(u-v) + (1-\cos(u))\cdot\sin(2(u-v))\). We evaluate the sign of 29 over two subcases:

• Case \(\mathbf{\frac{\partial g}{\partial u} \le 0}\): Since \(h(v,u) \ge 0\), equation 25 ensures \(D(v,u)^2 \ge g(v,u)^2\), meaning \(D(v,u) \ge g(v,u)\) and therefore \(w \ge 0\). This implies \(-2\cdot w\cdot\frac{\partial g}{\partial u} \ge 0\). Because \(\sin(u) > 0\) and \(\frac{\partial h}{\partial u} > 0\) for \(u \in (v, \pi/2)\), the entire expression in 29 is positive.

• Case \(\mathbf{\frac{\partial g}{\partial u} > 0}\): We analyze the discriminant of 29 , \(\Delta = 4\cdot\left(\frac{\partial g}{\partial u}\right)^2 - 4\cdot\sin(u)\cdot\frac{\partial h}{\partial u}\). Expanding we obtain: \[\label{eq:discriminant} \frac{\Delta}{4} = \cos(u-v)\cdot\left[\cos^2(u)\cdot\cos(u-v) - 2\cdot\sin(u)\cdot\sin(u-v)\right].\tag{30}\] The assumption \(\frac{\partial g}{\partial u} > 0\) implies \(0>\cos(2 u-v) = \cos(u)\cdot\cos(u-v)- \sin(u)\cdot\sin(u-v)\), we obtain \(\cos(u)\cdot\cos(u-v) < \sin(u)\cdot\sin(u-v)\). Because \(u \in (0, \pi/2)\), multiplying by \(\cos(u) \in (0,1)\) and using the bound \(\cos(u) < 2\) gives: \[\cos^2(u)\cdot\cos(u-v) < 2\cdot\sin(u)\cdot\sin(u-v).\] This ensures the bracketed term in 30 is negative, meaning \(\Delta < 0\). With a positive leading coefficient (\(\sin(u) > 0\)) and a negative discriminant, the quadratic has no real roots and remains positive for all \(w\).

In both cases, we obtain \(\frac{dw}{du} > 0\). Thus, the expected cost function increases with respect to the spanning angle \(\phi\). ◻