| paper | d4-conf-ijcai-2018-0558 |
| 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: Egalitarian-SNTV is in \(\mathrm{P}\), with running time \(O(L+m+\tau)\) on a standard word RAM. Egalitarian-Bloc and egalitarian-\(k\)-Borda are \(\mathrm{NP}\)-complete, even with uniform support masses. Each rule admits an exact algorithm using \(O(L^2+m\tau+\binom{m}{k}\tau k)\) word operations. · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given \(m\) candidates, committee size \(k\), a rational distribution \(\mu\) over a support \(T\) of complete rankings, a fixed rule \(r\in\{\text{egalitarian-SNTV},\text{egalitarian-Bloc},\text{egalitarian-}k\text{-Borda}\}\), and a threshold \(q\), decide whether there is a committee \(W\subseteq C\) with \(|W|=k\) such that \(\min_{t\in T} f^r_{m,k}(\operatorname{pos}_t(W))\ge q\); determine the complexity in \(m\), \(|T|\), and the input bit length.
A type is a complete candidate ranking; \(\mu_t>0\) is its rational population mass. For each size-\(k\) committee \(W\), its egalitarian score is the minimum \(f^r_{m,k}(\operatorname{pos}_t(W))\) over supported types, and the decision variable is \(W\). The masses define the population distribution, while this paper’s objective depends on them only through which types have positive mass.
The mirror covers Theorem 1’s egalitarian-SNTV tractability and egalitarian-Bloc and egalitarian-\(k\)-Borda hardness, Corollary 1’s FPT results, and Theorem 2’s parameterized results. It does not address the axiomatic propositions or experimental findings.
The strongest mirror is an exact one for egalitarian committee selection. Let \(C\) be \(m\) candidates, let \(k\) be the committee size, and let \(T\) be the finite set of complete rankings with positive mass in a society \(\mu\), where each \(\mu_t>0\) is rational and the masses sum to one. For a fixed rule \(r\), define a committee’s score by
\[
E_r(W,\mu)=\min_{t\in T} f^r_{m,k}(\operatorname{pos}_t(W)).
\]
The decision problem is: given \(C,k,\mu\), a fixed rule \(r\), and a score threshold \(q\), is there a size-\(k\) committee \(W\) with \(E_r(W,\mu)\ge q\)? A solution is the committee \(W\). The rule-specific cases use the paper’s scores: SNTV counts committee members ranked first; Bloc counts committee members in a voter’s top \(k\); and \(k\)-Borda sums their Borda scores.
A plausible regime is a large consultation choosing a small committee from a shortlist of six candidates. Millions of participants submit complete rankings, but there are at most \(6!=720\) distinct ranking types. Each type is a complete description for this problem: two participants with the same ranking give every committee the same score. If the goal is to protect every expressed viewpoint, the paper’s worst-off-voter objective has a natural population interpretation. As in the paper, even a very small positive-mass type counts as much as a large one.
Theorem 1, proved in this paper, is my lead anchor. It states that egalitarian-SNTV is in P, while deciding whether a committee reaches a given score is NP-hard for egalitarian-Bloc and egalitarian-\(k\)-Borda. The continuous question above specializes to those three rules: it predicts tractability for SNTV and hardness for Bloc and \(k\)-Borda. I would expect the two hardness results to transfer. For any discrete election, replace its voters by the distribution over their ranking types; the minimum score is unchanged. Conversely, for any continuous instance, one voter per positive-mass type has exactly the same score for every committee. The committee and type choices that carry the combinatorics remain in the instance; population counts do not remove them.
For Bloc, the mirror is especially concrete: ask whether some size-\(k\) committee places at least \(q\) of its members in the top \(k\) positions of every positive-mass ranking type. Theorem 1’s Bloc hardness is proved here by a reduction from SET COVER. That gives a clean Class B expectation: hardness persists in the continuous formulation. The continuous question also has useful parameterized refinements. Corollary 1, established in this paper using prior FPT results for related problems, says egalitarian-Bloc is FPT by the number of candidates, the number of voters, and committee size. Since duplicate rankings can be collapsed, the continuous mirror is FPT by \(m\), support size \(\tau=|T|\), and \(k\). Thus its expected landscape is NP-hard in general, with tractable parameter regimes.
Theorem 2, also proved here, sharpens the \(k\)-Borda case. It states that the score-threshold problem for egalitarian-\(k\)-Borda is W[1]-hard when parameterized by the number of voters or by committee size, and is in FPT when parameterized by the number of candidates. Its continuous counterpart asks the same threshold question over the positive-mass ranking types. In the reduction given here, the number of voters is bounded by a function of the source parameter, so the support size is too; the W[1]-hardness carries over for parameter \(\tau\), as well as for \(k\). The FPT result carries over for parameter \(m\). This is another Class B result: the hardness survives the change of population representation, though a candidate-parameterized algorithm remains available.
The mirror’s case is unusually faithful to the paper. The authors explicitly say that egalitarian rules disregard how many voters hold each preference type, and Proposition 4 proves independence of cloning voters. A distribution over ranking types therefore expresses the rule’s own treatment of the population. The weakest point is also that fidelity: the masses matter only through whether they are positive. The continuous problem is exactly equivalent, for these scores, to the discrete problem on one voter per supported type. A strict reader could say that continuization adds representation but no new computation. I would still present it as a valid, narrow mirror rather than a tractability-changing relaxation; the natural follow-up is whether a mass-sensitive fairness variant—one that limits the influence of types below some mass threshold—has a different complexity landscape, while recognizing that such a variant changes the paper’s rule.
The strongest case against is that this paper has already removed population multiplicity from the computation. Proposition 4 says every egalitarian committee scoring rule is independent of cloning voters. For a society \(\mu\), a committee’s score is therefore just
\[
\min_{t:\,\mu_t>0} f_{m,k}(\operatorname{pos}_t(W)).
\]
The rational masses carry no information beyond whether each ranking type is present. A continuous instance reduces to the discrete election with one voter per supported type; a discrete election reduces to the distribution over its distinct ranking types. Both transformations preserve every committee’s score.
That makes the proposed mirror mathematically sound, but leaves little new population computation to study. Theorem 1’s \(P\) and NP-hard cases, and Corollary 1’s FPT results, transfer to support size \(\tau\) by replacing “number of voters” with “number of distinct rankings.” Theorem 2’s W[1]-hardness also transfers: its reduction uses a number of voters bounded by a function of the source parameter, so collapsing duplicate rankings keeps the continuous support parameter bounded. These are not objections based on whether hardness survives; they are evidence that the continuous input has collapsed to the same support-set problem the paper already studies.
The collapse also prevents the masses from behaving like an aggregate population. For types \(t,u\), consider \(\mu_n=(1-1/n)\delta_t+(1/n)\delta_u\). As \(\mu_n\) approaches \(\delta_t\), any committee for which \(u\) gives a lower score still receives that lower egalitarian score at every \(n\); the score jumps only when \(u\)’s mass becomes exactly zero. A single rare type thus has full veto power, regardless of its share. This is a coherent support-robustness objective, and the paper openly embraces that feature. It is weak evidence for a continuous-population model whose computational questions concern mass distributions.
A mass-sensitive version, such as optimizing a lower-tail quantile or a leximin score distribution, could make the proportions matter. But that changes the objective; the paper’s complexity theorems do not anchor those variants. A consultation with millions of participants and few ranking types is plausible, so I cannot honestly rule out a worthwhile continuous question. The negative case is narrower: these particular anchors offer unusually little for continuization to add, because the paper’s defining cloning invariance has already reduced the problem to the set of represented types.
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.