| paper | d4-conf-sagt-2022-0022 |
| 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{NP}\text{-hard}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 8
statement extracted from the paper’s text layer
Given candidates \(C\) with fixed gender labels, committee size \(k\), and a distribution \(\mu\) over nonempty approval ballots \(A_t\subseteq C\), decide the following promise problem: either some \(k\)-candidate committee \(W\) satisfies \(U_c(W)<1/k\) for every \(c\in C\) and has gender imbalance \(0\), or every committee satisfying those JR inequalities has gender imbalance at least \(\varepsilon k\), for the constant \(\varepsilon>0\) from Theorem 8. Here \(U_c(W)=\sum_{t:\,c\in A_t,\ A_t\cap W=\varnothing}\mu_t\), and the masses are binary-encoded rationals summing to \(1\).
A society is a support of \(\tau\) approval-ballot types with rational masses \(\mu_t\geq 0\) summing to \(1\); candidates have fixed binary gender labels. Choose a committee \(W\subseteq C\) of size \(k\), with JR defined by \(U_c(W)<1/k\) for each \(c\), and measure its objective by the absolute difference between its male and female candidate counts. The lead computational question is the Theorem 8 promise gap for zero versus at least \(\varepsilon k\) imbalance.
Theorem 8's reduction does not establish hardness when the support size \(\tau\) is small or bounded, so it leaves the low-support hardness landscape open.
fatal: False
The mirror covers Theorem 8's gender-balance gap and, separately, Theorem 6's tree-restricted minimum justifying group problem. It leaves the approximation guarantees, random-profile threshold results, and experiments without a deterministic mass-input analogue.
My strongest mirror is the paper’s gender-balance hardness result, Theorem 8, with its tree-representation algorithm, Theorem 6, as a separate, tractable counterpart.
Let voter types be nonempty approval ballots \(A_t\subseteq C\), each with positive rational mass \(\mu_t\), where \(\sum_t\mu_t=1\). The support has size \(\tau\); candidates have fixed binary gender labels, and \(k\le |C|\) is the committee size. A voter group may contain any measurable portion of a type’s mass. For a candidate \(c\) and committee \(W\), define the mass of voters who approve \(c\) but are not represented by \(W\) as
\[
U_c(W)=\sum_{t:\,c\in A_t,\ A_t\cap W=\varnothing}\mu_t.
\]
Then \(W\) provides continuous JR exactly when \(U_c(W)<1/k\) for every \(c\). If \(U_c(W)\ge 1/k\), that unrepresented mass contains a cohesive group of size \(1/k\) approving \(c\); conversely, any unrepresented cohesive group of that size contributes to some \(U_c(W)\). Thus the population is continuous, while the committee remains a size-\(k\) set of candidates.
Continuous JR Gender-Imbalance Gap is my lead question. Given this instance, distinguish between: (YES) some JR committee has gender imbalance \(0\); and (NO) every JR committee has imbalance at least \(\varepsilon k\), for the constant \(\varepsilon>0\) from Theorem 8. Here the imbalance is the absolute difference between the numbers of male and female candidates in \(W\). The solution is the correct answer to this promise problem.
Theorem 8, proved in the paper, says this distinction is NP-hard even when \(n=k\). Its proof reduces from a gap version of Exact Cover by 3-Sets, using the cited hardness in Lemma 2. This is a direct population mirror: turn each discrete ballot type with \(q_t\) voters into mass \(\mu_t=q_t/k\). With \(n=k\), one voter corresponds to mass \(1/k\), so a discrete unrepresented cohesive group exists exactly when the continuous condition fails. Candidate genders, committee size, JR, and the imbalance objective all retain their meanings. The mirror is therefore Class B: the hardness transfers from the discrete problem. It does not rely on fractional committees or lotteries.
A plausible regime is a large association or university electorate selecting a fixed-size governing committee. Many members may share approval ballots because they belong to recurring constituencies or coalitions; one might have hundreds of thousands of voters but only tens or hundreds of observed ballot types. The type is the complete description relevant to this problem: the approval ballot. This is a sensible high-multiplicity version of the authors’ JR-and-diversity problem. The same formal model also permits larger support when the setting calls for it.
A separate question mirrors Theorem 6, also proved in the paper. Given the same rational-mass society and a tree on the candidates such that every approval set induces a connected subtree, find a smallest set \(W\subseteq C\) satisfying \(U_c(W)<1/k\) for every candidate \(c\). This is the continuous minimum \(n/k\)-justifying-group problem; \(k\) remains the target committee size, while \(W\) may be smaller. I expect this version to be tractable in time polynomial in \(m,\tau,L\), where \(L\) is the mass encoding length. The paper’s deepest-first algorithm appears to extend by replacing voter counts and the threshold \(\lceil n/k\rceil\) with rational mass sums and the threshold \(1/k\). The tree condition is the same structural restriction the authors study, not a simplification invented for the mirror.
These two questions cover Theorems 8 and 6, plus the paper’s definitions of JR and justifying groups. They do not claim to mirror the impartial-culture threshold or the experiments: those concern random generation of profiles, rather than a deterministic society represented by its type masses. Nor do I claim that the paper’s approximation ratios in \(n\) transfer unchanged to this mass-input model.
The weakest point is that Theorem 8’s hardness reduction does not establish hardness when \(\tau\) is much smaller than the population: its witness profiles can have many distinct ballot types. Its hardness comes from the committee and set-cover structure, so it shows that the continuous mirror is a well-posed computational problem whose worst-case hardness survives—not that continuization makes this problem easier. That limitation leaves the mirror credible, but narrows what this paper can establish about the benefits of high multiplicity.
The strongest case against is that both proposed mirrors remain close to weighted versions of finite approval problems. Theorem 8’s reduction uses \(n=k\), so its hardness transfers by putting each discrete voter at mass \(1/k\). That establishes a continuous formulation, but the reduction itself does not show that hardness persists when the population is large relative to the number of ballot types. Theorem 6’s tree algorithm also appears to admit a direct weighted adaptation, rather than requiring a new continuous technique. Those are fair limits on what this paper demonstrates about the benefits of continuization.
They do not, though, defeat either mirror. Theorem 8’s formulation is exact: a committee is continuously JR precisely when every candidate has less than \(1/k\) unrepresented approving mass. For a discrete profile normalized to masses \(n_t/n\), that condition is equivalent to the original threshold \(n/k\), including when \(n/k\) is not an integer. The reduction therefore supplies a valid Class B result for the continuous problem. Its support may grow with the reduction, but the problem also has a meaningful regime with many repeated approval ballots and small support. The committee’s discrete gender objective does not erase the continuous population in its representation constraints.
Theorem 6 has a credible continuous counterpart too. At each tree node, its algorithm can test whether the types whose ballots lie in the relevant subtree and share a candidate have total mass at least \(1/k\). It can then remove the types whose ballots intersect the selected subtree and continue. With rational masses, these checks use sums and comparisons polynomial in \(m,\tau,L\). The exchange argument appears to carry over because any unrepresented cohesive mass of at least \(1/k\) has a common approved candidate. This gives a plausible tractable mirror, not just a relabeling of the voters.
There is no basis here for a universal negative. The paper has computational results to mirror, and both questions continuize the population while retaining the authors’ representation and committee objectives. The objections above narrow the novelty claim: Theorem 8 does not establish hardness for small support, and Theorem 6 may need only a straightforward weighted proof. They do not show that the questions are unworthy. On the programme’s stated criteria, the anti case is weak.
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.