| paper | Collusion-Proof and Sybil-Proof Reward Mechanisms for Query Incentive |
| authors | — |
| venue | AAAI 2023 |
| filed under | unclassified |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | no |
The paper contains no named algorithmic or computational-complexity result under ChoCo’s strict anchor rule, so bit (a) fails objectively. The proposed continuous formulation is additionally weakened by replacing one endogenous query tree with repeated layered channels and imported objectives. This is a re-modeling rather than a faithful population mirror of a qualifying result.
fails bit a — no named computational result to mirror
The proposed mirror targets Theorem 1 and Theorem 4 with Lemmas 3–4, but no qualifying computational result; experiments, fairness claims, and remaining mechanism properties are not covered.
Under ChoCo’s strict anchor rule, this paper has no admissible computational anchor. Its named results are mechanism-design statements, not complexity results: Theorem 1 proves an impossibility, Theorem 2 proves monotonicity, Theorems 3 and 4 prove properties of two mechanisms, and Lemmas 1–5 and Proposition 1 analyse those mechanisms. None asserts that a problem is in P, NP-hard, FPT, W[1]-hard, or similar. The paper also contains no named algorithmic problem whose complexity is classified. The cited prior work does not repair that omission.
So I would not present this as evidence that ChoCo has found a new continuous complexity problem. I would record it as “a plausible population mirror exists, but the paper supplies no qualifying computational result to anchor it.” That is different from saying that no mirror exists.
The strongest honest mirror is a high-multiplicity query-network model for a large Q&A or crowdsourcing platform. Suppose the network is a repeated layered referral architecture: many agents occupy a small number of complete role types, such as depth, expertise, solving ability, referral cost, parent role, child-role pattern, and budget parameters. Agents with the same role are interchangeable in everything the mechanism uses. Let \(T\) be the finite set of such types and let \(\mu_t\) be the fraction of agents of type \(t\). A finite type-transition matrix records which child types can be reached from each parent type. The regime is \(N\gg |T|\): a large population distributed over a fixed number of repeated network roles.
Mass is therefore agent mass, not fractional outcomes. An action is a mass flow of agents who propagate, answer, or misreport their children. The mechanism outputs a reward density \(x_{t,i,n}\) for a type-\(t\) agent at position \(i\) on a winning path of length \(n\). The budget constraint is imposed on the aggregate reward of every positive-mass path type, or equivalently on its induced path measure. Sybil attacks are modelled as splitting a positive-mass role into a chain of synthetic identity roles; collusion is modelled as merging adjacent role masses into one reported identity.
The natural continuous mechanism-design question is:
Given a finite type system, rational type masses, a finite maximum path length \(H\), a budget \(B\), and the allowed propagation/deviation transitions, find a nonnegative reward-density rule \(x\) that gives positive reward to every positive-mass truthful winning-path role, respects the budget, and satisfies the Sybil and collusion inequalities for every permitted identity split and coalition up to horizon \(H\). If no such rule exists, output a violated inequality.
This is a genuine population continuization of the paper’s model: the actions, shortest-path allocation, budget constraint, and strategic deviations remain the same; only exchangeable agents are represented by mass and rewards by densities.
If I were allowed to use the paper’s mechanism theorems as provisional anchors, the lead would be Theorem 1, proved in this paper: “For \(n\ge 3\), there is no Reward Mechanism that can achieve PO, SP, and CP simultaneously.” Its continuous analogue is expected to remain infeasible. The proof is pointwise: a single positive-mass path of length at least three already yields the contradiction between the SP and CP inequalities. Thus continuity does not dissolve this impossibility; it makes the result a type-level certificate. This is not Class A, B, or C in ChoCo’s complexity trichotomy—it is a structural impossibility that survives the mirror.
A second, more positive provisional anchor is Theorem 4, also proved here, together with Lemmas 3 and 4. Theorem 4 states that GCRM satisfies IC, PO, and BB; Lemma 3 gives its bounded Sybil behaviour; Lemma 4 gives its finite Sybil/collusion guarantees. The corresponding continuous problem would be:
Given the type masses, path-flow system, budget \(B\), and requested finite robustness levels \(K_{\mathrm{SP}}\) and \(K_{\mathrm{CP}}\), choose \(\alpha\in(0,1)\) and the GCRM reward density
\[ x(i,n)=\frac{\alpha^{\,n-i}}{(1+\alpha)^i}B \]
so as to maximise truthful completion probability, or minimise expected propagation delay, subject to IC, PO, BB, \(K_{\mathrm{SP}}\)-SP, and \(K_{\mathrm{CP}}\)-CP over all positive-mass path types.
For an explicitly given finite type/path system, this should be a tractable finite-dimensional program: the aggregate budget and robustness conditions are linear once the reward densities are variables, while restricting to GCRM leaves a one-parameter algebraic optimisation problem. If the path system is given implicitly, its tractability would depend on a pricing/separation problem over feasible type paths. This is the closest connection to ChoCo’s Class A methodology, although the paper itself proves no such complexity classification.
The mirror would cover the paper’s impossibility and reward-mechanism results, not its experimental comparison, vague fairness claims, or arbitrary network topologies. The authors would probably recognise the layered high-multiplicity version as their model’s aggregate analogue: the same referral actions and strategic deviations are preserved. They might object that the paper studies one task and one winning path, whereas the continuous formulation naturally introduces a distribution over repeated branches or query channels.
That is the weakest point, and it is serious. In an atomless population, a single winning path has zero mass, while Sybil attacks and coalitions concern individual identities. Without a finite-\(N\) blow-up interpretation or a distribution over repeated isomorphic query channels, PO and strategic deviations can become vacuous. The repair is to define the continuum as the limit of large finite layered networks and retain per-agent reward densities and pathwise deviation constraints. But that makes the mirror less clean than the voting-population case and may be judged a batch-query extension rather than the exact one-task problem.
My positive verdict would therefore be modest: the paper has a credible high-multiplicity population mirror, especially for layered referral networks and approximate reward robustness, but it has no named computational result that qualifies as a ChoCo anchor.
The proponent’s opening concession is decisive under ChoCo’s anchor rule: this paper has no admissible computational anchor. Theorem 1 is an impossibility theorem, Theorem 2 a monotonicity statement, and Theorems 3–4 and Lemmas 1–5 verify properties of explicitly given mechanisms. None classifies a computational problem. Turning one of these statements into a newly invented feasibility or optimization problem does not make it a mirror of a computational result.
The proposed high-multiplicity setting also fails as a faithful population continuization. The paper’s primitive is one task owner and one endogenous rooted query tree. Agents are distinguished by their parent, children, depth, report, and position on the selected shortest winning path. A distribution over role types and a transition matrix does not determine the tree, the correlations between subtrees, or the path on which rewards are paid. To make a type complete, one must encode exact adjacency or an entire rooted subtree; then the type is no longer a fixed exchangeable role, but effectively a representation of the individual network structure.
The suggested repair—many repeated layered query channels—changes the model. If each channel retains its own budget and pathwise incentive constraints, the copies merely replicate the same finite mechanism and the masses cancel. If there is one aggregate budget, per-agent rewards and profitable opportunity change with the number of channels. If Sybil and collusion constraints are imposed only in aggregate, they no longer express the paper’s individual strategic properties. Thus the continuum either has no effect on the object or ceases to represent the object.
This is especially clear for Theorem 1. Its \(n\) is the length of a winning path, not population size. The contradiction between SP, CP, and PO already occurs on one finite path of length at least three and contains no population parameter. In an atomless population, an individual path has measure zero; declaring a “positive-mass path type” either turns each whole path into an atom, abandoning the intended population limit, or retains pointwise constraints, in which case the continuous masses are irrelevant. The proposed violated-inequality output is therefore a finite mechanism-feasibility certificate, not a population-complexity question.
The GCRM proposal does not rescue the case. Theorem 4 and Lemmas 3–4 again hold pointwise for a given path and use the explicit closed form
\[ x(i,n)=\frac{\alpha^{n-i}}{(1+\alpha)^i}B. \]
The paper supplies neither a completion-probability objective nor a delay model, so maximizing those quantities is an imported problem, not a continuous version of a named result. With an explicitly given finite path system, choosing \(\alpha\) is a one-parameter algebraic optimization. With an implicit tree, any difficulty comes from representing or searching the network and its feasible paths, not from high population multiplicity. A general LP over reward variables would likewise be ordinary finite mechanism design; its constraints are ex-post constraints over identities and reports, not constraints over a society distribution.
There is a legitimate near-miss: one could study a new stochastic model with a continuum of repeated query channels, a distribution over network environments, solver abilities, and aggregate welfare objectives. That may be interesting, but it is a new crowdsourcing/network-mechanism programme. It does not mirror this paper’s one-task query tree or any computational result it proves.
So the negative case is strong, though not a literal impossibility theorem about all imaginable re-modellings: the paper’s results are structurally pointwise and identity-dependent, while its only plausible continuum requires changing the population into repeated tasks or channels. Under ChoCo’s population-continuization standard, there is no worthwhile mirror here.
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.