| paper | Eliciting Kemeny Rankings |
| authors | — |
| venue | AAAI 2024 |
| filed under | voting · incomplete-info |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Corollary 2
statement extracted from the paper’s text layer
Given \(k\) alternatives, a society distribution \(\mu\) over complete rankings, independent sampling access to \(\mu\), and \(\rho, \delta > 0\), design an adaptive pair-query policy and output ranking \(\sigma\) minimizing queries subject to \(\Pr[\mathrm{KS}_\mu(\sigma) - \min_\pi \mathrm{KS}_\mu(\pi) \le \rho] \ge 1-\delta\).
Types are complete rankings \(t \in L(C)\), with masses \(\mu_t\). Each decision queries a pair of alternatives from a fresh sample of type \(t\) and observes its comparison; the policy outputs a ranking, minimizing expected or worst-case query count subject to the PAC Kemeny-score guarantee.
The PAC theorem factors entirely through pairwise marginals and uses sampling-oracle access, so it does not computationally manipulate an explicitly represented distribution over ranking types.
fatal: False
The mirror covers Proposition 1 and Corollary 2 for sampling with replacement; it does not preserve the finite-population correction in Propositions 2 and 3, nor the instability and pruning lemmas as separate anchors.
The strongest honest case is a single mirror: *Continuous Kemeny PAC Elicitation*. I would not claim that every result in the paper has a meaningful continuum analogue.
Let \(C=[k]\), let \(T=L(C)\) be the set of complete rankings, and let \(\mu\in\Delta(T)\) be the population distribution. Thus \(\mu_t\) is the fraction of society with ranking \(t\). For each pair \(i,j\), define
\[ q_{ij}(\mu)=\sum_{t:\,i\succ_t j}\mu_t . \]
A query to \((i,j)\) samples a fresh unit of population mass according to \(\mu\) and observes whether that sampled agent ranks \(i\) above \(j\). The elicitor adaptively chooses pairs and, after some number of queries, outputs a ranking \(\sigma\).
The continuous problem is:
Given \(k\), sampling access to a society \(\mu\), accuracy \(\rho>0\), and failure probability \(\delta\), find an adaptive pair-query policy and output ranking \(\sigma\) such that
\[ > \Pr\!\left[ > \mathrm{KS}_\mu(\sigma) > -\min_{\pi\in L(C)}\mathrm{KS}_\mu(\pi) > \le \rho > \right]\ge 1-\delta, > \]
while minimizing the number of queries.
Here
\[ \mathrm{KS}_\mu(\sigma) =\sum_{(i,j)\in\sigma}q_{ji}(\mu), \]
so the objective is exactly the population’s expected pairwise disagreement with \(\sigma\). A solution is the query policy together with the final ranking; it need not reconstruct \(\mu\), because Kemeny’s objective depends only on its pairwise marginals.
My lead anchor is Proposition 1 (⋆), proved by the authors in the extended version rather than cited from elsewhere, together with its direct consequence Corollary 2. Proposition 1 shows that, after \(t\) samples of every pair, choosing a Kemeny ranking of the confidence-shifted empirical matrix gives, with probability \(1-\delta\), an additive Kemeny-score error bounded by \(k(k-1)c_\delta^t\), where
\[ c_\delta^t= \sqrt{\frac{1}{2t}\log\frac{k(k-1)}{\delta}}. \]
Corollary 2 states that Algorithm 1 is a \((\delta,\rho)\)-PAC algorithm. Equivalently, the population can be elicited to additive Kemeny-score accuracy \(\rho\) using
\[ O\!\left( \left(\frac{k(k-1)}{\rho}\right)^2 \log\frac{k(k-1)}{\delta} \right) \]
samples per pair, up to the paper’s displayed constants.
This is genuinely a population continuization. The paper itself defines \(q_{ij}\) as the fraction of voters preferring \(i\) to \(j\), and its bandit feedback is obtained from a randomly sampled voter. Replacing finite proportions \(n_t/n\) by masses \(\mu_t\) changes none of the definitions. The observed matrix \(Q\) is simply the linear image of the continuous society \(\mu\).
A plausible high-multiplicity regime is a large recommendation or consultation platform: millions of users rank a fixed slate of products, candidates, or policies, but their rankings come from a few hundred or thousand recurring preference templates. The type is the complete ranking; mass is the fraction of users with that ranking; \(N\gg\tau\), where \(\tau\) is the number of occupied ranking types. Querying a randomly selected user about two products is precisely sampling from \(\mu\). The paper’s examples of movie and online-shopping platforms make this scenario especially natural.
The fact that different profiles can induce the same \(Q\), as in the paper’s Example 1, is not a defect. Kemeny is a \(C_2\) rule: for this task, pairwise population masses are sufficient statistics. The mirror retains the complete rankings as types and derives \(Q\) from them; it does not mistakenly make \(Q\) itself the population.
I would classify the full exact problem as Class B, with an A-like statistical layer. The sample-complexity guarantee is independent of the number of named voters and therefore captures the benefit of continuization. But the final operation \(K(\widehat Q+c\mathbf 1)\) is an exact Kemeny optimization over permutations. The paper explicitly states that computing Kemeny rankings is NP-hard, citing Bartholdi, Tovey, and Trick (1989). That hardness is driven by the number of alternatives, not by voter multiplicity, so it transfers to the continuous weighted-population version. Continuization makes population estimation clean; it does not dissolve the agenda-side combinatorics.
This also explains why the mirror is plausible to the original authors: it preserves their candidates, ranking types, pairwise feedback, Kemeny objective, confidence guarantee, and adaptive-query interpretation. Only the finite electorate is replaced by a distribution over voter types. It is not continuity in the outcome space—the output remains a discrete ranking—and it is not merely a noise model.
I would not use Propositions 2 and 3 as additional anchors. Their without-replacement improvement is meaningful for a large finite cohort, where type masses are represented by many individual copies, but the finite-population correction disappears in an ideal atomless limit. They are useful for the high-multiplicity dictionary, not independent continuum results. Likewise, Lemmas 2 and 3 are negative results about Kendall-tau instability, not separate mirrors.
The weakest point is the access model. The paper treats \(Q\) as unknown and grants sampling access, whereas the ChoCo formulation often imagines \(\mu\) explicitly given as an instance. If explicit \(\mu\) is required, the elicitation part disappears and only weighted Kemeny aggregation remains. That is still a valid continuous population problem, but it no longer mirrors the paper’s central contribution as closely. The case therefore depends on accepting sampling access to a continuous society as the natural computational representation of an unknown population.
The mirror generates several worthwhile questions: whether structure on \(\mu\) such as single-peakedness or small support makes the Kemeny postprocessing tractable; the complexity of optimal adaptive pair selection with unequal query costs; sharper sample bounds using the paper’s triangle-inequality and realizable-Borda constraints; and a formal finite-\(N\) to \(\mu\) dictionary quantifying rounding and without-replacement effects.
The strongest negative case attacks the proponent’s anchor itself: Proposition 1 and Corollary 2 do not actually compute over a society distribution.
Their input is an arbitrary pairwise-probability matrix \(Q\in[0,1]^{k\times k}\). Proposition 1 does not require \(Q\) to come from any finite profile \(P(k,n)\), or even from any distribution over transitive rankings. The algorithm samples Bernoulli outcomes with means \(q_{ij}\), then runs Kemeny optimization on the resulting matrix. Thus the theorem remains unchanged if \(Q\) is generated by an abstract stochastic comparison oracle rather than by a population of voters.
Lifting \(Q\) to a distribution \(\mu\) over rankings is therefore only a non-injective representation change. If two societies have the same pairwise marginals, they induce exactly the same observations, objective, confidence bounds, and algorithmic transcript. The proponent is right that this is harmless for a \(C_2\) rule; but that is also the negative point. For this anchor, the entire \(k!\)-type population has been quotiented down to \(O(k^2)\) pairwise means. The continuous society has no computational role beyond supplying Bernoulli samples.
The platform story establishes that such a high-multiplicity regime is plausible, but it does not change the theorem. Sampling a fresh user from a population of recurring preference types is statistically natural; it is not yet a continuous-population optimization problem of the ChoCo kind. The complexity being measured is oracle query complexity, with the society itself neither explicitly represented nor manipulated. The paper’s algorithm would make the same guarantee for a non-realizable \(Q\), so the population interpretation is semantically dispensable.
The natural repair is to give \(\mu\) explicitly. But then the elicitation problem disappears: compute \(q_{ij}(\mu)\) exactly and solve weighted Kemeny. That is a legitimate high-multiplicity Kemeny problem, and existing high-multiplicity work should be treated as supporting evidence rather than as a novelty objection. Nevertheless, it is not a continuous mirror of Proposition 1 or Corollary 2; it is the underlying Kemeny aggregation problem with rational weights, while the paper’s contribution concerns learning unknown pairwise probabilities.
A richer repair could make the full distribution matter—for example, requiring uncertainty sets over realizable ranking distributions, type-sensitive query costs, or guarantees depending on correlations between pairwise preferences. But then the problem is no longer the paper’s \(C_2\)-based PAC result. It becomes a new distributionally robust or type-aware elicitation problem, potentially worthwhile, but unsupported by the stated propositions. If it remains \(C_2\), it collapses back to \(Q\); if it uses more of \(\mu\), it changes the problem.
The without-replacement results do not rescue the mirror: their finite-population correction disappears in the atomless limit. They support a finite high-multiplicity dictionary, but do not provide a distinct continuous-population computation.
This is a real objection to the particular PAC anchor: it risks presenting a stochastic bandit formulation as a new continuization when the theorem already factors completely through pairwise probabilities. But the universal negative claim is ultimately weak. The programme explicitly treats Kemeny Ranking as a natural continuous/high-multiplicity problem, and the explicit-\(\mu\) weighted version is defensible even if the paper’s PAC theorem does not establish it. I could not honestly claim that no worthwhile continuous mirror exists; only that the proponent’s chosen anchor does not by itself supply one.
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.