Answer: \(R^*(\gamma)=\max\{3/2,\,2-\gamma\}\) for every \(\gamma\ge0\), with the infimum attained.
Theorem 2.3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor all α ∈[0, 1/2], GENERALIZED-LRMα is a (group) strategyproof mecha- nism for the 1-facility location problem. Moreover, on loca- tion profile x ∈Rn, the expectation of its maximum cost is (3/2 + α) · opt(x) (that is, its approximation ratio is 3/2 + α), and the standard deviation of its maximum cost is (1/2 −α) · opt(x).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite-support rational distribution \(\mu\) over ideal locations on \(\mathbb{R}\), let a randomized mechanism choose a facility location \(Y\). For each \(\gamma\), determine the minimum worst-case ratio \(\mathbb{E}[\max_{x\in\operatorname{supp}\mu}|x-Y|]/(\operatorname{diam}(\operatorname{supp}\mu)/2)\), subject to normalized standard deviation at most \(\gamma\) on every positive-diameter society and group strategyproofness against deviations by positive-mass submeasures.
A society is a finitely supported probability measure \(\mu\) on \(\mathbb R\), given by the list of its \(\tau\) distinct ideal locations and their positive binary-rational masses, summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
A mechanism \(M\) maps every such society to a distribution of one facility location \(Y\in\mathbb R\); individual cost is \(c_M(x;\mu)=\mathbb E_{Y\sim M(\mu)}|x-Y|\). Locations and reports may be any real numbers. On rationally encoded inputs, let \(L\) be the total input bit length; state running times in \(\tau,L\) and any encoded parameters, with the number of facilities fixed at \(m=1\).
A coalition is any nonzero binary-rational submeasure \(\sigma\le\mu\). It may split and relocate its mass into any finitely supported binary-rational measure \(\nu\) on \(\mathbb R\) with \(\nu(\mathbb R)=\sigma(\mathbb R)\), producing \(\mu'=\mu-\sigma+\nu\). Group strategyproofness means that every such deviation has some \(x\in\operatorname{supp}\sigma\) with \(c_M(x;\mu')\ge c_M(x;\mu)\): a coalition cannot make all its members strictly better off in expected cost.
Write \(D_\mu=\operatorname{diam}(\operatorname{supp}\mu)\), \(C_\mu(Y)=\max_{x\in\operatorname{supp}\mu}|x-Y|\), and \(o_\mu=D_\mu/2\). Require finite second moments of \(C_\mu(Y)\); on singleton societies require the facility at the unique ideal location almost surely.
For \(\gamma\in\mathbb R_{\ge0}\), let \(\mathcal M_\gamma\) contain all group-strategyproof mechanisms satisfying \(\operatorname{sd}_{Y\sim M(\mu)}(C_\mu(Y))/o_\mu\le\gamma\) on every society with \(D_\mu>0\).
What is the optimal approximation tradeoff \(R^*(\gamma)=\inf_{M\in\mathcal M_\gamma}\sup_{\mu:D_\mu>0}\mathbb E_{Y\sim M(\mu)}[C_\mu(Y)]/o_\mu\), for every \(\gamma\in\mathbb R_{\ge0}\)?
For finite-agent societies, group-strategyproof mechanisms achieve approximation ratio \(3/2+\alpha\) and normalized standard deviation \(1/2-\alpha\) for every \(\alpha\in[0,1/2]\); a matching worst-case lower bound holds even under individual strategyproofness ([source](https://www.cs.cmu.edu/~dwajc/pdfs/procaccia18.pdf)).
No result settling this exact mass-coalition tradeoff was located in the literature search.
The optimal tradeoff is
\[ R^*(\gamma)=\max\left\{\frac32,\,2-\gamma\right\} \qquad\text{for every }\gamma\ge0. \]
The infimum is attained. Rational masses allow every individual mass deviation to be represented by a finite coalition of equally weighted agents. This representation is used only in the proof; implementing the optimal mechanism requires no population expansion.
We use the finite-agent results supplied in the question, in the following precise form.
For every \(\alpha\in[0,1/2]\), the mechanism that selects uniformly from the four indexed locations
\[ a,\qquad \frac{a+b}{2}-\alpha(b-a),\qquad \frac{a+b}{2}+\alpha(b-a),\qquad b, \]
where \(a,b\) are the extreme reports, is group strategyproof in expected distance. Coincident indexed locations retain their combined probability.
Moreover, for every \(r\in[3/2,2)\), any individually strategyproof two-agent mechanism with worst-case expected approximation ratio at most \(r\) satisfies
\[ \sup_{u\ne v} \frac{\operatorname{sd}\!\left(\max\{|u-Y|,|v-Y|\}\right)} {|u-v|/2} \ge 2-r. \]
These are the upper construction and worst-case lower bound of [Theorems 2.3 and 2.4 in the cited paper](https://www.cs.cmu.edu/~dwajc/pdfs/procaccia18.pdf). The latter is a supremum statement; it does not assert a pointwise bound at every profile.
Fix \(\gamma\ge0\), and put \(s=\min\{\gamma,1/2\}\). For a society \(\mu\), let
\[ a=\min\operatorname{supp}\mu,\qquad b=\max\operatorname{supp}\mu,\qquad D=b-a. \]
Define \(M_s(\mu)\) by selecting each of the following four indexed locations with probability \(1/4\):
\[ a,\qquad a+sD,\qquad b-sD,\qquad b. \]
This is the finite-agent construction above with \(\alpha=1/2-s\). On a singleton society, all four locations coincide with its unique ideal location.
We now verify group strategyproofness for every permitted mass deviation, including splitting.
Let \(\sigma\le\mu\) be a nonzero coalition and let \(\nu\) be a permitted report measure of equal total mass. Set \(\mu'=\mu-\sigma+\nu\). Because all masses involved are rational and both supports are finite, there is a positive integer \(N\) such that every atomic mass of \(\mu,\sigma,\nu\) is an integer multiple of \(1/N\).
Represent \(\mu\) by \(N\) labelled agents, placing exactly \(N\mu(\{x\})\) agents at each \(x\in\operatorname{supp}\mu\). Select exactly \(N\sigma(\{x\})\) of those agents for the deviating coalition. This is possible because \(\sigma\le\mu\), and the selected coalition is nonempty.
Assign reports to the selected agents so that exactly \(N\nu(\{z\})\) selected agents report each \(z\in\operatorname{supp}\nu\). Such an assignment exists because
\[ \sum_z N\nu(\{z\})=\sum_x N\sigma(\{x\}). \]
The resulting empirical report measure is exactly \(\mu'\).
The finite-agent mechanism depends only on the extreme reports. Its output distribution before and after this deviation therefore agrees exactly with \(M_s(\mu)\) and \(M_s(\mu')\), respectively. Finite-agent group strategyproofness supplies a selected agent, whose true location is some \(x\in\operatorname{supp}\sigma\), such that
\[ c_{M_s}(x;\mu')\ge c_{M_s}(x;\mu). \]
This is precisely the required mass-coalition condition. The argument accommodates any number of reported locations and any permitted splitting of coalition mass.
Suppose \(D>0\), and write \(o=D/2\). Since \(0\le s\le1/2\), all four output locations lie in \([a,b]\).
At either endpoint, the maximum cost equals \(D=2o\). At either inner location, it equals
\[ (1-s)D=2(1-s)o. \]
Thus \(C_\mu(Y)/o\) takes the two values \(2\) and \(2(1-s)\), each with probability \(1/2\), allowing coincidence when \(s=0\). Consequently,
\[ \frac{\mathbb E[C_\mu(Y)]}{o}=2-s, \qquad \frac{\operatorname{sd}(C_\mu(Y))}{o}=s. \]
The distribution has finite support, so its second moment is finite. Together with the singleton condition and Section 2, this proves \(M_s\in\mathcal M_\gamma\). Hence
\[ R^*(\gamma)\le 2-\min\{\gamma,1/2\} =\max\{3/2,2-\gamma\}. \]
Let \(M\in\mathcal M_\gamma\), and denote its worst-case expected approximation ratio by \(r\). If \(r\) is infinite, the desired lower bound is immediate. Assume henceforth that \(r\) is finite.
Define a two-agent mechanism by
\[ F(u,v)=M\!\left(\frac12\delta_u+\frac12\delta_v\right). \]
Moving either agent’s report is an allowed mass deviation: select the submeasure of mass \(1/2\) at that agent’s true location and relocate it to the reported location. This remains valid when both agents occupy the same location. The mass-coalition condition therefore implies that \(F\) is individually strategyproof.
The singleton requirement gives \(F(u,u)=\delta_u\). For \(u\ne v\), its maximum-cost objective and optimum coincide with those of the corresponding society. Thus \(F\) has approximation ratio at most \(r\), finite second moments, and normalized standard deviation at most \(\gamma\) at every nondegenerate profile.
Let \(Y\sim F(0,1)\). The triangle inequality gives
\[ \mathbb E|Y|+\mathbb E|1-Y|\ge1. \]
At least one endpoint therefore has expected cost at least \(1/2\).
If \(\mathbb E|1-Y|\ge1/2\), strategyproofness prevents the agent at \(1\) from improving by reporting \(2\). For \(Y'\sim F(0,2)\), this yields
\[ \mathbb E|1-Y'|\ge\frac12. \]
For every real \(y\),
\[ \max\{|y|,|2-y|\}=1+|y-1|. \]
The optimum at \((0,2)\) equals \(1\), so this profile has expected approximation ratio at least \(3/2\).
If instead \(\mathbb E|Y|\ge1/2\), let the agent at \(0\) report \(-1\). Strategyproofness gives expected distance from \(0\) at least \(1/2\) under \(F(-1,1)\). Using
\[ \max\{|y+1|,|y-1|\}=1+|y|, \]
and again an optimum of \(1\), gives the same lower bound. Hence \(r\ge3/2\).
Suppose \(0\le\gamma<1/2\) and, for contradiction, \(r<2-\gamma\). The preceding argument gives
\[ \frac32\le r<2. \]
All hypotheses of the finite-agent lower bound in Section 1 have now been verified for \(F\). Applying it gives
\[ \sup_{u\ne v} \frac{\operatorname{sd}(C_{u,v}(Y))}{|u-v|/2} \ge 2-r>\gamma, \]
contradicting the uniform standard-deviation bound inherited from \(M\).
Therefore \(r\ge2-\gamma\) when \(\gamma<1/2\). When \(\gamma\ge1/2\), the bound \(r\ge3/2\) suffices. Together with Section 3, this proves the stated formula.
The mechanism scans the \(\tau\) distinct locations to find the two extremes, then computes at most four output atoms. It uses \(O(\tau)\) comparisons and \(O(1)\) additional arithmetic operations, with the number of facilities fixed at \(m=1\).
For rationally encoded locations of total input length \(L\) and a rational parameter \(\gamma\) of bit length \(B\), elementary exact integer arithmetic gives the conservative bound
\[ O\!\left(\tau(L+B)^2\right) \]
bit operations. The output description has length \(O(L+B)\). Masses need not be expanded into agents.
For an arbitrary unencoded real parameter, the four formulas define the mechanism mathematically; a bit running time requires an encoding or computational representation of that parameter.
⟨structured verdict parsed — rendered above⟩
The claimed tradeoff is proved. The finite-agent results have the required scope, the transfer to mass coalitions handles splitting, and the lower bound applies to the induced two-agent mechanism. No major or minor mathematical issues were found.
Theorem 2.3 establishes group strategyproofness for the four-location construction for every finite population and every \(\alpha\in[0,1/2]\). The indexed interpretation at coincident locations agrees with the paper’s stated probabilities and moment formulas.
Theorem 2.4 and its proof establish the worst-case normalized standard-deviation bound used by the prover, including for two-agent mechanisms. The prover correctly uses a supremum bound rather than asserting a bound at each profile. Substituting \(\alpha=r-3/2\) gives the stated threshold \(2-r\). No anonymity, continuity, or restriction of outputs to the reported interval is required. See [Theorems 2.3–2.4 and the lower-bound proof](https://www.cs.cmu.edu/~dwajc/pdfs/procaccia18.pdf).
Every society has finite, nonempty support, so its extreme locations exist. The parameter \(s=\min\{\gamma,1/2\}\) belongs to \([0,1/2]\), and \(\alpha=1/2-s\) belongs to the cited theorem’s parameter range.
Each of the four indexed outputs has probability \(1/4\). Coinciding outputs combine their probabilities. On singleton societies, all outputs equal the unique ideal location, as required.
The finitely many atomic masses of \(\mu,\sigma,\nu\) have a common denominator \(N\). Thus all agent counts used in the argument are nonnegative integers.
The inequality \(\sigma\le\mu\) ensures that the specified coalition can be selected from the agents representing \(\mu\). Its nonzero mass makes it nonempty. Equality of the total masses of \(\sigma\) and \(\nu\) ensures that every selected agent can receive exactly one report with the specified report multiplicities.
The resulting empirical measure is precisely \(\mu-\sigma+\nu\), including when reports overlap existing locations. The number of agents remains fixed even when the support size changes.
Because the finite-agent construction depends only on the extreme reports, its distributions agree with the society mechanism before and after the deviation. The selected agent supplied by finite-agent group strategyproofness has a true location in \(\operatorname{supp}\sigma\). Its expected-cost inequality is exactly the required coalition condition.
This argument covers arbitrary real locations, splitting, coincident reports, and singleton profiles. Population expansion is used only to establish strategyproofness.
For \(D>0\), maximum distance over the society’s support is determined by its two extremes. The endpoint outputs have maximum cost \(D\); the inner outputs have maximum cost \((1-s)D\).
Therefore the normalized maximum cost takes values \(2\) and \(2(1-s)\), each with probability \(1/2\). Its mean is \(2-s\), and its standard deviation is \(s\). These calculations remain valid at both boundary parameters: \(s=0\) gives a constant maximum cost, and \(s=1/2\) makes the two inner outputs coincide.
Finite support of the output distribution guarantees finite second moments on every society. Hence the construction belongs to \(\mathcal M_\gamma\) and establishes the claimed upper bound.
The society \(\frac12\delta_u+\frac12\delta_v\) is admissible for every pair of real locations. Relocating one agent corresponds to an allowed coalition of mass \(1/2\). This remains valid when \(u=v\), because the coalition is then a submeasure of the unit mass at that location.
Thus the society mechanism’s coalition condition implies individual strategyproofness of \(F\). The singleton condition supplies \(F(u,u)=\delta_u\). At nondegenerate profiles, the maximum-cost objective, optimum, approximation guarantee, and normalized standard-deviation guarantee are inherited without alteration.
The direct argument for \(r\ge3/2\) uses the triangle inequality correctly. Each strategyproofness comparison evaluates the deviating agent’s cost at its true location. Both displayed maximum-distance identities hold for every real output, including outputs outside the reported interval. The two cases exhaust the possibilities.
For \(\gamma<1/2\), the contradiction assumption gives \(3/2\le r<2\), exactly the required theorem range. The cited bound then makes the supremum of normalized standard deviations strictly greater than \(\gamma\), contradicting the inherited uniform bound.
For \(\gamma\ge1/2\), the direct lower bound suffices. Infinite worst-case ratios are correctly handled separately. The matching construction therefore establishes both the formula and attainment of the infimum.
Finding the extremes requires \(O(\tau)\) comparisons, followed by a constant number of rational arithmetic operations. For rationally encoded locations and parameter, the claimed conservative bit bound \(O(\tau(L+B)^2)\) and output length \(O(L+B)\) are valid.
The distinction between encoded rational parameters and arbitrary unencoded real parameters is explicit and appropriate. No computational population expansion is required.
No additional clarification is needed to make the argument verifiable.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.