d4-conf-aaai-2008-0282 (d4-conf-aaai-2008-0282)

For each batch size \(m\), let a society be a rational distribution \(\mu\) over types \(p\in\{0,\ldots,m\}\), where \(p\) is the number of positive labels among an agent's \(m\) points. Agents report counts \(r\in\{0,\ldots,m\}\), and a deterministic rule \(F_m\) maps the reported mass vector \(\nu\) to \(c^+\) or \(c^-\). Define \(R_\mu(c^+)=\sum_p\mu_p(m-p)/m\), \(R_\mu(c^-)=\sum_p\mu_p p/m\), and \(r^*(\mu)=\min_c R_\mu(c)\). What is the infimum, over families of rules \((F_m)_m\) that are mass-group-strategyproof for every society, of their worst-case truthful approximation ratio \(\sup_{m,\mu}R_\mu(F_m(\mu))/r^*(\mu)\); is it \(3\)?

For each integer \(m\geq1\), types and reports are counts in \(\{0,\ldots,m\}\). A society is a probability distribution \(\mu\), given by the list of its \(\tau\) positive-mass types and their binary rational masses; \(\tau\) is the support size, not the number of possible types. Let \(L\) be the total input bit length; state any running times in \(m,\tau,L\).
A deterministic rule \(F_m\) maps rational reported distributions to \(\{c^+,c^-\}\), without payments. Type \(p\) minimizes its true loss \(\ell_p(c^+)=(m-p)/m\), \(\ell_p(c^-)=p/m\); when \(2p=m\), it is indifferent. Outcome ties may be resolved arbitrarily by the rule.
A coalition deviation consists of nonnegative rational masses \(a_{pr}\), with \(b_p=\sum_r a_{pr}\leq\mu_p\), producing \(\nu_r=\mu_r-b_r+\sum_p a_{pr}\). Coalition members may report truthfully, and a type's mass may split among reports.
The rule is mass-group-strategyproof if no such deviation makes every participating type \(p\) with \(b_p>0\) weakly better off and a positive mass strictly better off, comparing \(F_m(\nu)\) with \(F_m(\mu)\) using true losses.
Define \(R_\mu(c)=\sum_p\mu_p\ell_p(c)\) and \(r^*(\mu)=\min_c R_\mu(c)\). Set \(0/0=1\) and \(x/0=+\infty\) for \(x>0\).
What is \(\inf_{(F_m)_m}\sup_{m\geq1,\mu} R_\mu(F_m(\mu))/r^*(\mu)\), where each \(F_m\) is mass-group-strategyproof for every rational society? Is this infimum \(3\)?
For finite societies, no deterministic strategyproof mechanism achieves \(3-\varepsilon\) for any \(\varepsilon>0\), even with two agents holding equally many points; a deterministic strategyproof \(3\)-approximation exists ([source](https://cdn.aaai.org/AAAI/2008/AAAI08-020.pdf)).
No result settling the rational mass problem defined here was identified in the literature search.

The infimum is \(+\infty\), not \(3\). The decisive feature is that an indifferent type may assist a coalition containing a strict beneficiary who reports truthfully. For comparison, restricting the question to odd \(m\) gives infimum \(3\).

Even \(m\): every admissible rule has unbounded ratio. Fix an even integer \(m\geq2\), put \(t=m/2\), and let \(\delta_p\) denote unit mass at type \(p\). For any rational \(0<\epsilon<1/2\), define
\[ \mu_\epsilon=\epsilon\delta_0+(1-2\epsilon)\delta_t+\epsilon\delta_m, \qquad \nu_\epsilon^-=(1-\epsilon)\delta_0+\epsilon\delta_m, \qquad \nu_\epsilon^+=\epsilon\delta_0+(1-\epsilon)\delta_m. \]
Here and below these expressions mean rational probability distributions.

There are two possible outcomes at \(\mu_\epsilon\).

• Suppose \(F_m(\mu_\epsilon)=c^+\). Consider the coalition specified by

\(a_{00}=\epsilon\) and \(a_{t0}=1-2\epsilon\), with every other \(a_{pr}=0\).
Thus type \(0\) participates truthfully, and all indifferent mass reports \(0\). The resulting distribution is \(\nu_\epsilon^-\). If its outcome were \(c^-\), participating type \(0\) would reduce its loss from \(1\) to \(0\), while participating type \(t\) would retain loss \(1/2\). This would be a forbidden deviation. Consequently,
\(F_m(\nu_\epsilon^-)=c^+\).
At this society,
\(R_{\nu_\epsilon^-}(c^+)=1-\epsilon\) and
\(r^*(\nu_\epsilon^-)=R_{\nu_\epsilon^-}(c^-)=\epsilon\).
The approximation ratio is therefore \((1-\epsilon)/\epsilon\).

• Suppose \(F_m(\mu_\epsilon)=c^-\). Use instead

\(a_{mm}=\epsilon\) and \(a_{tm}=1-2\epsilon\), with every other entry zero.
This produces \(\nu_\epsilon^+\). An outcome \(c^+\) would strictly benefit participating type \(m\), while type \(t\) remained indifferent. Hence strategyproofness forces
\(F_m(\nu_\epsilon^+)=c^-\).
Here again the selected risk is \(1-\epsilon\), whereas the optimal risk is \(\epsilon\).

All specified masses are nonnegative rational numbers, and each participating type contributes exactly its available mass. Thus both deviations satisfy the definition.

Taking \(\epsilon=2^{-n}\) for integers \(n\geq2\) proves that every mass-group-strategyproof rule for this fixed even \(m\) has supremum ratio \(+\infty\). The witnessing true society has support size \(\tau=3\), and the society with the large ratio has \(\tau=2\); no mass splitting is required.

In particular, \(m=2\) already forces every admissible family to have infinite worst-case ratio. Constant rules are admissible, so the class of families is nonempty. Therefore
\[ \inf_{(F_m)_m}\sup_{m\geq1,\mu} \frac{R_\mu(F_m(\mu))}{r^*(\mu)} =+\infty. \]

Odd \(m\): the exact fixed-\(m\) optimum. To distinguish the indifference obstruction from the remaining problem, fix odd \(m\), and set
\(k=(m-1)/2\), \(h=(m+1)/2\), and \(\alpha=h/(2m)\).
The optimal worst-case ratio for this fixed \(m\) is
\((3m-1)/(m+1)\).

For the upper bound, let \(P(\mu)=\sum_{p\geq h}\mu_p\), and choose \(c^+\) exactly when \(P(\mu)\geq1/2\).

There are no indifferent types. A beneficial switch from \(c^-\) to \(c^+\) therefore requires every participating type to satisfy \(p\geq h\). For any such deviation,
\[ P(\nu)-P(\mu) =\sum_{p,r}a_{pr} \bigl(\mathbf{1}_{r\geq h}-\mathbf{1}_{p\geq h}\bigr) \leq0. \]
It cannot cross the threshold upwards. For a beneficial switch from \(c^+\) to \(c^-\), every participating type satisfies \(p\leq k\), and the same expression is nonnegative. It cannot cross downwards. This proves mass-group-strategyproofness, including arbitrary splitting.

Write \(x=\sum_p\mu_p p/m\). The two risks are \(1-x\) and \(x\). If the rule chooses \(c^+\), then \(x\geq(h/m)P(\mu)\geq\alpha\). If it chooses \(c^-\), then \(1-x\geq(h/m)(1-P(\mu))>\alpha\). Whenever the selected outcome is suboptimal, its ratio is consequently at most
\[ \frac{1-\alpha}{\alpha}=\frac{3m-1}{m+1}. \]
When it is optimal, the ratio is \(1\), including the stipulated zero-risk convention. The rule takes \(O(\tau)\) exact rational operations, or \(O(\tau L^2)\) bit operations using schoolbook arithmetic.

For the matching lower bound, consider
\[ A=\tfrac12\delta_m+\tfrac12\delta_k,\qquad B=\tfrac12\delta_m+\tfrac12\delta_0,\qquad C=\tfrac12\delta_h+\tfrac12\delta_0. \]
Any admissible rule must satisfy \(F_m(A)=F_m(B)\): otherwise, the negative type at whichever society receives \(c^+\) can report as the other negative type and obtain \(c^-\). Likewise, \(F_m(B)=F_m(C)\), because the changing types \(m\) and \(h\) both strictly prefer \(c^+\).

If their common outcome is \(c^+\), society \(C\) has ratio \((1-\alpha)/\alpha\). If it is \(c^-\), society \(A\) has that ratio, since its mean is \(1-\alpha\). This proves the lower bound. Taking the supremum over odd \(m\) gives \(3\).

Relation to the cited mechanism. The [paper’s Mechanism 1](https://cdn.aaai.org/AAAI/2008/AAAI08-020.pdf) assigns local ties to the positive side. Its corresponding mass rule chooses \(c^+\) at \(\mu_\epsilon\) and \(c^-\) at \(\nu_\epsilon^-\). The explicit coalition above therefore violates the present definition. Assigning an indifferent report to a voting side does not remove its true indifference.

⟨structured verdict parsed — rendered above⟩

The output correctly resolves the stated problem: the infimum is \(+\infty\). The even-\(m\) argument is rigorous under the task’s explicit permission for truthful coalition participants. The additional odd-\(m\) result is also correct. No major or minor mathematical issues were found.

1. Even-\(m\) construction

Fixing even \(m\geq2\) makes \(t=m/2\) an allowed integer type. For rational \(0<\epsilon<1/2\), all three displayed distributions have nonnegative rational masses summing to \(1\). In particular, the indifferent mass \(1-2\epsilon\) is strictly positive.

In the first case, the coalition has
\[ b_0=\epsilon,\qquad b_t=1-2\epsilon, \]
and all other participation masses vanish. These quantities equal the available masses of the participating types. Substituting the specified reports into the task’s distribution-update formula gives exactly \(\nu_\epsilon^-\).

If the outcome changes from \(c^+\) to \(c^-\), type \(0\) strictly improves and type \(t\) remains indifferent. The strictly improving mass is \(\epsilon>0\). Type \(0\)’s truthful report does not invalidate the deviation: the task expressly permits truthful coalition members. Consequently, mass-group-strategyproofness forces \(F_m(\nu_\epsilon^-)=c^+\).

The second case is symmetric and valid: the specified coalition produces \(\nu_\epsilon^+\), type \(m\) would strictly improve under a switch to \(c^+\), and type \(t\) remains indifferent. Thus \(F_m(\nu_\epsilon^+)=c^-\).

2. Risks and unboundedness

At \(\nu_\epsilon^-\), the selected risk is \(1-\epsilon\), while the alternative risk is \(\epsilon\). Since \(\epsilon<1/2\), the latter is the optimal risk. The corresponding computation at \(\nu_\epsilon^+\) is identical with outcomes exchanged.

The quantifiers are correct: for every admissible fixed rule and every permitted \(\epsilon\), at least one of the two endpoint-supported societies has ratio
\[ \frac{1-\epsilon}{\epsilon}. \]
The witnessing society may depend on the rule’s outcome at \(\mu_\epsilon\); a supremum over all societies permits this dependence.

Taking \(\epsilon=2^{-n}\) gives ratio \(2^n-1\), which is unbounded. Every witness is a finite rational input. No uniform bound on input length is required by the objective.

Thus the argument establishes infinite worst-case ratio already for \(m=2\). Constant rules are admissible because deviations never change their outcome, so the class over which the infimum is taken is nonempty. The claimed infimum follows.

3. Odd-\(m\) strategyproofness

For odd \(m\), every type has a strict preference. A profitable switch to \(c^+\) can therefore involve only types \(p\geq h\). For those participants, every summand in the displayed change in \(P\) is nonpositive. Hence their deviation cannot move \(P\) from below \(1/2\) to at least \(1/2\).

Conversely, a profitable switch to \(c^-\) can involve only types \(p\leq k\). Every summand is then nonnegative, preventing movement from at least \(1/2\) to below \(1/2\).

The argument covers arbitrary rational participation masses and report splitting. It also correctly handles the rule’s threshold tie convention.

4. Odd-\(m\) approximation bound and runtime

The risk identities \(R_\mu(c^+)=1-x\) and \(R_\mu(c^-)=x\) are correct. The stated inequalities bound the optimal risk below by \(\alpha\) whenever the selected outcome is suboptimal. Accordingly,
\[ \frac{1-\alpha}{\alpha}=\frac{3m-1}{m+1} \]
is the claimed upper bound. Optimal selections have ratio \(1\), including zero optimal risk under the stipulated convention.

The runtime bounds are valid conservative bounds. The rule scans the \(\tau\) supported types and sums the relevant rational masses. Intermediate numerators and denominators can be kept at bit length \(O(L)\), supporting the stated \(O(\tau L^2)\) schoolbook bit bound.

5. Odd-\(m\) lower bound and edge case

The equality \(F_m(A)=F_m(B)\) is justified in either possible direction of disagreement: the changing negative type can move its mass to the other negative report and obtain its strictly preferred outcome. The analogous reasoning establishes \(F_m(B)=F_m(C)\) using the changing positive type.

The means at \(C\) and \(A\) are respectively \(\alpha\) and \(1-\alpha\), giving the stated lower bound for either common outcome.

For \(m=1\), the three societies coincide and \(\alpha=1/2\). Both outcomes have ratio \(1\), matching the formula. Thus coincident types in this edge case do not break the argument. The fixed-\(m\) bounds approach \(3\) over odd \(m\), validating the restricted-family claim.

6. Source comparison and scope

[Mechanism 1 in the cited paper](https://cdn.aaai.org/AAAI/2008/AAAI08-020.pdf) assigns local ties to the positive side and chooses the positive outcome when its weighted positive side is at least half. Its corresponding mass rule therefore selects \(c^+\) at \(\mu_\epsilon\) and \(c^-\) at \(\nu_\epsilon^-\), as asserted. The displayed coalition violates the present task’s definition.

No cited theorem is needed for the central conclusion, and no additional clarification is required. The output establishes an approximation impossibility, not a complexity classification of the original continuous problem.

⟨structured verdict parsed — rendered above⟩