| paper | d4-conf-aaai-2014-0465 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 10
Given \(K\) options, an unknown society \(\mu\) over complete weak rankings, and an oracle that answers a queried pair by sampling a fresh member of the society, design an adaptive algorithm that returns a ranking \(\tau\) with \(d_M(\tau,\prec^{CO_\epsilon}_\mu)<\rho\) with probability at least \(1-\delta\), while bounding or minimizing its expected number of pair queries.
A large crowd is a distribution \(\mu\) over complete weak-ranking types, with mass \(\mu_t\) for each type \(t\). The algorithm sees only fresh pairwise responses sampled from that society; its objective is expected query count subject to the paper's PAC maximum-rank-difference guarantee.
The theorem uses only pairwise marginals and never exploits respondent identities or support size, so the mirror gains no type-specific algorithmic leverage.
fatal: False
The mirror covers Theorem 10's expected-query guarantee for \(RANKEL^{CO_\epsilon}_{d_M}\); it leaves the other ranking-procedure and distance variants, and their experiments, outside the anchored claim.
The strongest honest case is a single, fairly narrow mirror: continuous population PAC rank elicitation with adaptive pair queries. It treats the crowd as the society, rather than treating pairwise randomness as noise attached to an otherwise finite model.
Take \(K\) options and let a type be a complete weak ranking of them, including indifferences. A society is a distribution \(\mu\) over these types: \(\mu_t\) is the fraction of the crowd with ranking \(t\), and \(\tau\) is the number of types with positive mass. For each pair, the population induces \(y_{i,j}=\mu\{t:o_i\succ_t o_j\}+\tfrac12\mu\{t:o_i\sim_t o_j\}\), matching the paper’s comparison convention. A query selects a pair and obtains a response from a fresh, independently sampled member of the population. This is plausible for a large product audience or annotation pool with many respondents but a smaller number of recurring preference types.
Lead mirror — Continuous-Population PAC Rank Elicitation. The unknown instance is such a population, accessed only through pair-query sampling, together with \(K\), \(\epsilon\), \(\rho\), and \(\delta\). The algorithm adaptively chooses which pairs to query and returns a ranking \(\tau\). Its goal is to have \(d_M(\tau,\prec^{CO_\epsilon}_\mu)<\rho\) with probability at least \(1-\delta\), while minimizing expected pairwise queries. Here \(\prec^{CO_\epsilon}_\mu\) is the paper’s \(\epsilon\)-insensitive Copeland relation induced by the population, and \(d_M\) is its maximum-rank-difference distance to a linear extension.
The anchor is Theorem 10, proved in this paper; the paper gives a proof sketch and omits technical proofs for space. It bounds the expected sample complexity of \(RANKEL^{CO_\epsilon}_{d_M}\). In the paper’s notation, \(\Delta_{i,j}=|1/2-y_{i,j}|\), \(\Delta_{(r)}\) is the \(r\)-th smallest such pairwise margin, and \(v^{CO_\epsilon}_{d_M}(r,Y)\) measures the remaining worst-case MRD ambiguity when \(r\) pair entries are unresolved. With \(r_1=2\arg\max\{r\in[K^2]:v^{CO_\epsilon}_{d_M}(r,Y)<\rho\}\) and \(R_1=\sum_{r=1}^{K^2-r_1}(\Delta_{(r)}+\epsilon)^{-2}\), the theorem states that the expected number of comparisons is \(O(R_1\log(R_1/\delta))\). Thus the bound depends on how close pairwise probabilities are to the Copeland decision threshold and on how much unresolved ambiguity the requested rank tolerance permits.
The expected direction is Class A in query complexity: adaptive sampling can elicit an approximately correct population ranking with an instance-dependent expected sample bound. This is the theorem’s actual guarantee; it is not a claim of polynomial bit-running time in \(K,\tau,L\). The mirror covers this MRD/Copeland result only. It does not try to continuize every ranking procedure or distance measure in the paper.
The connection to the authors’ problem is direct: they motivate pairwise elicitation with crowdsourcing, define the target order from aggregate pairwise probabilities, and study adaptive queries to recover that order. A large crowd with recurring preference types supplies a concrete population interpretation of those probabilities. The mirror also has a discrete bridge: a finite crowd with \(n_t\) members of each type induces \(\mu_t=n_t/n\), and querying a randomly selected member with replacement gives the same pairwise sampling model.
The important limitation is that the paper starts with unknown stochastic pairwise distributions \(Y\); it does not require those distributions to arise from a shared distribution over coherent individual rankings. The proposed mirror imposes that structure, and its theorem applies on this restricted, natural regime because the query responses for each pair have the required distributions. Also, if the exact mass vector were given to the algorithm, the elicitation task would largely disappear: the mirror must retain the paper’s sampling-oracle access to the population. This is the soft spot, but it does not reduce the population to a noise model: the probabilities are generated by the mass of actual ranking types.
Further questions include whether the expected bound can be strengthened to a high-probability bound, what the corresponding bound is for NDP distance, and how the query complexity changes when respondents are sampled without replacement from a finite crowd.
The honest negative case rests on Theorem 10, the proponent’s strongest anchor. The paper proves an expected sample complexity bound for adaptive PAC rank elicitation. A large crowd with recurring preference types is a plausible setting for it. The problem is that adding population masses does not produce a distinct computational question.
Let a type specify a respondent’s answer to every pair query, and let \(\mu_t\) be the fraction of respondents of type \(t\). Querying pair \((i,j)\) then produces exactly the pairwise outcome distribution whose expectation is \(y_{i,j}\). The ranking targets and distance guarantees in the paper depend only on \(Y\), not on how its entries are decomposed into type masses. Since each query samples just one pair and does not track respondent identity across queries, different mass distributions with the same pairwise marginals are indistinguishable to the algorithm. If types are restricted to complete rankings, that imposes extra consistency on \(Y\); Theorem 10 still applies to every instance in that restricted family.
So the proposed mirror inherits the paper’s bound unchanged: \(O(R_1\log(R_1/\delta))\) expected queries, with \(R_1\) determined by the pairwise margins and ranking ambiguity. The bound has no dependence on support size \(\tau\) or mass bit length \(L\). If the masses are known, the pairwise expectations and target order can be computed from them. If the masses are hidden and queries are the only access, the task reduces to the paper’s original sampling problem. In either case, the continuous optimization questions that motivate ChoCo do not arise.
A stronger proposal might let the algorithm reuse respondents’ complete ballots, or derive sharper guarantees by exploiting a small support of coherent ranking types. That would use information the paper’s pair-query model does not provide, so it would define a new problem rather than mirror Theorem 10. Studying such a problem could be worthwhile, but the paper’s result does not establish that it has a distinct continuous-computational contribution.
This negative case has a real limit: the crowd interpretation is natural, and the theorem does give a valid guarantee for population-generated pairwise preferences. If a continuous mirror may simply recast an existing theorem as a population application, this anchor survives. The case against is strongest under ChoCo’s narrower novelty standard: at the level the algorithm observes and the theorem analyzes, the stochastic pairwise model already captures the proposed population mirror.
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.