| paper | Dynamic Social Choice with Evolving Preferences |
| authors | D. Parkes, Ariel D. Procaccia |
| venue | AAAI 2013 |
| filed under | voting · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-hard already for fixed \(m=4\) and \(\tau=1\). · discrete side: polynomial · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 4.10
statement extracted from the paper’s text layer
Given fixed finite \(A\) and \hat{Θ}, rational type masses \(ρ_θ\), rational kernels \(P_θ(≻'∣≻,a)\), rational discount factor γ, initial mass state \(μ_0\), rational piecewise-linear anonymous reward ̅\(R(μ,a)\), and an anonymous polyhedral local restriction Ψ(μ), where μ ranges over ∏_θΔ\(L(A)\) and \(F_a\) is the induced affine update, compute a finite rational polyhedral stationary policy π with π(μ)∈Ψ(μ) that is ε-optimal for Σ_{k≥0}γ^k̅\(R(μ_k,π(μ_k))\), with μ_{k+1}=F_{π(μ_k)}μ_k.
A mean-field social-choice MDP whose society is the mass vector μ=(μ_{θ,≻}) over behavioural types and rankings, with action-dependent affine updates \(F_a\), discounted reward, and anonymous local or onto policy constraints.
The exact policy and output representation remains unresolved: arbitrary continuum rewards may not admit finite optimal policy descriptions, while the ε-approximate variant is only sketched. This limits what follows directly from Theorem 4.10 but does not kill the mass-simplex question.
fatal: False
The mirror covers Theorem 4.10's anonymous local-axiom optimization and the onto branch of Theorem 5.1; it leaves nondictatorship, other nonlocal axioms, transition-model learning, and finite-population stochastic fluctuations outside.
The strongest positive case is a mean-field version of the paper’s own social-choice MDP, not merely the static profile simplex.
Let \(A\) be the alternatives and \(L(A)\) the rankings. Retain a finite set \(\widehat{\Theta}\) of behavioural types, where a type specifies the transition kernel used by its agents. The actual instantaneous type is \((\theta,\succ)\): agents with the same \(\theta\) and current ranking \(\succ\) are indistinguishable for the problem. A society is therefore a mass vector \(\mu=(\mu_{\theta,\succ})\), with \(\sum_{\succ}\mu_{\theta,\succ}=\rho_\theta\) and \(\sum_\theta\rho_\theta=1\).
Choosing alternative \(a\) moves the mass according to the paper’s transition model:
\[ (F_a\mu)_{\theta,\succ'}=\sum_{\succ\in L(A)} \mu_{\theta,\succ}P_\theta(\succ'\mid \succ,a). \]
Thus the population is continuous, while time remains discrete and the action set remains \(A\). An anonymous reward is a function \(\overline R(\mu,a)\), and a deterministic stationary policy is \(\pi:\mu\mapsto a\). Its value is
\[ V_\pi(\mu)=\sum_{k=0}^{\infty}\gamma^k \overline R(\mu_k,\pi(\mu_k)), \qquad \mu_{k+1}=F_{\pi(\mu_k)}\mu_k. \]
This is a genuine population continuization: the finite count vector is replaced by a point in a simplex of masses. It is also the natural law-of-large-numbers limit of the paper’s independently transitioning agents. The aggregate transition becomes deterministic because individual randomness averages out.
My lead anchor is Theorem 4.10, proved in this paper. It states that, given a social-choice MDP \(M\), an anonymous reward function \(R\), the partition \(\widehat{\Theta}\) of agents into types, a refinement \(\Theta\) of that partition, and a restriction \(\Psi\subseteq S\times A\) symmetric with respect to the induced state equivalence relation \(E_\Theta\), if \(|A|=O(1)\) and \(|\Theta|=O(1)\), then an optimal deterministic \(\Psi\)-consistent policy, itself symmetric with respect to \(E_\Theta\), can be computed in polynomial time in the number of agents \(n\).
The continuous problem I would hand to a prover is:
Continuum Anonymous-Local Dynamic Social Choice. Given rational type masses \(\rho_\theta\), rational transition kernels \(P_\theta\), discount factor \(\gamma\), an anonymous aggregate reward \(\overline R\), and an anonymous local restriction \(\Psi(\mu)\subseteq A\), compute an optimal deterministic stationary policy \(\pi\) such that \(\pi(\mu)\in\Psi(\mu)\) for every population state \(\mu\).
For an exact computational formulation, \(\overline R\) and \(\Psi\) can be supplied as finite rational piecewise-linear or threshold formulas in the mass coordinates, and the policy as a finite symbolic decision procedure. The paper’s natural examples fit this representation: Condorcet consistency, Pareto optimality, and unanimity are all aggregate linear-threshold conditions. For example, \(\Psi(\mu)\) must contain \(a\) whenever \(a\) beats every other alternative by strict majority mass.
This is recognisably the same question. The paper already solves the finite problem by discarding agent identities and retaining counts of rankings within behavioural types. The mirror replaces those normalized counts by exact masses. The action, transition kernels, discounted objective, and social-choice restriction are unchanged.
The regime is also credible. Consider a large online advocacy platform with millions of members, a small number of alternatives, and a handful of behavioural cohorts learned from observed reactions. With \(m=4\) alternatives and \(t=6\) behavioural types, there are only \(t\,m!=144\) instantaneous population cells, compared with millions of agents. A state is not “what voter \(i\) does,” but what fraction of each cohort currently holds each ranking. This is precisely the high-multiplicity regime the paper’s polynomial-in-\(n\) result presupposes.
I would expect the structured approximation version of this problem to be Class A: for fixed \(m\) and \(t\), the state space has constant dimension, the transition maps are affine, and the Bellman operator is a discounted contraction. Fixed-dimensional discretization, piecewise-linear dynamic programming, or continuous-optimization methods provide a plausible route to \(\varepsilon\)-optimal policies. I would not claim that the paper’s polynomial theorem automatically proves an exact polynomial algorithm for the continuum. Infinite-horizon optimal policies may have infinitely many regions, especially with discontinuous consensus rewards. That exact issue is a legitimate continuum-computational question rather than a reason to reject the mirror.
A second, genuinely distinct anchor is Theorem 5.1, also proved by the authors in the full version; the conference paper says that its intricate proof is relegated there. It states that, given a social-choice MDP, an anonymous reward function, a type partition \(\widehat{\Theta}\), and a state \(\hat s\), if the number of alternatives \(m\) and the number of types are constant, then an optimal deterministic policy satisfying either ontological surjectivity (“onto”) or nondictatorship can be computed in polynomial time in \(n\).
I would mirror the onto branch, because it has an unambiguous continuum meaning:
Continuum Onto Dynamic Social Choice. Given the same population transition system, reward, discount factor, and initial mass state \(\mu_0\), compute an optimal deterministic stationary policy \(\pi\) subject to
\[ \forall a\in A\;\exists \mu\in\mathcal X \text{ such that }\pi(\mu)=a, \]
where \(\mathcal X\) is the population simplex.
The policy must therefore maximize \(V_\pi(\mu_0)\) while selecting every alternative somewhere in the continuum of possible population profiles. This is not a cosmetic replacement of “profile” by “distribution”: onto-ness remains a global constraint on the social choice function. The finite theorem’s guided-search idea has a natural continuous counterpart involving witness regions in the population simplex.
I would expect the fixed-dimensional, approximate version again to be tractable, while the exact all-state version is a plausible Class C boundary case. The onto requirement quantifies over a continuum of states, and policy regions may have complicated geometry. That makes the question interesting precisely because it tests whether the paper’s symmetry argument survives high multiplicity, rather than assuming that it does.
I would not use the nondictatorial half as a main mirror. In an atomless society, dictatorship by one named individual is either impossible or vacuous. A type-level substitute—“no fixed positive-mass behavioural type always determines the outcome”—is possible, but it is an adaptation rather than a direct continuation of the paper’s definition.
The main weakness is that the finite theorem’s polynomial state compression does not remain a finite-state compression: the continuum quotient is a simplex, not a finite set of count vectors. Exact policy representation and the disappearance of aggregate transition noise are real modelling choices. Nevertheless, those are precisely the questions a continuous mirror should expose. The mirror retains the paper’s changing preferences, action-dependent transitions, discounted objective, anonymous social-choice constraints, and type-based symmetry; it changes only the population representation from high-multiplicity counts to masses. That is a credible continuous computational problem even if its eventual answer is “tractable,” “continuum-specifically hard,” or open.
The negative case cannot honestly rely on the absence of multiplicity: this paper explicitly motivates millions of MoveOn members and a small number of behavioural types. Nor is existing high-multiplicity work an objection. The strongest case against must instead attack what survives after taking the limit.
For Theorem 4.10, the atomless limit changes the computational object more radically than the proponent admits. Equation (1) gives independent transitions for individual agents. With fixed type masses, the empirical distribution after action \(a\) converges to
\[ (F_a\mu)_{\theta,\succ'}=\sum_{\succ}\mu_{\theta,\succ}P_\theta(\succ'\mid\succ,a), \]
and aggregate fluctuations disappear. The finite stochastic MDP therefore becomes a deterministic controlled affine dynamical system. That is a legitimate mean-field model, but the paper’s central dynamic phenomenon—stochastic evolution of preference profiles—has vanished.
There is also no exact continuous analogue of the theorem as stated. In the finite MDP, an anonymous reward \(R\) and restriction \(\Psi\) are simply functions on a finite state space. In the continuum, arbitrary \(\overline R\) and \(\Psi\) have no finite input representation, and an optimal policy may require infinitely many regions. Restricting them to rational piecewise-linear formulas and requiring a symbolic policy, as the proponent suggests, is a sensible new control problem, but not a consequence or direct continuization of Theorem 4.10. An \(\varepsilon\)-optimal formulation is more defensible, yet it is likewise a new mean-field-control problem whose complexity parameters and output representation are absent from the paper.
The obvious repairs do not restore the anchor. Adding common shocks would preserve aggregate randomness, but common shocks violate the paper’s product transition model. Imposing a finite policy language makes the problem computable, but changes the policy class. Averaging over initial population states would produce a meaningful control problem, but changes the paper’s fixed-state objective. With \(m\) and the number of types fixed, \(n\) has disappeared entirely; the paper’s polynomial-in-\(n\) result supplies no complexity statement about the remaining continuous problem.
Theorem 5.1 is weaker still. The proponent chooses onto-ness, but in the proposed deterministic continuum model the orbit from a fixed initial state \(\mu_0\),
\[ \mathcal O=\{\mu_0,\mu_1,\mu_2,\ldots\}, \]
is countable, whereas the population simplex is uncountable. Any optimal policy can be changed at states outside \(\mathcal O\) to assign each missing alternative, without changing its value from \(\mu_0\). Even requiring each alternative on a positive-volume set does not fix this: the orbit has measure zero. Thus onto-ness becomes an off-trajectory decoration rather than a substantive dynamic constraint. Requiring witnesses to be reachable from a positive-measure set of initial states, or evaluating performance over all initial states, would be nontrivial—but it would no longer be the paper’s onto theorem.
The nondictatorial branch is worse: in an atomless society, an individual has zero mass and cannot be a dictator. A type-level substitute could be designed, but that is a new axiom rather than a continuation of the paper’s definition.
This is not an airtight negative verdict. A local-axiom continuum model with structured rewards, a specified policy representation, and an approximate objective is genuinely natural, and the paper supplies a credible high-multiplicity setting for it. The honest negative conclusion is narrower: Theorem 5.1’s onto anchor degenerates, while Theorem 4.10’s proposed mirror loses the paper’s stochastic MDP and requires substantial new encoding choices. I could argue against accepting the proponent’s case as already compelling, but I could not honestly claim that no worthwhile continuous mirror exists in any scenario.
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.