| paper | Let’s Agree to Agree: Targeting Consensus for Incomplete Preferences through Majority Dynamics |
| authors | Sirin Botan, Simon Rey, Zoi Terzopoulou |
| venue | IJCAI 2022 |
| filed under | voting · incomplete-info |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper contains no numbered result asserting hardness, tractability, approximation, or parameterized complexity. Its majority-dynamics process has a coherent high-multiplicity population mirror, but the proposed agenda-selection problem is explicitly left as future work. Therefore the paper fails the required computational-anchor test.
fails bit a — no named computational result to mirror
The proposed agenda-selection problem is a new computational extension rather than a computational result established by Proposition 2.
fatal: True
The mirror covers Proposition 2's Condorcet-consensus damage under majority dynamics, but no named computational result; the remaining propositions, experiments, and open computational questions are not covered.
The strongest honest case is conditional: the paper has a very natural population mirror, but it does not contain a qualifying named computational-complexity result. Its numbered propositions concern preservation, loss, and control of consensus; none asserts NP-hardness, membership in \( \mathrm{P} \), parameterized tractability, or similar. The paper itself leaves “the computational complexity of selecting a suitable order for control” as an open question. Thus the construction below is a computational continuation of a named structural result, not a complexity theorem already established by the authors.
My lead anchor is Proposition 2, proved in this paper: “For \(m>3\), MD does not preserve CW existence (thus neither CW identity).” It gives a particularly good mirror target because the failure is caused by the chair’s choice of issue order, not by the identities of individual agents.
The mirror is a finite-support continuous population. The alternatives are \(A\), and a type \(t\) is a strict partial order \(\succ_t\) over \(A\). A society is a rational distribution \(\mu\) over these types; \(\mu_t\) is the fraction of the population with that partial preference. For a current population state \(\nu\), define
\[ S_\nu(a,b)=\sum_{t:a\succ_t b}\nu_t. \]
Given an agenda \(\sigma=(p_1,\ldots,p_\ell)\), where \(\ell=\binom{m}{2}\) and exactly one of \(ab\) or \(ba\) occurs for each unordered pair, update the population exactly as in the paper. For \(p_j=ab\), every type that has not compared \(a\) and \(b\) receives \(ab\) when \(S_\nu(a,b)\ge S_\nu(b,a)\), and receives \(ba\) otherwise; ties therefore retain the paper’s tie-breaking rule. The added relation is closed transitively. The resulting mass is transported along this deterministic type-update map.
This gives the following precise problem.
Continuous Condorcet-Damage Agenda: given \(A\), a finite list of strict-partial-order types with rational masses \(\mu\), and an alternative \(w\) such that \(w\) is the unique initial Condorcet winner, decide whether there exists an agenda \(\sigma\) for which
\[ \mathrm{CW}(MD_\sigma(\mu))=\bot. \]
A yes-certificate is the ordered list \(\sigma\); verification consists of simulating the \(\binom{m}{2}\) updates and checking the final pairwise majorities. The objective version asks the chair to output such an agenda, if one exists.
This is recognisably the authors’ problem. It preserves incomplete preferences, majority adoption, transitive closure, one global agenda, and the final Condorcet-consensus test. It does not make preferences fractional, give different population blocks different agendas, or replace the dynamics by an unrelated voting rule. The paper’s three-agent counterexample becomes the continuous instance with mass \(1/3\) on each of its three types and the same agenda beginning with \(bc\) and \(bw\).
The high-multiplicity correspondence is exact. If every \(\mu_t\) is rational, clear denominators and create \(n_t\) identical clones of type \(t\). At every update,
\[ nS_\mu(a,b)=N^P_{ab}, \]
so all majority comparisons, ties, transitive closures, and final winners coincide. Conversely, every finite profile induces such a distribution. This is unusually strong support for the mirror: the paper’s dynamics depend only on aggregate pairwise support, and never on named-agent identity or interaction history.
The natural regime is a large consultation or deliberative platform over a fixed, moderate set of policy alternatives. Millions of respondents may fall into a relatively small number of response patterns because they receive the same briefing, belong to the same expertise or stakeholder category, or complete a standardized survey with missing comparisons. The chair is an agenda setter deciding which pair of alternatives is discussed next. Here \(n\gg\tau\), and mass—not individual count—is the meaningful quantity.
I would expect this problem to lie in the Class A/Class B boundary, but not naturally in Class C. Given an agenda, simulation is polynomial in \(m\), the number of explicit types \(\tau\), and the encoding length of the masses. Exhaustively enumerating agendas gives fixed-parameter tractability in \(m\). If the full agenda-selection problem is NP-hard, the likely source is the combinatorics of ordering issue pairs and alternatives, so hardness should transfer to a discrete or high-multiplicity version: Class B. A polynomial algorithm might instead exploit the structure of partial orders and majority margins, giving Class A. The proposition itself proves neither possibility.
It generates several worthwhile follow-up problems: target-specific agenda control, minimum-length agendas reaching consensus, weighted agenda costs, robustness over all agendas, and parameterized complexity in \(m\), \(\tau\), or the number of incomparable pairs. These are also directly connected to the paper’s own list of open questions.
The weakest point is decisive under a strict reading of the programme: there is no named computational anchor in the paper. Proposition 2 is a strong semantic anchor, but it is not a hardness result. Moreover, Continuous Condorcet-Damage Agenda is a computational extension of the paper’s structural result, not a problem whose complexity the paper established. If the source-screening rule requires a numbered NP-/P-/FPT-style result, this paper should not count as a ChoCo computational anchor.
Subject to that caveat, the population mirror itself is strong: it is an exact rational-clone continuization of the paper’s anonymous majority dynamics, and Proposition 2’s consensus damage survives unchanged when individual voters are replaced by population mass.
On ChoCo’s stated screening rule, I would reject this paper as an anchor—not because its population mirror is incoherent, but because it contains no computational result to mirror.
Proposition 2 is a semantic counterexample, not a complexity theorem. Its content is essentially
\[ \forall m>3\;\exists P\;\exists\sigma: \mathrm{CW}(P)\neq\bot \quad\text{and}\quad \mathrm{CW}(\mathrm{MD}_\sigma(P))=\bot. \]
The literal continuous translation merely replaces \(P\) by a distribution \(\mu\). The same constant-size witness, with masses such as \(1/3\), establishes the result immediately. That is not a computational question: the existence of a damaging agenda is already exhibited by the proposition.
The proponent’s proposed problem,
\[ \exists\sigma\; \mathrm{CW}(\mathrm{MD}_\sigma(\mu))=\bot, \]
is different. It is a newly invented agenda-control problem, not a continuous version of a computational problem analysed in the paper. The paper only mentions the complexity of selecting an order as future work. Verification is plainly polynomial for a supplied agenda, and exhaustive enumeration gives an \(f(m)\operatorname{poly}(\tau,L)\) procedure, but these observations do not turn Proposition 2 into a named computational result.
The strongest alternative modelling does not repair that gap. One could distribute mass over continuous utility or “latent opinion” parameters, but with finitely many alternatives the dynamics uses only the induced strict partial order. The parameter distribution therefore collapses exactly to masses on finitely many preference types. Adding confidence weights, networks, arrival times, or issue-specific influence would create a different model rather than a better continuization of this paper.
Indeed, for rational \(\mu\), clearing denominators produces an exactly equivalent finite profile: all majority comparisons, ties, transitive closures, and final consensus outcomes coincide. This confirms that the high-multiplicity regime is sensible, but here it supplies no continuous objective, mass-transfer decision, approximation problem, or optimization structure. The only genuinely computational questions—agenda selection, minimum updates, or control costs—are new problems left open by the authors.
The usual negative grounds do not apply: a large deliberative platform can plausibly contain many agents per preference type, and the paper’s outcomes are anonymous rather than identity-dependent. Thus the proposed mirror is mathematically legitimate, and if ChoCo permits open computational questions as anchors, the negative case is weak.
My strongest honest conclusion is therefore narrower: this paper has no worthwhile continuous mirror of any computational result it actually proves. A future high-multiplicity study of its agenda-control questions could be worthwhile, but that would be a new ChoCo project built on the paper’s model, not a computational continuization of the paper itself.
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.