| paper | d4-conf-aaai-2008-0282 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 7
statement extracted from the paper’s text layer
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 input batch size \(m\), the population is mass over positive-label-count types \(p\in\{0,\ldots,m\}\). Report flows determine \(\nu\), a deterministic rule selects \(c^+\) or \(c^-\), and the objective is the worst-case ratio to minimum truthful misclassification risk, subject to no positive-mass coalition being able to make all its members weakly better off and some positive mass strictly better off.
The mirror covers the deterministic strategyproof frontier in Theorem 7 and the 3-approximation mechanism in Theorem 5. It leaves the randomized results in Theorems 9–10 and the sampling guarantee in Theorem 12 aside.
The strongest honest mirror is the paper’s deterministic, no-payment classification problem. The paper has no named theorem classifying a problem as in P, NP-hard, or FPT. Its useful anchors are instead named results about the approximation guarantees and incentive properties of mechanisms. So this is a case for a continuous mechanism-performance question, not a conventional complexity-class result.
Take a finite set of public agent templates \(G\), where template \(g\) has \(m_g\) data points. An agent’s type is \(t=(g,p)\), where \(p\) is the number of its points whose true label is positive. This is a complete type for the paper’s constant-classifier problem: as the paper observes, point identities do not matter here; only the positive and negative counts do. A society is a distribution \(\mu\) over these types, and \(\mu_{g,p}\) is the fraction of agents of that type. For fixed \(m_g=m\), there are only \(m+1\) possible label-count types, so a population can be very large while its type support \(\tau\) remains small.
A type-\((g,p)\) agent can report any count \(r\in\{0,\ldots,m_g\}\). A mechanism sees the reported mass vector \(\nu_{g,r}\) and chooses \(c^+\) or \(c^-\). The agent’s risks are \(R_{g,p}(c^+)=(m_g-p)/m_g\) and \(R_{g,p}(c^-)=p/m_g\). Since the paper measures total error across data points, the society’s risks are \(R_\mu(c^+)=\sum_{g,p}\mu_{g,p}(m_g-p)/\sum_{g,p}\mu_{g,p}m_g\) and \(R_\mu(c^-)=\sum_{g,p}\mu_{g,p}p/\sum_{g,p}\mu_{g,p}m_g\); let \(r^*(\mu)=\min\{R_\mu(c^+),R_\mu(c^-)\}\). For a continuum incentive notion, require that no positive-mass coalition can misreport so that every member weakly improves and a positive mass strictly improves. Individual-only strategyproofness would be vacuous for agents of zero mass.
Theorem 5, proved in the paper, says that Mechanism 1 is a \(3\)-approximation group-strategyproof mechanism. Mechanism 1 labels each agent positive if \(P_i\ge N_i\), totals the points controlled by positive agents as \(P'\) and by negative agents as \(N'\), then chooses \(c^+\) if \(P'\ge N'\), and \(c^-\) otherwise. Its continuous counterpart is a concrete mechanism-design question: given rational reported masses \(\nu_{g,r}\), does there exist an efficiently evaluable mass-group-strategyproof rule with risk at most \(3r^*(\mu)\) on every society? The direct mirror uses \(\widehat P=\sum_{g,r\ge m_g/2}m_g\nu_{g,r}\) and chooses \(c^+\) when \(\widehat P\ge\frac12\sum_{g,r}m_g\nu_{g,r}\), choosing \(c^-\) otherwise. The expected answer is tractable: its weighted sums take time polynomial in \(\tau\), the input bit length \(L\), and the largest batch size \(M=\max_g m_g\). Carrying over group strategyproofness requires proving the finite argument for measurable coalitions that may split a type’s mass among reports.
Theorem 7, also proved in the paper, is the lead anchor. It says that for every \(\epsilon>0\), no deterministic strategyproof mechanism achieves a \((3-\epsilon)\)-approximation. Its proof uses three datasets with two agents, each holding \(2k+1\) points: in \(S_I\), \((P_1,N_1)=(2k+1,0)\) and \((P_2,N_2)=(k,k+1)\); in \(S_{II}\), those counts are \((2k+1,0)\) and \((0,2k+1)\); in \(S_{III}\), they are \((k+1,k)\) and \((0,2k+1)\). Strategyproofness forces the same decision on all three datasets. If that decision is \(c^+\), then on \(S_{III}\) its ratio is \((3k+1)/(k+1)\), which exceeds \(3-\epsilon\) for sufficiently large \(k\); the symmetric case gives the same lower bound.
Its continuous mirror is the deterministic mass-strategyproof approximation frontier. For a fixed finite template system, consider all deterministic rules \(F\) from reported mass vectors \(\nu\) to the two constant hypotheses. Find the infimum worst-case approximation ratio over rules satisfying mass group strategyproofness on every society and every profile of other agents’ reports. A solution is a rule and a matching proof of its optimal ratio. I expect the frontier to remain \(3\): the three finite datasets embed as societies with mass \(1/2\) in each of two persistent role groups. The relevant deviations can be made by an entire positive-mass group, so every member gains together. That is a transfer of the paper’s impossibility argument to the continuous incentive notion, not an NP-hardness claim.
The scenario is a large sensor or reporting network making a binary decision from agents’ batches of labeled readings. With a fixed batch size, many agents can share the same template and positive-label count, while the number of possible types stays small compared with the population. This is especially plausible here because the paper itself reduces its simple setting to \(P_i,N_i\). The action remains truthful or false reporting of labels, the alternatives remain \(c^+\) and \(c^-\), and the loss remains the paper’s misclassification risk. Only the population is represented by type masses. The paper’s later distribution \(\rho_i\) over data points is not already this mirror: it randomizes what is sampled *within each of finitely many agents*, rather than replacing the agent population with a distribution over agent types.
The weakest point is that the paper proves individual strategyproofness in Theorem 7, while an atomless population needs a nonvacuous coalition notion. The lower-bound transfer depends on modeling role groups whose members share a type and can coordinate a positive-mass deviation. If that is not a regime the authors would recognize, the individual-SP lower bound does not automatically carry over. Also, the constructive continuous rule is a weighted extension of a simple counting mechanism; it does not expose the paper to the continuous-optimization toolbox. The case survives as a precise high-multiplicity question about whether the paper’s exact deterministic incentive-approximation frontier persists when agent counts become masses, and about the assumptions needed for that persistence. It does not cover the paper’s randomized mechanisms or its within-agent sampling results.
I would vote against taking this paper as a ChoCo mirror, though the case rests on programme scope rather than on a failure of the high-multiplicity model. The paper has no named theorem about the complexity of a computational problem. Theorem 5 gives an approximation and incentive guarantee for a mechanism; Theorem 7 gives an impossibility bound on strategyproof mechanisms. Those are substantial results, but they classify what mechanisms can achieve, not the complexity of finding an optimal intervention or solving another computational task. The proponent’s proposed mirrors therefore shift the project toward continuous mechanism design.
Theorem 5 has a coherent mass version. For repeated agents with the same batch size, one can describe a type by its positive-label count and replace the finite sums in Mechanism 1 with weighted sums over reported type masses. Group strategyproofness is a natural incentive notion here, and the paper itself studies it. The sensor-network scenario makes repeated types plausible. Still, the mirrored question is whether a simple two-outcome rule retains its approximation and incentive guarantees. The rule uses aggregate counts and a threshold; this gives ChoCo no complexity landscape to chart.
Theorem 7 is the proponent’s strongest anchor. Its three profiles can be represented by two role groups of positive mass, and a role group can make the corresponding deviation together. So I cannot dismiss the mass-strategyproof frontier as incoherent or claim that identity prevents the embedding. But that frontier is an impossibility characterization over mechanisms. The finite theorem gives no computational resource bound to transfer. Adding efficient evaluability would make a legitimate mechanism-design question, yet it would still be a different target from the programme’s complexity questions.
The same sensor scenario survives the better modeling test: many agents can hold fixed-size batches, and their relevant types can be their positive-label counts. The difficulty for the negative case is that this makes the continuous society sensible. My argument is that the resulting work belongs to a neighboring programme on incentive and approximation frontiers, not to ChoCo’s stated aim of charting computational complexity under population continuization.
So the negative case is limited. If ChoCo includes continuous mechanism-design characterizations, Theorem 7 may be a worthwhile mirror, and I cannot honestly claim that no plausible continuous scenario exists. Under the programme’s stated scope, though, neither anchor supplies the computational problem whose complexity continuization is meant to illuminate.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.