Answer: Every deterministic mass-SGSP mechanism satisfies \(R_d(F)=+\infty\) for every fixed \(d\in\mathbb Q_{>0}\).
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateNo deterministic strong group strategyproof mechanism has an approximation ratio less than $\frac{n+2}{4}$ for the social cost.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(d>0\) and a rational finite-support probability measure \(\mu=\sum_{j=1}^{\tau}\mu_j\delta_{x_j}\) over ideal locations on \(\mathbb R\), a deterministic mechanism \(F\) chooses a range \((a,b)\) with \(b-a\le d\). Let \(SC_\mu(a,b)=\int c_d(x;a,b)\,d\mu(x)\), and let \(OPT_\mu\) be its minimum over feasible ranges. Call \(F\) mass-SGSP if there are no submeasure \(\eta\le\mu\) and replacement measure \(\nu\) with \(\nu(\mathbb R)=\eta(\mathbb R)\) such that, under \(F(\mu-\eta+\nu)\), the coalition is weakly better off \(\eta\)-almost everywhere and strictly better off on positive \(\eta\)-mass. Prove or refute that every deterministic mass-SGSP \(F\) has unbounded worst-case ratio \(SC_\mu(F(\mu))/OPT_\mu\) over rational finite-support societies.
Fix \(d\in\mathbb Q_{>0}\), with the facility at \(0\). A society is given by its support: \(\mu=\sum_{j=1}^{\tau}\mu_j\delta_{x_j}\), with distinct \(x_j\in\mathbb Q\), positive binary rational masses, and \(\sum_j\mu_j=1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length. Any running time is stated in \(\tau,L\); there is no candidate-count parameter \(m\).
A feasible outcome is an endpoint pair \((a,b)\in\mathbb R^2\) with \(0\le b-a\le d\), representing the closed accessibility interval \([a,b]\). Define \(c_d(x;a,b)=|x|-\operatorname{length}([\min\{x,0\},\max\{x,0\}]\cap[a,b])\).
Set \(SC_\mu(a,b)=\sum_j\mu_jc_d(x_j;a,b)\) and \(OPT_\mu=\min_{0\le b-a\le d}SC_\mu(a,b)\). A deterministic mechanism \(F\) selects one feasible outcome for every society, with no computational restriction.
Call \(F\) mass-SGSP if there are no nonnegative rational finite-support measures \(\eta\le\mu\) and \(\nu\) on \(\mathbb Q\), with \(\eta(\mathbb R)=\nu(\mathbb R)>0\), such that, writing \(\mu'=\mu-\eta+\nu\), we have \(c_d(x;F(\mu'))\le c_d(x;F(\mu))\) for \(\eta\)-almost every \(x\), strictly on a set of positive \(\eta\)-mass. Coalition members may retain their reports, and each type's mass may be split.
Define \(R_d(F)=\sup_\mu SC_\mu(F(\mu))/OPT_\mu\), with \(0/0=1\) and a positive numerator divided by zero equal to \(+\infty\).
For every fixed \(d\in\mathbb Q_{>0}\), must every deterministic mass-SGSP mechanism satisfy \(R_d(F)=+\infty\), or does one exist with \(R_d(F)<+\infty\)?
For discrete societies of \(n\) agents, deterministic SGSP mechanisms have social-cost approximation ratio at least \((n+2)/4\); a deterministic SGSP mechanism achieves \(n-1\) for \(n\ge2\). [Verified source](https://arxiv.org/html/2409.08993v1).
No published result settling exactly the mass-SGSP question above was located.
For every fixed \(d\in\mathbb Q_{>0}\), every deterministic mass-SGSP mechanism satisfies \(R_d(F)=+\infty\). Unboundedness is already witnessed by societies with \(\tau\le 3\).
The proof adapts the three-profile construction underlying the discrete lower bound in [Theorem 3 of the supplied paper](https://arxiv.org/html/2409.08993v1). We verify the mass deviations explicitly, including retained reports and rationality.
Fix a deterministic mass-SGSP mechanism \(F\).
The society \(\delta_d\) has optimum zero. If \(F(\delta_d)\) gives its type positive cost, then \(R_d(F)=+\infty\) immediately. Otherwise, writing \(F(\delta_d)=(a,b)\), zero cost means that \([a,b]\) covers the entire segment \([0,d]\). Because \(b-a\le d\), necessarily \(F(\delta_d)=(0,d)\).
The same argument applies to \(\delta_{-d}\). Thus it remains to consider mechanisms satisfying
\(F(\delta_d)=(0,d),\qquad F(\delta_{-d})=(-d,0).\)
We first prove that, for any society supported in \([-d,d]\) with positive mass at both \(-d\) and \(d\), its selected interval contains \(0\).
Indeed, suppose its outcome \((a,b)\) has \(a>0\). Let the entire society report \(d\), using the admissible deviation \(\eta=\mu\), \(\nu=\delta_d\). The resulting outcome is \((0,d)\). Every nonpositive true type has unchanged cost, since both intervals save it zero distance. Every positive true type now has zero cost and therefore weakly benefits. The positive mass at \(d\) strictly benefits: its original saving was less than \(d\) because \(a>0\). This contradicts mass-SGSP.
If \(b<0\), the entire society can instead report \(-d\), with the symmetric contradiction. Consequently \(a\le0\le b\), as claimed.
For any such outcome, define its left and right reach by \(p=-a\) and \(q=b\). Feasibility gives
\(p\ge0,\qquad q\ge0,\qquad p+q\le d.\)
For \(0\le t\le d\), the costs are
\(c_d(-t;a,b)=\max\{t-p,0\},\qquad c_d(t;a,b)=\max\{t-q,0\}.\)
Choose rational numbers \(0<\alpha<1/2\) and \(0<\varepsilon<d\). Consider
\(\mu_0=\frac12\delta_{-d}+\frac12\delta_d,\)
\(\mu_L=\alpha\delta_{-d}+\left(\frac12-\alpha\right)\delta_{-\varepsilon}+\frac12\delta_d,\)
\(\mu_R=\frac12\delta_{-d}+\left(\frac12-\alpha\right)\delta_{\varepsilon}+\alpha\delta_d.\)
All three outcomes contain \(0\), by the preceding argument. Write their reaches as \((p_0,q_0)\), \((p_L,q_L)\), and \((p_R,q_R)\).
Suppose \(p_L>p_0\). At \(\mu_0\), the negative half can use
\(\eta=\frac12\delta_{-d},\qquad \nu=\alpha\delta_{-d}+\left(\frac12-\alpha\right)\delta_{-\varepsilon}.\)
This produces \(\mu_L\). Every coalition member has true type \(-d\), so every member strictly benefits when the left reach increases. This is forbidden.
Suppose instead \(p_L<p_0\). At \(\mu_L\), use the reverse deviation
\(\eta=\alpha\delta_{-d}+\left(\frac12-\alpha\right)\delta_{-\varepsilon},\qquad \nu=\frac12\delta_{-d}.\)
This produces \(\mu_0\). The true type \(-\varepsilon\) weakly benefits because its cost is nonincreasing in the left reach. The retained positive mass \(\alpha\) at true type \(-d\) strictly benefits. This is also forbidden.
Therefore \(p_L=p_0\).
If \(q_L>q_0\), let the entire society \(\mu_0\) report \(\mu_L\): take \(\eta=\mu_0\), \(\nu=\mu_L\). All negative true types have unchanged cost because \(p_L=p_0\), while the positive half at \(d\) strictly benefits.
If \(q_L<q_0\), use the reverse full-society deviation from \(\mu_L\) to \(\mu_0\). Again all negative true types have unchanged cost, and the positive half at \(d\) strictly benefits.
Both possibilities contradict mass-SGSP. Hence \(q_L=q_0\).
For \(\mu_R\), the same comparisons with signs exchanged first force \(q_R=q_0\) through right-half deviations, and then force \(p_R=p_0\) through full-society deviations. Thus all three outcomes have common reaches \(p,q\), satisfying \(p+q\le d\).
Every deviation above uses nonnegative rational measures of equal mass. The reports retained by coalition members are included in both \(\eta\) and \(\nu\), exactly as permitted by the definition.
Dropping the nonnegative costs of the near-zero types gives
\(SC_{\mu_L}(F(\mu_L))\ge\alpha(d-p)+\frac12(d-q),\)
\(SC_{\mu_R}(F(\mu_R))\ge\frac12(d-p)+\alpha(d-q).\)
Taking the average of these lower bounds yields
\(\max\{SC_{\mu_L}(F(\mu_L)),SC_{\mu_R}(F(\mu_R))\}\ge\frac{\frac12+\alpha}{2}(2d-p-q)\ge\left(\frac14+\frac{\alpha}{2}\right)d.\)
Meanwhile, the feasible interval \([0,d]\) gives
\(OPT_{\mu_L}\le\alpha d+\left(\frac12-\alpha\right)\varepsilon.\)
The interval \([-d,0]\) gives the identical bound for \(OPT_{\mu_R}\). Therefore
\(R_d(F)\ge\frac{\left(\frac14+\frac{\alpha}{2}\right)d}{\alpha d+\left(\frac12-\alpha\right)\varepsilon}.\)
This inequality also holds if either optimum is zero, using the stipulated infinite-ratio convention whenever its numerator is positive.
Now choose \(\alpha=2^{-k}\) and \(\varepsilon=\alpha d\), for any integer \(k\ge2\). These locations are rational, and all masses are positive dyadic rationals. Each perturbed society has exactly three distinct support points. The preceding bound becomes
\(R_d(F)\ge\frac{\frac14+\frac{\alpha}{2}}{\alpha\left(\frac32-\alpha\right)}\ge\frac{1}{6\alpha}=\frac{2^k}{6}.\)
Since \(k\) is arbitrarily large, \(R_d(F)=+\infty\). This completes the proof without any computational assumption.
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the stated mass-SGSP question. Every deterministic mass-SGSP mechanism has infinite approximation ratio, with unbounded ratios already on societies of support size at most three. No major or minor issues were found.
For \(\delta_d\), the feasible interval \([0,d]\) gives zero cost. Thus, if the selected outcome has positive cost, the stipulated ratio convention immediately gives \(R_d(F)=+\infty\).
Otherwise, zero cost requires the intersection of the selected interval with \([0,d]\) to have length \(d\). Since the selected interval is closed and has length at most \(d\), it must equal \([0,d]\). The argument for \(\delta_{-d}\) is identical.
The resulting case distinction is exhaustive: either unboundedness is already established on a singleton society, or both displayed endpoint outcomes are forced.
The full-society deviations are admissible: \(\eta=\mu\) satisfies \(\eta\le\mu\), and both \(\eta\) and the replacement singleton measure have total mass one and rational finite support.
If \(a>0\), every nonpositive true type receives zero saving under both the original interval and \([0,d]\). Every positive true type in the stipulated support range receives zero cost under \([0,d]\), hence weakly benefits. The original saving of type \(d\) is strictly less than \(d\), so its positive mass strictly benefits. This violates mass-SGSP.
The case \(b<0\) is symmetric. Because feasibility requires \(a\le b\), these cases exhaust intervals failing to contain zero.
For intervals containing zero, the reach definitions, feasibility inequalities, and displayed cost formulas follow directly from the intersection-length definition. In particular, \(p,q\le d\), so endpoint costs are exactly \(d-p\) and \(d-q\).
The restrictions \(0<\alpha<1/2\) and \(0<\varepsilon<d\) ensure that all displayed masses are positive and sum to one. Each perturbed society has three distinct rational support points.
All three societies have positive mass at both endpoints, so the preceding containment argument applies to every selected outcome.
Left reach for \(\mu_L\). Both displayed half-society deviations have equal removed and replacement mass \(1/2\), and their removed measures are bounded by their respective starting societies. Direct substitution gives the stated destination societies.
If \(p_L>p_0\), all removed mass has true type \(-d\), whose cost strictly decreases. If \(p_L<p_0\), the reverse deviation weakly benefits type \(-\varepsilon\) and strictly benefits the positive mass \(\alpha\) at type \(-d\). Consequently, both strict inequalities are forbidden, establishing \(p_L=p_0\).
The inclusion of retained endpoint reports in the coalition is expressly allowed by the task.
Right reach for \(\mu_L\). With equal left reaches, every negative true type has unchanged cost under the two outcomes. A strict increase in right reach strictly benefits type \(d\). Thus the forward or reverse full-society deviation rules out either strict inequality, establishing \(q_L=q_0\).
Reaches for \(\mu_R\). The stated sign exchange is sufficient and valid. Right-half deviations first force equality of right reaches; the reverse deviation has positive retained mass \(\alpha\) at \(d\), ensuring strict improvement. Full-society deviations then force equality of left reaches because right-side costs are unchanged and type \(-d\) has positive mass.
Therefore, the assertion that all three outcomes share the same reaches is justified. No assumption that the selected interval has length exactly \(d\) is used.
Dropping the near-zero types’ nonnegative costs gives the two stated lower bounds. Their average is correctly computed as
\[ \frac{\frac12+\alpha}{2}(2d-p-q). \]
Since \(p+q\le d\), this is at least \((1/4+\alpha/2)d\). At least one of the two societies therefore has social cost at least this amount.
The proposed comparison intervals give the stated upper bound
\[ \alpha d+\left(\frac12-\alpha\right)\varepsilon \]
on each optimum. This quantity is strictly positive. Applying that common upper bound to whichever society attains the social-cost lower bound justifies the displayed ratio inequality. The zero-optimum convention is handled correctly whenever that selected society has zero optimum.
For every integer \(k\ge2\), the choices \(\alpha=2^{-k}\) and \(\varepsilon=\alpha d\) satisfy every parameter restriction. The locations remain rational, the masses are positive dyadic rationals, and the support points remain distinct.
Substitution gives the stated denominator \(\alpha(3/2-\alpha)\). The final estimate is valid: the numerator is at least \(1/4\), and the denominator is at most \(3\alpha/2\), giving the lower bound \(1/(6\alpha)=2^k/6\).
The mechanism and \(d\) remain fixed while \(k\) grows. Hence the supremum is infinite. Increasing input bit length is permitted; the task asks for a uniform approximation ratio over all admissible societies.
The argument is self-contained. Its reference to the discrete construction is attribution, rather than an application of an external theorem requiring additional hypotheses. No clarification or repair is needed.
This establishes an approximation impossibility without computational restrictions. It does not establish a polynomial-time or computational-hardness classification, so the requested complexity-status field is marked unresolved.
⟨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.