Error in the Euclidean Preference Model

The paper's numbered results concern representability, probability, counting, and approximation-error bounds, not the complexity of a computational problem. Peters' \(\mathrm{NP}\)-hardness result is only cited from another paper, so the mandatory computational bit fails. A plausible high-multiplicity Euclidean-unfolding extension exists, but it cannot repair the absence of a qualifying anchor.

The objection that survived

Theorem 4 deliberately uses \(I^\ast\) distinct preferences and a uniform held-out query, whereas the proposed mirror adds population-weighted fitting; this limits directness but does not make the continuous question incoherent.

What the mirror covers

The proposed mirror covers the paper's representability threshold, capacity bound, and held-out Kendall–tau error questions in Theorem 1, Lemma 1, and Theorem 4, with possible pathology extensions from Theorems 2–3. It does not cover a computational result proved by this paper, because none is stated.

Open questions for a prover

The case FOR (proponent)

There is one important qualification. Strictly speaking, this paper contains no numbered theorem or lemma asserting that a computational problem is NP-hard, in P, W[1]-hard, or FPT. The NP-hardness statement is only cited from Peters (2017) in the related-work discussion. I would not misrepresent Theorem 4 as a complexity theorem. Under a literal reading of the anchoring rule, this paper has no qualifying computational anchor.

Under the broader reading that permits named exact quantitative results to anchor computational continuizations, there is nevertheless a strong positive case. My lead is Theorem 4.

The natural regime is a large electorate facing a fixed slate of \(A\) candidates, as in a national election or repeated public-choice setting. A type is a complete ranking \(t\in\mathcal R_A\), where \(|\mathcal R_A|=A!\). The mass \(\mu_t\) is the fraction of voters with ranking \(t\). Thus a finite profile with \(n_t\) voters of type \(t\) becomes \(\mu_t=n_t/N\), and \(N\) can be very large while the number of distinct types remains much smaller. This is exactly the kind of national-election setting the paper itself mentions.

For alternative locations \(X=(x_a)_{a\in A}\in(\mathbb R^d)^A\), let \(R_d(X)\) be the set of rankings induced by some ideal point \(w\in\mathbb R^d\). For a type \(t\), define \(\delta_X(t)=\min_{\rho\in R_d(X)}d_K(t,\rho)\), where \(d_K\) is Kendall–tau distance. Then the finite and continuous losses coincide up to normalization: \(\sum_t\mu_t\delta_X(t)=N^{-1}\sum_i\delta_X(\pi_i)\).

The lead problem is Population Euclidean Unfolding with Held-Out Error. An instance consists of \(A,d\), a rational training distribution \(\mu\) over \(\mathcal R_A\), a rational query distribution \(\nu\), and a permitted training loss \(B\). The task is to choose alternative locations \(X\) minimizing \(\sum_t\nu_t\delta_X(t)\), subject to \(\sum_t\mu_t\delta_X(t)\le B\). A solution is \(X\), together with ideal-point witnesses for the nearest represented rankings if an explicit model certificate is required. The paper’s setting is the special case \(\nu_t=1/A!\), with \(B\) equal to the best achievable training loss.

This is a faithful mirror of Theorem 4 (proved in this paper): a fitted Euclidean model is evaluated on a fresh uniformly random preference, and error is Kendall–tau distance to the closest preference representable by the fitted model. If \(|\operatorname{supp}\mu|\ge r_{A,d}\), Theorem 4 supplies the paper’s displayed lower bound involving \(\hat r\) and \(n_{k,A}\), independently of which \(d\)-dimensional model is chosen. The continuous formulation therefore asks a genuine computational question: can one find the best low-dimensional embedding for a high-multiplicity population, and how much held-out ordinal error is unavoidable?

I would expect the exact optimization version to be Class B. The zero-training-loss case contains recognition of \(d\)-Euclidean profiles, which the paper cites as NP-hard from Peters (2017); arbitrary finite profiles embed as rational mass distributions. Whether the weighted held-out optimization introduces a genuinely continuum-specific source of hardness is an additional open question. Theorem 4 itself is a lower-bound theorem, not an algorithm.

A second worthwhile anchor is Lemma 1, proved in this paper. Define the representable population capacity by \(\operatorname{Cap}_d(\mu)=\sup_X\sum_{t:\delta_X(t)=0}\mu_t\). The precise problem is: given \(A,d\), a rational mass vector \(\mu\), and a rational threshold \(q\), decide whether \(\operatorname{Cap}_d(\mu)\ge q\), and if so output \(X\) representing at least \(q\) mass.

This is the weighted high-multiplicity version of the paper’s parameter \(r\), the maximum number of distinct preferences simultaneously representable. For the uniform distribution over all \(A!\) rankings, Lemma 1 gives \(\operatorname{Cap}_d(\mu)=r_{A,d}/A!\le\hat r/A!\). For a genuine electorate, the objective is more meaningful than counting types: representing a type shared by \(40\%\) of voters matters more than representing a type shared by one voter.

The expected complexity is again Class B for exact recognition: the threshold \(q=1\) asks whether every positive-mass type is jointly \(d\)-Euclidean. The cited Peters hardness transfers through \(\mu_t=n_t/N\). This does not claim that every high-multiplicity restriction is hard; bounded-support or structured distributions may admit column-generation, geometric, or fixed-parameter algorithms. It does show that the mirror preserves the paper’s central computational difficulty rather than trivializing it.

The third anchor is Theorem 1, cited from Bogomolnaia and Laslier (2007). Define \(D_\infty(A,q)\) to be the smallest dimension \(d\) such that every society \(\mu\) with at most \(q\) positive-mass ranking types has some \(d\)-dimensional Euclidean representation. A solution is the integer \(D_\infty(A,q)\), and, for a particular \(\mu\), alternative locations and ideal points representing its support.

Theorem 1 gives this worst-case quantity exactly, with the same case distinction as printed in the paper: \(d\) is sufficient precisely when \(d\ge M\), where \(M\) is one of \(\min\{q-1,A-1\}\) or \(\min\{q,A-1\}\). Thus this continuous mirror is Class A for worst-case dimension provisioning: the answer is available in closed form. The instance-specific problem of finding the minimum dimension for a given \(\mu\) is more difficult and is expected to fall into Class B because exact Euclidean recognition embeds into it.

These mirrors cover the paper’s Euclidean-representation and approximation results, especially Theorem 1, Lemma 1, and Theorem 4. Theorem 2 and Theorem 3 suggest further population questions: one can define the maximum mass that can be packed into disjoint circulant pathologies, or the probability that a sample drawn from a continuous type law contains such a pathology. Theorem 2 would make positive pathology mass a certificate of non-representability, while Theorem 3 would provide a uniform-culture lower bound for the sampled version.

The weakest point is that the paper is fundamentally geometric and statistical, not an algorithmic social-choice paper. Its results concern representability, random-profile prevalence, and approximation error rather than bribery, control, winner determination, or an explicit optimization algorithm. The continuous problems above are therefore mirrors of its mathematical questions, not claims that the authors already formulated a continuous computational problem. There is also a real plausibility concern for recommender systems: identical complete rankings may be rare. The national-election interpretation is stronger because the paper itself names that setting and because a fixed candidate slate naturally creates many repeated ranking types.

So the honest positive verdict is conditional: the paper has a convincing population mirror, with Theorem 4 as the strongest anchor, and the mirror preserves both its Euclidean structure and its unavoidable approximation error. But if a named complexity-class result is mandatory, the paper fails that preliminary requirement.

The case AGAINST (opponent, writing after the proponent)

The negative case is decisive under the programme’s stated admission rule: this paper has no qualifying computational anchor. Theorem 1 is a representability threshold, Lemma 1 is a counting upper bound, and Theorems 2–4 are geometric or probabilistic statements. The only complexity claim—Peters’ NP-hardness result—is cited from another paper and is not proved or stated as a named computational result here. The proposed “Population Euclidean Unfolding” is therefore a new problem inspired by the paper, not a continuous mirror of one of its computational results.

Theorem 1 does not rescue the case. \(D_\infty(A,q)\) is just the paper’s finite-profile question with \(I=q\), rewritten using a distribution whose support has size at most \(q\). The masses play no role: Euclidean representability depends only on which rankings have positive mass. A genuinely mass-sensitive version—say, representing at least a specified fraction of voters—would be a new weighted coverage or fitting problem, no longer the theorem being mirrored. Quantifying over every \(\mu\) collapses back to the support-based worst case; fixing \(\mu\) changes the question.

Lemma 1 has the same defect. Its \(r_{A,d}\) counts how many rankings from the uniform universe of \(A!\) permutations can coexist in one Euclidean model. The proposed

\[ \operatorname{Cap}_d(\mu)=\sup_X\sum_{t:\delta_X(t)=0}\mu_t \]

is a reasonable research definition, especially for repeated ranking types, but it is not what Lemma 1 proves. At threshold \(1\), the masses disappear and the question is simply recognition of whether the support of \(\mu\) is \(d\)-Euclidean—the cited Peters problem. At lower thresholds, it becomes a newly invented weighted maximum-representable-subset problem. That might be worth studying independently, but the paper supplies neither its computational formulation nor a result about it.

Theorem 4 is the proponent’s strongest candidate, but it also changes the object materially. The paper fits a model to \(I^\ast\) distinct preferences and then evaluates a fresh preference drawn uniformly from all \(A!\) rankings. Multiplicity is deliberately absent: duplicating a ranking does not change the fitted object or the theorem’s condition \(I^\ast\ge r\). Introducing a population mass \(\mu\), a query distribution \(\nu\), and a training-loss constraint \(B\) creates a weighted multidimensional-unfolding problem that the paper never formulates. If \(\nu\) remains uniform, the query is not really the society’s preference distribution; if \(\nu\) becomes realistic, the paper’s impartial-culture lower bound no longer supports the formulation. The theorem’s lower bound is fundamentally about the capacity of Euclidean geometry over the permutation universe, not about population mass.

The same issue affects the additional references to Theorems 2 and 3. A circulant pathology in a continuous society is either a support condition—positive mass for each required ranking makes the pathology present, regardless of how small those masses are—or it requires a new thresholded notion of pathological mass. Theorem 3 concerns a finite random sample; under an infinite-population interpretation, ordinary occupancy either remains a sampling problem or becomes eventually trivial.

A repeated-ranking national-election regime is certainly plausible, and I would not reject it on the mistaken ground that voters have to be individually named. The honest weakness of the negative case is that this paper could inspire a worthwhile new project on weighted Euclidean unfolding. But that project would be a new population-weighted learning problem, not a continuous computational mirror anchored in this paper. Since none of the paper’s named results establishes the required computational question, no proposed anchor survives the programme’s standard.

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.