| paper | Non-Obvious Manipulability for Single-Parameter Agents and Bilateral Trade |
| authors | — |
| venue | AAMAS 2023 |
| filed under | unclassified |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper fails bit (a): its numbered results are structural characterisations, impossibility theorems, or existence constructions, and none asserts a qualifying computational result. The batch formulation is a plausible high-multiplicity extension of repeated bilateral trade, but it cannot supply the missing computational anchor. Therefore the formal verdict is red despite the mirror being a sensible Class \(A\) follow-up.
fails bit a — no named computational result to mirror
The batch consists of independent two-agent instances, so \(\mu\) only reweights pointwise outcomes and creates no population-level computational bottleneck; the proponent expressly acknowledges this limitation.
fatal: False
The proposed mirror covers only Theorem 5's WNOM, efficient, IR, WBB bilateral-trade construction; it leaves the structural characterisations and subsidy impossibility results untouched.
The strongest honest positive case is a narrow Class A extension of Theorem 5, not a continuum of buyers and sellers competing in one anonymous market.
The lead anchor is Theorem 5, proved in this paper. It states that there exists an efficient, individually rational, weakly budget-balanced, WNOM mechanism for bilateral trade. Strictly speaking, this is a constructive existence theorem, not a named \(P\)- or NP-hardness result. The paper contains no numbered theorem asserting a computational-complexity classification: Theorems 1–3 and 7 are structural characterisations, Theorems 4 and 6 are impossibility results, and Theorem 5 is an explicit mechanism construction. Thus this is a near-anchor under a broad reading of “computational result”, but not a qualifying anchor under the programme’s strict gate.
The corresponding problem is Batch-WNOM Bilateral Trade\(_\infty\). An instance consists of a finite rational set of buyer values \(V=\{v_1,\ldots,v_p\}\subseteq[0,1]\), seller costs \(C=\{0,1\}\), and rational masses \(\mu_{ij}\ge0\) summing to \(1\). The mass \(\mu_{ij}\) represents the fraction of a large batch of independent, otherwise identical buyer–seller transactions whose buyer has value \(v_i\) and seller has cost \(c_j\). This models, for example, a procurement platform repeatedly running the same bilateral-trade mechanism on a large population of standardised orders and suppliers. The number of transactions is large compared with \(p\), and agents sharing a value or cost type are interchangeable.
The decision variable is an anonymous direct mechanism table. For every reported pair \((\widehat v,\widehat c)\in V\times C\), it specifies a discrete trade decision \(f(\widehat v,\widehat c)\in\{0,1\}\), a buyer payment \(p_B(\widehat v,\widehat c)\ge0\), and a seller payment \(p_S(\widehat v,\widehat c)\ge0\). The table must be individually rational at truthful reports, weakly budget balanced for every report pair, and WNOM for both agents using the paper’s worst-case inequalities over the other agent’s reports. Its objective is to maximise aggregate gains from trade, \(\sum_{i,j}\mu_{ij}(v_i-c_j)f(v_i,c_j)\).
Theorem 5 supplies an explicit solution:
\(f(\widehat v,\widehat c)=1\) exactly when \(\widehat v\ge\widehat c\);
\(p_B(\widehat v,\widehat c)=\widehat v\) and \(p_S(\widehat v,\widehat c)=\widehat c\) when trade occurs, and both payments are zero otherwise.
At truthful reports, every trading agent receives zero utility, so individual rationality holds. Since \(p_S\le p_B\) whenever trade occurs, weak budget balance holds. The paper’s proof establishes WNOM. The aggregate solution therefore achieves the first-best value \(\sum_{i,j}\mu_{ij}(v_i-c_j)\mathbf 1[v_i\ge c_j]\). It can be constructed and evaluated in time polynomial in \(p\) and the encoding length of \(\mu\), so I would classify this narrow mirror as Class A.
The high-multiplicity bridge is exact. If \(\mu_{ij}=n_{ij}/N\), replace the mass cell by \(n_{ij}\) cloned transactions. The mechanism remains discrete at the transaction level; only the aggregate objective and payment totals are weighted. All individual utility comparisons and WNOM inequalities are preserved exactly, while aggregate quantities scale by \(N\). Thus this is not fractionalising the item or replacing a ranking by an average: it is a repeated bilateral-trade regime with rational clone multiplicities.
The authors should recognise this as their problem repeated over a large typed batch. It preserves the roles, values, costs, trade rule, payments, IR, WBB, and WNOM semantics of Theorem 5. It deliberately does not claim to model endogenous matching among a common pool of buyers and sellers, which would introduce a new strategic environment.
That limitation is also the weakest point. Population mass is computationally almost inert here: the same local mechanism is applied independently to every transaction, and \(\mu\) merely weights the final totals. The construction is therefore more a faithful high-multiplicity extension than a new complexity phenomenon. If the strict requirement is that the paper itself contain a named \(P\), NP-hardness, approximation, or parameterized result, this paper has no qualifying anchor and should receive no formal ChoCo mirror verdict. If constructive mechanism synthesis is admitted, Theorem 5 supports the narrow positive case above. Natural follow-ups would be a finite-type welfare-optimisation problem using the threshold characterisation in Theorem 7, and a genuinely many-buyer/many-seller model with an explicitly defined positive-mass or cohort-level analogue of NOM.
The decisive objection is that this paper has no qualifying computational anchor. Theorem 5 is an existence construction, not a complexity theorem, optimization algorithm, approximation result, or parameterized classification. Theorems 1–3 and 7 are structural characterizations; Theorems 4 and 6 are subsidy impossibilities. Thus the proposed mirror already fails ChoCo’s strict entry condition.
The proposed Batch-WNOM Bilateral Trade\(_\infty\) does not repair that gap. It is a legitimate high-multiplicity regime, but it is a distribution over independent two-agent instances, not a society participating in one mechanism. For each pair, Theorem 5 already supplies the same pointwise rule:
\[ f(\widehat v,\widehat c)=\mathbf 1[\widehat v\ge \widehat c], \qquad p_B=\widehat v,\quad p_S=\widehat c \]
when trade occurs. WNOM and individual rationality are checked separately for each buyer and seller; they do not depend on \(\mu\). The proposed objective merely computes
\[ \sum_{i,j}\mu_{ij}(v_i-c_j)\mathbf 1[v_i\ge c_j], \]
which the theorem’s mechanism attains simultaneously for every distribution. The mass vector is therefore an external weighting of already solved local instances. Cloning each pair \(n_{ij}\) times preserves the theorem exactly, but introduces no population-level computational problem. This is evidence that the high-multiplicity regime is sensible, not a reason to call it a continuous mirror.
The stronger rescue would be to make buyers and sellers interact in one common market. That immediately ceases to be the paper’s bilateral-trade setting. One must specify matching, market clearing, allocation among multiple agents, and NOM extrema over all other reports. A proper agent type is then role-specific—buyer value or seller cost—not the pair \((v_i,c_j)\); the pair distribution encodes a fixed matching of agents. If matching is fixed, we return to independent bilateral trades. If matching is endogenous, we have a new many-agent mechanism-design problem.
There is also a continuum-specific obstruction. In an atomless market, one agent’s report has zero mass and cannot affect an aggregate price or clearing condition. NOM’s defining best- and worst-case comparisons are individual, so the population component either becomes strategically irrelevant or requires positive-mass blocs. Treating a bloc as the strategic unit changes the solution concept; retaining pivotal named agents produces a discrete-continuum hybrid. Neither is a mirror of the paper’s two-agent theorem.
One could instead optimize expected revenue or subsidy over a distribution of values and costs using Theorem 7. That may be a worthwhile new mechanism-design problem, but it changes the objective and is driven by continuity of the type/value domain—not by continuization of the population. The integrals in Theorem 3 already concern one agent’s type domain, and are not population continuity. Likewise, Theorems 1–3 cannot simply be compressed into a mass vector: their labellings and extrema range over every other named report.
The universal claim that no imaginable NOM market extension could ever be worthwhile is not formally provable; an anonymous many-agent NOM model could become an interesting new paper. But it would not be a continuous computational mirror of a computational result in this paper. The only proposed anchor is therefore defeated, and under ChoCo’s stated gate this paper should receive no mirror verdict.
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.