Optimizing Positional Scoring Rules for Rank Aggregation (d4-conf-aaai-2017-0886)

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\).

Let \(A\) contain \(m\) alternatives and let \(2\le d\le m\). A type \(\theta=(B,\pi)\) consists of \(B\subseteq A\), \(|B|=d\), and a strict ranking \(\pi\) of \(B\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational, with \(\sum_\theta\mu(\theta)=1\). Here \(\tau\) is the support size, not the number of possible types. Let \(L\) be the total input bit length.
The input also contains \(C\subseteq\{(x,y)\in A^2:x\ne y\}\) with nonnegative binary-rational weights \(w(x,y)\).
Define \(\nu_j^\mu(x)=\sum_{\theta:\pi_\theta(j)=x}\mu(\theta)\) and \(\Delta_j^\mu(x,y)=\nu_j^\mu(x)-\nu_j^\mu(y)\), for \(1\le j\le d\); absent alternatives contribute zero. Scores are not divided by an alternative's appearance mass.
A feasible scoring vector satisfies \(s\in\mathbb R^d\) and \(s_1\ge\cdots\ge s_d\ge0\). Define \(G_\mu(s)=\sum_{(x,y)\in C}w(x,y)\mathbf1\{\Delta^\mu(x,y)\cdot s>0\}\) and \(\operatorname{OPT}_\mu=\max_sG_\mu(s)\). Tied scores do not satisfy a constraint; an algorithm outputs a rational feasible vector.

For each fixed constant \(\eta\in(0,1/24]\), is there an algorithm polynomial in \(m,\tau,d,|C|,L\) that always outputs \(s\) with \(G_\mu(s)\ge(23/24+\eta)\operatorname{OPT}_\mu\), or is achieving this approximation guarantee NP-hard?

For finite agent profiles, achieving \(23/24+\eta\) is NP-hard for every fixed \(\eta\in(0,1/24]\); a polynomial-time \(1/d\)-approximation is known. [Source](https://arxiv.org/pdf/1609.07460)
No result explicitly treating this rational support-input formulation was identified in the search.

Result

For every fixed \(\eta\in(0,1/24]\), achieving a \((23/24+\eta)\)-approximation in the rational support-input model is \(\mathrm{NP}\)-hard. Consequently, the requested polynomial-time algorithm cannot exist unless \(\mathrm{P}=\mathrm{NP}\).

The proof is an exact, polynomial-size transfer from finite profiles. It works even when the permitted masses are restricted to dyadic rationals.

1. Known finite-profile hardness and matching hypotheses

We use the finite-profile hardness theorem supplied in the question: for every fixed \(\eta\in(0,1/24]\), approximating OptPSR within \(23/24+\eta\) is \(\mathrm{NP}\)-hard. This is Theorem 7 of [Caragiannis et al., *Optimizing positional scoring rules for rank aggregation*](https://arxiv.org/pdf/1609.07460).

Its model matches the present one: every agent strictly ranks exactly \(d\) alternatives; feasible scores are weakly decreasing and nonnegative; alternative scores are raw positional sums; and a comparison is satisfied precisely when its score difference is strictly positive. The hardness construction uses integer constraint weights and explicitly realizable finite profiles. Thus its weights are admissible binary rationals.

We now prove the representation transfer.

2. A polynomial transformation preserving every objective value

Let \(P\) be a finite profile with \(N\ge1\) agents over the alternative set \(A\). Write \(n_j^P(x)\) for the number of agents ranking \(x\) in position \(j\), and define

\(\delta_j^P(x,y)=n_j^P(x)-n_j^P(y).\)

The finite-profile objective is

\(G_P(s)=\sum_{(x,y)\in C}w(x,y)\mathbf1\{\delta^P(x,y)\cdot s>0\}.\)

For each distinct type \(\theta\) occurring in \(P\), let \(c_\theta\) be its multiplicity. Then \(c_\theta\) is a positive integer and \(\sum_\theta c_\theta=N\).

Construction. Let \(U\) be the smallest power of two satisfying \(U\ge N\). Introduce a set \(D\) of \(d\) fresh alternatives, disjoint from \(A\), and use the alternative set \(A'=A\cup D\). Keep \(C\), its weights, and \(d\) unchanged.

For each original type, assign mass

\(\mu(\theta)=c_\theta/U.\)

If \(U>N\), add one further type \(\theta_D\), consisting of any fixed strict ranking of \(D\), with mass

\(\mu(\theta_D)=(U-N)/U.\)

If \(U=N\), omit this additional type.

Every listed mass is positive and dyadic. Their sum is

\(\sum_\theta c_\theta/U+(U-N)/U=1,\)

where the second term is zero when the additional type is omitted. Every type ranks exactly \(d\) distinct alternatives. The constructed society therefore satisfies all input requirements.

Preservation of comparisons. The additional type contains no original alternative. Hence, for every \(x\in A\) and every position \(j\),

\(\nu_j^\mu(x)=\sum_{\theta:\pi_\theta(j)=x}c_\theta/U=n_j^P(x)/U.\)

Consequently, for every \((x,y)\in C\),

\(\Delta_j^\mu(x,y)=\delta_j^P(x,y)/U,\)

and thus

\(\Delta^\mu(x,y)\cdot s=(\delta^P(x,y)\cdot s)/U.\)

Because \(U>0\), these two expressions have the same sign, including simultaneous equality to zero. Therefore every comparison has exactly the same satisfaction status under \(P\) and under \(\mu\).

The feasible scoring vectors also remain exactly the same, because their definition depends only on \(d\). It follows that, for every feasible \(s\),

\(G_\mu(s)=G_P(s),\)

and hence

\(\operatorname{OPT}_\mu=\operatorname{OPT}_P.\)

Encoding bounds. Identical rankings can be aggregated by sorting their encoded lists. There are at most \(N\) original support types, so the constructed support size satisfies \(\tau\le N+1\). Moreover, \(|A'|=m+d\), and every mass has numerator and denominator encoded using \(O(\log(N+1))\) bits, since \(U<2N\).

Each ranking requires \(O(d\log(m+d+1))\) bits. Accordingly, the support encoding uses at most

\(O\bigl((N+1)(d\log(m+d+1)+\log(N+1))\bigr)\)

bits, in addition to the alternative and constraint encodings. Both the transformation and its output size are polynomial in the explicit finite-profile input size.

3. Transfer of approximation hardness

Fix \(\eta\in(0,1/24]\), and suppose an algorithm of the requested kind exists.

Given a finite-profile instance from the known hard family, apply the transformation above and run that algorithm. All its input parameters and its total input bit length are polynomially bounded in the finite-profile instance size, so this composition runs in polynomial time.

Let \(s\) be its rational feasible output. Since the scoring dimension and feasibility conditions are unchanged, the same vector is a valid finite-profile output. Exact preservation gives

\(G_P(s)=G_\mu(s)\ge(23/24+\eta)\operatorname{OPT}_\mu=(23/24+\eta)\operatorname{OPT}_P.\)

This would provide a polynomial-time \((23/24+\eta)\)-approximation for the finite-profile problem, contradicting its approximation-hardness theorem unless \(\mathrm{P}=\mathrm{NP}\).

Thus the rational support-input formulation inherits the stated hardness. No expansion of arbitrary rational societies into finite electorates is needed: the reduction runs from finite profiles to polynomial-size rational supports.

⟨structured verdict parsed — rendered above⟩

The output resolves the assigned question. The cited hardness theorem matches the objective and feasible scoring vectors, and the transfer preserves every objective value with polynomial encoding size. No major or minor mathematical issues were found.

• Cited theorem and hypotheses. Theorem 7 states the claimed approximation hardness for every constant \(\eta\in(0,1/24]\). The source defines votes as strict rankings of exactly \(d\) alternatives, permits weakly decreasing nonnegative scoring vectors, uses raw positional sums, and counts a comparison only when its score difference is strictly positive. These hypotheses match USER_TASK. The hardness construction uses integer weights and realizes its constraints using agents and placeholder alternatives. Thus the prover’s invocation is applicable. [Source, Sections 2 and 5](https://arxiv.org/pdf/1609.07460).

• Validity of the constructed support. Aggregating identical types gives positive integer multiplicities \(c_\theta\) summing to \(N\). Since \(U\ge N\), each original mass \(c_\theta/U\) is positive. When \(U>N\), the added mass \((U-N)/U\) is also positive; when \(U=N\), omitting it respects the requirement that listed types have positive mass. The total mass is exactly

\[ \frac{N}{U}+\frac{U-N}{U}=1. \]
Every denominator is a power of two, so every mass is dyadic.

• Alternatives and ranking domains. The dummy type ranks \(d\) distinct fresh alternatives. Original types remain valid types over \(A'\). The dummy type cannot coincide with an original type because their ranked subsets are disjoint. The required dimension restriction remains valid:

\[ 2\le d\le m+d=|A'|. \]
Keeping \(C\) unchanged is legitimate because every original constrained pair remains a pair of distinct alternatives in \(A'\). Adding unconstrained alternatives is permitted.

• Positional-frequency calculation. For an original alternative \(x\), the dummy type contributes zero at every position. Aggregation therefore gives exactly

\[ \nu_j^\mu(x)=\frac{n_j^P(x)}{U}. \]
Subtracting the corresponding identity for \(y\) proves
\[ \Delta_j^\mu(x,y)=\frac{\delta_j^P(x,y)}{U}. \]
These identities hold for every constrained pair and every position, including positions at which either alternative never appears.

• Strict comparisons and ties. Taking the dot product preserves the same positive scaling factor:

\[ \Delta^\mu(x,y)\cdot s=\frac{\delta^P(x,y)\cdot s}{U}. \]
Since \(U>0\), positivity, negativity, and equality to zero are all preserved. Consequently, strict satisfaction and failure through a tie are preserved exactly. This checks the task’s tie convention.

• Objective and optimum preservation. Constraint weights are unchanged, so equality of every satisfaction indicator implies \(G_\mu(s)=G_P(s)\) for every feasible \(s\). The scoring dimension remains \(d\), and neither feasibility condition depends on the number of alternatives. The two feasible sets are therefore identical, justifying \(\operatorname{OPT}_\mu=\operatorname{OPT}_P\). This reasoning also covers the zero vector and instances with zero optimum.

• Encoding and running time. The stated bounds are correct. For every \(N\ge1\), the least power of two at least \(N\) satisfies \(N\le U<2N\), including \(N=1\). Numerators and denominators consequently require \(O(\log(N+1))\) bits. There are at most \(N+1\) support types, each with a ranking of length \(d\), and only \(d\) new alternatives. Sorting and aggregating explicitly listed rankings is polynomial in the explicit finite-profile input size. The unchanged constraints and weights introduce no additional encoding growth.

• Approximation transfer and quantifiers. For any fixed permitted \(\eta\), the hypothesized algorithm runs in polynomial time on the transformed instance. Its rational output is immediately a valid finite-profile scoring vector and satisfies the claimed approximation inequality there because both objective values and optima agree. The reduction requires no conversion of arbitrary rational societies into electorates. It establishes hardness even on the dyadic subclass.

No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩