| paper | d4-conf-ijcai-2021-0227 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
parameterized→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete and \(\mathrm{W[1]}\)-hard parameterized by \(k\); not FPT unless \(\mathrm{FPT}=\mathrm{W[1]}\). · discrete side: parameterized · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given candidates \(C\), committee size \(k\), a support \(T^+\) of complete rankings with positive binary-rational masses \(\mu_t\) summing to \(1\), and a rational threshold \(q\), does there exist \(S\subseteq C\) with \(|S|=k\) such that \(\sum_{t\in T^+}\mu_t\min_{c\in S}\beta_t(c)\ge q\), where \(\beta_t(c)\) is candidate \(c\)’s Borda score in ranking \(t\)?
A society is a distribution \(\mu\) over complete candidate rankings; choose a \(k\)-candidate committee to maximize \(\sum_{t\in T^+}\mu_t\min_{c\in S}\beta_t(c)\).
Covers Pessimist winner determination and its W[1]-hardness; leaves the paper’s CC, Egalitarian-Median, and Egalitarian-Best results unmirrored.
The strongest mirror I believe in is Continuous Pessimist Winner Determination. A type \(t\) is a complete ranking of the candidates; its mass \(\mu_t\) is the fraction of the population with that ranking. Given the supported rankings \(T^+\), their positive binary-rational masses summing to \(1\), a candidate set \(C\), committee size \(k\), and a rational threshold \(q\), ask whether there is a committee \(S\subseteq C\), \(|S|=k\), with
\[
\Phi_\mu(S)=\sum_{t\in T^+}\mu_t\min_{c\in S}\beta_t(c)\ge q,
\]
where \(\beta_t(c)\) is candidate \(c\)’s Borda score under ranking \(t\). A solution is such a committee; the optimization version returns one maximizing \(\Phi_\mu\). This is the paper’s Pessimist rule written as average satisfaction per unit of population.
A plausible regime is a large membership organization choosing a board from a recurring slate. Millions of members may cast ballots drawn from a modest set of ranking templates, with each template shared by many members. The decision variable remains the paper’s \(k\)-candidate committee, and the objective still says that each voter values the committee by its least-preferred member’s Borda score, then aggregates those values across voters. Types and masses are therefore part of the actual model, not a softened version of the committee-selection question.
My anchor is Theorem 2, proved in this paper by a parameterized reduction from Independent Set on regular graphs: PESSIMIST is W[1]-hard parameterized by committee size \(k\). The continuous problem preserves that hardness. For a discrete election with \(n\) voters, assign each ranking type mass \(\mu_t=|\{v:\text{voter }v\text{ has ranking }t\}|/n\). Then \(\Phi_\mu(S)\) is exactly the paper’s total Pessimist score divided by \(n\), so the winning committees are identical; a threshold for the discrete score rescales by \(1/n\). The reduction preserves \(k\), and its rational masses have polynomial encoding length. One can also interpret the same distribution as an electorate with \(r\) copies of every voter for arbitrarily large \(r\): the population grows while the support and masses stay fixed. I expect hardness to transfer—the committee and candidate combinatorics remain.
This case covers the Pessimist winner-determination result, rather than claiming a mirror for the whole paper. A natural follow-up is whether the continuous problem is fixed-parameter tractable in support size \(\tau=|T^+|\). Enumerating each type’s worst-ranked committee member gives an \(m^\tau\operatorname{poly}(m,\tau,L)\)-time algorithm, so the question is whether that dependence can be improved to \(f(\tau)\operatorname{poly}(m,\tau,L)\).
The weakest point is that this is a very faithful high-multiplicity reformulation: normalizing the voter scores does not change the winners, and the hardness reduction’s support grows with its source instance. It establishes hardness for the general continuous model, but does not show hardness when the number of distinct rankings is small, or a new computational effect caused by fractional masses. That limits the positive claim to a credible continuous-population formulation whose hardness survives the embedding.
The strongest objection is that Theorem 2’s reduction does not establish hardness in a genuinely large, low-support population. Its construction uses voter-specific dummy blocks, and the paper does not bound the number of distinct rankings. So the hardness may rely on support \(\tau\) growing with the instance. The paper’s polynomial-time result for a constant number of voters does not settle the more relevant case of a large population with a constant number of ranking types. That leaves the proponent’s proposed question about parameterizing by \(\tau\) open, rather than supported by Theorem 2.
But this only narrows what the theorem transfers; it does not defeat the mirror. For a membership organization with many people using recurring ranking templates, the continuous problem is well-defined: choose a \(k\)-member committee maximizing the population-weighted average of each type’s least-preferred committee member’s Borda score. Ranking is a complete type for this rule, the objective retains the paper’s meaning, and the population does not vanish in the limit. Normalizing by population size is appropriate.
I can’t honestly make the requested universal negative case. There is a named computational result to mirror, a plausible high-multiplicity regime, and no continuous treatment in the supplied prior art that already answers the question. The reduction’s support may be large, and the continuous formulation may yield the same winners on embedded discrete instances; neither is a valid objection under the programme’s criteria. The negative case is therefore weak: it identifies a gap in the proponent’s hardness claim for small \(\tau\), but does not show that the mirror is not worth asking.
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.