| paper | d4-conf-aaai-2016-0692 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: NP-hard, even for dyadic masses; polynomial-time solvability in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
Given alternatives \(C\) and a support list of complete rankings \((\sigma^r,\mu_r)_{r=1}^{\tau}\), where each \(\mu_r>0\) is a binary rational and \(\sum_r \mu_r=1\), find a permutation \(\pi\) minimizing \(\sum_{r=1}^{\tau}\mu_r d_{\mathrm{AP}}(\pi,\sigma^r)\), with \(d_{\mathrm{AP}}\) exactly as defined in the paper.
Each complete ranking is a voter type, \(\mu_r\) is its population share, and the decision variable is the consensus ranking \(\pi\). Minimize the population-weighted AP disagreement \(\sum_r\mu_r d_{\mathrm{AP}}(\pi,\sigma^r)\), equivalently maximize the mass-weighted MAP log-likelihood for fixed \(\beta>0\).
Covers Theorem 1’s AP maximum-likelihood center optimization; it leaves the paper’s sampling guarantees, reconstruction algorithms, and experiments outside the mirror.
My strongest case is a direct high-multiplicity version of the paper’s AP maximum-likelihood center problem. It treats each complete ranking as a voter type and replaces the count of voters with that type by its population fraction. The paper’s AP distance already defines the aggregation objective, so this does not simplify away the question the authors study.
The anchor is Theorem 1: for an arbitrary multiset \(P\) of permutations and \(\beta>0\), finding the center permutation \(\pi_{\mathrm{AP}}\) that maximizes \(\prod_{\sigma\in P}\Pr_{\mathrm{MAP}(\beta,\pi)}(\sigma)\) is NP-hard. The paper states this as its own theorem and says the proof is in the extended version; it derives the result by reduction from the previously established NP-hard Kendall-ML problem. Since the model’s normalization is independent of the center, this is equivalently the problem of minimizing the average AP distance to the observed rankings.
Call the mirror AP-Center\(_\infty\). Its instance is a set \(C\) of \(n\) alternatives and a support list \((\sigma^1,\mu_1),\ldots,(\sigma^\tau,\mu_\tau)\), where each \(\sigma^r\) is a complete ranking of \(C\), each \(\mu_r\) is a positive binary rational, and \(\sum_r\mu_r=1\). The question is to find a permutation \(\pi\) minimizing
\[ F_\mu(\pi)=\sum_{r=1}^{\tau}\mu_r\,d_{\mathrm{AP}}(\pi,\sigma^r), \]
where \(d_{\mathrm{AP}}\) is exactly the paper’s AP distance. Any global minimizer is a solution. Equivalently, it maximizes the mass-weighted MAP log-likelihood for any fixed \(\beta>0\). The instance size is measured by \(n,\tau\), and the bit length \(L\) of the masses and rankings.
A plausible regime is a very large public consultation or consumer panel ranking the same slate of proposals or products. Each person’s type is their complete ranking; people with identical rankings are indistinguishable for this aggregation problem. For a compact slate, the possible type space is finite, and a large panel can have \(N\gg\tau\): millions of responses grouped into a much smaller set of ranking types. The output is naturally interpreted as a population-level central ranking, while the masses are percentages rather than individual names. As the number of alternatives varies across the complexity family, \(\tau\) remains the number of represented types, not the full \(n!\) universe.
I expect hardness to transfer. Given a discrete instance with \(N\) rankings, set \(\mu_\sigma\) to the count of \(\sigma\) divided by \(N\); then \(F_\mu\) is the discrete average AP distance scaled by \(1/N\). This is a polynomial-size mapping, so Theorem 1’s hardness applies to the continuous problem. That establishes hardness on a discrete subfamily; it does not claim that every rational-mass instance can be expanded into a polynomial-size multiset. The mirror therefore gives a meaningful Class B question, even though it predicts no tractability gain. Further questions include whether AP-Center\(_\infty\) admits useful approximation guarantees, or fixed-parameter algorithms in support size \(\tau\).
The scope is deliberately narrow: it mirrors the AP-ML center-optimization result, not the paper’s sample-complexity theorems, probabilistic reconstruction guarantees, or clustering and classification experiments. The authors should recognize the objective: the mirror asks for the same AP central permutation they define, with fractional type frequencies replacing integer counts. The point is the population interpretation, not a claim that their paper already studies continuous voters.
The soft spot is that the paper frames the center as a hidden ground-truth ranking learned from samples, whereas this mirror treats the same center as an aggregate choice for a population. Some authors may regard AP as an information-retrieval statistic rather than a social-choice objective. Still, the formal optimization problem is unchanged, and ranking a common slate for a large panel is a plausible setting in which an AP-weighted central ranking is the collective decision.
The strongest negative case is semantic: the paper studies rankings as noisy observations of a hidden center, whereas a society consists of people expressing preferences. An AP maximum-likelihood center is not automatically a collective choice rule, and AP’s position-sensitive distance is not a voter’s utility. A consultation panel’s rankings, for example, might be evidence about a latent “correct” order rather than preferences to aggregate.
That objection does not defeat the better mirror. The paper itself connects ranking models to voter preferences and rank aggregation. A panel choosing an order for proposals or products could reasonably want a consensus ranking that penalizes disagreement near the top more heavily. Each person’s complete ranking is a type; repeated rankings can have large population mass. The authors’ exact objective then gives the proposed collective rule, without changing its AP weighting.
For support rankings \(\sigma^1,\ldots,\sigma^\tau\) with masses \(\mu_r\), the objective is
\[
F_\mu(\pi)=\sum_{r=1}^{\tau}\mu_r d_{\mathrm{AP}}(\pi,\sigma^r).
\]
If the rankings came from a finite sample of size \(N\), with \(a_r\) occurrences of type \(r\), then \(\mu_r=a_r/N\), and \(F_\mu\) is exactly the sample’s average AP distance. The log-likelihood differs from \(-\beta N F_\mu(\pi)\) only by a term independent of \(\pi\). Thus Theorem 1’s NP-hard center problem supplies a direct computational anchor; on its explicit sample instances, converting counts to rational masses is polynomial-size.
One can argue that this is less compelling than the paper’s statistical reconstruction setting, or that it mostly changes how the same ranking data are represented. But neither point defeats the mirror: the population interpretation is plausible, and the programme explicitly treats continuous-population complexity questions as worthwhile even when hardness carries over. I cannot make an honest case that this anchor fails. The negative case is weak here, and the proponent’s mirror survives.
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.