| paper | d4-conf-ijcai-2019-0714 |
| 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: The normalized rational-mass decision problem is \(\mathrm{NP}\)-complete when \(\ell\) is part of the input. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given candidates \(C\), committee size \(k\), a finite support of complete rankings \(\pi\) with rational masses \(\mu_\pi\) summing to \(1\), and rational thresholds \(q_1,\ldots,q_\ell\) for \(\ell\le |C|\), decide whether there is a committee \(S\subseteq C\) of size \(k\) such that \(\sum_\pi \mu_\pi\sum_{c\in S}[\operatorname{pos}_\pi(c)\le t]\ge q_t\) for every \(t\in[\ell]\).
A decision problem over a listed distribution \(\mu\) of ranking types: choose binary committee variables \(y_c\in\{0,1\}\) with \(\sum_{c\in C}y_c=k\), satisfying \(\sum_\pi\mu_\pi\sum_{c\in C}y_c[\operatorname{pos}_\pi(c)\le t]\ge q_t\) for every \(t\in[\ell]\). There is no scalar objective; the thresholds specify feasible compromises.
Theorem 3’s hardness allows the number of score goals \(\ell\) to grow with the input, which may fit organizers choosing many thresholds less often than those choosing a few criteria.
fatal: False
The chosen mirror captures Theorem 3’s MULTIBLOC hardness. It does not cover Theorem 1’s tractability result, the approximation and parameterized results, the restricted-domain results, or the experiments.
My lead is C-MULTIBLOC, the continuous-population version of the paper’s Theorem 3. A voter type is a complete ranking \(\pi\) of the candidates; the society is a listed distribution \(\mu\) over ranking types, with rational masses summing to one. For a committee \(S\) of size \(k\), its average \(t\)-Bloc score is
\[ F_t^\mu(S)=\sum_{\pi}\mu_\pi\sum_{c\in S}[\operatorname{pos}_{\pi}(c)\le t]. \]
The instance gives \(C\), \(k\), a finite support for \(\mu\), an integer \(\ell\), and rational thresholds \(q_1,\ldots,q_\ell\). It asks whether there is a size-\(k\) committee \(S\) with \(F_t^\mu(S)\ge q_t\) for every \(t\in[\ell]\). A solution is that committee. As in the paper, there is no single scalar objective: the thresholds describe which compromises are feasible, and repeated queries can trace the Pareto frontier.
Theorem 3 states that MULTIBLOC is NP-complete, where \(\ell\)-MULTIBLOC combines \(1\)-Bloc through \(\ell\)-Bloc and \(\ell\) is part of the input. This is an original result of the paper, rather than a result cited from elsewhere; its proof is not included in the supplied text. C-MULTIBLOC keeps all those goals and the discrete choice of committee, changing the electorate into proportions of ranking types.
This has a natural high-multiplicity regime: for example, a large university or recurring conference choosing a fixed-size catering menu for a large constituency. Many people may share complete rankings of the options, so the number \(N\) of participants can be much larger than the number \(\tau\) of distinct rankings. A type’s mass then means the fraction of participants with that ranking, and a threshold such as \(q_t\) has a direct per-capita interpretation. The committee remains an actual menu of \(k\) items; only the population is continuous.
A second, complementary question is C-\(\{R_\delta,R_\rho\}\)-MULTIGOAL. Use an even-sized candidate set, the paper’s specified scoring families \(R_\delta,R_\rho\), and the same distribution over complete rankings. For a size-\(k\) committee \(S\), define each rule’s average score as its per-ranking score averaged under \(\mu\). The input includes rational thresholds \(q_\delta,q_\rho\); it asks whether one committee meets both, and a solution is such a committee. Theorem 2 says that \(\{R_\delta,R_\rho\}\)-MULTIGOAL COMMITTEE is NP-complete. This is also an original result of the paper; the authors say its proof is omitted and follows from a reduction from KNAPSACK. The two rules are separable, polynomial-time computable, and use exponentially growing score values. This anchor matters because it gives a fixed-goal mirror alongside Theorem 3’s growing number of goals, though the constructed rules make it the less natural of the two.
I expect both continuous questions to be Class B: hardness transfers. Given an \(n\)-voter instance with thresholds \(t_j\), set \(\mu_\pi\) to the fraction of voters with ranking \(\pi\), and set \(q_j=t_j/n\). Each continuous average score is exactly the corresponding discrete score divided by \(n\), so the feasible committees are identical. The transformation has polynomial encoding size. The witnesses are still committees, and their scores can be checked exactly using rational arithmetic, so the resulting decision problems are in NP as well. The hardness is driven by the choice among candidates and the simultaneous score constraints, not by the number of voters. These mirrors do not rely on fractional committees, lotteries, or continuous outcomes.
The weakest point is also the limit of the positive case: these are faithful continuous-population formulations, but their hardness does not show that continuization makes the paper’s problems easier or brings them within reach of continuous-optimization tools. Theorem 2’s criteria are artificial, and Theorem 3’s hardness allows the number of goals to grow. I would not claim these results mirror the paper’s tractability, approximation, or experimental findings. A useful follow-up is whether the fixed-goal tractability result remains tractable with binary-encoded rational masses, and how complexity changes with support size \(\tau\).
The negative case is weak, and I can’t honestly say it defeats both anchors. The paper has named computational results, and the voters are described by complete rankings that determine everything these rules use. There is no identity dependence or loss of meaning when identical rankings are grouped into types.
Theorem 3 has a plausible mirror. A large university choosing a menu for a constituency could have many people sharing rankings of the dishes. Thresholds for the \(t\)-Bloc scores can express how many highly ranked options the menu should offer, in fractions of the population. Letting \(\ell\) grow makes the goal set less typical than a fixed handful of criteria, so the theorem’s particular hardness result may have limited practical reach. But that weakens its appeal; it does not defeat the continuous question. A more focused version with a few natural criteria would still be worth asking, even if Theorem 3 no longer supplies its complexity result.
Theorem 2 is the weaker anchor. The \(R_\delta\) and \(R_\rho\) scoring families are constructed to encode knapsack weights, and it is hard to give their exponentially growing scores a persuasive policy interpretation. A large population does not fix that. But this only makes that particular mirror a poor flagship. It does not rule out a better mirror using ordinary committee scores.
The strongest general reservation is that these problems choose a discrete committee from scores computed over a fixed society; they do not change or allocate the population. That leaves less room for the continuous optimization machinery that motivates the programme. Still, the programme asks computational questions about a continuous population, and these score constraints depend directly on its type masses. Treating that reservation as decisive would wrongly exclude a population-based question merely because its answer is a committee.
So the best case against is that Theorem 2 has contrived criteria and Theorem 3’s growing goal set may be an awkward target. I cannot make the stronger claim that no worthwhile continuous mirror exists: Theorem 3’s mirror survives in a natural high-multiplicity scenario.
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.