| paper | Non-Obvious Manipulability in Extensive-Form Mechanisms: The Revelation Principle for Single-Parameter Agents |
| authors | Thomas Archbold, Bart de Keijzer, Carmine Ventre |
| venue | IJCAI 2023 |
| filed under | voting · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
All numbered results are structural characterizations or revelation-principle existence statements, not algorithmic or complexity results. The proposed \(\mu\)-based clone-symmetric NOM problem is a plausible high-multiplicity extension, but its computational content comes from additional representation and feasibility choices. Since ChoCo requires a named computational result from the paper, bit (a) fails.
fails bit a — no named computational result to mirror
The proposed extension covers single-parameter direct-versus-indirect NOM implementability over repeated valuation types; Theorem 1, Lemma 1, Theorem 3, and the paper's other structural conclusions receive no computational mirror.
The strongest honest case is a qualified one. The paper suggests a plausible high-multiplicity mirror, but it has no admissible computational anchor under ChoCo’s strict rule.
The best candidate is Theorem 2, proved in this paper: “For every NOM indirect mechanism implementing social choice function \(f\) for single-parameter agents there is a NOM direct mechanism implementing \(f\).” It is the strongest anchor because single-parameter agents naturally occur in large populations of bidders, workers, sellers, or users sharing valuation classes.
A precise mirror would be High-Multiplicity NOM Revelation. An instance contains finitely many valuation types \(V=\{v_1,\ldots,v_\tau\}\subseteq\mathbb Q_{\ge 0}\), a rational population distribution \(\mu\in\Delta_\tau\), and an anonymous target allocation rule \(F\). For a denominator \(N\) of \(\mu\), the corresponding finite society has \(N\mu_j\) clone agents of type \(v_j\). Each agent receives an indivisible allocation \(a_i\in\{0,1\}\) and payment \(p_i\), with utility \(v_i a_i-p_i\). The target rule is specified compactly through the reported type histogram \(\rho\), so that an agent reporting \(w\) receives \(A(w,\rho)\).
The decision variable is a payment rule together with either a direct-revelation mechanism or a uniform family of clone-symmetric extensive-form trees \(T_N\), described at the level of valuation types rather than individual clones. The mechanism must implement \(F\) and satisfy, for every true type \(v\), false report \(w\), and every report profile \(b_{-i}\) of the other agents, both NOM inequalities: the supremum and infimum of \(v a_i-p_i\) under truthful reporting must be at least the corresponding supremum and infimum under reporting \(w\). One may additionally minimize the worst-case aggregate subsidy subject to individual rationality and no deficit.
The expected outcome is Class A, provided \(F\) has an efficient type-level representation: Theorem 2 predicts that indirect protocols give no extra implementability power, while the finite type support suggests that payment feasibility can be reduced to overlappingness and cycle constraints. Further questions include whether the direct mechanism and payments can be computed in time polynomial in \(\tau\) and the encoding length of \(\mu\), whether finite-\(N\) mechanisms round to the continuous rule, and whether multi-parameter populations produce a genuine continuum-specific separation between direct and indirect mechanisms.
The regime is plausible: millions of bidders with a small number of common valuation, eligibility, and demand classes. Mass is the fraction of bidders in each complete type; individual allocations remain discrete. This is genuinely population continuization, not merely fractionalising the outcome.
The serious weakness is that Theorem 2 itself is not a complexity result. It gives a structural equivalence, with no input encoding, running time, approximation guarantee, or parameterized claim. Moreover, its proof reasons about named agents and their implementation-tree positions; compressing clones into type masses may change precisely those strategic distinctions. Thus this is a credible research problem inspired by the paper, but not a qualifying ChoCo anchor as written.
The paper’s other named results do not repair this: Theorem 1 and Lemma 1 are structural characterisations, and Theorem 3 is another revelation-principle theorem for \(n=2\), not a computational result. The cited polynomial result of Aziz and Lam is prior work, not a named result proved or stated as a theorem in this paper. Hence, under the programme’s stated standard, the paper has no named computational anchor.
The negative case is unusually strong on ChoCo’s formal criterion: this paper contains no named computational result to continuize. Theorem 2 is an existence theorem about implementability classes. For a fixed finite set of named agents, it says that if some extensive-form mechanism is NOM, then a direct-revelation mechanism is NOM as well. It specifies no computational input, encoding, decision or optimization problem, running time, approximation guarantee, or parameterized claim. Theorem 1 and Lemma 1 are likewise structural characterizations, and Theorem 3 is another finite-agent revelation-principle theorem. Thus there is no qualifying computational anchor here.
The proposed single-parameter mirror does not cure that defect. A large population of bidders with repeated valuation classes is a perfectly sensible high-multiplicity regime; the problem is not the story. The problem is that the theorem is about individual strategic interaction, not population frequencies. Its NOM conditions quantify over every named agent, every false type, every compatible profile of the other agents, and that agent’s individual payment and allocation. The distribution \(\mu\) does not appear.
For finite \(N\), one can certainly form a clone model with \(N\mu_v\) agents of each valuation type. But then Theorem 2 simply applies separately to each finite \(N\). Treating \(\mu\) as a compact description creates a possible high-multiplicity mechanism-design problem, but not a continuous counterpart of the theorem’s content. To make it algorithmic one must additionally specify a uniform representation of \(f_N\), a uniform family of implementation trees \(T_N\), payment encoding, subsidy or deficit objectives, and the meaning of clone symmetry. None of these is supplied by the paper, and the theorem gives no method for constructing or computing them.
Passing genuinely to a continuum creates a more fundamental mismatch. Under an anonymous aggregate rule, one individual’s report changes the population distribution by zero mass, so the individual’s report has no effect on the aggregate outcome; NOM then becomes vacuous at the aggregate level. If one retains a nonzero effect for a particular agent, one must introduce a tagged agent or a finite-\(N\) perturbation. The model is then no longer solely a society distribution: it retains precisely the individual identity and sequential information that the proposed continuization was meant to remove. Alternatively, allowing a positive mass of agents to deviate produces a coalitional or mass-NOM concept, which may be interesting but is a new incentive notion, not a mirror of Theorem 2.
The strongest possible repair would be to define a type-level, clone-symmetric family of extensive-form mechanisms and ask whether direct and indirect type-level protocols have the same implementability or payment-feasibility region. That is a legitimate new research problem, but it is not what the paper proves. The original implementation tree can distinguish agents, histories, and compatible profile sets; replacing it by a type-level tree changes the mechanism class. Keeping those distinctions leaves an object whose state space is indexed by full profiles—up to \(\tau^N\) possibilities—not by \(\mu\) alone. Theorem 1’s cycle graph does not provide a polynomial-size aggregate representation or a separation oracle for this compression; it merely characterizes feasibility once the relevant labels and tree are given.
The same diagnosis applies to any attempt to promote Theorem 1, Lemma 1, or Theorem 3 into anchors. One could invent a computational problem around choosing labels, designing uniform trees, or minimizing aggregate subsidies, but its computational content would come from those additional choices, not from a named result of this paper. The paper’s contribution is that implementation details do, or sometimes do not, matter for NOM—not that any such object can be computed efficiently over a distribution of agent types.
I would not claim that no future mean-field mechanism-design model involving NOM could ever be worthwhile. A tagged-agent limit or a collective-deviation notion might produce interesting theory. But that concession confirms the negative verdict for this paper: every plausible worthwhile formulation changes the strategic object, while the literal high-multiplicity formulation merely repeats a finite-agent structural equivalence for each \(N\). Under ChoCo’s standard, this paper supplies no continuous computational mirror.
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.