| paper | Aggregation over Metric Spaces: Proposing and Voting in Elections, Budgeting, and Legislation |
| authors | L. Bulteau, Gal Shahaf, E. Shapiro, Nimrod Talmon |
| venue | JAIR 2021 |
| filed under | voting · distortion |
| judged by | gpt-5.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: \(\mathrm{NP}\text{-complete}\), even for \(\tau\leq 4\) with masses that are integer multiples of \(\frac14\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Observation 4
statement extracted from the paper’s text layer
Given \(m\) alternatives and an explicitly listed finite-support rational distribution \(\mu\) over complete rankings \(\pi\in S_m\), output an integral ranking \(\rho\in S_m\) minimizing \(F_\mu(\rho)=\sum_{\pi\in S_m}\mu_\pi d_{\mathrm{KT}}(\pi,\rho)\); equivalently, decide whether \(\min_{\rho\in S_m}F_\mu(\rho)\le B\).
Voter types are complete rankings \(\pi\in S_A\), with mass \(\mu_\pi\); the decision variable is one integral ranking \(\rho\), and the objective is its expected Kendall–Tau distance from the population.
The distribution collapses to pairwise weighted-tournament data, so the continuum adds little population-level structure and may yield only a normalized weighted-Kemeny restatement.
fatal: False
The mirror covers Observation 4's \(L_1\)-Kemeny NP-hardness. It leaves the paper's other \(L_p\), Condorcet, one-dimensional, budgeting, committee, and legislation results without a separately specified continuous analysis.
My lead mirror is a high-multiplicity version of the paper’s social-welfare aggregation problem.
The anchor is Observation 4, proved in the paper. It states that, for social welfare functions whose voters submit linear orders and whose distance is adjacent-swap distance, the paper’s \(L_1\) aggregation point is exactly a Kemeny ranking, and therefore computing an \(L_1\) aggregation point is NP-hard. The proof given is the identification of the objective: minimizing \(\sum_i d(\pi_i,\rho)\) is precisely Kemeny aggregation. The underlying NP-hardness of Kemeny is standard prior hardness, but the equivalence to the paper’s \(L_1\) rule is established here.
I would call the continuous problem Continuous Kemeny Aggregation over a Population Distribution. An instance consists of a finite alternative set \(A\), with \(|A|=m\), and a rational distribution \(\mu\) over complete rankings \(T=S_A\). A type is therefore one complete ranking \(\pi\); two voters of the same type are indistinguishable because the paper’s problem uses no information beyond that ranking. The mass \(\mu_\pi\) is the fraction of the population holding ranking \(\pi\). The decision variable is still one integral ranking \(\rho\in S_A\), not a fractional or random ranking. The objective is
\[ F_\mu(\rho)=\sum_{\pi\in S_A}\mu_\pi d_{\mathrm{KT}}(\pi,\rho), \]
where \(d_{\mathrm{KT}}\) is the minimum number of adjacent swaps needed to transform \(\pi\) into \(\rho\). The task is to output a ranking minimizing \(F_\mu\); equivalently, given a rational threshold \(B\), decide whether some ranking has \(F_\mu(\rho)\le B\). Ties may be returned as co-winners.
This is a genuine population continuization. The metric space of possible outcomes remains the paper’s discrete space of rankings. What becomes continuous is only the electorate: the finite sum over named voters becomes an expectation over voter types.
The natural regime is a large membership-based consultation, party, union, or civic platform asking millions of members to rank the same fixed shortlist of policy proposals, budget priorities, or legislative drafts. The agenda has fixed or moderate size \(m\), while the population is much larger than the number of observed ranking types. For example, a stable eight-item agenda has at most \(8!\) possible complete rankings, while a very large membership may contain many repeated rankings and therefore \(n\gg |\operatorname{supp}(\mu)|\). The type is not merely a preference label: in this problem the ranking is the complete description of everything used by the aggregation rule.
The authors should recognize this immediately as their own problem. Nothing essential has been simplified: the same alternatives, same ranking space, same adjacent-swap metric, same \(L_1\) objective, and same integral output are retained. Only the finite electorate is represented by its empirical distribution.
The expected complexity classification is Class B: hardness transfers. Given any finite Kemeny instance with rankings \(\pi_1,\ldots,\pi_n\), define
\[ \mu_\pi=\frac{|\{i:\pi_i=\pi\}|}{n}. \]
Then, for every output ranking \(\rho\),
\[ F_\mu(\rho) =\sum_{\pi}\mu_\pi d_{\mathrm{KT}}(\pi,\rho) =\frac{1}{n}\sum_{i=1}^{n}d_{\mathrm{KT}}(\pi_i,\rho). \]
Thus the continuous and discrete optimizers are identical. Constructing the distribution by counting duplicate rankings is polynomial, so a polynomial algorithm for the continuous problem would yield a polynomial algorithm for the NP-hard problem in Observation 4. The hardness is therefore not caused by population multiplicity; it lives in the combinatorics of ordering the alternatives. This is exactly the kind of hardness the programme predicts should survive continuization.
The reverse dictionary also holds for rational masses: if the masses have common denominator \(N\), the distribution corresponds to a discrete electorate containing \(N\mu_\pi\) copies of each type. With binary-encoded denominators that expansion may be exponentially larger than the compact distribution, which is an important high-multiplicity encoding issue rather than a defect in the model.
The mirror generates several further questions: whether the weighted problem is fixed-parameter tractable in \(m\) or in the number of supported ranking types; whether approximation guarantees can depend on the support size rather than the population size; whether implicitly represented distributions admit useful separation or sampling algorithms; and how the complexity changes when the population distribution is uncertain or given by a succinct generative model.
My weakest point is that this mirror is unlikely to produce a new tractability phenomenon. It is essentially weighted Kemeny aggregation, and the exact finite-to-distribution identity is immediate. Moreover, exact repeated rankings are a stylized assumption in some real electorates, and the regime is less persuasive when almost every voter has a distinct ranking. Still, that weakness concerns novelty and empirical realism, not whether the question is the continuous analogue of the paper’s problem. Under the programme’s standards, this is a clean, author-recognizable population mirror whose correct result is precisely that Kemeny hardness survives.
The strongest negative case is that the proposed mirror adds almost no population-level structure to the paper’s problem. For a distribution \(\mu\) over rankings, the objective \(F_\mu(\rho)=\sum_{\pi}\mu_\pi d_{\mathrm{KT}}(\pi,\rho)\) depends only on the pairwise marginals \(q_{ab}=\Pr_{\pi\sim\mu}[a\succ_\pi b]\). Indeed, for every pair \(\{a,b\}\), the contribution is \(1-q_{ab}\) if \(\rho\) puts \(a\) before \(b\), and \(q_{ab}\) otherwise. Thus the entire population distribution collapses to a weighted tournament.
That makes the proposed “continuous” instance merely a weighted Kemeny profile in different notation. With rational masses, it is exactly a finite electorate after multiplying by a common denominator; with sparse support, it is simply a list of distinct rankings with multiplicities; with explicit dense support, the input already has \(m!\) coordinates. A succinct representation would make the complexity depend on the chosen representation of the distribution rather than on any canonical continuous-population phenomenon. The paper’s aggregation rule does not use identities, higher-order correlations between voter types, or any mass-level operation. The continuum contributes normalization and compression, but no new object for this rule to compute over.
One could try to rescue the mirror by adding continuous Kemeny bribery or winner robustness: transfer mass between rankings until a target ranking becomes optimal. That would yield linear inequalities over the post-intervention distribution, with separation governed by Kemeny optimization. But this is no longer the computational result proved in Observation 4; it adds an intervention problem absent from the paper. It may be a good ChoCo problem, but it cannot support the claim that this paper itself supplies a worthwhile continuous mirror without importing a new research agenda.
That is the best negative argument, but it does not defeat the anchor under the programme’s rules. Observation 4 is an explicit computational result. A complete ranking is a legitimate voter type, repeated rankings have a natural high-multiplicity interpretation, the objective is independent of individual identity, and the continuum does not degenerate. The rational-profile identity is precisely the kind of discrete-to-continuous relationship the programme asks analysts to chart; it is not a novelty collision merely because weighted Kemeny or high-multiplicity elections may already be known. Nor may one object that the answer is unchanged or that hardness comes from the alternatives.
So the honest assessment is that the negative case is weak. I would not claim that this paper has no worthwhile continuous mirror: the proponent’s Observation 4 anchor 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.