| paper | Simulating Multiwinner Voting Rules in Judgment Aggregation |
| authors | — |
| venue | AAMAS 2022 |
| filed under | frontier · ja |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 14
statement extracted from the paper’s text layer
Given an agenda \(\Phi\), integrity constraint \(\Gamma\), rational distribution \(\mu\) over complete judgment types \(\theta\), and partial judgment \(d\), decide whether some feasible judgment \(J\models\Gamma\) agreeing with \(d\) maximizes the PAV-JA population score \(\sum_{\theta}\mu_{\theta}\bigl(f_{\mathbf u}(|J^+\cap\theta^+|)-f_{\mathbf v}(|J^+\setminus\theta^+|)\bigr)\).
A society is a rational mass distribution \(\mu\) over complete judgment or approval types \(\theta\); the output remains a discrete feasible judgment \(J\models\Gamma\), selected by maximizing expected PAV-JA score, with the partial-outcome query inherited from Outcome(PAV-JA).
The mirrors cover Theorems 14 and 15, with Theorem 11 not surviving as a clean population mirror; they leave the simulation, stability, proportionality, and DNNF results untreated.
The strongest positive case is an approval-based, high-multiplicity version of the paper’s judgment-aggregation outcome problems. My lead anchor is Theorem 14, with Theorems 15 and 11 as two additional, independently defensible mirrors. All three are hardness-transfer cases: the continuous population does not dissolve the combinatorics, but it gives a faithful and useful high-multiplicity formulation.
The natural regime is a large electorate deciding a common agenda of \(m\) policy propositions. A voter type is a complete judgment type \(\theta\in\{0,1\}^{\Phi}\), or, in the approval-based special case, its approved issue set \(\theta^+\subseteq\Phi\). Two residents of the same type are indistinguishable to the rule: they agree on exactly the same issues. The society is a rational distribution \(\mu=(\mu_\theta)\), where \(\mu_\theta\) is the fraction of residents of type \(\theta\). A plausible setting is a city or large organisation with millions of residents but only dozens or hundreds of recurring issue-attitude profiles, subject to a common legal, budgetary, or logical integrity constraint \(\Gamma\).
The collective output remains discrete: a judgment \(J\in\{0,1\}^{\Phi}\) satisfying \(\Gamma\). If \(\Gamma\) is a committee constraint, \(J^+\) is still an ordinary \(k\)-member committee. Only the population is continuous. For a finite profile with \(n_\theta\) voters of type \(\theta\), setting \(\mu_\theta=n_\theta/N\) preserves every comparison of outcomes, because the paper’s sums over voters become normalized expectations over \(\mu\). Conversely, every rational \(\mu\) can be cleared to a finite cloned electorate. This is exactly the high-multiplicity bridge, not a fractionalization of the committee or the judgment.
My lead problem is Continuous PAV-JA Outcome. An instance consists of an agenda \(\Phi\) with \(m\) issues, an integrity constraint \(\Gamma\), a rational distribution \(\mu\) over judgment types, and a partial judgment \(d\). Let \(f_{\mathbf w}(q)=\sum_{r=1}^{q}w_r\). For PAV-JA, use \(\mathbf u=(1,\ldots,1)\) and \(\mathbf v=(1/m,1/(m-1),\ldots,1)\). Define the population score of a feasible judgment \(J\) by \(U^{\mathrm{PAV}}_\mu(J)=\sum_{\theta}\mu_\theta\bigl(f_{\mathbf u}(|J^+\cap\theta^+|)-f_{\mathbf v}(|J^+\setminus\theta^+|)\bigr)\). The question is whether there exists a \(J\models\Gamma\) such that \(J\) agrees with \(d\) and maximizes \(U^{\mathrm{PAV}}_\mu\) over all feasible judgments. A solution is such an optimal judgment.
This is a direct mirror of Theorem 14, proved in this paper: \(\mathrm{Outcome}(\mathrm{PAV\text{-}JA})\) is NP-hard. The paper’s proof reduces from a maximum-PAV committee-membership problem, using the earlier simulation of PAV. The continuous formulation changes the voter multiplicities into rational masses but retains the PAV-JA objective, the integrity constraint, the output judgment, and the partial-outcome query. The authors should recognise it immediately as their own problem with a compressed electorate.
I expect hardness to transfer, placing this in Class B. The reduction’s combinatorics live in candidate or issue selection and in the feasible-output structure, not in named voter identities. The continuous version therefore does not make the problem easy merely because many identical voters have been grouped. This also exposes useful follow-up questions: is the problem fixed-parameter tractable in the number \(\tau\) of supported types, in \(k\), or in the structure of \(\Gamma\)? Do DNNF or other compiled representations of \(\Gamma\) yield tractable weighted variants? What approximation guarantees are available when \(\mu\) is estimated from survey data rather than given exactly?
The second mirror is Continuous CC-JA Outcome. It has the same instance format and the same feasibility and partial-judgment query, but uses the CC-JA scoring vectors. Thus \(f_{\mathbf u}(q)=1\) for \(q\ge1\) and \(0\) for \(q=0\); if \(h=\lceil m/2\rceil+1\), then \(f_{\mathbf v}(q)=1\) exactly when \(q\ge h\). Its objective is \(U^{\mathrm{CC}}_\mu(J)=\sum_{\theta}\mu_\theta\bigl(f_{\mathbf u}(|J^+\cap\theta^+|)-f_{\mathbf v}(|J^+\setminus\theta^+|)\bigr)\). The task is again to decide whether some optimal feasible judgment agrees with \(d\).
This mirrors Theorem 15, proved here: \(\mathrm{Outcome}(\mathrm{CC\text{-}JA})\) is \(\Theta_2^p\)-complete. The paper’s reduction uses voter types that approve literal issues and an integrity constraint encoding the logical part of a MaxSAT instance. Those are entirely natural population types in a policy-agenda interpretation: many residents approve the same small bundle of propositions, while the collective judgment must satisfy consistency constraints. The expected classification is again hardness transfer, probably with the same \(\Theta_2^p\) upper bound under an analogous explicit representation of \(\Gamma\) and rational masses. A worthwhile next question is whether restricted integrity languages, such as DNNF constraints, change the weighted complexity of CC-JA even though the paper’s Theorem 8 only addresses max-sum and max-num.
The third mirror is Continuous \(k\)-Indiff-Indiff Max-Sum. Here the paper’s alternatives are \(X\), the agenda is \(\Phi_X^{\succeq}\), and the population distribution \(\mu\) is over complete judgment types \(\theta\in\{0,1\}^{\Phi_X^{\succeq}}\). For each \(A\in\binom{X}{k}\), let \(J_A\) be the canonical judgment satisfying \(k\)-indiff-indiff: alternatives in \(A\) are top and mutually indifferent, alternatives outside \(A\) are mutually indifferent, and every member of \(A\) is preferred to every alternative outside \(A\). Define \(V_\mu(A)=\sum_{\theta}\mu_\theta\,|\{\phi\in\Phi_X^{\succeq}:J_A(\phi)=\theta(\phi)\}|\). The problem is to output an \(A\) maximizing \(V_\mu(A)\); equivalently, given a rational threshold \(q\), decide whether the maximum score is at least \(q\).
This is a direct high-multiplicity version of Theorem 11, proved here: computing an outcome of max-sum induced by \(k\)-indiff-indiff on \(\top\)-restricted ballots is NP-hard, via a reduction from NAE-3SAT. Its reduction already contains repeated judgment types: each variable type is replicated \(10u\) times, while the clause information is represented by a finite collection of further types. Normalizing those multiplicities gives a rational \(\mu\) without changing the optimizer. The expected classification is therefore Class B. The further question is whether the hardness remains when \(\tau\) is genuinely small, or whether bounded type support permits a compact dynamic program or weighted optimization algorithm.
These mirrors cover only the paper’s outcome-computation and hardness results: Theorems 11, 14, and 15, with Proposition 7 supporting the PAV interpretation. They do not claim to continuize every simulation theorem, the Gehrlein-stability theorem, the proportionality axioms, or the DNNF encoding results. That narrow scope is a strength: each proposed problem preserves the paper’s actual decision variable, scoring rule, feasibility constraint, and outcome query.
The weakest point is that these are primarily weighted high-multiplicity reformulations, not examples where continuity creates a new LP or dissolves discrete hardness. The paper’s hardness may be carried by the agenda and by \(\Gamma\), and the theorem statements themselves do not establish complexity as a function of \(\tau\) and the mass encoding length. I would not present these as Class A or Class C discoveries. But that does not undermine the mirror: Class B is an explicit target of the programme. The paper supplies unusually clean population objects—approval and judgment types, aggregate scoring, and logical feasibility—and its named hardness results make it possible to ask, precisely, which parts of the difficulty survive compression of millions of voters into a distribution over recurring types.
The strongest negative case is narrower than the requested universal claim: the paper offers no evidence for a Class A or Class C continuization. Its computational content is outcome determination over a finite agenda, and the proposed distributions merely replace voter counts by weighted empirical frequencies. There is no new population-side variable, intervention, or continuous optimization problem. But that observation alone is not a valid objection under ChoCo: a faithful Class B mirror is explicitly worthwhile.
Theorem 14 is the hardest anchor to defeat. A correct population version uses the full judgment type \(\theta\), with
\[ U_\mu(J)=\sum_{\theta}\mu_\theta\left( f_{\mathbf u}(|J^+\cap\theta^+|) -f_{\mathbf v}(|J^+\setminus\theta^+|) \right). \]
For \(\mu_\theta=n_\theta/n\), this is exactly the paper’s PAV-JA score divided by \(n\). Every discrete instance therefore embeds verbatim, and rational masses can be expanded back into cloned voters. The objection that the result is “only weighted PAV” does not work: high multiplicity is the programme’s subject, and inherited hardness is an intended Class B outcome.
There are genuine limitations. Theorem 14 does not establish hardness when the number of supported types \(\tau\) is small; its reduction may use essentially one approval type per edge or gadget. With a simple committee constraint, the mirror largely becomes weighted PAV, while with arbitrary \(\Gamma\), much of the hardness may be encoded in the integrity constraint. Those facts weaken the novelty claim, but they do not make the question ill-posed. Parameterized complexity in \(\tau\), structured \(\Gamma\), and approximation from estimated \(\mu\) are legitimate follow-up questions.
Theorem 15 is similarly not defeated. The proponent overstates one point: the \(\Theta_2^p\) upper bound does not automatically transfer to binary rational masses. The representation of \(\mu\), the threshold, and \(\Gamma\) must be fixed; weighted optimization can alter the upper-bound argument. But equal rational masses already give the exact discrete instances from the theorem, so hardness transfers. A better formulation would state the weighted complexity separately rather than claim “probably the same” class. That is a technical repair, not a fundamental failure of the mirror.
Theorem 11 is the weakest anchor. Its reduction uses arbitrary \(\top\)-restricted judgment assignments, including types that are not rankings or approval ballots. Under the programme’s central model, those are not ordinary voter types. The clause-pair types are also largely bespoke, so the reduction does not demonstrate hardness in a genuinely compressed recurring-type regime. Replacing them by rankings or approval sets would require a new reduction. Thus this anchor should be dropped or explicitly presented as a broader judgment-population extension, not as a clean ChoCo mirror.
That still leaves Theorem 14, and probably Theorem 15. The paper has named computational results, anonymous aggregate objectives, sensible repeated approval/judgment types, and exact high-multiplicity embeddings. The honest negative conclusion is therefore not that no worthwhile continuous mirror exists. It is that the proponent has shown at most Class B mirrors, has not shown a population-driven tractability gain, and has overstated the third anchor and the weighted complexity claims. A universal negative would require rejecting the programme’s own explicit commitment to Class B hardness-transfer questions.
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.