| paper | d4-conf-ecai-2020-0025 |
| 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}\)-complete, even with dyadic masses; also \(\mathrm{W}[1]\)-hard parameterized by \(k\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a candidate set \(A\), committee size \(k\), and a finite support \(T\) of pairs of rankings over \(A\), with rational masses \(\mu_t\ge 0\) summing to \(1\), define \(b_{t,z}(S)=\sum_{c\in S}(m-r_{t,z}(c))\), where \(r_{t,z}(c)\) is candidate \(c\)'s position in type \(t\)'s ranking for layer \(z\in\{1,2\}\). Given a rational threshold \(q\), is there an integral committee \(S\subseteq A\), \(|S|=k\), such that \(\sum_{t\in T}\mu_t\max_{z\in\{1,2\}}b_{t,z}(S)\ge q\)?
A society is a distribution \(\mu\) over supported types \(t\), each a complete pair of rankings for the two layers. Choose binary committee variables \(x_c\in\{0,1\}\) with \(\sum_{c\in A}x_c=k\), maximizing \(\sum_{t\in T}\mu_t\max_{z\in\{1,2\}}\sum_{c\in A}x_c(m-r_{t,z}(c))\). The committee remains indivisible; only the population is represented by mass.
The mirror covers Theorem 1 for Max-\(k\)-Borda and, separately, Theorem 5 for Global-SP Max-CC. It does not address the paper’s results for Min, Sum, Pareto, or Vector rules, or its other parameterized and domain-restriction results.
The strongest mirror is a high-multiplicity version of Max-\(k\)-Borda. Take a large professional association choosing a small standards committee from a fixed slate of candidates. Members rank the slate for two possible policy settings, such as public versus industry funding. The paper’s own uncertain-future and candidate-attribute examples give a natural reason for those two rankings. In a standardized ballot regime, many members can submit the same pair of rankings, so the number \(N\) of members can be much larger than the number \(\tau\) of distinct ranking pairs.
A type is the complete pair \(t=(\succ_{t,1},\succ_{t,2})\) of rankings; \(\mu_t\) is the fraction of members with that pair, with \(\sum_t\mu_t=1\). Types must match exactly across both layers; approximate clustering would change the model. The decision remains an indivisible committee \(S\subseteq A\) of size \(k\). If \(r_{t,z}(c)\) is candidate \(c\)’s position in type \(t\)’s ranking for layer \(z\), define
\[ b_{t,z}(S)=\sum_{c\in S}\bigl(m-r_{t,z}(c)\bigr), \qquad F_\mu(S)=\sum_t\mu_t\max_{z\in\{1,2\}}b_{t,z}(S). \]
The problem is: given the candidates, \(k\), the supported types with their rational masses, and a rational threshold \(q\), decide whether there is a size-\(k\) committee \(S\) with \(F_\mu(S)\ge q\). A solution is such a committee, or the maximizing committee in the optimization version. This keeps the paper’s per-member choice of best layer and its committee decision intact; only the population aggregate is expressed as mass.
My lead anchor is Theorem 1, proved in this paper: *Max-\(k\)-Borda is NP-hard and W[1]-hard with respect to \(k\), even when \(\ell=2\).* The authors prove it by reduction from Independent Set. The continuous problem above mirrors that result directly. Given any finite election with \(N\) voters, assign each distinct ranking-pair type mass equal to its multiplicity divided by \(N\). Then
\[ F_\mu(S)=\frac{1}{N}\sum_{v\in V}\max_{z\in\{1,2\}}b_{v,z}(S). \]
Thus the discrete threshold \(R\) becomes \(q=R/N\), with exactly the same feasible committees and score comparisons. Clearing the denominators in a rational-mass instance gives the reverse finite-clone interpretation. The expected classification is Class B: the hardness survives because the combinatorics of choosing candidates survive the population normalization. The paper does not establish hardness when \(\tau\) is bounded. In fact, for fixed \(\tau\), enumerating each type’s best layer gives an \(\ell^\tau\)-time algorithm: for each layer assignment, add the resulting weighted Borda scores and choose the \(k\) highest-scoring candidates. That makes the support parameter a worthwhile follow-up.
A second, independent anchor is Theorem 5, also proved here: *Max-CC is NP-hard even for Global-SP profiles*, meaning all rankings in all layers are single-peaked with respect to one shared candidate axis. Its continuous mirror uses the same type and mass representation, but replaces \(b_{t,z}(S)\) by
\[ g_{t,z}(S)=\max_{c\in S}\bigl(m-r_{t,z}(c)\bigr). \]
Given the shared axis \(\pi\), require every ranking in every supported type to be single-peaked with respect to \(\pi\), and ask whether a size-\(k\) committee satisfies \(\sum_t\mu_t\max_z g_{t,z}(S)\ge q\). Again the solution is an integral committee. The paper proves its hardness by reduction from Vertex Cover, and the same equal-mass construction transfers that hardness to this normalized population problem. This is also Class B. It shows that the mirror’s hardness is not confined to unrestricted ranking profiles. A natural follow-up is whether the Global-SP problem has useful algorithms when parameterized by support size, and how the answer compares with the unrestricted Max-CC problem.
I think the authors would recognize both as their problems: the rankings, layers, committee size, and Max-\(R\) semantics are unchanged. Their scenarios need not all have large electorates. A large association with a fixed candidate slate and repeated standardized ballots is a plausible high-multiplicity regime, even if a seven-person jury is not. The continuous object here is the society’s distribution over complete multimodal preference types; neither the layers nor the committee are continuized.
The scope is deliberately narrow: these questions mirror the paper’s Max-\(k\)-Borda and Max-CC hardness results, not its full complexity landscape. The weakest point is also clear: the mirror faithfully preserves hardness, but this paper supplies no new continuous optimization method or evidence that hardness dissolves. Its strongest ChoCo contribution would be to make the high-multiplicity problems explicit and then investigate support-sensitive algorithms or approximation, rather than to claim that the paper’s NP-hardness becomes tractable.
The strongest case against these anchors is that the population continuum does very little mathematical work in either problem. Once the committee is fixed, its score is a weighted sum of finitely many type scores. For Max-\(k\)-Borda, each type contributes the maximum of two additive candidate scores; for Max-CC, it contributes the maximum of its best committee-member scores across layers. The committee remains indivisible, and there is no optimization over the population or over mass transfers. The resulting problems look like weighted finite-profile winner determination, rather than problems that call on continuous optimization.
That makes the mirrors weak examples of ChoCo’s continuous-optimization motivation. But it does not defeat them under the programme’s stated scope: computational questions about a society given as a distribution are in scope, and the distribution is precisely the population object. A weighted profile can still have a meaningful complexity landscape in \(m,\tau,L\), even when its outcomes are discrete.
Theorem 1 is a valid anchor. Its reduction uses a separate voter for each graph edge, so it establishes hardness when the number of types can grow with the instance; it does not show hardness in the more distinctive high-multiplicity regime where a large electorate has small support. That limitation weakens the theorem’s evidence for the most compelling continuous scenario. Yet it does not invalidate the better mirror: exact ranking-pair types with rational masses define a sensible Max-\(k\)-Borda problem, and asking what bounded support buys is worthwhile. The fact that a finite election can be encoded by assigning each type its multiplicity divided by the electorate size is the high-multiplicity bridge, not a reason to dismiss it.
Theorem 5 has the same limitation. Its Vertex Cover construction uses edge voters, so it does not establish hardness for small support. Still, the stronger mirror with a common single-peaked axis and repeated ranking-pair types remains coherent. A large association with recurring preference patterns is plausible, and the common axis is a meaningful domain restriction. The committee’s discreteness and the per-voter maximum across layers do not make the population representation degenerate; they simply leave the committee-selection part combinatorial.
I cannot honestly defeat either anchor across all reasonable scenarios. There is no continuous treatment in the supplied paper that already answers these questions, and the existing high-multiplicity literature supports treating the regime as sensible. The fair negative conclusion is narrower: these are valid but not especially compelling flagship mirrors for showcasing continuous-optimization technology, and the paper’s hardness reductions do not by themselves illuminate the low-support regime that best motivates a continuum. That is a case for modest expectations and careful prioritization, not for claiming that no worthwhile mirror 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.