| paper | d4-conf-aaai-2021-0145 |
| 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: Both objectives are \(\mathrm{NP}\)-hard for every fixed rule pair in \(\{\mathrm{SAV},\mathrm{MSAV}\}^2\). Their rational-threshold decision versions are \(\mathrm{NP}\)-complete. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 6
statement extracted from the paper’s text layer
Given candidate sets \(C_1,C_2\), committee sizes \(k_1,k_2\), community shares \(\alpha_1,\alpha_2\), and binary-rational distributions \(\mu_i\) over approval sets \(S\subseteq C_i\), choose disjoint committees \(w_i\subseteq C_i\) of sizes \(k_i\) maximizing either \(\min\{U_1(w_1),U_2(w_2)\}\) or \(U_1(w_1)U_2(w_2)\), where \(U_i(w_i)=\alpha_i\sum_S\mu_i(S)q_{f_i}(S,w_i)\) and \(f_i\in\{\mathrm{SAV},\mathrm{MSAV}\}\). What is the computational complexity of finding such an allocation as a function of the candidate counts, support sizes, and input bit length?
The society has types \((i,S)\), meaning community \(i\) and approval set \(S\), with mass \(\alpha_i\mu_i(S)\). The decisions remain integral disjoint committees; their utilities are the mass-weighted SAV/MSAV scores, and the objective is maximum egalitarian or Nash welfare.
For SAV/MSAV, each community’s distribution can be compressed to rational candidate scores, so the mirror may add little beyond a weighted finite allocation problem; this limits its distinctive continuous-optimization value.
fatal: False
The mirror covers Theorem 6’s NP-hardness for maximum egalitarian and Nash welfare with SAV/MSAV utilities. It leaves the paper’s other welfare functions, envy-freeness results, implication results, and parameterized algorithms aside.
A credible mirror is a pair of large membership organizations choosing recipients from overlapping award slates. Each organization has many voters, and a voter’s type is the pair consisting of their organization and the set of nominees they approve. Mass is the fraction of the combined voter population with that type. This is a plausible high-multiplicity regime when the slates are manageable and many members share approval ballots; duplicating every voter makes the population arbitrarily large without changing the type distribution.
Call the problem Mass Winners Allocation for SAV/MSAV Welfare. An instance gives candidate sets \(C_1,C_2\), committee sizes \(k_1,k_2\), population shares \(\alpha_1,\alpha_2>0\) summing to \(1\), and, for each community \(i\), a binary-rational distribution \(\mu_i\) over its supported approval sets \(S\subseteq C_i\). A feasible solution is a pair \(w_1\subseteq C_1,w_2\subseteq C_2\) with \(|w_i|=k_i\) and \(w_1\cap w_2=\varnothing\). For \(f_i\in\{\mathrm{SAV},\mathrm{MSAV}\}\), set
\[
U_i(w_i)=\alpha_i\sum_{S}\mu_i(S)\,q_{f_i}(S,w_i),
\]
where \(q_{\mathrm{SAV}}(S,w)=|S\cap w|/|S|\) for nonempty \(S\), and \(q_{\mathrm{MSAV}}(S,w)=|S\cap w|/\min(|S|,|w|)\), with zero contribution when the denominator is zero. The question is to return an allocation maximizing either \(\min\{U_1(w_1),U_2(w_2)\}\) or \(U_1(w_1)U_2(w_2)\). Maximizing the product is equivalent to maximizing the paper’s NSW objective, which takes the square root.
My lead anchor is Theorem 6, proved in this paper. It says that for every pair \(f_1,f_2\in\{\mathrm{SAV},\mathrm{MSAV}\}\), computing an allocation with maximum egalitarian social welfare and computing one with maximum Nash social welfare are both NP-hard. The result still holds when each election is simultaneously voters-interval and candidates-interval. The theorem is proved here using the reduction developed for Theorem 5, whose starting numerical problem’s strong NP-hardness is cited to Wojtczak (2018).
The mirror preserves the paper’s candidate sets, overlap, disjoint committees, committee sizes, approval utilities, and welfare objectives. It changes the electorate representation to masses of approval types. In a discrete instance with \(n_i\) voters in community \(i\), take \(\alpha_i=n_i/(n_1+n_2)\) and let \(\mu_i(S)\) be the fraction of that community voting \(S\). Then \(U_i(w_i)\) is the paper’s score divided by the same factor \(n_1+n_2\) for both communities. Both welfare objectives therefore have exactly the same maximizing allocations. Aggregating repeated ballots into rational masses is a polynomial-size transformation. The interval restrictions also have continuous counterparts: replace each position in the discrete voter ordering by a consecutive interval of mass, retaining the approval intervals and candidate ordering.
I expect hardness to transfer (Class B). The reduction’s combinatorics lie in choosing disjoint, indivisible candidates, not in having a finite number of voters. The continuous population makes the aggregation natural but does not relax that choice. The authors should recognize this as their problem with voters represented by type masses; it does not continuize the outcome space.
The further questions are whether the problem changes when the support size \(\tau\) is bounded, what approximation guarantees are possible for the two welfare objectives, and which restrictions on the mass distribution restore efficient algorithms.
My weakest point is the scenario’s empirical fit: large electorates with repeated approval ballots are plausible for broad membership organizations, but small grant panels are not a high-multiplicity regime. The mathematical match is stronger than that particular application claim, and the paper’s hardness remains even when the finite profiles are represented as arbitrarily large populations with the same masses.
The strongest objection is that the population is passive input data here. The algorithm never changes voters or allocates anything to them; it chooses two finite committees of named candidates. For fixed committee sizes, SAV and MSAV depend on each approval distribution only through candidate scores. For example, SAV reduces community \(i\)’s utility to \(\sum_{c\in w_i} a_{ic}\), where
\[
a_{ic}=\alpha_i\sum_{S\ni c,\;S\ne\emptyset}\frac{\mu_i(S)}{|S|}.
\]
MSAV has the same form with denominator \(\min(|S|,k_i)\). Thus the full type distribution can be compressed to a vector of rational scores. The mirror introduces no fractional population decisions or continuum-specific structure; its clearest computational interpretation is a succinct, weighted version of finite candidate allocation.
That objection does not defeat the lead anchor. Theorem 6 is a named computational result, and the proposed mirror preserves its task. Given finite electorates of sizes \(n_1,n_2\), let \(N=n_1+n_2\), set \(\alpha_i=n_i/N\), and let \(\mu_i\) be the empirical ballot distribution in community \(i\). Then each continuous utility is the paper’s score divided by \(N\). Both welfare objectives have the same maximizing allocations. Conversely, rational masses can be scaled to integer voter counts. Theorem 6’s NP-hardness therefore transfers exactly. Large membership organizations with repeated approval ballots are also a plausible high-multiplicity setting. The hardness residing in candidate choices is not a valid objection under the programme’s criteria.
The passive-input point weakens the claim that this mirror opens a distinctive continuous-optimization route, but it does not make the question unintelligible or unworthy: complexity under a compact high-multiplicity encoding is still a computational question the authors could recognize. I cannot make a strong case against this mirror, and I cannot honestly support the universal claim that no worthwhile scenario exists.
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.