| paper | d4-conf-aaai-2026-0317 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{PSPACE}\text{-complete}\), hence \(\mathrm{NP}\text{-hard}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3.4
statement extracted from the paper’s text layer
Given a candidate set \(C\), committee size \(k\), a finite support of approval types \(A\subseteq C\) with positive binary-rational masses \(\mu_A\) summing to \(1\), and two size-\(k\) committees \(W_s,W_t\), decide whether there is a finite path \(W_s=W_0,\ldots,W_r=W_t\) in which consecutive committees differ by one swap and every \(W_i\) satisfies \(\sum_{A:\,c\in A,\ A\cap W_i=\emptyset}\mu_A<1/k\) for every \(c\in C\).
A society is a finite-support distribution over approval-ballot types, with support size \(\tau\) and rational masses; committees remain size-\(k\) subsets of \(C\), swaps define graph edges, and the objective is reachability through committees satisfying mass-based JR.
The mirror covers Theorem 3.4’s JR connectivity decision problem; it leaves the isolation and approximation results, rule-specific results, and restricted-domain results unmirrored.
I would lead with the paper’s JR-Reconfiguration result. It has a direct population mirror: replace the explicit voter list with a distribution over approval ballots, while keeping the committee and its one-candidate-at-a-time transitions as the decision objects.
Let \(C\) be the candidates, with \(|C|=m\), and let \(k\) be the committee size. A type is an approval ballot \(A\subseteq C\); a continuous society is a finite-support distribution \(\mu\) over such types, with rational masses \(\mu_A>0\) summing to \(1\). For a committee \(W\) of size \(k\), define
\[ u_\mu(c,W)=\sum_{\substack{A\subseteq C:\\ c\in A,\ A\cap W=\emptyset}}\mu_A. \]
Call \(W\) continuously JR if \(u_\mu(c,W)<1/k\) for every candidate \(c\). This is exactly JR expressed in population shares: a violation exists precisely when at least a \(1/k\) fraction of voters approve some common candidate \(c\) and none of them approves anyone in \(W\).
The named question is Continuous JR-Reconfiguration. An instance consists of \(C\), \(k\), the supported approval types and their binary rational masses, and two continuously JR committees \(W_s,W_t\). Ask whether there is a finite sequence \(W_s=W_0,\ldots,W_r=W_t\) of size-\(k\) committees such that every \(W_i\) is continuously JR and consecutive committees differ by one swap, \(|W_i\setminus W_{i+1}|=1\). A solution is such a path; the objective is reachability, as in the paper.
A plausible regime is a large civic consultation or participatory budgeting election with millions of residents choosing among a fixed candidate set. Many residents may submit the same approval ballot, perhaps because they share issue priorities or belong to recurring civic groups. Then the number of residents \(n\) can greatly exceed the number \(\tau\) of distinct ballots, and each type is a complete description for this problem: its members’ approvals are identical. The population mass records each group’s share. The committee still has \(k\) indivisible seats, and each update still replaces one candidate, preserving the question the authors study.
The anchor is Theorem 3.4, proved in this paper: given an approval profile \((A,k)\) and two JR committees, deciding whether they are connected in \(\mathrm{JR}(A,k)\) is PSPACE-complete. The paper proves membership and reduces from SAT-Reconfiguration; it cites Gopalan et al. for that source problem’s PSPACE-hardness.
I expect the continuous problem to be PSPACE-complete, with hardness transferring from the discrete problem. Every explicit profile maps to masses \(\mu_A=n_A/n\), where \(n_A\) counts voters of type \(A\). The JR condition and the committee-transition graph are preserved exactly. In the paper’s reduction, ballots can be grouped by type and encoded as rational masses with polynomial bit length, so the hardness construction carries over. Membership in PSPACE follows by searching the graph of at most \(\binom{m}{k}\) committees, checking each committee’s JR condition by exact rational arithmetic. This is a Class B mirror: the relevant combinatorics lie in the candidate and reconfiguration structure, not in having many individually listed voters.
The scope here is deliberately one result: Theorem 3.4’s JR connectivity decision problem. Further questions include whether PSPACE-hardness persists under restrictions on \(\tau\), and whether useful parameterized algorithms exist in \(k\) or \(\tau\).
The weakest point is that this is a very faithful high-multiplicity reformulation: JR connectivity depends on the normalized support masses, and the paper’s discrete profiles embed directly. A referee might regard it as a change of representation rather than a new continuous phenomenon. But that is also why the mirror is credible: it asks the authors’ same computational question about a population represented by proportions, and it identifies a boundary where making the population continuous does not remove the hardness.
The strongest case against this mirror is that it may add little new mathematics: the state space is still the finite graph of size-\(k\) committees, and continuity only changes how JR is checked. For a distribution \(\mu\) over approval types, a committee \(W\) satisfies JR exactly when, for every candidate \(c\), the mass of voters who approve \(c\) and approve nothing in \(W\) is less than \(1/k\). Aggregating a finite electorate by ballot type gives precisely this condition with masses \(n_A/n\); every transition is the same candidate swap as in the paper.
That makes the mirror a direct high-multiplicity formulation of Theorem 3.4, rather than a problem newly exposed to continuous optimization. The paper’s PSPACE-completeness result may therefore transfer with little change in the proof or algorithmic picture. This is the best negative point, but it is a concern about incremental novelty, not a fundamental reason the question is ill-posed or unworthy under ChoCo’s criteria. The paper does not already establish the computational result for rational population distributions, and existing high-multiplicity work would support the regime rather than collide with it.
The stronger version of the mirror survives: consider large consultations where many residents share approval ballots, represent those ballot groups by rational population shares, and ask whether two JR committees are connected through JR committees. The population is the continuous object; the committee and its swaps remain discrete. Mass does not vanish, and no individual-identity information needed by the question is lost. Since an unchanged hardness result is explicitly a worthwhile boundary result, I cannot honestly defeat this anchor. The negative case is weak here.
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.