| paper | Optimizing Positional Scoring Rules for Rank Aggregation |
| authors | I. Caragiannis, Xenophon Chatzigeorgiou, George A. Krimpas, A. Voudouris |
| venue | AAAI 2017 |
| filed under | voting · theory |
| 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: For every fixed \(\eta\in(0,1/24]\), achieving a \((23/24+\eta)\)-approximation is \(\mathrm{NP}\text{-hard}\), even with dyadic support masses. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 7
Given a finite alternative set \(A\), ranking length \(d\), weighted ordered-pair constraints \(C\), and a rational finite-support distribution \(\mu\) over types \(\theta=(B,\pi)\) with \(B\subseteq A\), \(|B|=d\), output a monotone scoring vector \(s\) maximizing \(G_\mu(s)=\sum_{(x,y)\in C}w(x,y)\mathbf{1}\{\Delta^\mu(x,y)\cdot s>0\}\); determine the complexity of guaranteeing \(G_\mu(s)\ge(23/24+\eta)\operatorname{OPT}_\mu\).
The types are \(\theta=(B,\pi)\), with mass \(\mu_\theta\); each type contributes its integral local ranking, while the aggregate position counts are fractional masses. The decision variable is the monotone scoring vector \(s\), and the objective is the total weight of satisfied ground-truth pairwise constraints.
The mirror covers Theorem 7 and Theorem 1, hence Corollary 2; it leaves the approximation results in Theorems 4 and 6, experiments, and noise-model extensions unmirrored.
The strongest positive case is a high-multiplicity version of the paper’s own crowdsourcing problem. The continuous object is the population of workers, not the scoring vector, alternatives, or outcome ranking.
Let \(A\) be the alternatives and let every worker rank exactly \(d\) alternatives. A type is a pair \(\theta=(B,\pi)\), where \(B\subseteq A\), \(|B|=d\), and \(\pi\) is a complete ranking of \(B\). Thus two workers have the same type precisely when they receive the same \(d\)-alternative task and submit the same ranking. A continuous society is a rational distribution \(\mu\) over these types. Its mass \(\mu_\theta\) is the fraction of all submitted rankings of type \(\theta\).
Define \(r^\mu_j(x)\) as the mass of workers placing \(x\) in position \(j\), and define \(\Delta^\mu_j(x,y)=r^\mu_j(x)-r^\mu_j(y)\). For a scoring vector \(s=(s_1,\ldots,s_d)\), with \(s_1\ge\cdots\ge s_d\ge0\), alternative \(x\) receives aggregate score \(\sum_j r^\mu_j(x)s_j\). Given weighted partial-ground-truth constraints \(C\), the gain of \(s\) is \(G_\mu(s)=\sum_{(x,y)\in C}w(x,y)\,1\{\sum_j\Delta^\mu_j(x,y)s_j>0\}\). The decision variable is the scoring rule \(s\); the solution is a scoring vector maximizing \(G_\mu(s)\).
This is a genuine population continuization. Each worker still submits an integral local ranking, and the final output is still an ordinary ranking of alternatives. Only the empirical worker population becomes a mass distribution. A natural regime is a large rating or peer-grading platform repeatedly using a finite template of local tasks. If there are \(q\) recurring \(d\)-alternative tasks, then at most \(q d!\) local ranking types are possible, while the number of workers can be millions. Thus \(N\gg\tau\), where \(\tau\) is the number of positive-mass types. The paper’s different-task setting is preserved because the task subset \(B\) is part of the type.
My lead anchor is Theorem 7, proved in this paper. It states that, for every constant \(\eta\in(0,1/24]\), \({\sf OptPSR}\) is NP-hard to approximate within \(23/24+\eta\). Equivalently, unless \(\mathrm{P}=\mathrm{NP}\), no polynomial-time algorithm can always find a scoring vector whose satisfied-constraint weight is at least a \((23/24+\eta)\)-fraction of optimum. The proof is an approximation-preserving reduction from MAX-3LIN-2: the scoring gaps \(a_i=s_i-s_{i+1}\) encode binary variables, and carefully weighted pairwise-ranking constraints encode both variable consistency and equation satisfaction.
The corresponding continuous problem is:
Continuous OptPSR Approximation. Given \(A\), \(d\), a rational finite-support distribution \(\mu\) over incomplete-ranking types \((B,\pi)\), a weighted constraint set \(C\), and \(\eta\in(0,1/24]\), output a valid scoring vector \(s\) maximizing \(G_\mu(s)\), or, in the approximation version, output \(s\) with \(G_\mu(s)\ge(23/24+\eta)\operatorname{OPT}_\mu\).
This is expected to be Class B: hardness transfers. Take any discrete profile \(\Pi\) from the paper and let \(\mu_\theta=n_\theta/N\), where \(n_\theta\) is the number of agents of type \(\theta\). Then \(\Delta^\mu_j(x,y)=\delta_j(x,y,\Pi)/N\). Every strict inequality has exactly the same truth value, so every scoring vector obtains exactly the same gain in the continuous and discrete instances. The reduction in Theorem 7 therefore becomes a rational-mass reduction with polynomial encoding length. If one wants an explicitly huge society, simply replicate every worker type an arbitrary number of times; \(\mu\) and the optimization problem do not change.
This is a particularly good transfer because the reduction’s combinatorics live in the score positions, score gaps, and constraint system—not in the identities of individual workers. Continuization removes irrelevant multiplicity while preserving the source of hardness. The resulting questions are whether the hardness remains under fixed task templates, bounded support, or particular parametric distributions such as mixtures of Plackett–Luce types, and whether the approximation threshold changes under those restrictions.
A second, independent anchor is Theorem 1, also proved in this paper. It states that the algorithm Regions solves \({\sf OptPSR}\) exactly in time \(\mathcal{O}(|C|^d\operatorname{poly}(|C|,d))\). Consequently, Corollary 2 states that \({\sf OptPSR}\) is polynomial-time solvable when \(d\) is constant. The algorithm partitions the monotone scoring-vector cone according to the signs of the linear forms \(\boldsymbol{\delta}(x,y,\Pi)\cdot s\), checks the resulting regions by linear programming, and returns a region of maximum total weight.
The corresponding problem is:
Continuous OptPSR Exact-\(d\). Given \(A\), a rational distribution \(\mu\) over incomplete-ranking types, and weighted constraints \(C\), compute a scoring vector \(s\) maximizing \(G_\mu(s)\), with \(d\) treated as a parameter.
This is expected to be Class A for fixed \(d\). After one linear pass over the support of \(\mu\), the paper’s Regions algorithm applies unchanged with \(\Delta^\mu\) in place of \(\delta(\Pi)\). The sign-pattern bound and all feasibility LPs remain valid for rational fractional coefficients. Thus the running time is polynomial in the input size for constant \(d\), with the same exponential dependence on \(d\) as in Theorem 1.
The authors should recognise both mirrors as their problem. Their objective is unchanged: choose the positional scoring rule whose aggregate ranking best agrees with known pieces of a true ranking. Their own representation by the quantities \(\boldsymbol{\delta}(\Pi)\) already makes the population histogram the mathematically relevant object. The continuous version merely replaces integer rank-position counts by their normalized mass counterparts. It also fits their motivating applications better than a named-individual model: a large platform naturally cares about \(23\%\) of workers producing one local ranking, not about the identities of those workers.
The scope is deliberately limited. I am mirroring Theorem 7 and Theorem 1, not the experimental claims, the Bradley–Terry and Plackett–Luce simulations, or every approximation result in Sections 4–5. Those could support further mirrors, but these two anchors already give a coherent boundary: the same continuous-population problem is exactly tractable for fixed \(d\), yet remains hard in the unrestricted regime.
The weakest point is that this paper’s mirror is close to a normalized high-multiplicity reformulation. Since the paper already compresses a profile to rank-position differences, continuity does not create a dramatic new algorithmic phenomenon here. Moreover, the paper’s actual experiments involve only \(392\) workers, so they are not themselves strong evidence of \(N\gg\tau\). The positive case therefore should not claim that continuization dissolves the paper’s hardness. Its defensible claim is narrower: repeated crowdsourcing populations make the mass model natural, the exact and approximation questions remain computationally meaningful, and the paper supplies named results whose algorithmic and hardness behavior survives in that continuous-population setting.
The negative case has one serious argument, and it applies to both anchors: the paper has already quotiented out individual workers. Its formal input is not really a list of agents. After defining the counts \(\nu_j(x,\Pi)\), the authors explicitly replace the profile by the vectors \(\boldsymbol{\delta}(x,y,\Pi)\), and every theorem depends only on those vectors.
For a finite profile with \(N\) workers, let \(\mu\) assign mass \(n_\theta/N\) to each type \(\theta=(B,\pi)\). Then
\[ \Delta^\mu_j(x,y)=\frac{\delta_j(x,y,\Pi)}{N}. \]
Consequently, for every scoring vector \(s\),
\[ \Delta^\mu(x,y)\cdot s>0 \quad\Longleftrightarrow\quad \delta(x,y,\Pi)\cdot s>0. \]
Thus \(G_\mu(s)=G_\Pi(s)\) for every \(s\), and the two instances have exactly the same optimum, optimal scoring vectors, and approximation behaviour. Conversely, every rational distribution over ranking types can be expanded into a finite profile by clearing denominators. This is not merely a high-multiplicity approximation or a limit theorem; it is an exact change of coordinates.
That defeats the proposed Theorem 7 mirror as a worthwhile continuization. The reduction’s large numbers of agents are only a way of implementing coefficients in linear inequalities. Dividing all those counts by the population size changes nothing. Replicating every type a million times creates the advertised regime \(N\gg\tau\), but it creates no new instance for the problem: the paper’s objective cannot distinguish the original profile from its replication. The hardness therefore transfers, but only as a tautological invariance under positive scaling. It does not reveal whether population multiplicity dissolves or creates computational difficulty.
Theorem 1 has the same problem. Regions does not optimize over a population, nor over mass transfers between types. It optimizes over the already-continuous scoring vector \(s\). Replacing \(\delta\) by \(\Delta^\mu\) leaves every separating hyperplane
\[ \delta(x,y,\Pi)\cdot s=0 \]
unchanged. The sign-pattern arrangement, feasibility LPs, and running time are literally the same. The resulting “continuous” theorem is therefore not a new continuous-optimization result: it is Theorem 1 applied after normalizing its integer coefficients.
The proposed crowdsourcing scenario does make repeated worker types plausible, and that point should not be denied. Nor is worker identity an objection: the paper itself declares identity irrelevant. But precisely because identity is irrelevant, refining the type to include worker names, latent competence, or reliability cannot strengthen this mirror while preserving the paper’s problem. Those attributes disappear from the objective. If they are made relevant—for example through expected performance, worker-specific noise, adaptive task assignment, or incentives—the resulting problem is a new statistical or mechanism-design problem, not a continuous mirror of Theorems 1 or 7.
Likewise, using a succinct Plackett–Luce or Bradley–Terry law could create computational work in evaluating the induced aggregate quantities. But then the new difficulty lies in representing or integrating the distribution, not in continuizing the population; once the quantities \(\Delta^\mu_j(x,y)\) are available, the original OptPSR problem returns unchanged. Taking expected gain rather than gain on the aggregate profile changes the objective again.
So the strongest negative conclusion is that every faithful version of these two anchors collapses to the paper’s existing count-vector formulation, while every version with genuinely new continuous-population content changes the computational problem. This is a genuine collision, not the mistaken claim that “continuity does not help.” The algorithms and hardness results may survive, but their survival is exactly why there is no distinct continuous mirror worth adding.
The negative case is not airtight against a broad convention that regards any normalized profile as sufficient evidence for ChoCo. Under that convention, the proponent’s mirror is valid. But under the programme’s stronger standard—a continuous population should introduce a meaningful mass-based computational object—this paper offers no such object.
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.