| paper | d4-conf-aaai-2021-1195 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Answer: A correct policy achieving the stated additive guarantee can be constructed and executed in polynomial time. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given alternatives \(C\), a support \(S\subseteq C!\), and rational ranking-type masses \(\mu_\sigma\) summing to \(1\), find an adaptive pairwise-comparison policy \(P\) that identifies each queried user’s ranking and satisfies \(Q_\mu(P)\leq \operatorname{OPT}(\mu)+2(m-1)\), where \(Q_\mu(P)=\sum_{\sigma\in S}\mu_\sigma d_P(\sigma)\) and \(\operatorname{OPT}(\mu)\) is the minimum per-capita query mass of any correct policy.
The society consists of ranking types \(\sigma\in S\) with masses \(\mu_\sigma\). The decision variable is a pairwise-comparison policy applied to each user individually; its objective is the mass-weighted number of queries per capita.
The mirror covers the generic expected-query guarantee for exact ranking recovery. It leaves the paper’s entropy analyses for Mallows, mixture, and Plackett–Luce models, its empirical results, and preference-model fitting questions outside the mirror.
My strongest case is a continuous version of preference elicitation workload for a large virtual-democracy or personalization service. The platform needs each user’s complete ranking to make that user’s decisions, while many users share the same ranking and query conditions. Let a type be a complete ranking \(\sigma\in C!\), and let \(\mu_\sigma\) be the fraction of users with that ranking. In the relevant regime, the number \(N\) of users is very large compared with the number \(\tau\) of ranking types. The platform knows the cohort proportions \(\mu\), but not which current user has which type.
Define Continuous Query-Mass Elicitation as follows. An instance gives \(C\), a support \(S\subseteq C!\) of size \(\tau\), and rational masses \(\mu_\sigma\) summing to \(1\). A policy asks users pairwise-comparison questions, with each user’s next question depending on that user’s own answers. It must identify every ranking in \(S\). If \(d_P(\sigma)\) is the number of questions policy \(P\) asks a user of type \(\sigma\), its per-capita query mass is
\[
Q_\mu(P)=\sum_{\sigma\in S}\mu_\sigma d_P(\sigma).
\]
The optimization problem is to minimize \(Q_\mu(P)\); the policy itself is the solution. This is the mass-weighted workload of applying the elicitation process to a continuous cohort.
My lead anchor is Theorem 1 (Moran and Yehudayoff 2016), cited and restated in this paper, not proved there. It says: if a ranking \(\sigma\) is drawn from any distribution \(D\), Algorithm 1 correctly elicits \(\sigma\) using at most \(H(D)+2(m-1)\) pairwise-comparison queries in expectation. In the mirror, \(D\) becomes the cohort’s actual type proportions \(\mu\): the expected query count for one user is exactly the query mass across the population. Since any correct binary-query policy has expected depth at least \(H(\mu)\), this gives a policy within \(2(m-1)\) of the optimum. Also \(H(\mu)\le\log\tau\), so its expected workload is at most \(\log\tau+2(m-1)\).
This supports a tractable additive-approximation version of the continuous problem. With the support list as input, the insertion probabilities in Algorithm 1 can be computed by scanning the at most \(\tau\) supported rankings and summing their rational masses. That makes the policy executable in time polynomial in \(m,\tau,L\); this running-time conclusion is an inference from the algorithm and the sparse-support encoding, while Theorem 1 itself bounds the number of comparison queries. I would leave exact minimum-workload policy design as a further question.
The scenario fits the paper’s own motivating settings: it discusses many decision makers, larger elections, virtual democracy, and eliciting users one by one. Here the paper’s distribution over one hidden ranking becomes the society’s distribution over actual preference types. That is a change in what the distribution *means*: \(\mu_\sigma\) is population mass, not merely uncertainty about one person. The mirror covers the paper’s exact-ranking recovery by pairwise comparisons; it does not extend to every result about fitting preference models or to winner computation.
The weakest point is that the mathematical bridge is exceptionally direct: the continuous query-mass objective equals the paper’s expected query count. A reader could see this as relabeling an average-case result, especially because the paper already studies probabilistic ranking models. The scenario is most convincing when users need individually tailored rankings; if the sole goal were an anonymous election outcome and the exact \(\mu\) were already known, eliciting each ranking would serve no purpose. The result is also a query-complexity anchor, not a hardness result or a classification of exact optimization. It makes a positive case for a useful continuous workload problem, but it does not address where discrete hardness disappears.
The strongest case against this anchor is that its continuous problem adds no distinct computation. Set \(D=\mu\): the expected number of questions asked of one user is exactly \(Q_\mu(P)\), the proposed population’s per-capita query mass. The paper’s Algorithm 1 already gives a policy with expected cost at most \(H(\mu)+2(m-1)\), and its insertion probabilities can be computed by scanning the \(\tau\) supported rankings. Calling the probabilities population shares instead of uncertainty about one user changes their interpretation, while leaving the decision tree and its objective intact.
A more realistic large-cohort version does not change that point. If each user needs a personalized ranking, the system still has to query users individually; the population masses do not reveal which ranking belongs to a particular user. Total interaction cost for a finite cohort scales with its size, while per-capita cost remains the paper’s expected query count. If the task needs only the anonymous distribution of rankings, then known \(\mu\) already supplies it. If \(\mu\) is unknown, estimating it is a statistical learning problem rather than the paper’s exact recovery of one user’s ranking.
That makes this a weak ChoCo anchor: the population is an averaging interpretation around an existing average-case sorting problem, rather than a new computational treatment of society-level mass. But it does not defeat the mirror under the programme’s stated gate. A large service with many users drawn from a small set of ranking types is a sensible high-multiplicity regime, and minimizing its per-capita elicitation workload is a coherent question. The paper’s original algorithm already answers an additive-approximation version, which limits the novelty, but does not make the population question ill-posed.
So I can make a case against this being a worthwhile *new* continuization result. I cannot honestly argue that no worthwhile continuous mirror exists in any scenario, or that this anchor should be rejected outright.
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.