| paper | d4-conf-aaai-2012-0108 |
| 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 constructible and evaluable: select any alternative minimizing \(\sum_{P\in\mathcal R}\mu_P\hat d(P,x)\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given alternatives \(A\), an explicit distance table \(d\) on rankings, a discount factor \(\gamma>1-1/D\), and an initial rational distribution \(\mu^0\) over \(\tau\) supported rankings, find an optimal stationary winner policy for infinite discounted reward. At each distribution \(\mu\), choosing \(x\) gives reward \(\sum_{P:P[1]=x}\mu_P\); each mass at a ranking \(P\) not already placing \(x\) first sends fraction \(q(P,x)=\frac{1}{\gamma}\left(\frac{1}{\hat d(P,x)}-(1-\gamma)\right)\) to a \(d\)-closest ranking \(S(P,x)\) with \(x\) first, where \(\hat d(P,x)=d(P,S(P,x))\), and the remaining mass stays at \(P\).
Types are rankings \(P\), each carrying mass \(\mu_P\); actions select a winner \(x\); the objective is discounted first-place mass under the deterministic mass flow induced by the paper's independent transition probabilities.
Theorem 1 gives no input encoding or runtime bound, so its policy characterization is a weaker computational anchor than an algorithmic result; the case rests on treating the explicit finite minimization as a computation.
fatal: False
Covers Theorem 1's unanimity and ℓ1-votewise policy characterization, including the scoring-rule specialization in Corollary 2 when its distance is explicit. It leaves other consensus notions, heterogeneous or empirically specified preference dynamics, and complexity for succinct distance descriptions open.
The positive case is narrow. This paper has no named theorem establishing a standard complexity result such as membership in P, NP-hardness, or FPT. The closest anchor is Theorem 1, proved in the paper: it characterizes optimal policies for a specified social-choice MDP and gives their form. If the anchor requirement means a standard complexity classification, then this paper has no qualifying anchor. The mirror below uses Theorem 1 only under the allowance for a named result that solves an optimization problem by characterization.
Theorem 1 says: for a distance \(d\) on rankings, with \(D\) an upper bound on its values and discount factor \(\gamma>1-1/D\), the authors construct an MDP whose states are preference profiles, whose actions are alternatives, and whose reward is the number of voters who rank the chosen alternative first. Its independent voter transitions are constructed from \(d\). A deterministic voting rule is optimal in this MDP exactly when it is \(\ell_1\)-votewise distance-rationalizable with respect to unanimity via \(d\). The proof is the authors’ result; the paper does not give a general runtime bound for finding nearest rankings under arbitrary succinct descriptions of \(d\).
The mirror I would lead with is Continuous Unanimity-Drift Control. An instance has a finite set of \(m\) alternatives, a distance table \(d\) on their rankings, a rational discount factor satisfying Theorem 1’s condition, and an initial society \(\mu^0\): a distribution with rational masses over \(\tau\) supported rankings. A type is a ranking; members of a type share the transition behavior induced by \(d\). At time \(t\), the decision is a winning alternative \(x_t\). For each ranking \(P\), let \(S(P,x)\) be a \(d\)-closest ranking with \(x\) first, and let \(\hat d(P,x)=d(P,S(P,x))\). A voter with \(P\) moves to \(S(P,x)\) with probability
\[
q(P,x)=\frac{1}{\gamma}\left(\frac{1}{\hat d(P,x)}-(1-\gamma)\right)
\]
when \(P\) does not already rank \(x\) first; otherwise the voter stays at \(P\). In the continuum, the mass distribution evolves by the expected transition flow. The reward per unit of population is \(\sum_{P:P[1]=x_t}\mu_t(P)\). The question is: given \(\mu^0\), which first action maximizes the infinite discounted reward \(\sum_{t\ge 0}\gamma^t\sum_{P:P[1]=x_t}\mu_t(P)\)? A full solution can be represented by an optimal stationary policy on distributions.
The theorem’s value formula gives the policy directly: at distribution \(\mu\), choose
\[
x\in\arg\min_{a\in A}\sum_P\mu_P\hat d(P,a).
\]
Thus this is a genuine population-mass version of the paper’s dynamic winner-selection problem, not a model that makes outcomes fractional or merely adds noise to a finite profile. For the explicit distance-table input specified here, I expect Class A: compute the nearest distance for each supported ranking and alternative, then compare \(m\) weighted sums. With a succinct distance description, the potentially hard part is the pricing task of finding \(S(P,x)\); the paper does not settle its complexity.
A plausible regime is a large online community choosing among a short list of policies or recommendations. Many members may share one of relatively few rankings, and the paper’s common transition model gives members with the same ranking identical responses to a selected winner. Here \(\tau\) can be moderate even when the population is very large. The authors would likely recognize the mass model as an aggregation of their setup: the reward is additive and the voter transitions are independent. The analogy is strongest for their constructed dynamics, which they present as an interpretation of distance rationalizability, rather than as an empirically established model of how autonomous people revise preferences.
This mirror covers only Theorem 1’s unanimity and \(\ell_1\)-votewise setting with its constructed transitions. It leaves out other consensus notions and other dynamic models. It also generates useful follow-up questions: how hard is nearest-ranking pricing for compactly described distances, how closely do finite replicated populations approximate the mass dynamics, and which heterogeneous response models still admit an optimal-policy formula?
The soft spot is that Theorem 1 is principally a representation result, not a complexity theorem. The expected tractability depends on how \(d\) is encoded, and the continuum replaces random finite-population transitions with deterministic mass flow. So this is a credible positive case for a continuous analogue of the paper’s problem, but a weak anchor for the programme’s broader goal of charting a complexity landscape.
The best negative case is that Theorem 1 is a representation theorem, not a complexity result. It equates distance-rationalizable rules with optimal policies in a specially constructed MDP, but does not specify an input encoding or analyze the cost of finding an optimal policy. Corollary 2 gives a scoring-rule instance of the same equivalence. Neither result establishes a complexity landscape of the kind ChoCo is meant to chart.
The proponent’s population lift is coherent. For a unit-mass society, the theorem’s value formula becomes
\[
V^\star(\mu)=\frac{1}{1-\gamma}-\min_{x\in A}\sum_P \mu_P\hat d(P,x).
\]
This preserves the population as the continuous object, and the mass interpretation fits the model: voters with the same ranking have the same transition behavior. The proposed online-community scenario is plausible enough. There is no good objection based on identity, multiplicity, degeneration, or the fact that the paper’s original model is finite.
The difficulty for the mirror is the computational question left after this lift. To compute the policy, one needs the values \(\hat d(P,x)\), which depend on finding a closest ranking with \(x\) first. The paper treats \(d\) as an arbitrary function; it does not specify whether it is an explicit table, a compact formula, or some other representation. With a compact encoding, the complexity of that nearest-ranking task becomes the real issue, but it is a new problem driven by the encoding of \(d\), not a complexity result in the paper. The community story motivates the interpretation, but the preference transitions are constructed from the distance rather than constrained by an observed or otherwise specified response model.
So the strongest case against is narrow: this is a valid continuous restatement of the theorem’s policy characterization, but a weak anchor for a computational-complexity programme. That case does not establish the requested universal claim. If a named exact policy characterization is enough to anchor a mirror, then the proponent’s mirror survives; I would call the negative case weak rather than claim no worthwhile mirror exists.
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.