d4-conf-ijcai-2015-0255 (d4-conf-ijcai-2015-0255)

Given \(\tau\) ranking types \(t\in S_n\) with positive rational masses \(\mu_t\) summing to \(1\), and fixed strictly decreasing rational weights \(w\), find a ranking \(\rho\in S_n\) minimizing \(\sum_t \mu_t d_{PS}(\rho,t)\).

Let \(m\geq 1\) be the number of items. A ranking \(\pi\in S_m\) maps each item to its position, with position \(1\) best. A society is given by its support: the list of the \(\tau\) distinct ranking types with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number \(m!\) of possible types.
A common weight vector \(w\in\mathbb{Q}^m\) is supplied in binary and satisfies \(w_1>\cdots>w_m\); its entries may have either sign. Define positional Spearman distance by \(d_{PS}(\rho,t)=\sum_{i=1}^{m}(w_{\rho(i)}-w_{t(i)})^2\). Let \(L\) be the total input bit length.
Find a full ranking \(\rho\in S_m\) minimizing \(\sum_t\mu_t d_{PS}(\rho,t)\); any minimizer is acceptable.

Is computing such an optimal ranking possible in time polynomial in \(m,\tau,L\), or is this optimization problem NP-hard?

For an explicitly listed finite society, positional Spearman minimizers are precisely the rankings returned by the positional scoring rule with the same strictly decreasing weights, yielding a polynomial-time algorithm. This establishes the discrete analogue; it does not state a complexity result for binary-encoded rational-mass support input.

Result

The problem is polynomial-time solvable, including for binary-encoded rational masses. Compute each item’s expected positional weight and rank the items in decreasing order of these scores. The rational arithmetic can be performed exactly with polynomially many bits.

1. Reduction to positional scores

For each item \(i\), define
\(s_i=\sum_{t=1}^{\tau}\mu_t w_{t(i)}\).

Expanding the objective gives
\( F(\rho) =\sum_{i=1}^{m}w_{\rho(i)}^2 -2\sum_{i=1}^{m}w_{\rho(i)}s_i +\sum_{t=1}^{\tau}\mu_t\sum_{i=1}^{m}w_{t(i)}^2. \)

Because every ranking is a permutation, both \(\sum_i w_{\rho(i)}^2\) and \(\sum_i w_{t(i)}^2\) equal \(\sum_{j=1}^{m}w_j^2\). Using \(\sum_t\mu_t=1\), we obtain
\( F(\rho)=2\sum_{j=1}^{m}w_j^2-2\sum_{i=1}^{m}w_{\rho(i)}s_i. \)

Thus minimizing \(F\) is equivalent to maximizing
\(H(\rho)=\sum_i w_{\rho(i)}s_i\).
This identity holds regardless of the signs of the weights.

2. Sorting the scores is optimal

Write the items in their order under a ranking as \(i_1,\ldots,i_m\), so that \(\rho(i_j)=j\). Suppose adjacent positions satisfy \(s_{i_j}<s_{i_{j+1}}\). Swapping these two items changes \(H\) by
\( (w_j-w_{j+1})(s_{i_{j+1}}-s_{i_j})>0, \)
since the weights are strictly decreasing.

Repeatedly swapping adjacent score inversions terminates: each swap decreases the number of pairs whose earlier item has strictly smaller score. The resulting score sequence is nonincreasing, and \(H\) never decreases.

Every ranking with nonincreasing scores has the same value of \(H\), because the numerical score sequence is the same; only items with equal scores can exchange positions. Consequently, every such ranking maximizes \(H\). Conversely, any ranking whose scores are not nonincreasing has an adjacent inversion and therefore cannot maximize \(H\).

Hence the minimizers are precisely the rankings that order items by decreasing \(s_i\), with arbitrary tie-breaking.

3. Exact computation has polynomial bit complexity

Write the input rationals as
\(w_j=a_j/b_j\) and \(\mu_t=p_t/q_t\), with integer numerators and positive integer denominators. Define
\( B=\prod_{j=1}^{m}b_j,\qquad Q=\prod_{t=1}^{\tau}q_t, \)
and the integers
\( W_j=a_j(B/b_j),\qquad P_t=p_t(Q/q_t). \)

For each item, compute the integer
\( S_i=\sum_{t=1}^{\tau}P_tW_{t(i)}. \)
Then \(s_i=S_i/(BQ)\). Because the denominator \(BQ\) is common and positive, sorting the integers \(S_i\) sorts the scores exactly.

We now bound all intermediate integer sizes. Since \(L\) is the total input bit length, the products \(B\) and \(Q\) each have \(O(L+1)\) bits. Also, \(|a_j|\leq 2^L\), so the coarse bound \(|W_j|\leq 2^{2L}\) suffices. Positivity and normalization of the masses imply
\( P_t>0,\qquad \sum_{t=1}^{\tau}P_t=Q. \)
Therefore
\( |S_i| \leq\sum_tP_t|W_{t(i)}| \leq Q\max_j|W_j| \leq 2^{3L}. \)
The same bound applies to every partial sum used to compute \(S_i\). Thus all required integers have \(O(L+1)\) bits.

Constructing these integers requires \(O(m+\tau+m\tau)\) integer arithmetic operations. Sorting requires \(O(m\log m)\) integer comparisons. Integer multiplication, exact division, addition, and comparison on these bit lengths all take polynomial time.

4. Algorithm and conclusion

• Compute \(B,Q\), the integers \(W_j,P_t\), and each integer score \(S_i\).
• Sort the items by decreasing \(S_i\), breaking ties arbitrarily.
• Assign positions \(1,\ldots,m\) in that order.

The resulting ranking is optimal, and the running time is polynomial in \(m,\tau,L\). This directly handles the rational-mass support representation without expanding masses into repeated voters.

⟨structured verdict parsed — rendered above⟩

The prover fully resolves the task. The argument is correct and rigorous for binary-encoded rational masses, including signed weights, tied scores, and \(m=1\). No major or minor issues were found.

1. Objective reduction

The definition \(s_i=\sum_{t=1}^{\tau}\mu_t w_{t(i)}\) is well-defined for every item.

Expanding each squared difference gives the displayed expression for \(F(\rho)\). The first term uses \(\sum_t\mu_t=1\). Because \(\rho\) and every support ranking \(t\) are permutations, their squared-weight sums equal \(\sum_j w_j^2\). Therefore
\[ F(\rho)=2\sum_{j=1}^{m}w_j^2-2\sum_{i=1}^{m}w_{\rho(i)}s_i \]
is correct. Its first term is independent of \(\rho\), so minimizing \(F\) is equivalent to maximizing \(H\). No assumption on the signs of the weights is needed.

2. Optimality and characterization of minimizers

For an adjacent pair with \(s_{i_j}<s_{i_{j+1}}\), the stated change in \(H\),
\[ (w_j-w_{j+1})(s_{i_{j+1}}-s_{i_j}), \]
is correct and strictly positive.

The termination argument is valid: swapping an adjacent strict inversion removes that pair’s inversion, while preserving the total inversion contributions involving every other item. Thus the nonnegative integer inversion count strictly decreases.

Starting from any ranking, this process reaches a nonincreasing score sequence with no smaller value of \(H\). Every nonincreasing arrangement has the same numerical score sequence and hence the same \(H\). Together, these facts establish that every sorted ranking is globally optimal.

Conversely, any sequence that is not nonincreasing contains an adjacent strict inversion, which permits a strict improvement. The characterization of all minimizers, including arbitrary tie-breaking, follows.

3. Exact arithmetic and bit complexity

The positive denominator products \(B\) and \(Q\) are valid common denominators. All displayed divisions are exact, and
\[ S_i=\sum_t P_tW_{t(i)},\qquad s_i=\frac{S_i}{BQ} \]
holds exactly. Sorting the integer scores therefore preserves all score comparisons and ties.

The bit bounds are valid. The aggregate encoded lengths of the denominators bound the bit lengths of their products by \(O(L+1)\). The coarse bounds on \(W_j\), \(Q\), and \(S_i\) follow.

Normalization gives \(\sum_tP_t=Q\), with every \(P_t>0\). Consequently, the absolute-value bound also applies to partial sums despite possibly negative weights. Intermediate products, denominator products, and exact-division operands likewise have \(O(L+1)\) bits.

The stated arithmetic-operation and comparison counts are polynomial in \(m,\tau\). Standard exact integer arithmetic on the established bit lengths takes polynomial time. There is no expansion into a potentially exponentially large voter list.

4. Scope and edge cases

The algorithm outputs the required item-to-position permutation. Equal scores may be ordered arbitrarily. For \(m=1\), the unique ranking is returned and the optimality argument remains valid. Positive masses summing to one ensure the support is nonempty.

The proof establishes a polynomial-time algorithm for the precise rational-mass support representation in the task. No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩