| paper | d4-journals-jet-2009-0052 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: accept exactly when \(\bigcup_{t=1}^{\tau} I_t=\binom{N}{2}\). For every accepted society, \(q_0=3\) suffices. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite contestant set \(N\) and a finite support \(T\) of complete juror types with positive rational masses \(\mu_t\) summing to one, determine whether there is a threshold \(q_0\) and a constructible mechanism scheme such that, for every \(q\ge q_0\) with \(q\mu_t\in\mathbb{Z}\) for all \(t\), the mechanism Nash implements the true ranking in the jury containing \(q\mu_t\) jurors of each type, for every admissible state.
Represent jurors by complete types \(t\), including their preference functions and indifferent-pair sets \(I_t\), with society distribution \(\mu\). For each compatible scale \(q\), instantiate \(q\mu_t\) individually strategic jurors of type \(t\), with the type assignment known to the designer; mechanisms map their ranking and permutation messages to a ranking of \(N\).
The distribution represents a family of finite atomic games: each mechanism still relies on individual deviations, so it does not define Nash implementation for an atomless population.
fatal: False
The mirror covers Theorem 1’s implementation result and uses Proposition 1’s pair-coverage condition and Proposition 2’s designer-information requirement; it does not continuize rankings or cover a genuinely nonatomic equilibrium.
The paper has no named computational-complexity result: it classifies no problem as being in P, NP-hard, FPT, or similar. Its strongest computationally adjacent anchor is Theorem 1, proved here. It says that if there are at least three jurors, every pair of contestants is an indifferent pair for at least one juror, and the designer knows which jurors have which indifferent pairs, then the socially optimal rule is Nash implementable. The theorem supplies a mechanism: jurors announce a ranking and a permutation; the outcome depends on whether rankings agree, whether a single juror deviates along allowable adjacent swaps, or whether the announced permutations must be composed. This is a constructive implementation result, not a complexity classification.
The most credible mirror I see is High-Multiplicity Nash Implementation for a Jury. Picture a large, standing professional association ranking a fixed slate of scholarship applicants or nominees. Its many jurors share a small number of stable, fully specified preference-function types. A type includes the juror’s preferences over rankings in every state and the corresponding set \(I_t\) of indifferent pairs. The mass \(\mu_t\) is the fraction of jurors of type \(t\); the number of jurors is large compared with the support size \(\tau\). As in the paper, the jurors share a true ranking that is not verifiable, and the mechanism designer knows each juror’s indifferent-pair information.
Precisely, the instance consists of a finite contestant set \(N\), a finite support \(T\) of admissible juror types, and positive binary-rational masses \(\mu_t\) summing to one. For every integer scale \(q\) that makes all \(q\mu_t\) integral, form a finite jury with \(q\mu_t\) jurors of type \(t\). The question is whether there is a threshold \(q_0\) and a mechanism scheme for all such juries of size at least \(q_0\) that Nash implements the socially optimal rule for every true ranking and every admissible state. A solution is a mechanism scheme, with a proof that a correct-ranking equilibrium exists and no incorrect-ranking profile is an equilibrium for every such jury.
Theorem 1 is the lead anchor for this problem. If every contestant pair belongs to \(I_t\) for some type with \(\mu_t>0\), that type occurs in every sufficiently large scaled jury; once there are at least three jurors, Theorem 1 supplies the mechanism. The paper’s Proposition 1, proved here, gives the matching coverage necessity: if the socially optimal rule is Nash implementable, every pair must be an indifferent pair for at least one juror. Proposition 2, also proved here, says the designer must know which jurors have each pair among their indifferent pairs. In the mirror, those are substantive input requirements: aggregate mass or aggregate pair coverage alone may not provide enough information to construct the mechanism.
I expect the known-type version to be tractable: checking whether the support covers all \(\binom{|N|}{2}\) pairs takes a scan of the type signatures, and Theorem 1 gives a mechanism construction. That is a prediction for the mirror, not a runtime bound established by the paper; in particular, the paper does not analyze the cost of evaluating its outcome rule. The scope is just socially optimal Nash implementation. It does not continuize rankings or outcomes.
The weakest point is that a truly atomless population makes any one juror’s deviation change zero mass, which undercuts the individual-deviation Nash reasoning of the paper. I have therefore defined the mirror as a continuous type distribution representing a family of finite, high-multiplicity juries. That preserves the authors’ underlying implementation question, but whether they would accept this finite-family interpretation as a continuous mirror is the central vulnerability. Further questions include the runtime of the mechanism, and whether implementation survives when the designer knows only type masses rather than the identities of jurors carrying the relevant indifferent-pair information.
The strongest reason against a ChoCo mirror is that this paper proves a mechanism-existence result, not a computational result. Theorem 1 gives necessary conditions, sufficient conditions, and a mechanism that implements the socially optimal rule. Propositions 1 and 2 say what information and pair coverage the designer needs; none asks for an algorithm, complexity classification, or optimization over a society. A computational problem could be added, but it would need to be motivated separately.
The best version of the proposed mirror is a large association with a small support of fully specified juror types, represented by proportions \(\mu_t\), and finite juries formed by replicating those types. That is a sensible high-multiplicity regime, so the objection is not that jurors cannot repeat. But for every compatible jury size \(q\), the paper’s conditions already settle implementability: pair coverage in the support is necessary, the designer must know the coverage, and Theorem 1 supplies the mechanism once there are at least three jurors. The mass values determine how many copies appear; the mechanism still operates on \(q\) individual message pairs. This leaves no computational task over the distribution itself.
Taking the population genuinely to a continuum creates a more basic problem. The theorem’s Nash condition lets one juror change their message. In an atomless population, that deviation changes no aggregate message distribution. Any outcome rule defined on those distributions therefore cannot respond to an individual deviation, so every profile is an equilibrium; it cannot select the true ranking across different states. The paper’s mechanism makes the discrete dependence explicit: it distinguishes unanimity from exactly one dissenter, then uses the dissenter’s indifferent pairs. As \(q\) grows, that one dissenter has mass \(1/q\), which vanishes. Preserving their effect requires individual identities or atomic players; requiring positive-mass coalitions instead changes the equilibrium concept.
Proposition 1 would become a support-coverage condition, while Proposition 2 either requires identity-level information that the distribution does not contain or is built into the type description. Those conditions may be useful in mechanism design, but they do not supply a continuous computational problem. One could add objectives such as jury recruitment or robustness to mass deviations; those would be new questions, not computational mirrors of the paper’s implementation result.
The negative case is not airtight: finite replicated committees are a plausible high-multiplicity setting, and a computational study of mechanism design might be worthwhile in its own right. But under ChoCo’s population-continuum and computational scope, I would reject this paper as a mirror: its substantive object remains an individually strategic finite game, and aggregating jurors by mass either leaves that game unchanged or removes the unilateral deviations its result depends on.
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.