| paper | d4-conf-aaai-2006-0007 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in \(m,\tau,L\), including the exact optimum and an optimal rational vector. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 10
statement extracted from the paper’s text layer
Given a candidate set \(C\) and a finite support \(T\) of complete rankings with binary-rational masses \(\mu_t\ge 0\) summing to \(1\), define \(w_\mu(a,b)=\sum_{t:a\succ_t b}\mu_t-\sum_{t:b\succ_t a}\mu_t\) and \(E_\mu=\{(a,b):w_\mu(a,b)>0\}\). Compute the optimum and an optimal vector \(x\) of \(\min\sum_{(a,b)\in E_\mu}w_\mu(a,b)x_{ab}\), subject to \(x_{ab}+x_{ba}=1\) for each distinct pair and \(x_{ab}+x_{bc}+x_{ca}\ge 1\) for each distinct triple.
The input is a distribution over complete ranking types. The decision variables \(x_{ab}\) are fractional pairwise-order variables; the objective is the \(LP_3\) lower bound on per-capita majority-margin penalty. Adding \(\sum_{\{a,b\}\subseteq C}\min(p_\mu(a,b),p_\mu(b,a))\), where \(p_\mu(a,b)=\sum_{t:a\succ_t b}\mu_t\), gives a lower bound on total per-capita Kendall disagreement.
The mirror covers the \(LP_3\) majority-margin bound of Theorem 10. It does not assess the paper’s cycle-bound comparisons, search procedures, or exact-solver experiments.
The strongest numbered computational anchor is Theorem 10, proved in this paper. It says that, for every weighted majority graph, the optimum of LP2—minimizing the weighted edges selected subject to every directed cycle receiving total value at least \(1\)—equals the optimum of LP3. LP3 has a variable \(x_{ab}\) for each ordered candidate pair, constraints \(x_{ab}+x_{ba}=1\), and triangle constraints \(x_{ab}+x_{bc}+x_{ca}\ge1\); its objective is the weighted sum over majority edges. The paper computes this bound and uses LP3 in its experiments. The theorem establishes equality of the two optima; the polynomial-time conclusion follows because LP3 has polynomial size and linear programming is polynomial-time solvable.
A concrete mirror is Continuous Kemeny Bound. An instance consists of candidates \(C\) and a support of \(\tau\) complete ranking types \(t\), each with binary-rational mass \(\mu_t\ge0\) summing to \(1\). For each pair, define \(p_\mu(a,b)=\sum_{t:a\succ_t b}\mu_t\), and put a directed edge \(a\to b\) of weight \(w_\mu(a,b)=p_\mu(a,b)-p_\mu(b,a)\) whenever this is positive. The task is to return the optimum and an optimal vector \(x\) for LP3 with objective \(\min\sum_{a\to b} w_\mu(a,b)x_{ab}\), the pair-complement constraints above, and all triangle constraints. Here \(x_{ab}\) is a fractional pairwise-order variable in the relaxation. The society is the continuous object; the fractional vector is the paper’s method for calculating a lower bound on its per-capita Kemeny disagreement. This problem is tractable in \(m,\tau,L\): the margins come from the support, and LP3 has \(O(m^2)\) variables and \(O(m^3)\) constraints.
A plausible regime is a large election or public consultation over a fixed, modest slate of alternatives. Millions of people may cast rankings, while many share the same ballot type; the input records those types and their population fractions. The type is the complete ranking, and mass is the fraction of the electorate holding it. A discrete profile with \(n_t\) voters of each type becomes \(\mu_t=n_t/n\), so the bound is exactly the normalized bound the paper computes. The population is continuous in the model; the ranking outcome remains an ordinary permutation in the underlying election problem. That makes this a close mirror of the paper’s bound computation, rather than a continuation of outcome space.
The natural next question is Continuous Kemeny Ranking: given the same rational distribution \(\mu\), return a permutation \(\pi\) minimizing \(\sum_t\mu_t\,\mathrm{KT}(\pi,t)\), where \(\mathrm{KT}\) is Kendall distance. This is the exact per-capita version of the paper’s ranking objective. I expect hardness to transfer: a four-vote profile maps to at most four ranking types of mass \(1/4\), preserving the optimal rankings. The introduction reports NP-hardness, including the four-vote result, but attributes it to prior work rather than stating it as a numbered theorem here. I would therefore treat that hardness as support for this follow-up, not as my formal anchor.
The scope of this case is the paper’s Kemeny lower-bound computation, with exact continuous Kemeny optimization as the next question it motivates. Its weakest point is that Theorem 10 anchors a tractable bound, not the paper’s headline hardness claim, and the LP already accepts weighted graphs. The continuous formulation is still meaningful for a high-multiplicity electorate, but its clearest contribution is a precise, per-capita computational problem and a direct bridge to exact Kemeny optimization—not a new hardness result.
The strongest case against the anchor is that Theorem 10 already solves the proposed Continuous Kemeny Bound. The theorem compares LP2 and LP3 for weighted majority graphs, and LP3 accepts arbitrary nonnegative edge weights. Given a society \(\mu\), its pairwise margins supply those weights; the bound is then exactly the LP3 value. The support types and their masses matter only when computing the margins. The paper already proves polynomial-time solvability of the resulting LP, so presenting it as a new continuous-population computation would largely restate an existing result.
That does not defeat the stronger Continuous Kemeny Ranking mirror. For rational masses, choose a common denominator \(D\) and make \(D\mu_t\) copies of each ranking type \(t\). Every ranking’s continuous Kendall cost is its discrete Kemeny score divided by \(D\), so the minimizing rankings coincide. The paper’s Kemeny objective and computational methods apply to that profile. This is a close identity, though, and the paper does not state it as a result about continuous societies.
I can’t honestly turn that into a strong universal negative. A large rank-aggregation dataset with repeated ballot types is a sensible high-multiplicity regime, and the task explicitly treats a discrete-to-continuous identity as a potentially worthwhile finding. Theorem 10’s mirror is already answered in the paper; the exact-ranking mirror is largely a rescaling of its underlying problem. But under ChoCo’s stated standard, that leaves a plausible mirror standing. The negative case is therefore weak: the paper offers little new work for the bound anchor, but I can’t rule out a worthwhile continuous mirror of its Kemeny computation.
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.