Rank Aggregation Using Scoring Rules

The strongest honest case is a high-multiplicity mirror of the paper’s tie-breaking problem for Baldwin, with Theorem 6.8 as the lead. This is a Class B mirror: continuity does not dissolve the hardness, because the difficult combinatorics live in the candidate set rather than in the number of voters.

Take candidates \(C\), and let a voter type be a complete ranking \(t\in L(C)\). A society is a rational distribution \(\mu\) over these rankings; \(\mu_t\) is the fraction of the population of type \(t\). For any surviving candidate set \(R\subseteq C\), define the weighted Borda score

\[ B_\mu^R(c)=\sum_t \mu_t\bigl(|R|-\operatorname{pos}(t|_R,c)+1\bigr). \]

A Baldwin elimination step removes any candidate of minimum \(B_\mu^R\), with all tied choices permitted. The removed candidate is placed at the bottom of the eventual ranking. Thus the action variable is an elimination sequence, and the objective is the position that sequence can give a designated candidate.

The high-multiplicity regime is quite plausible: imagine eight large constituencies—say, institutional stakeholders, customer segments, or search-provider blocs—where every member of a constituency has the same ranking of the candidates. There may be millions of agents but only eight ranking types. More generally, any rational \(\mu\) can be realised by taking a sufficiently large finite population with \(N\mu_t\) members of type \(t\). Replicating the entire population scales every score by the same factor and therefore preserves every tie and every possible elimination sequence.

My lead problem is Continuous Baldwin Winner Determination:

Given \(C\), a rational distribution \(\mu\) over rankings, and a designated candidate \(d\), does there exist a Baldwin elimination sequence under the weighted scores above in which \(d\) is the last remaining candidate?

This is the direct population-continuous version of the paper’s WINNER DETERMINATION problem for Seq.-Borda-Loser. The relevant anchor is Theorem 6.8, proved in this paper. It states that WINNER DETERMINATION for Sequential-Borda-Loser is NP-complete even when the number of voters is fixed at \(n=8\), and gives the ETH lower bound \(2^{o(m)}\operatorname{poly}(m)\).

The reduction transfers exactly. Given an eight-voter profile \(P\), set \(\mu_t\) to the fraction of those eight voters having ranking \(t\). On every residual candidate set \(R\), the continuous Borda score is the discrete score divided by eight. Consequently, the tied minimum-score candidates are identical at every round, and the discrete and continuous elimination sequences coincide. The continuous problem is therefore NP-hard even with support size at most eight and masses with denominator eight. Membership in NP follows because an elimination sequence of length \(m-1\) is a certificate whose weighted score comparisons can be checked exactly.

This is especially good evidence for a mirror because the theorem itself rules out the objection that the hardness is caused by a huge number of individually specified voters. Eight ranking types can represent arbitrarily large constituencies, while the hardness remains. The result belongs to the programme’s Class B: the reduction’s combinatorics live in the alternatives and their rankings, so high multiplicity does not remove them.

A second, weaker but genuinely distinct mirror comes from Theorem 6.1, proved here. Define Continuous Sequential Position-\(k\) Determination as follows:

Given a rational society \(\mu\), a scoring system \(s\), a candidate \(d\), and \(k\), is there a valid weighted Sequential-\(s\)-Winner or Sequential-\(s\)-Loser elimination sequence whose output ranking places \(d\) in position \(k\)?

The paper’s subset dynamic program extends verbatim: replace each integer voter-score sum by a rational weighted sum over types. Reachable elimination sets are computed by dynamic programming over subsets of candidates. This gives the same \(2^m\)-state algorithm, with running time polynomial in the explicit support size \(\tau\) and encoding length \(L\), and the paper’s one-sided \(m^k\) or \(m^{m-k}\) refinements. Thus the continuous problem is fixed-parameter tractable in \(m\), for every scoring system covered by the theorem. This is a Class A parameterized mirror, although the extension is technically routine rather than a new continuous phenomenon.

The paper’s authors should recognise both questions as their own problems with the voter list replaced by its empirical distribution. The ranking output remains discrete; only the population becomes continuous. The sequential rule, its tie semantics, and the position objective are unchanged. The Mallows and Euclidean experiments in the paper are not themselves prior continuous computational work—they are distributional profile-generation models—but they make the distributional interpretation of rankings familiar.

The scope is deliberately narrow: these mirrors cover Theorem 6.8 and Theorem 6.1. I would not claim a mirror for the paper’s axiomatic results or simulations, since those do not state computational problems over a continuous population.

The weakest point is that the lead construction can look like an eight-voter profile with the voters merely renamed “large blocs.” It does not yield a new polynomial-time algorithm; it shows that the continuous version preserves hardness. If a continuous mirror is required to make the problem easier, this case is weak. Under ChoCo’s trichotomy, however, that is precisely a legitimate outcome: a natural high-multiplicity formulation exists, and Theorem 6.8 shows that this problem is one where continuization stops helping.