| paper | d4-conf-aaai-2014-0223 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | unclear |
Theorem 3 is a named impossibility result about mechanism properties, not about the complexity of computing a mechanism. The paper defines a mechanism and proves its properties, but gives no named computational result to anchor a ChoCo mirror.
fails bit a — no named computational result to mirror
Theorem 3 establishes incompatibility on \(m\)-chotomous domains; Theorems 1 and 2 prove properties of the proposed mechanisms on top-only preferences, and Theorem 4 proves Pareto efficiency on \(m\)-chotomous domains. None gives a complexity or running-time result.
The strongest honest positive case is that this paper has a plausible high-multiplicity exchange market underneath it, but no named computational-complexity result to anchor a ChoCo mirror.
A plausible regime would be a large consortium of similar institutions exchanging indivisible resource bundles. Let a type \(\theta=(e_\theta,R_\theta)\) specify an institution’s endowment class and its complete preference over bundles. The society is a distribution \(\mu\) over types; each unit of mass still receives an integral bundle, even though aggregate allocation shares can be fractional. An allocation variable could be \(x_{\theta,B}\), the mass of type \(\theta\) receiving bundle \(B\), subject to type-mass and per-good supply constraints.
The paper’s closest anchor is Theorem 3, proved here: for each \(m\in\{3,\ldots,|K|-1\}\), there is no exchange mechanism that is simultaneously individually rational, Pareto efficient, and strategy-proof on the \(m\)-chotomous preference domain. A natural neighboring question is whether that incompatibility persists for a continuum of these institution types, while each institution still receives an integral bundle. I would expect the obstruction to persist if the finite witness can be represented by positive-mass cohorts. But strategy-proofness needs care: a mechanism defined only on \(\mu\) cannot see a single agent’s measure-zero report change. Defining deviations by positive-mass cohorts instead would change the paper’s strategy-proofness question.
That is a meaningful population-continuity question, and the type classes give it a plausible scenario. But it is an axiomatic mechanism-existence question, not a complexity question of the kind this programme requires. Theorem 1 establishes Pareto efficiency of the proposed mechanisms on the top-only domain; Theorem 2 establishes their strategy-proofness there; and Theorem 4 establishes their Pareto efficiency on \(m\)-chotomous domains. None states a complexity classification or an algorithmic running-time bound. The conclusion’s suggestion that manipulation complexity might be studied is future work, not a result proved here.
So under the stated anchor rule, there are zero qualifying anchors and no continuous computational problem I can responsibly present as the paper’s mirror. The weakness in the nearby positive case is fundamental: its strongest result is precisely the kind of axiomatic result the programme puts out of scope.
The proposed exchange setting is plausible: a large consortium could contain many institutions with similar endowment and preference patterns. But the proponent’s only named anchor is Theorem 3, which proves an axiomatic impossibility: no mechanism satisfies individual rationality, Pareto efficiency, and strategy-proofness on the stated domain. Its continuum mirror would still ask whether such a mechanism exists. That is a coherent question, but it is outside ChoCo’s computational remit.
The stronger versions do not supply a computational anchor either. One could ask for a type-level allocation of integral bundles that is individually rational and Pareto efficient. But the paper does not define a scalar objective or an algorithmic allocation problem of that kind; Pareto efficiency is a property, and many assignments may satisfy it. One could instead ask whether a mechanism with the three properties can be computed or found. That turns the paper’s existence question into a new computational problem. In a continuum, strategy-proofness also needs a careful agent-level formulation: changing one person’s report has measure zero, while letting a positive-mass cohort deviate changes the question the finite theorem asks.
The paper’s Algorithm 1 does not fill this gap. It describes a mechanism and the paper proves properties of its outcomes, but gives no complexity classification or running-time result to mirror. Nor does the conclusion’s suggestion to study the complexity of finding a best manipulation count as a result: it is explicitly future work. A continuous cohort-manipulation problem could be worth studying in its own right, but it would be a new question rather than a mirror of a result established here.
The consortium story may also require a substantial model change: the paper’s goods are heterogeneous and uniquely endowed, and each agent’s endowment is part of the information relevant to the exchange. Repeated institution types would therefore need a resource-copy or category model. That does not by itself rule out a sensible high-multiplicity version; it reinforces that the proponent’s scenario cannot supply the missing computational result.
So none of the proponent’s candidates survives as a ChoCo computational anchor. This is a strong reason to pass on this paper for the programme. It is not proof that no future computational study could grow from its exchange model; it is the narrower and better-supported conclusion that this paper itself offers axiomatic results, not the complexity result a continuous computational mirror would chart.
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.