| paper | d4-conf-aaai-2017-0108 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: polynomial-time solvable · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given \(n\) alternatives with known item features and a rational finite-support society \(\mu\) over complete rankings, accessible through independent type samples, define \(P^\mu_{ij}=\Pr_{t\sim\mu}[i\succ_t j]\). If \(P^\mu\in\mathcal P_n(\psi,r,A)\cap\mathcal P_n^{ST}\) and satisfies the theorem's margin and conditioning assumptions, how many uniformly sampled item pairs and independent type samples per pair suffice for an algorithm to return a ranking whose normalized pairwise disagreement with \(P^\mu\) is at most \(\varepsilon\) with probability at least \(1-\delta\)?
Types are complete rankings \(t\in S_n\) with rational masses \(\mu_t\); each query draws a type from the society and observes its preference on a selected pair. The target is a ranking \(\hat\sigma\) minimizing normalized disagreement with the pairwise majority matrix \(P^\mu\), using the paper's feature low-rank assumptions.
The guarantee depends on \(\mu\) only through its pairwise marginals \(P^\mu\), so type distributions with identical marginals add no population-specific runtime question.
fatal: False
The mirror covers Theorem 1's sample-efficiency guarantee for feature low-rank, stochastically transitive pairwise preferences; it does not separately mirror Propositions 1–3, the experiments, or model subsumption.
The strongest positive anchor is Theorem 1, “Guaranteed rank aggregation with sub-linear sample complexity using item features.” It is proved in this paper, using cited matrix-completion results and an approximate pairwise-ranking procedure; it is not a cited theorem. The paper has no named worst-case complexity result saying the underlying problem is in P, NP-hard, or parameterized-hard. Theorem 1 is instead an algorithmic *sample-complexity* guarantee, so it supports a narrower mirror.
Lead mirror: Continuous-Population Feature-Aware Ranking. Consider a large meal platform ranking a fixed menu of, say, six dishes. A customer’s type \(t\) is their complete strict ranking of those dishes, and \(\mu_t\) is the fraction of customers with that ranking. Millions of customers and at most \(6!=720\) possible types give a credible high-multiplicity regime, with many customers sharing each type. Each dish keeps its feature vector from the paper, such as nutrition or preparation method. The population’s pairwise preference probability is \(P^\mu_{ij}=\sum_t\mu_t\,\mathbf 1[i\succ_t j]\).
The problem is: given the dish features and sample access to customers drawn from \(\mu\), return a ranking \(\sigma\) whose normalized pairwise loss is at most \(\varepsilon\). Here loss means the fraction of item pairs for which \(\sigma\) reverses the population’s majority preference. The sampling interface follows the paper: choose \(m\) pairs uniformly at random, then obtain \(K\) independent customer responses for each chosen pair. A valid solution is an algorithm with a stated query bound and a probability guarantee for that loss. The underlying society is the rational support distribution \(\mu\); the learner sees it through the pairwise reports, as the paper’s learner sees preferences through its data.
This mirrors the paper’s central ranking task: infer an ordering of items from non-actively selected pairwise preferences, using item features. It asks about the customer population, not continuous items or outcomes. For the mirror to match Theorem 1, assume its induced \(P^\mu\) satisfies the paper’s Feature Low Rank condition, \(P^\mu\in\mathcal P_n(\psi,r,A)\), and is stochastically transitive. The feature condition means \(\psi(P^\mu)=A^\top H A\) for a latent matrix \(H\) of rank at most \(r\), with \(A\) derived from the known item features.
Theorem 1 states that if \(P\in\mathcal P_n(\psi,r,A)\cap\mathcal P_n^{ST}\), and \(\psi\) is \(L\)-Lipschitz on \([P_{\min}/2,1-P_{\min}/2]\), then a \(\gamma\)-approximate pairwise-ranking procedure succeeds with high probability when enough pairs and reports are sampled. Specifically, with \(\Delta=\min_{i\ne j}|\psi(P_{ij})-\psi(1/2)|\), \(m>48C_2^2d^2\log(n)(1+\gamma)^2/(\kappa^8\varepsilon^2\Delta^4)\) uniformly sampled pairs, and \(K\ge16(1+\gamma)mL^2\log(n)/(n^2\Delta^2\varepsilon)\) independent comparisons per pair, Algorithm 3 returns \(\hat\sigma\) with \(\operatorname{dist}(\hat\sigma,P)\le\varepsilon\) with probability at least \(1-3/n^3\). Here \(\kappa\) is the feature matrix’s inverse condition number, and the paper gives Copeland’s procedure as a \(5\)-approximate ranking procedure. This theorem is proved in the paper. In the mirror, it says that a large customer population can be ranked accurately from relatively few sampled comparisons when the feature and margin assumptions hold.
I expect this mirror to be tractable in the sample-efficiency sense: the feature structure lets the learner use fewer observations than generic pairwise ranking may require. That is not a Class A runtime-complexity result in the programme’s sense. The theorem does not establish polynomial running time for every implementation; the paper explicitly treats the convex completion step as an oracle. Follow-up questions include whether an explicit rational support list for \(\mu\) admits a runtime bound polynomial in \(n,\tau,L\), and what query bounds remain when the margin or low-rank assumptions are weakened.
The mirror covers the paper’s feature-assisted ranking guarantee from sparse pairwise comparisons. It does not turn the model-subsumption propositions or the experiments into additional anchors. Its weakest point is that this paper already works with a probabilistic pairwise matrix \(P\) and sampled comparison data. A distribution over complete rankings gives those probabilities a coherent population interpretation, but it also restricts the theorem to pairwise matrices realizable by such a distribution. And because the paper studies statistical sample complexity rather than discrete computational hardness, this is a plausible continuous-population reading of its ranking problem, but a weak bridge to the programme’s central complexity questions.
The strongest objection is that the anchor is a sample-complexity theorem, not a computational-complexity result. Theorem 1 bounds how many pairwise reports are needed; it gives no running-time bound, and its proof treats the convex completion step as an oracle. So it offers no Class A/B/C result about exact, approximate, or parameterized computation for a continuous version to mirror.
The restaurant example does give a sensible high-multiplicity population: many customers can share a ranking over a small menu. But that population structure does no work in the theorem. Its target and assumptions depend on the pairwise matrix \(P\). For a ranking distribution \(\mu\), the relevant matrix is just \(P^\mu_{ij}=\sum_t\mu_t\mathbf 1[i\succ_t j]\); two distributions with the same pairwise marginals are indistinguishable to the loss and the theorem. The feature dimension and geometry that drive the result describe the items, not the customers. If \(\mu\) is explicit, its marginals can be computed directly; if it is available only through sampled responses, the problem is the statistical estimation task the paper already formulates in terms of \(P\). Either way, adding \(\mu\) supplies a population interpretation, but not a new population-dependent computational question.
One could instead ask for an exact minimum-disagreement ranking from \(\mu\), or for the least mass whose preferences must change to alter the ranking. Those could be worthwhile problems, but the first changes the paper’s task and the second adds interventions and costs absent from it. They do not rescue a mirror of Theorem 1.
This is a case against prioritizing a mirror of this particular paper, not an airtight case that no useful scenario exists. The customer-population interpretation is plausible; the weakness is that the paper’s result is already about learning from probabilistic pairwise preferences, and its guarantee is driven by item features and sampling rather than by the continuous population.
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.