| paper | d4-conf-aaai-2026-3832 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Answer: \(\mathrm{NP}\)-complete for both fixed choices \(X\in\{\mathrm{JR},\mathrm{EJR}^+\}\), already for every fixed \(k'\ge2\); also FPT parameterized by the support size \(\tau\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3.3
statement extracted from the paper’s text layer
Given candidates \(C\), committee size \(k\), an approval-ballot support \(\mathcal T\subseteq 2^C\), positive rational masses \(\mu_A\) summing to \(1\), a threshold \(k'\ge 2\), and \(X\in\{\mathrm{JR},\mathrm{EJR}^+\}\), are there two size-\(k\) committees \(W_1,W_2\) with \(|W_1\setminus W_2|\ge k'\), both satisfying mass-\(X\)? For each \(W\), mass-\(\mathrm{JR}\) requires \(\sum_{A:\,c\in A,\ |A\cap W|<1}\mu_A<1/k\) for every \(c\notin W\); mass-\(\mathrm{EJR}^+\) requires \(\sum_{A:\,c\in A,\ |A\cap W|<\ell}\mu_A<\ell/k\) for every \(c\notin W\) and \(\ell\in[k]\).
The society is a rational distribution \(\mu\) over complete approval-ballot types \(A\in\mathcal T\). The decision variables are two ordinary size-\(k\) committees; there is no separate optimization objective. Their distance and mass-based proportionality constraints determine whether the instance is a yes-instance.
The mirrors cover Theorems 3.3, 3.1, and 3.5 as mass-based decision problems. They leave the paper’s algorithms parameterized by voter count, counting and prevalence approximations, and experimental measures of axiom restrictiveness and candidate importance outside these anchors.
The clean mirror is to make the electorate a distribution over approval ballots while keeping candidates and committees discrete. For a finite candidate set \(C\), committee size \(k\), and support \(\mathcal T\subseteq 2^C\), let each ballot type \(A\in\mathcal T\) have positive rational mass \(\mu_A\), with \(\sum_A\mu_A=1\). The type is the complete approval ballot; mass is the share of voters with that ballot. The input is \((C,k,\mathcal T,\mu)\), with support size \(\tau=|\mathcal T|\) and binary mass encoding length \(L\).
For a committee \(W\), define
\[
b_{c,\ell}(W)=\sum_{\substack{A\in\mathcal T:\ c\in A\\ |A\cap W|<\ell}}\mu_A .
\]
These are the shares of voters who approve an excluded candidate \(c\) but have fewer than \(\ell\) approved winners. The natural mass versions of the paper’s axioms are: \(W\) satisfies mass-JR if \(b_{c,1}(W)<1/k\) for every \(c\notin W\); it satisfies mass-EJR+ if \(b_{c,\ell}(W)<\ell/k\) for every \(c\notin W\) and \(\ell\in[k]\). The strict threshold has a direct interpretation: a group of mass at least \(\ell/k\) cannot consist entirely of voters with fewer than \(\ell\) approved winners.
This is not outcome-space continuity: a solution is still an ordinary size-\(k\) committee, and the problems below are decision problems, so they have no separate optimization objective. Only the population has become continuous. It is also an exact bridge for finite elections. Given an \(n\)-voter profile, set \(\mu_A\) to the fraction of voters with ballot \(A\). If \(q\) voters have fewer than \(\ell\) winners, the finite axiom’s bad group exists exactly when \(q\ge\lceil \ell n/k\rceil\), equivalently \(q/n\ge\ell/k\). Thus each paper problem below embeds answer-for-answer in its mass version.
The lead anchor is Theorem 3.3, an authors’ result, with proofs deferred to their accompanying full version. It says that for every \(k'\ge2\), both JR-DIFF-COMMITTEES and EJR+-DIFF-COMMITTEES are NP-complete and W[1]-hard parameterized by committee size \(k\). Its mass mirror, Mass-DIFF-\(X\), takes \((C,k,\mathcal T,\mu,k')\), where \(X\) is either JR or EJR+, and asks whether there are size-\(k\) committees \(W_1,W_2\), both satisfying mass-\(X\), with \(|W_1\setminus W_2|\ge k'\). A solution is the pair of committees. This directly mirrors the paper’s question about the diversity of proportional outcomes. Because every finite election maps exactly to an empirical mass distribution, I expect the unrestricted mass problem to be hard by transfer (Class B), not continuum-specifically hard. That does not settle whether small \(\tau\) changes the picture.
A second anchor, Theorem 3.1, is also the authors’ result, proved in the accompanying full version rather than cited from earlier work. It states that JR-NOT-EJR+ is NP-complete and W[1]-hard parameterized by \(k\); the paper also notes that its reduction establishes hardness when asking for a JR committee that fails even \(2\)-EJR+. The mirror, Mass-JR-NOT-Mass-EJR+, takes \((C,k,\mathcal T,\mu)\) and asks whether some size-\(k\) committee satisfies mass-JR but not mass-EJR+. A solution is that committee, with a candidate and level \(\ell\) witnessing failure, meaning \(b_{c,\ell}(W)\ge\ell/k\). It asks whether the stronger axiom actually rules out something allowed by the weaker one, a central question in the paper. I again expect hardness to transfer from the finite problem.
A third, narrower anchor is Theorem 3.5, another authors’ result whose proof is in the accompanying full version. It says that 2-CANDIDATES-JR is NP-complete and W[1]-hard parameterized by \(k\). Mass-2-CANDIDATES-JR takes the mass election and a specified pair \(C'\subseteq C\), and asks whether there is a mass-JR size-\(k\) committee containing \(C'\). The solution is the committee. This mirrors the paper’s candidate-importance question in a concrete way: can these two particular candidates coexist in a proportional outcome? Here too I expect hardness to transfer.
The regime is a large civic platform or participatory-budgeting election with a shared slate of projects and many participants approving bundles from it. Participants with the same approval ballot are one type, exactly because the paper’s problems use no other voter-specific information. The paper’s own pabulib data have \(69\) to \(95{,}899\) voters and \(7\) to \(138\) candidates, making the population-scale motivation concrete. The intended high-multiplicity regime is where the electorate is much larger than the number of distinct ballots, \(\tau\); the paper does not report \(\tau\), so these data establish scale but not how often that regime occurs. This is a reasonable scenario for the authors’ model: it preserves their ballots, axioms, and committee choices, while expressing electorate thresholds as shares.
My weakest point is that the transferred hardness establishes hardness of the unrestricted rational-mass problems, but does not show that hardness persists when \(\tau\) is small. Nor do the reported experiments establish that voters greatly outnumber distinct ballot types. That leaves a worthwhile follow-up: parameterize these mirrors by \(\tau\), and ask whether the algorithms or hardness change in the genuinely high-multiplicity regime. The mirrors cover the paper’s committee-diversity, axiom-comparison, and candidate-containment results; they do not try to continuize its counting or experimental measures.
The strongest case against these mirrors is that this paper’s voter model already factors through ballot-type frequencies. Its axioms ignore voter identities, and their thresholds are proportional to \(n\). For any profile, the relevant input can therefore be written as the empirical distribution \(\mu_A=|\{i:A_i=A\}|/n\). Conversely, any rational distribution in the proposed mirrors can be expanded into a finite profile using a common denominator. The mirrors introduce no new population states; their main change is to encode repeated voters by binary masses. That may matter for running time, but it makes the novelty hinge on compressed-input complexity rather than a new model of proportionality.
That objection reaches Theorem 3.3 directly: committee distance concerns candidate sets, while the population only determines which committees pass the axiom. It reaches Theorem 3.1 for the same reason: whether JR and EJR+ differ is determined by ballot frequencies and the relative thresholds. And Theorem 3.5 asks whether two named candidates can coexist in a committee passing that same frequency-based JR test. In all three cases, the proposed mass predicate is a faithful reformulation of the finite one.
But reformulation is not enough to defeat the anchors. The paper’s explicit input lists voters; the mirror’s input can encode a large electorate with support size \(\tau\) and mass bit length \(L\). Whether these problems admit algorithms in \(m,\tau,L\), or have different complexity when \(\tau\) is small, is a real computational question. The paper’s results parameterized by the number of voters do not by themselves answer it. Saying that the unrestricted instances expand back to finite elections also does not settle the value of studying their compressed representation.
Nor does the scenario fail on multiplicity grounds. A civic platform with many participants choosing from a shared slate can plausibly have large cohorts with identical approval ballots. For this paper’s questions, an approval ballot is a complete voter type: the axioms use no other individual information. The reported dataset’s voter counts make scale plausible, though it does not report the number of distinct ballots, so it does not establish that its own instances have small \(\tau\).
So the negative case is narrow: these are unusually clean mirrors, but their potential contribution lies chiefly in the high-multiplicity encoding and its algorithms, not in changing the underlying proportionality questions. That is a legitimate reason to rank them below mirrors with richer continuous structure. It does not honestly support the universal claim that none is worthwhile. Each of the three anchors survives the stronger version of that objection.
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.