| paper | d4-conf-aaai-2016-0360 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | unclear |
The named results establish an equilibrium property, welfare bounds, and an axiomatic characterization, but none asserts an algorithm or a computational complexity result. Optimizing welfare over limiting equilibria would be a new computational question, not a continuous mirror of a qualifying result in this paper.
fails bit a — no named computational result to mirror
The proposed limit-equilibrium task draws on the plurality and MAP equilibrium and PoA/PoS results, while leaving Theorem 4 aside; none of these results qualifies as a computational anchor.
The best positive case is an asymptotic mirror for large crowdsourcing or peer-grading systems. Let the alternatives be the possible ground truths. A voter type is the signal \(s\in A\) the agent receives; agents with the same signal share the paper’s prior, signal model, utility, and voting options. With many agents and at most \(m\) signal types, the mass of type \(s\), conditional on truth \(\theta\), is \(\mu^\theta_s=\pi_\theta(s)\). A decision variable \(x_{s,v}\) records how much of that type reports vote \(v\), with \(\sum_v x_{s,v}=\mu^\theta_s\). The objective remains the paper’s: how likely the mechanism’s outcome is to reveal \(\theta\).
A concrete candidate is the Limit-Equilibrium Truth-Revelation problem. Its input is a finite alternative set \(A\), a rational Mallows-like signal model, and a mechanism such as plurality or MAP, with the paper’s uniform prior and common-interest utility. A limit equilibrium is a limit of aggregate vote masses induced by symmetric pure BNE as the number of agents tends to infinity. The task is to compute the best and worst limiting truth-revelation welfare over those equilibria, relative to sincere voting; the solution includes the limiting mass vectors witnessing the extrema. Defining equilibrium through finite-game limits matters: in a static atomless game, one agent cannot affect the outcome, so ordinary unilateral-deviation incentives lose the pivotal behavior the paper studies.
The paper offers relevant named results, but no qualifying computational anchor under the requested criterion: none asserts a complexity classification such as polynomial-time solvability or NP-hardness. Theorem 2, proved here, says that for any Mallows-like model based on a weakly neutral distance with uniform prior, sincere voting is a BNE under plurality. Corollary 1, also stated here, says that for those models the PoA for plurality and MAP is at least \(m/2\) when \(m\) is even, and at least \(m\) for weak BNE, while the PoS tends to \(1\) as \(n\) grows. These support the proposed limit-equilibrium question, but neither is a computational-complexity result, so presenting either as the required anchor would stretch your instructions. Theorem 4 is a mechanism characterization, not one either.
The mirror is plausible as a population model: a platform may have millions of workers but only a small set of possible signals, and mass is the natural way to describe their proportions. It also tracks the paper’s own asymptotic focus. The scope would be the paper’s equilibrium truth-revelation results for plurality and MAP, not its separate strategy-proofness characterization. The expected complexity class of the proposed computation is open from the evidence here; fixed \(m\) gives a finite type-and-action space, but that does not establish tractability as \(m\) varies.
The weakest point is the same feature that makes the limit precise: finite-agent pivotal incentives do not survive automatically in an atomless population. The finite-game limit is a defensible continuous question, but an author or referee could regard it as an asymptotic reformulation rather than a new computational problem. More fundamentally, this paper supplies no named computational anchor for the programme’s required hardness-versus-tractability comparison.
The strongest objection is the one the proponent concedes: this paper has no named computational result to mirror. Theorem 2 proves an equilibrium property, Corollary 1 gives PoA and PoS bounds, and Theorem 4 characterizes mechanisms axiomatically. None classifies the complexity of a computational problem or gives an algorithm whose tractability could change under continuization. That is a serious mismatch with ChoCo’s stated aim of charting computational complexity.
The proposed limit-equilibrium task does not fix that mismatch; it adds a new task. In a literal atomless game, one voter has no effect on the outcome, so unilateral deviations cannot express the pivotal incentives behind Theorems 2 and 3. Defining equilibria as limits of finite games preserves those incentives only by importing the finite games’ vanishing pivotal events into the definition. One could then ask for an algorithm to find the best and worst limiting equilibria, but that is a new complexity question, not a computational mirror of a result in this paper. As stated, it also needs choices about which equilibria count, how the sequence of finite games is handled, and how welfare limits are defined before it is a precise complexity problem.
The same issue applies to Corollary 1. Its asymptotic PoA and PoS bounds could be restated using limiting type frequencies, but computing equilibrium welfare across those limits would again be a newly chosen problem. Theorem 4 is an even weaker anchor: its characterization ranges over finite electorate sizes \(n\), and its condition explicitly relates \(\alpha_n\) to \(\alpha_{n+1}\). A continuum version would need a new axiom and a new statement. Neither offers a computational result for ChoCo to mirror.
I would not argue that the population model is implausible. A large crowdsourcing platform with many agents and a small signal space is a convincing high-multiplicity regime: agents sharing a signal are indistinguishable under the paper’s model. That makes this a sensible candidate for continuous *analysis*. The negative case is narrower: the paper does not supply the computational anchor the programme is designed to continuize. The proponent’s candidate may be worth studying as a new algorithmic question about limiting Bayesian games, but calling it a mirror of this paper stretches the programme’s criteria. This is a strong case against prioritizing the paper for ChoCo, though it cannot establish that no useful continuous computational question could ever be built from the model.
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.