| paper | d4-conf-aaai-2016-0039 |
| 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: All three guarantees hold. The explicit PTAS sampling bound uses \(e=\min\{\epsilon,1\}\), agreeing with the stated inverse-square bound for \(0<\epsilon\le1\); larger fixed accuracies use \(e=1\). · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given alternatives \(A\) and a finite support of uncertainty types \(t\), with rational masses \(\mu_t\) and pairwise probabilities \(q_t(a,b)=\Pr_{D_t}[a\succ b]\) realizable by distributions over rankings, find a ranking \(\hat\sigma\) minimizing \(H_\mu(\sigma)=\sum_t\mu_t\mathbb{E}_{\rho\sim D_t}[d_{\mathrm{KT}}(\sigma,\rho)] = \sum_{a\succ_\sigma b}\sum_t\mu_t q_t(b,a)\), or return one satisfying \(H_\mu(\hat\sigma)\le(1+\epsilon)\min_\sigma H_\mu(\sigma)\). In the sample-access variant, each draw samples \(t\sim\mu\) and returns \(q_t(a,b)\) for a queried pair; determine whether the paper’s two guarantees hold: \(O(m^4\log(m/\delta)/\epsilon^2)\) draws per pair followed by the FAST PTAS, or \(O(\log(m/\delta)/\epsilon^2)\) followed by an exact FAST solver when \(\epsilon<1/3\), with success probability at least \(1-\delta\).
A society is a distribution \(\mu\) over complete uncertainty profiles \(D_t\), each describing the rankings a cohort may hold; for this objective, each profile can be represented by its pairwise probabilities \(q_t(a,b)\). The decision variable is a social ranking \(\sigma\), and the objective is the mass-weighted expected Kendall tau distance \(H_\mu(\sigma)\).
All cohorts collapse into a single mixture distribution or aggregate tournament, so the mirror carries no type-specific optimization structure; the proponent specifies type masses and pairwise marginals but does not address this collapse. It bounds the population-specific contribution, while the paper’s own objective is defined by the same aggregate, so the computational mirror remains well-posed.
fatal: False
The mirror covers the expected-Kendall optimizer and the approximation and elicitation guarantees of Theorems 1 and 2. It leaves the Mallows structural characterization in Theorem 3, the loss bounds for ignoring uncertainty in Theorem 4, and the empirical simulations outside the mirror.
The strongest mirror is Continuous Uncertain-Kemeny. It preserves the paper’s question—choose a social ranking that minimizes expected Kendall tau disagreement with people’s uncertain preferences—and makes the population the continuous object.
A type \(t\) is an uncertainty profile \(D_t\) over rankings of the alternatives. For this objective, the profile is fully represented by its pairwise probabilities \(q_t(a,b)=\Pr_{D_t}[a\succ b]\). An instance gives the alternatives \(A\), \(\tau\) supported types, and rational masses \(\mu_t\) summing to \(1\); the profiles’ pairwise probabilities are rational and realizable by distributions over rankings. Mass is the fraction of the population with that profile. The decision variable is a ranking \(\sigma\), and the objective is
\[ H_\mu(\sigma)=\sum_{t=1}^{\tau}\mu_t\,\mathbb{E}_{\rho\sim D_t}[d_{\mathrm{KT}}(\sigma,\rho)]. \]
The task is to return a ranking minimizing \(H_\mu\). Equivalently,
\[ H_\mu(\sigma) = \sum_{a\succ_\sigma b}\sum_t\mu_t q_t(b,a), \]
so the objective depends only on the pairwise probabilities, not on full distributions over the \(m!\) rankings.
My lead anchor is Theorem 1, proved in this paper. It states that, for voters whose uncertain preferences are distributions over rankings, a social ranking minimizing the expected sum of Kendall tau distances is exactly a minimum-feedback ranking of the tournament whose edge weight from \(a\) to \(b\) is the sum, over voters, of their probabilities of preferring \(a\) to \(b\). The theorem is a computational characterization, not itself a new NP-hardness proof: the paper obtains the hardness consequence from the cited NP-hardness of FAST, due to Bartholdi, Tovey, and Trick (1989).
Continuous Uncertain-Kemeny is the population version of that underlying optimization problem. Replacing the finite sum of voter probabilities by the mass-weighted sum over types gives precisely the continuous objective above; dividing the original objective by population size does not change its minimizers. The expected direction is hardness transfers (Class B). Given any explicit discrete Kemeny profile, make each distinct ranking a deterministic uncertainty type and assign it mass equal to its number of voters divided by the electorate size. Then \(H_\mu\) is the discrete Kemeny objective scaled by the electorate size, so both problems have the same optimal rankings. The continuous problem therefore retains the paper’s FAST hardness.
The regime is large digital preference-elicitation platforms or broad policy surveys: many participants receive the same information and use the same uncertainty profile, while the number of distinct profiles \(\tau\) is much smaller than the headcount. For example, tens of thousands of participants might fall into a few hundred information or response cohorts. A type records everything this problem uses about its members: their pairwise likelihoods over alternatives. This is a cohort regime, not a claim that every voting setting has few types.
A useful secondary anchor is Theorem 2, proved in the paper using the cited FAST PTAS of Kenyon-Mathieu and Schudy (2007) and the paper’s Lemma 1. It says that a \((1+\epsilon)\)-approximate ranking can be obtained with probability at least \(1-\delta\) in either of two ways: sample \(O(m^4\log(m/\delta)/\epsilon^2)\) random voters per pair and run the FAST PTAS, giving polynomial time in \(m\) for fixed \(\epsilon\); or sample \(O(\log(m/\delta)/\epsilon^2)\) per pair and run an exact FAST solver on the estimated tournament, assuming \(\epsilon<1/3\), with no polynomial-time guarantee.
Its continuous counterpart is Sampled Continuous Uncertain-Kemeny: the population is a distribution \(\mu\) over uncertainty types, and for a queried pair \((a,b)\), an oracle samples a person according to \(\mu\) and returns that person’s \(q_t(a,b)\). Given \(A,\epsilon,\delta\) and this sampling access, output a ranking \(\hat\sigma\) such that \(H_\mu(\hat\sigma)\le(1+\epsilon)\min_\sigma H_\mu(\sigma)\) with probability at least \(1-\delta\). The expected direction is tractable for fixed accuracy, using the PTAS-based method; the lower-sample method retains the paper’s exact-solver caveat. This is a sampling-access variant of the population problem, not a claim that uncertainty or sampling replaces continuization.
The mirror’s scope is the paper’s expected-Kendall objective and the computation and approximation of its minimizing social ranking. It does not continuize rankings or alternatives. Its plausibility rests on the same linear aggregation of pairwise probabilities that drives Theorem 1; the authors should recognize the mass-weighted version as their objective over a high-multiplicity population. The exact discrete embedding also makes this a meaningful compressed-input regime: binary rational masses can represent multiplicities whose explicit electorate would be much larger than the mass-support description.
The weakest point is the homogeneity requirement. Real platform participants may have sufficiently idiosyncratic uncertainty profiles that \(\tau\) approaches the population size. The mirror is strongest where repeated information contexts or elicitation patterns create genuine cohorts; outside those settings it is less compelling. Further questions include how exact complexity depends on \(m,\tau\), and input bit length, and when a known mass distribution permits better approximation than the sample-oracle bounds.
The strongest case against this mirror is that, for this objective, the population disappears under an exact sufficient statistic. If type \(t\) has uncertain-ranking distribution \(D_t\), define the mixture \(\bar D=\sum_t\mu_tD_t\). Then, for every social ranking \(\sigma\),
\[ \sum_t\mu_t\,\mathbb E_{\rho\sim D_t}[d_{\mathrm{KT}}(\sigma,\rho)] =\mathbb E_{\rho\sim\bar D}[d_{\mathrm{KT}}(\sigma,\rho)]. \]
The same collapse holds for the paper’s alternative objective: it depends on the aggregate pairwise weights, not on which types supplied them. This is not an objection that the answer stays the same. It is a concern that there is no population-level computational structure left to study: all type differences, multiplicity, and support size can be replaced by one mixture distribution, or directly by its pairwise marginals. Theorem 1 already identifies those marginals as the complete input to the optimization. Given a continuous instance, one sums the type-weighted marginals and runs the same weighted FAST problem.
That leaves Theorem 1 as a formally valid mirror, but a thin one. A population of many cohorts is plausible, and the discrete-to-continuous dictionary is clean. Yet the theorem’s computational content is already entirely about the aggregate tournament; the masses merely give another way to supply its weights. A richer question about the composition of cohorts would need type-specific constraints or a type-sensitive objective. Those may be worthwhile models, but they no longer mirror the paper’s expected-sum objective.
Theorem 2 has an even narrower opening. Its sampling bounds already do not depend on the number of voters \(n\). Replacing a random draw from a finite electorate with a draw from a probability distribution over types yields the same concentration problem and the same FAST methods. That makes the proposed continuous sampling version coherent, but it adds no population-dependent computational question: the population has again entered only through estimates of aggregate pairwise weights.
This is the best negative case I can make, and it does not establish the requested universal claim. The objections concern how little of the population survives in this particular model, not whether a continuous mirror is sensible. A mass distribution over uncertainty profiles is an admissible high-multiplicity regime, and the authors could reasonably regard its mass-weighted objective as theirs. Under ChoCo’s gate, both anchors therefore remain viable; the case against is weak.
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.