| paper | d4-conf-aaai-2010-0176 |
| 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}\)-complete and fixed-parameter tractable parameterized by \(k\), with deterministic running time \(2^{O(k)}\operatorname{poly}(m,\tau,L)\). · discrete side: parameterized · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given candidates \(C\), a current ranking \(\pi\), an integer \(k\), and a finite-support distribution \(\mu\) over rankings of \(C\) with binary-rational masses summing to \(1\), decide whether there is a ranking \(\sigma\) such that \(D_\mu(\sigma)<D_\mu(\pi)\), \(|L_\mu(\pi)\setminus L_\mu(\sigma)|\le k\), and \(|L_\mu(\sigma)\setminus L_\mu(\pi)|\le k\). Here \(D_\mu(\rho)=\sum_t\mu_t d_K(\rho,t)\), and \(L_\mu(\rho)\) contains the candidate pairs on which at least one positive-mass type disagrees with \(\rho\).
A society is a distribution \(\mu\) over complete ranking types; the decision variable is an output ranking \(\sigma\), with per-capita Kemeny cost and the paper's \(k\)-pair local neighborhood. The candidates and output ranking stay discrete. Pairwise masses can be aggregated and denominators cleared to use the weighted multi-tournament algorithm.
The mirror covers Theorem 3's local-search result for Kemeny aggregation; it leaves the paper's general weighted feedback arc set result and its one-sided cross minimization application aside.
My lead is Continuous \(k\)-local Kemeny improvement. The paper’s best anchor for it is Theorem 3, proved in this paper. As printed, the theorem names “\(k\)-LSFKOA”; the section defines the corresponding local-search problem as \(k\)-LSKOA. Its content is: given \(m\) votes over \(n\) candidates, a current ranking \(\pi\), and an integer \(k\), one can determine whether there is a ranking \(\pi^\star\) with strictly smaller total Kendall distance to the votes than \(\pi\), while changing at most \(k\) pairs in each direction between the disagreement sets \(L(\pi)\) and \(L(\pi^\star)\). The theorem gives a deterministic running time of \(2^{O(\sqrt{k}\log k)}n\log n\). The paper proves this by extending its feedback-arc-set algorithm to multi-tournaments and applying the Kemeny-to-multi-tournament modeling. I do not see a numbered hardness theorem in the paper; its hardness remarks are background, not eligible anchors under the requested standard.
Here is the continuous problem. Let \(C\) be a set of \(n\) candidates and let \(\mathcal R(C)\) be the rankings of \(C\). An instance consists of a current ranking \(\pi\), an integer \(k\), and a finite-support distribution \(\mu\) over rankings. Each positive-mass ranking \(r_i\) is a voter type, and its binary-rational mass \(\mu_i\) is the fraction of the population holding that ranking; the masses sum to \(1\). Write \(d_K(\sigma,r_i)\) for the number of candidate pairs ordered differently in \(\sigma\) and \(r_i\), and define the per-capita Kemeny cost by
\[
D_\mu(\sigma)=\sum_i\mu_i d_K(\sigma,r_i).
\]
Let \(L_\mu(\sigma)\) be the paper’s disagreement-pair set: include \((a,b)\) when \(\sigma\) puts \(a\) before \(b\), but some positive-mass type puts \(b\) before \(a\). The question is whether there exists a ranking \(\sigma\) such that
\[
D_\mu(\sigma)<D_\mu(\pi),\qquad
|L_\mu(\pi)\setminus L_\mu(\sigma)|\le k,\qquad
|L_\mu(\sigma)\setminus L_\mu(\pi)|\le k.
\]
A solution is the improving ranking \(\sigma\). This mirrors the paper’s one-step local-improvement question; it does not ask for a globally optimal ranking or a bound on a sequence of improvements.
The regime is a large electorate ranking a fixed slate of candidates: for example, a recurring poll with millions of respondents and a comparatively small number \(\tau\) of distinct complete rankings. People with the same ranking are indistinguishable for the Kemeny objective and neighborhood definition, so grouping them preserves everything the problem uses. The society is the distribution of rankings; the candidates and the output ranking remain discrete.
The discrete-to-continuous correspondence is exact. If a finite profile has \(N\) voters and type \(r_i\) occurs \(n_i\) times, set \(\mu_i=n_i/N\). Then \(D_\mu(\sigma)\) is the discrete total Kendall cost divided by \(N\), and \(L_\mu(\sigma)\) is precisely the disagreement set from the positive-count vote types. Thus the improving-rankings answer is unchanged. Conversely, any rational \(\mu\) can be represented by a finite profile after scaling by a common denominator. For the algorithm, aggregate each pair’s voter mass into the corresponding multi-tournament arc weights; scaling by a common denominator makes those weights integers. Theorem 3 therefore gives a tractable mirror: the stated subexponential parameterized bound in \(k\) and \(n\), with time to read and aggregate the \(\tau\) types and polynomial bit overhead in their encoding length \(L\).
This is a plausible problem for the authors to recognize: their Kemeny objective already sums pairwise disagreement across voters, and their algorithm explicitly uses a weighted multi-tournament representation. The mirror covers Theorem 3’s local-search decision for Kemeny aggregation, not the paper’s other application to one-sided cross minimization. It is a Class A result for this mirror, though it does not show that continuity dissolves a hardness result.
The soft spot is that this is a representation gain more than a change in the answer: rational distributions correspond exactly to scaled finite profiles, and the theorem is already efficient for the discrete local-search problem. So I would present the value as a natural high-multiplicity formulation and an exact algorithm for a large population described by \((\tau,L)\), not as a new tractability phenomenon caused by continuity. A related question is whether a mass-weighted neighborhood measure would be useful; that could address the sensitivity of \(L_\mu\) to an arbitrarily small positive-mass type, but it would be a different local-search problem from the paper’s anchor.
Theorem 3 is a valid computational anchor, and a large survey population with many respondents sharing rankings is a convincing high-multiplicity regime. I would not argue that voters are too individuated, or that the Kemeny objective cannot be stated over a distribution.
The difficulty for the proposed mirror is that the paper’s own algorithm already works on the relevant aggregate. For each candidate pair, sum the mass of types supporting each orientation. These pair weights determine the Kemeny cost of every ranking; whether a pair belongs to \(L(\pi)\) depends only on whether the opposing orientation has positive mass. So the full distribution over ranking types supplies no further information to this query. Clear the denominators of the rational masses: the pair weights become integer multiplicities, the disagreement sets stay the same, and every objective value is multiplied by a common factor. Theorem 3 is proved through weighted multi-tournaments, and the paper says its result extends to those instances. The continuous formulation therefore fits the aggregate representation already used by the theorem.
That makes this more than “the discrete answer happens to be known.” The paper’s result already handles the compressed, weighted object a continuous input would produce. Computing its pair weights from \(\tau\) ranking types takes \(O(\tau n^2)\) arithmetic operations, after which the theorem applies; rational weights add bit-length costs, not a new optimization problem. Calling this a new continuous algorithm for Theorem 3 would largely rename its existing weighted-multitournament formulation. That is the strongest case against this anchor: a narrow collision with the paper’s own model, not a general objection to high multiplicity.
A mass-weighted neighborhood could be proposed—for example, measuring how much voter mass supports the changed candidate pairs. But the paper’s \(k\) counts candidate-pair changes, not population mass, and continuizing the society does not force that search metric to change. The mass-weighted version might be worth studying independently, but it would not rescue this anchor without a reason to think the authors regard that different neighborhood as their problem.
This negative case has a clear limit: the population regime is sensible, and the direct continuous statement is well-posed. Its weakness is that the theorem’s weighted aggregate seems already to contain the proposed mirror, rather than that no worthwhile variant could be formulated.
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.