Answer: \(+\infty\): no deterministic strategyproof mechanism has a finite multiplicative approximation guarantee, even allowing dependence on input parameters and masses.
Theorem 5.3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor any d ≥1, there is no deterministic SP o(√m)-approximation mechanism for LINEARd.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a rational distribution \(\mu\) over types \(t=(X_t,Y_t)\), where \(X_t\) is a public bundle and \(Y_t\) its true labels, consider deterministic mechanisms \(F\) mapping reported type distributions to separators in \(\mathrm{LINEAR}_d\). Require that for every type \(t\), every \(0<q\leq\mu_t\), and every alternative label vector \(\hat Y\), \(R_t(F(\mu))\leq R_t(F(\mu-q\delta_t+q\delta_{(X_t,\hat Y)}))\). What is the best worst-case approximation factor for \(F\) against \(\operatorname{OPT}(\mu)=\min_{c\in\mathrm{LINEAR}_d}R_\mu(c)\), and can it be achieved in time polynomial in the dimension, support size, bundle descriptions, and input bit length?
A society is given by its support: the list of \(\tau\) types with positive mass, each mass a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
For \(d\geq1\), a type is \(t=(X_t,Y_t)\), where \(X_t=(x_{t,1},\ldots,x_{t,k_t})\) is a public, nonempty list of points in \(\mathbb Q^d\), and \(Y_t\in\{+,-\}^{k_t}\) is private. Repeated coordinates are allowed, with independently labeled occurrences.
Let \(m=\sum_{t\in\operatorname{supp}(\mu)}k_t\), and let \(L\) be the total binary input length. The class \(\mathrm{LINEAR}_d\) consists of affine separators \(c_{a,b}(x)=+\) exactly when \(a\cdot x+b\geq0\), with \(a\in\mathbb R^d\), \(b\in\mathbb R\); constant classifiers are included.
Define \(R_t(c)=k_t^{-1}\sum_{j=1}^{k_t}\mathbf1\{c(x_{t,j})\ne Y_{t,j}\}\), \(R_\mu(c)=\frac{\sum_t\mu_t k_t R_t(c)}{\sum_t\mu_t k_t}\), and \(\operatorname{OPT}(\mu)=\min_{c\in\mathrm{LINEAR}_d}R_\mu(c)\).
A deterministic mechanism without payments selects one separator from each reported distribution, with all outcome choices fixed as part of the mechanism. Labels may be changed arbitrarily; bundles and their aggregate masses are public and cannot be changed.
To retain arbitrary real mass deviations, define the mechanism on all finitely supported distributions with real masses; computational inputs have rational masses. Require, for every such \(\mu\), every supported \(t\), every real \(0<q\leq\mu_t\), and every \(\hat Y\in\{+,-\}^{k_t}\), \(R_t(F(\mu))\leq R_t(F(\mu-q\delta_t+q\delta_{(X_t,\hat Y)}))\), where \(\delta_t\) is unit mass at \(t\) and both risks use the true labels.
An approximation guarantee \(\alpha\) means \(R_\mu(F(\mu))\leq\alpha\operatorname{OPT}(\mu)\) on every instance; any finite guarantee therefore requires zero error whenever \(\operatorname{OPT}(\mu)=0\).
What is the best worst-case approximation factor, including any necessary dependence on the input parameters and masses, achievable by these deterministic strategyproof mechanisms? Can it be attained on rational inputs in time polynomial in \(d,m,\tau,L\), or is the attainable factor unbounded?
For finite societies with at least two agents and \(M\) total example occurrences, no deterministic strategyproof mechanism achieves an \(o(\sqrt M)\) approximation for any \(d\geq1\); a deterministic strategyproof \(M\)-approximation exists. [Source](https://econcs.seas.harvard.edu/sites/g/files/omnuum6346/files/econcs/files/meir10.pdf)
Verified journal results concern two-classifier or shared-input restrictions and distributions over input points, rather than the mass-deviation model above. [Source](https://procaccia.info/wp-content/uploads/2012/07/spc.pdf) No result settling this exact continuous problem was found.
The attainable worst-case approximation factor is \(\boldsymbol{+\infty}\), for every \(d\geq1\).
More strongly, every deterministic mechanism satisfying the stated strategyproofness condition fails on some perfectly realizable rational instance with \(\tau=1\), \(m=15\), and mass \(1\). Thus allowing the factor to depend on the input parameters or masses does not help. The obstruction holds without any computational restriction.
The proof uses the fact that a distribution contains no individual identities: two equal masses reporting the same public bundle are interchangeable.
Fix \(d\geq1\), and consider the three points
\( x_1=(-1,0,\ldots,0),\qquad x_2=(0,\ldots,0),\qquad x_3=(1,0,\ldots,0). \)
Let \(X\) contain five occurrences of each point, grouped in this order. Its length is \(15\). Encode negative labels by \(0\) and positive labels by \(1\).
For any separator \(c\), let \(\pi(c)\) be its prediction vector on these three points. The possible vectors are exactly
\( \mathcal A=\{000,001,011,111,110,100\}. \)
Indeed, the affine score restricted to this line has the form \(ar+b\). Its positive region on the three ordered points is a prefix, a suffix, the whole set, or the empty set. Both excluded patterns, \(010\) and \(101\), would require two sign changes. Each of the six listed patterns is attainable, including the two constant patterns.
Because repeated coordinates receive identical predictions, every type with bundle \(X\) evaluates a separator solely through its alternative \(\pi(c)\).
For a label vector \(Y\in\{0,1\}^{15}\), write \(t_Y=(X,Y)\). Define
\( H(Y,Z)=\pi\!\left(F\!\left(\tfrac12\delta_{t_Y}+\tfrac12\delta_{t_Z}\right)\right). \)
This is a deterministic rule taking values in \(\mathcal A\). Since its argument is a distribution,
\( H(Y,Z)=H(Z,Y). \)
Furthermore, \(H\) is strategyproof for either argument under the preferences induced by classification error. To change the first argument from \(Y\) to \(\widehat Y\), apply the assumed strategyproofness condition with true type \(t_Y\) and \(q=\tfrac12\). This remains valid when \(Y=Z\): the supported type then has mass \(1\), from which mass \(\tfrac12\) may deviate. Consequently,
\( R_{t_Y}(H(Y,Z))\leq R_{t_Y}(H(\widehat Y,Z)). \)
Here and below, evaluating risk at an alternative means evaluating any separator realizing that prediction vector. Symmetry gives the corresponding condition for the second argument.
All distributions used here have rational masses and support size at most \(2\).
For each \(a\in\mathcal A\), let \(T_a\) label all five occurrences of \(x_i\) by \(a_i\). The singleton distribution \(\delta_{t_{T_a}}\) is perfectly realizable. Suppose, towards a contradiction, that \(F\) has zero error on all six such distributions. Then
\( H(T_a,T_a)=a\qquad\text{for every }a\in\mathcal A. \)
We now show that if label vectors \(Y\) and \(Z\) both induce strict preferences having \(a\) as their most preferred alternative, then
\( H(Y,Z)=a. \)
First, at the profile \((Y,T_a)\), the first argument can report \(T_a\) and obtain \(a\). Strategyproofness therefore forces \(H(Y,T_a)=a\), since \(a\) is the unique best alternative for \(Y\).
Next, at \((Y,Z)\), the second argument can report \(T_a\) and obtain \(H(Y,T_a)=a\). Since \(a\) is also uniquely best for \(Z\), strategyproofness forces \(H(Y,Z)=a\).
Thus zero error on the six singleton instances would imply unanimity on every strict preference domain represented by labels on \(X\).
We use the linked-domain dictatorship theorem of Aswal, Chatterji, and Sen. Two alternatives are *connected* in a domain of strict orders if the domain contains an order ranking the first alternative first and the second second, and another order reversing those top two positions. A domain is *linked* if its alternatives can be ordered so that the first two are connected and each later alternative is connected to at least two earlier ones.
The theorem states that, on a linked domain over at least three alternatives, every strategyproof unanimous social choice function for at least two voters is dictatorial. This precise implication is also covered by [Reffgen, Theorem 3.1](https://www.accessecon.com/pubs/SCW2008/GeneralPDFSCW2008/SCW2008-08-00329S.pdf).
We construct such a domain using the independently labeled repeated occurrences.
Choose \(z\in\{0,1\}^3\) and let \((w_1,w_2,w_3)\) be a permutation of \((1,3,5)\). In group \(i\), label
\( \frac{5+w_i}{2} \)
occurrences by \(z_i\), and the remaining occurrences by \(1-z_i\). These are valid integer counts. For a prediction \(s\), the number of errors is
\( E_{z,w}(s)=\sum_{i=1}^3\frac{5-w_i}{2} +\sum_{i=1}^3w_i\mathbf1\{s_i\ne z_i\} =3+\sum_{i=1}^3w_i\mathbf1\{s_i\ne z_i\}. \)
The subset sums of \((1,3,5)\) are
\( 0,1,3,4,5,6,8,9, \)
which are all distinct. Therefore each constructed label vector induces a strict total order on \(\mathcal A\). Let \(\mathcal D\) be the domain consisting of these induced orders.
We verify linkedness explicitly.
Let
\( a=000,\qquad b=011,\qquad c=110. \)
Relative to the infeasible vector \(z=010\), each of \(a,b,c\) changes exactly one coordinate. The other three alternatives change exactly two coordinates.
For any ordered pair of distinct alternatives from \(\{a,b,c\}\), assign weight \(1\) to the coordinate changed by the first, weight \(3\) to the coordinate changed by the second, and weight \(5\) to the remaining coordinate. Their weighted distances from \(z\) are then \(1\) and \(3\). Every other alternative has distance at least \(4\).
Thus every ordered pair from this triangle occurs as the top two positions of an order in \(\mathcal D\). All three triangle edges are connected.
Any two feasible alternatives differing in one coordinate are connected. To put \(u\) first and its neighbor \(v\) second, choose \(z=u\), assign weight \(1\) to their differing coordinate, and assign weights \(3\) and \(5\) to the others. Their distances are \(0\) and \(1\); every other alternative has distance at least \(3\). Choosing \(z=v\) reverses their top two positions.
Hence the following is a linked ordering:
| Alternative | Two earlier connected alternatives |
|---|---|
| \(000\) | First alternative |
| \(011\) | Connected to \(000\) |
| \(110\) | \(000,\ 011\) |
| \(001\) | \(000,\ 011\) |
| \(111\) | \(011,\ 110\) |
| \(100\) | \(000,\ 110\) |
The third row follows from the connected triangle; the last three rows follow from one-coordinate differences.
For each order \(P\in\mathcal D\), fix one representing label vector \(Y(P)\). Define
\( f(P,Q)=H(Y(P),Y(Q)). \)
Every hypothesis of the linked-domain theorem holds:
Therefore \(f\) is dictatorial.
But \(f\) is symmetric:
\( f(P,Q)=f(Q,P). \)
Choose \(P,Q\in\mathcal D\) with different most preferred alternatives. Such orders exist by the connectedness constructions. If the first voter is the dictator, \(f(P,Q)\) equals the top of \(P\), while \(f(Q,P)\) equals the different top of \(Q\), contradicting symmetry. The second-voter dictatorship gives the same contradiction.
Our assumption that all six realizable singleton distributions receive zero error is therefore false.
For every deterministic strategyproof \(F\), there exists \(a\in\mathcal A\) such that
\( R_{\delta_{t_{T_a}}}(F(\delta_{t_{T_a}}))>0 \quad\text{and}\quad \operatorname{OPT}(\delta_{t_{T_a}})=0. \)
This instance has \(\tau=1\), \(m=15\), and mass \(1\), with rational coordinates and labels. It defeats every finite multiplicative guarantee, including guarantees depending on \(d,m,\tau,L\), or the masses.
Thus no polynomial-time mechanism attains a finite factor; neither does a mechanism with unlimited computational power. The proof uses only deviations of mass \(\tfrac12\), so retaining arbitrary real deviations only strengthens the requirement.
The stated finite-agent approximation results do not conflict with this conclusion. Their mechanisms may distinguish individual agents. Here, equal masses with the same bundle are interchangeable because the mechanism receives only their aggregate distribution.
⟨structured verdict parsed — rendered above⟩
The output resolves the task correctly. Its conclusion is stronger than a growing lower bound: every deterministic strategyproof mechanism must make positive error on at least one of six realizable singleton distributions. Hence no finite multiplicative approximation guarantee is possible.
No major or minor mathematical issues were found.
The characterization
\[
\mathcal A=\{000,001,011,111,110,100\}
\]
is correct for all \(d\geq1\).
On the three selected collinear points, an affine score is an affine function of one scalar coordinate. Its nonnegative region gives a prefix, a suffix, all three points, or none. The convention that zero scores receive the positive label does not permit either excluded pattern \(010\) or \(101\). All six listed patterns are attainable.
Repeated coordinates necessarily receive identical predictions, so reducing outcomes to these six alternatives preserves every relevant type’s classification risk.
The definition of \(H\) is valid, and its symmetry follows exactly from equality of the underlying distributions. It does not require an additional anonymity assumption.
The strategyproofness reduction handles both relevant cases:
Reports that merge with an existing type also cause no difficulty: distributions aggregate their masses, as required by the model.
Consequently, the displayed risk inequality establishes strategyproofness for the first argument. Symmetry establishes it for the second argument. All these profiles and deviations use rational masses.
Each \(T_a\) is realizable, and zero error on its singleton distribution forces prediction vector \(a\). Therefore
\[
H(T_a,T_a)=a.
\]
Both subsequent applications of strategyproofness have the correct direction. If \(a\) is uniquely best for \(Y\), reporting \(T_a\) at \((Y,T_a)\) makes \(a\) available, forcing truthful selection of \(a\). If \(a\) is also uniquely best for \(Z\), the analogous deviation by the second argument at \((Y,Z)\) again forces \(a\).
This proves precisely the unanimity property needed for the restricted strict preference domain. The representing label vectors themselves need not be realizable.
The occurrence counts are valid: for weights \(1,3,5\), the majority-label counts are respectively \(3,4,5\).
The error calculation is correct:
\[
\sum_{i=1}^{3}\frac{5-w_i}{2}
=\frac{15-9}{2}=3.
\]
Thus preferences are determined by weighted Hamming distance from \(z\).
The listed subset sums
\[
0,1,3,4,5,6,8,9
\]
are correct and distinct. Distinct prediction vectors have distinct mismatch subsets relative to fixed \(z\), so every constructed preference is a strict total order on \(\mathcal A\).
The linkedness verification is also correct:
The ordering therefore satisfies the stated definition of a linked domain.
The cited result has been verified. [Reffgen’s Theorem 3.1](https://www.accessecon.com/pubs/SCW2008/GeneralPDFSCW2008/SCW2008-08-00329S.pdf) applies to a linked top-two preference domain over a countable alternative set with at least three alternatives, and a unanimous social choice function. It concludes dictatorship under top-two strategyproofness. Ordinary strategyproofness implies that condition; strict total orders satisfy the required preference structure.
The prover states a valid specialization, and all its hypotheses are established:
Fixing one label representative per order makes \(f\) well-defined. No assumption that the original mechanism depends only on ordinal preferences is needed.
Dictatorship contradicts symmetry because the domain contains orders with different top alternatives. The argument correctly covers either possible dictator.
The contradiction negates correctness on all six singleton distributions. Hence, for every deterministic strategyproof mechanism, at least one such distribution has positive output error and zero optimal error.
The parameter claims are correct: each failure instance has support size \(\tau=1\), occurrence count \(m=15\), mass \(1\), and rational coordinates. The auxiliary profiles have support size at most \(2\); their use does not change the parameters of the final failure instance.
Any finite multiplicative factor, including an instance-dependent finite factor, requires zero error when the optimum is zero. The demonstrated failure therefore excludes every such guarantee, regardless of running time.
The conclusion is an impossibility of finite approximation under the required incentive condition. It is not a computational hardness classification.
None. The theorem citation, calculations, domain construction, deviation quantifiers, and final impossibility conclusion are verifiable as written.
⟨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.