| paper | d4-conf-ijcai-2021-0456 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
parameterized→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-hard, even for \(\tau=1\), \(r=2\), and \(s=1\); fixed-parameter tractable parameterized by \((w,r,s)\). · discrete side: parameterized · adjudication: proved
full proof & adversarial review →
Corollary 15
statement extracted from the paper’s text layer
Given candidates C, a finite support T of partial-order types with binary-rational masses mu_t>0 summing to 1, and integers r,d,s, compute or decide whether there are r linear orders that each minimize K_mu(pi)=sum_{t in T} mu_t KT-dist(pi,t), have total pairwise Kendall–Tau diversity at least d, and have pairwise distance at least s.
A society is a distribution mu over partial-order types. Each candidate ranking has average Kendall–Tau disagreement K_mu; the decision asks for a diverse set of r optimal rankings. With common denominator D, pairwise costs become integer counts, while the input remains compact in the bit length of D.
For near-optimal diverse sets with delta>0, clearing denominators changes the additive imperfection to Ddelta, so the stated parameterized running time need not be polynomial in the binary input length.
fatal: False
The exact-optimum mirror covers Diverse KRA over partial-order types, including the single-ranking and four-complete-type cases. It leaves near-optimal diverse sets with delta>0, as well as the separate CO and PCO results, outside this formulation.
The mirror I believe in is 4-Type Continuous Kemeny Decision, and it is my lead. Given a candidate set \(C\), at most four complete ranking types \(T\subseteq S_C\), rational masses \(\mu_t>0\) summing to \(1\), and a rational threshold \(q\ge 0\), ask whether there is a linear order \(\pi\) with
\[ K_\mu(\pi)=\sum_{t\in T}\mu_t\,\operatorname{KT-dist}(\pi,t)\le q. \]
A solution is the ranking \(\pi\); the objective is its average Kendall–Tau disagreement with the society. Continuity lies in the population shares, while the decision remains a ranking.
My anchor is Theorem 18 of [3], which this paper cites in §3 rather than proving. It says that KRA on instances with four votes over candidate set \(C\), with integer threshold \(k\) on the sum of Kendall–Tau distances, has neither an \(O^*(2^{o(|C|)})\) algorithm nor an \(O^*(2^{o(\sqrt{k})})\) algorithm unless ETH fails.
The embedding is exact. For four votes \(\pi_1,\ldots,\pi_4\), give each distinct ranking type mass equal to its multiplicity divided by \(4\). Then \(K_\mu(\pi)=\frac14\sum_{i=1}^4\operatorname{KT-dist}(\pi,\pi_i)\), so the continuous threshold \(q=k/4\) preserves the answer. Thus the continuous problem inherits both lower bounds on this subfamily; for example, a subexponential algorithm in \(|C|\) for the general rational-mass problem would contradict the cited result.
A plausible regime is a large public consultation on the order in which projects should be funded, with four stable preference blocs. Millions of residents can share those four ranking types, so the number of agents can be large while the support stays at most four. Replicating each vote type changes the population size but leaves \(\mu\) and the per-capita Kemeny objective unchanged. This is a high-multiplicity version of the paper’s KRA problem, not a claim that continuization itself is new. I expect hardness transfers (Class B): the reduction’s combinatorics remain in the number of alternatives.
This mirror covers the paper’s total-order, single-ranking KRA decision problem and its cited four-vote lower bound. It does not cover the diverse-solution algorithm, partial-order votes, or the CO/PCO results. Natural follow-up questions include whether weighted KRA admits useful algorithms when the unanimity width is small, and whether a diverse weighted variant can handle rational masses with running time polynomial in their bit length.
The weak point is that the hardness anchor is cited from earlier work, and the concrete regime assumes four exact preference types. That makes the case narrow, but the restriction is also what makes the bridge especially clean: the paper’s own four-vote KRA instance becomes a society with four masses, and can represent an arbitrarily large population of repeated types.
The strongest case against is narrow, and it does not defeat the mirror. The proponent’s reduction is correct: for four votes, set \(\mu_t=n_t/4\) for each distinct ranking type, where \(n_t\) is its multiplicity, and set \(q=k/4\). The continuous decision then has exactly the same answer. Four stable blocs in a large consultation make a plausible high-multiplicity society. Treating that as merely a four-person problem would contradict ChoCo’s definition of type.
There is a scope problem with the chosen anchor: Theorem 18 of [3] is prior work cited by this paper, not a result established by it. Its four-vote lower bound also makes the proposed hardness transfer a particularly direct re-encoding of an existing discrete instance. That limits what this anchor says about the paper’s new contributions, especially Corollary 15 on diverse KRA. But it does not make the continuous question ill-posed or unimportant. The programme explicitly counts known answers as information about what to ask a prover, not as grounds to reject a mirror.
A stronger mirror would put rational masses on partial-order types and seek \(r\) rankings within \(\delta\) of the optimal *average* Kemeny cost, with the paper’s diversity and scatteredness requirements. That is a coherent population-level question. Its cost can be written using pairwise weights \(c_\mu(x,y)=\sum_t\mu_t[\text{type }t\text{ orders }y\text{ before }x]\). For the single-ranking version, multiplying by a common denominator converts these rational costs to integers; the paper’s pathwidth-based algorithm is therefore an immediate route to an answer, with the denominator’s bit length affecting the encoding. The diverse version may need more work because scaling can change the imperfection parameter, but that is a technical algorithmic issue, not a modeling failure.
Compact representations of Kemeny profiles already store each distinct ranking with its integer voter-count weight, so the four-bloc encoding is conventional; under ChoCo’s rules, that supports the high-multiplicity interpretation rather than counting as a collision. [A Kemeny-ranking implementation paper describes this representation](https://link.springer.com/article/10.1007/s11227-023-05058-w). The honest negative case is therefore weak: the anchor may be a poor choice for showing what is new in this paper, and its simplest continuous version may be settled by a routine weighted reduction. Neither point defeats the better mirror, and I see no fundamental obstacle to a worthwhile continuous question here.
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.