| paper | Sequential Deliberation for Social Choice |
| authors | Brandon Fain, Ashish Goel, Kamesh Munagala, Sukolsak Sakshuwong |
| venue | WINE 2017 |
| filed under | voting · distortion |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Deterministic additive \(\varepsilon\)-approximation of \(R_r\) is possible in time polynomial in \(m,\tau,L,\log(r+1),\varepsilon^{-1}\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite median graph \(G=(S,E)\), finite bliss-point types \(T\), rational masses \(\mu\), bliss points \(p_t\in S\), initial disagreement point \(a_1\in S\), and horizon \(r\), sample \(I_s,J_s\sim\mu\) independently and update \(A_{s+1}=\operatorname{med}_G(p_{I_s},p_{J_s},A_s)\); compute or \(\varepsilon\)-approximate \(\mathbb{E}[\operatorname{SC}_\mu(A_r)]/\min_{a\in S}\operatorname{SC}_\mu(a)\), where \(\operatorname{SC}_\mu(a)=\sum_t\mu_t d(p_t,a)\).
A finite-type high-multiplicity society \(\mu\) supplies pair-sampling probabilities and type-level bliss points; the state variable is the Markov distribution of the disagreement alternative, and the objective is expected social cost or squared social cost relative to the \(\mu\)-optimal alternative.
With \(G\) or the metric explicitly enumerated, exact finite-horizon evaluation is a routine finite-state Markov-chain computation and may expose little population-driven complexity.
fatal: False
The mirror directly covers Theorems 1 and 6, with natural extensions to Theorem 5, Theorem 7, Corollary 2, and the simplex result; it leaves individual-level truthfulness and other structural claims without a positive-mass deviation or analogous population model.
The strongest honest case is a clean, though modest, Class A mirror of the paper’s main performance result. The paper contains no named NP-hardness, membership-in-\(\mathrm P\), W[1]-hardness, or FPT theorem. Its named results are approximation and mechanism-performance theorems, so I would not manufacture a hardness anchor.
My lead anchor is Theorem 1, proved in this paper:
Sequential deliberation on a median-graph decision space gives
\[ > \mathbb E[\operatorname{Distortion}(a_t)]\le 1.208+\frac{6}{2^t}. > \]
The convergence is independent of the number of agents, the size of the median graph, and the initial disagreement point.
A natural continuous problem is Continuous Sequential Deliberation on Median Graphs.
An instance consists of a finite median graph \(G=(S,E)\), a finite set of complete agent types \(T=\{1,\ldots,\tau\}\), bliss points \(p_t\in S\), a rational mass vector \(\mu\in\mathbb Q^\tau\) with \(\sum_t\mu_t=1\), an initial disagreement point \(a_1\in S\), and a number \(r\) of bargaining rounds. A type contains everything relevant to the protocol; here that is its bliss point and the common distance-based utility rule.
In each round, draw \(I,J\) independently from \(\mu\), and set
\[ A_{s+1}=\operatorname{med}_G(p_I,p_J,A_s). \]
The social cost is
\[ \operatorname{SC}_\mu(a)=\sum_{t=1}^{\tau}\mu_t d(p_t,a), \]
and
\[ \operatorname{OPT}_\mu=\min_{a\in S}\operatorname{SC}_\mu(a). \]
The task is to compute, exactly or within additive error \(\varepsilon\),
\[ \mathbb E[\operatorname{SC}_\mu(A_r)] \quad\text{and}\quad \frac{\mathbb E[\operatorname{SC}_\mu(A_r)]}{\operatorname{OPT}_\mu}, \]
or to decide whether the latter is at most a given threshold. A solution is an exact value, an \(\varepsilon\)-accurate interval, or a certified threshold answer.
This is recognisably the authors’ problem. The action remains their sequential pairwise Nash-bargaining protocol, the outcome remains a point of the original median graph, and only the population is changed from named agents to masses of identical types. A concrete regime is a large participatory-budgeting population: millions of residents, each represented by one of \(\tau\) recurring ideal project bundles, where \(\tau\ll n\), and the decision space is a binary project space or another median graph. A type may represent a large demographic or institutional cohort with the same bliss point and utility scale.
The continuous theorem follows especially transparently on the hypercube. If
\[ f_k=\sum_t\mu_t p_{t,k}, \]
then the \(k\)-th coordinate evolves through the same two-state Markov chain as in the paper:
\[ \Pr[A_{s+1,k}=1\mid A_{s,k}=1]=2f_k-f_k^2, \qquad \Pr[A_{s+1,k}=1\mid A_{s,k}=0]=f_k^2. \]
Thus the expected social cost can be computed from \(\tau\) and the dimension \(D\), without expanding the population into \(n\) agents. On an explicitly represented graph, one can instead form the transition matrix
\[ P_{ab}=\sum_{i,j}\mu_i\mu_j \mathbf 1\!\left[\operatorname{med}(p_i,p_j,a)=b\right] \]
and compute the distribution after \(r\) rounds. This makes the natural expectation Class A: tractable. The continuous version does not introduce population-driven hardness; it replaces repeated individuals by their frequency vector.
The second worthwhile anchor is Theorem 6, also proved here:
For every metric decision space and every \(T\ge 1\), sequential deliberation has Squared-Distortion at most \(41\). Random dictatorship has unbounded Squared-Distortion.
The paper defines
\[ \operatorname{Squared\text{-}Distortion} = \frac{\mathbb E[(\operatorname{SC}(A))^2]} {(\operatorname{SC}(a^\ast))^2}. \]
Its continuous mirror is Continuous Squared-Distortion of Deliberation. The instance is a finite metric space \((S,d)\), type bliss points \(p_t\), masses \(\mu_t\), an initial disagreement point, and a horizon \(r\). Pairwise bargaining uses the paper’s Nash-bargaining rule \(B\), including its tie-breaking convention. The task is to compute
\[ \frac{ \mathbb E\!\left[ \left(\sum_t\mu_t d(p_t,A_r)\right)^2 \right] }{ \left( \min_{a\in S}\sum_t\mu_t d(p_t,a) \right)^2 }, \]
and compare it with the corresponding value for continuous random dictatorship, which samples \(t\sim\mu\) and outputs \(p_t\).
This also appears Class A for an explicitly represented metric: the type masses define the transition probabilities, and a finite Markov-chain computation gives the exact expectation. More importantly, the theorem’s proof itself survives replacing normalized sums over agents by expectations under \(\mu\). The constant \(41\) therefore remains valid for the continuum model, while the random-dictatorship counterfamily remains unbounded.
I would not extend the mirror automatically to Theorem 4’s truthfulness result. With an atomless population, one individual has zero mass, so “an agent benefits from misreporting” requires a new coalition or positive-mass deviation model. Likewise, uniqueness of the stationary distribution may transfer for finite type support, but it is not needed for the two anchors above.
The weakest point is that the paper already writes much of its analysis in terms of population fractions. For rational \(\mu\), the continuous instance can be expanded into a finite election by cloning each type \(n\mu_t\) times, and Theorems 1 and 6 then follow almost immediately. Consequently, this is not a strong candidate for discovering a new complexity boundary: it is primarily a high-multiplicity reformulation and exact mean-field evaluation problem. The paper also supplies no hardness result whose difficulty might dissolve under continuization.
Still, that weakness does not make the mirror illegitimate. The paper’s actual model is a finite set of agents; the continuous problem takes \(\mu\) itself as the society, makes \(\tau\) rather than \(n\) the population parameter, and asks for exact computation and approximation in that representation. The authors would recognise the protocol, objective, and bargaining dynamics as theirs. The strongest positive claim is therefore: the core sequential-deliberation performance problem has a precise, natural high-multiplicity mirror, and its main named guarantees extend unchanged and are tractable; this is a valid Class A mirror, but not a dramatic new computational landscape.
The negative case begins with the programme’s strongest gate: this paper has no named computational result to mirror. Theorem 1 and Theorem 6 are analytic performance bounds. Neither states a complexity theorem, defines an optimization or decision problem, or gives an algorithm whose input is a society and whose output is a solution. The proposed continuous tasks therefore add a computational problem that the paper itself never studies.
For Theorem 1, the proposed mirror is mathematically coherent, but it is already present in the proof at the level relevant to the theorem. On the hypercube, the paper’s analysis depends on the population only through
\[ f_k=\frac{|\{u:p_{u,k}=1\}|}{|N|}. \]
Replacing this with
\[ f_k=\sum_t \mu_t p_{t,k} \]
is exactly a change from empirical frequencies to probabilities. The transition probabilities, the stationary distribution, and the \(1.208\) bound then follow by the same calculation. This is not a new computational formulation of the paper’s result; it is the paper’s existing aggregate analysis with the finite electorate notation removed.
A stronger proposed mirror would ask for the exact finite-horizon expectation or stationary distribution on an arbitrary explicitly represented median graph. That is a valid finite-state Markov-chain problem, but it is not a population-continuation result. If the graph is explicit, one can enumerate states and transitions; if it is implicit, the difficulty lies in representing the outcome space and computing medians. In the hypercube case, the coordinate formula already reduces the calculation to arithmetic on the \(f_k\). None of these versions creates a population-side complexity landscape.
Nor does making the type space genuinely continuous repair this. The analysed model has a finite median-graph outcome space, and agents are relevant only through their bliss points, together with any utility parameters that affect bargaining. A continuum of distinct bliss points would change the outcome or utility space, not merely the population. Conversely, if agents with the same relevant parameters are grouped, the result is precisely the finite-type model already implicit in the proof.
Theorem 6 has the same problem. Its social cost is additive:
\[ \operatorname{SC}_\mu(a)=\sum_t\mu_t d(p_t,a), \]
and the squared objective introduces only cross-terms in these type averages. Replacing sums over agents by expectations under \(\mu\) reproduces the proof line by line. The bound \(41\) and the random-dictatorship counterexample already concern population fractions; the latter even uses a two-point population. The continuous version supplies no new computational question attached to the theorem.
One can again define a stronger task: given a finite metric space, a type distribution, and a horizon, compute
\[ \mathbb E\!\left[ \left(\sum_t\mu_t d(p_t,A_r)\right)^2 \right]. \]
With the entire metric explicitly available, this is just evaluation of a finite Markov chain whose transition probabilities are weighted by \(\mu_i\mu_j\). That may be useful as a generic analysis of randomized mechanisms, but it is not a continuous-population contribution specific to this paper. If the paper’s intended black-box premise is retained—namely, that the mechanism designer need not enumerate or understand the decision space—then the proposed transition-matrix algorithm no longer models the paper’s operational setting.
The usual stronger objections do not apply here. Mass is meaningful: large cohorts with identical bliss points are a sensible regime. Social cost does not depend on individual identity. Rational \(\mu\) can be cloned into a finite electorate with exactly the same pair-sampling law. Those facts establish that a high-multiplicity version is coherent; they do not establish that this paper contains a worthwhile ChoCo problem.
Thus the best negative verdict is not that the mirrors are ill-defined. They are well-defined, and the proponent is right about that. The case against them is that both anchors are analytic aggregate bounds whose population dependence has already been quotiented out. Their proposed computational tasks are new finite-chain evaluation exercises, not continuizations of computational results from the paper. Under ChoCo’s stated priority—complexity and algorithms for computational social-choice problems—the paper offers no strong anchor.
The honest weakness is that this is a prioritization argument, not a modelling impossibility. If the programme is willing to count exact evaluation of randomized deliberation under a type distribution as worthwhile in its own right, then the proponent has a legitimate Class A mirror.
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.