d4-conf-ijcai-2017-0056 (d4-conf-ijcai-2017-0056)

Given \(m\), a known \(0<\phi<1\), and binary-rational masses \(\mu_{r,S}\) summing to one over randomized-approval types \((r,S)\), where \(r\in[m-1]\) and \(|S|=r\), find a ranking \(\hat{\sigma}\) maximizing \(\sum_{r,S}\mu_{r,S}\log\Pr[(r,S)\mid\hat{\sigma},\phi]\).

Let \(A=\{1,\ldots,m\}\), with \(m\geq2\), and let \(\mathcal R(A)\) denote its strict rankings. The known common noise parameter \(\phi\in(0,1)\) is a binary rational.
A society is given by its support: the list of \(\tau\) types \((r,S)\) with positive binary-rational masses \(\mu_{r,S}\), where \(1\leq r\leq m-1\), \(S\subseteq A\), \(|S|=r\), and \(\sum_{r,S}\mu_{r,S}=1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length.
Under a proposed central ranking \(\sigma\), independently choose \(r\) uniformly from \(\{1,\ldots,m-1\}\) and draw \(\pi\) from the Kendall-tau Mallows model with centre \(\sigma\) and parameter \(\phi\); report the unordered set of its first \(r\) alternatives.
Thus \(P_\sigma(r,S)=\frac{1}{m-1}\frac{\sum_{\pi\in\mathcal R(A):\operatorname{top}_r(\pi)=S}\phi^{d_{\mathrm{KT}}(\pi,\sigma)}}{\sum_{\rho\in\mathcal R(A)}\phi^{d_{\mathrm{KT}}(\rho,\sigma)}}\). Input masses are arbitrary observed frequencies, without a promise that they equal a model distribution or have uniform size marginals.
The optimization problem is to return any ranking maximizing \(\sum_{r,S}\mu_{r,S}\log P_\sigma(r,S)\); ties between maximizers may be resolved arbitrarily.

Can an exact maximizing ranking be computed in time polynomial in \(m,\tau,L\), or is this optimization problem NP-hard?

For finite independent Mallows voters, randomized approval recovers the central ranking with probability at least \(1-\epsilon\) when \(n\geq\frac{2(m-1)^2}{(2p^*-1)^2}\log(m/\epsilon)\), where \(0<\epsilon<1\) and \(p^*>1/2\) is the average voter parameter. [Caragiannis–Micha](https://www.ijcai.org/Proceedings/2017/0022.pdf)
For fixed-size approval votes under Kendall-tau Mallows noise, approval winners are exactly the MLE best alternatives; this estimates the best alternative rather than the complete ranking. [Procaccia–Shah](https://www.cs.toronto.edu/~nisarg/papers/approval_voting.NIPS15.pdf) No result treating exactly the rational-mass optimization above was located.

Result

An exact maximizing ranking is computable in time polynomial in \(m,\tau,L\). Compute each alternative’s total approval mass
\[ w_a=\sum_{(r,S):\,a\in S}\mu_{r,S}, \]
and rank alternatives in nonincreasing order of \(w_a\). Every such ranking maximizes the likelihood, and these are exactly the maximizing rankings.

The proof applies to arbitrary observed masses and arbitrary size marginals.

1. Factorization of a reported set’s probability

Write \(\operatorname{pos}_\sigma(a)\) for the position of alternative \(a\) in \(\sigma\), starting at \(1\). For a finite set \(B\), let \(\sigma|_B\) denote the order induced by \(\sigma\) on \(B\).

Define \(Z_k(\phi)\) as the sum of \(\phi^{d_{\mathrm{KT}}(\eta,\gamma)}\) over all rankings \(\eta\) of a set of \(k\) alternatives, where \(\gamma\) is any fixed ranking. This sum depends only on \(k\) and \(\phi\): relabeling alternatives according to their positions in \(\gamma\) gives a distance-preserving bijection to permutations with the identity centre. In particular, the denominator in the question is \(Z_m(\phi)\).

Fix a reported type \((r,S)\). Every ranking \(\pi\) with \(\operatorname{top}_r(\pi)=S\) consists of a ranking \(\alpha\) of \(S\), followed by a ranking \(\beta\) of \(A\setminus S\). Conversely, each such pair \((\alpha,\beta)\) gives exactly one admissible \(\pi\).

Partition unordered pairs of alternatives into pairs within \(S\), pairs within its complement, and pairs crossing the two sets. The first two classes contribute respectively
\[ d_{\mathrm{KT}}(\alpha,\sigma|_S) \quad\text{and}\quad d_{\mathrm{KT}}(\beta,\sigma|_{A\setminus S}). \]
Every admissible \(\pi\) places each member of \(S\) before every member of its complement. Consequently, its number of crossing disagreements with \(\sigma\) is the fixed quantity
\[ c_\sigma(S) = \bigl|\{(b,a):b\notin S,\ a\in S,\ \operatorname{pos}_\sigma(b)<\operatorname{pos}_\sigma(a)\}\bigr|. \]
Thus
\[ d_{\mathrm{KT}}(\pi,\sigma) = c_\sigma(S) +d_{\mathrm{KT}}(\alpha,\sigma|_S) +d_{\mathrm{KT}}(\beta,\sigma|_{A\setminus S}). \]
Summing over the independent choices of \(\alpha\) and \(\beta\) gives
\[ P_\sigma(r,S) = \frac{Z_r(\phi)Z_{m-r}(\phi)} {(m-1)Z_m(\phi)} \,\phi^{c_\sigma(S)}. \]

To express the exponent through positions, list the positions occupied by \(S\) as \(t_1<\cdots<t_r\). Before its member at position \(t_i\), there are \(t_i-1\) alternatives, exactly \(i-1\) of which belong to \(S\). Hence that member contributes \(t_i-i\) crossing disagreements. Therefore
\[ c_\sigma(S) = \sum_{i=1}^r(t_i-i) = \sum_{a\in S}\operatorname{pos}_\sigma(a) -\frac{r(r+1)}2. \]

2. Reduction to sorting approval masses

All probabilities above are positive because \(\phi>0\). Taking logarithms and substituting the exponent yields
\[ \log P_\sigma(r,S) = b_r +(\log\phi)\sum_{a\in S}\operatorname{pos}_\sigma(a), \]
where
\[ b_r= \log\!\left(\frac{Z_r(\phi)Z_{m-r}(\phi)} {(m-1)Z_m(\phi)}\right) -\frac{r(r+1)}2\log\phi \]
is independent of \(\sigma\).

Multiplying by the masses, summing over the given support, and exchanging finite sums gives
\[ \sum_{r,S}\mu_{r,S}\log P_\sigma(r,S) = C+(\log\phi)\sum_{a\in A}w_a\operatorname{pos}_\sigma(a), \]
where \(C=\sum_{r,S}\mu_{r,S}b_r\) is independent of \(\sigma\).

Since \(0<\phi<1\), we have \(\log\phi<0\). Maximizing the likelihood is therefore equivalent to minimizing
\[ F(\sigma)=\sum_{a\in A}w_a\operatorname{pos}_\sigma(a). \]

Suppose adjacent positions \(i,i+1\) contain \(x,y\), with \(w_x<w_y\). Swapping them changes \(F\) by
\[ \bigl(iw_y+(i+1)w_x\bigr) -\bigl(iw_x+(i+1)w_y\bigr) =w_x-w_y<0. \]
Thus any ranking with an adjacent strict increase in approval mass cannot minimize \(F\).

Repeatedly swapping such adjacent pairs sorts any ranking into nonincreasing approval mass and decreases \(F\) at each swap. All rankings sorted this way have the same value of \(F\), since rearranging alternatives with equal masses leaves their contribution unchanged. Hence every sorted ranking minimizes \(F\). Conversely, every ranking that is not sorted has an adjacent strict increase and is not optimal.

This proves both the algorithm and the characterization of all maximizers.

3. Exact polynomial bit complexity

Index the supported types by \(j\in\{1,\ldots,\tau\}\), and write their rational masses as \(\mu_j=p_j/q_j\), with positive integer denominators. Set
\[ D=\prod_{j=1}^{\tau}q_j, \qquad W_a=\sum_{j:\,a\in S_j}p_j(D/q_j). \]
Then \(W_a=Dw_a\), so sorting the integer scores \(W_a\) sorts the approval masses exactly.

The bit length of \(D\) is at most the sum of the denominators’ bit lengths, hence is bounded by \(L\). Moreover, because the masses are positive and sum to \(1\), each \(W_a\) lies between \(0\) and \(D\). All intermediate score sums therefore have bit length bounded by \(O(L)\).

Computing \(D\), computing each integer \(p_j(D/q_j)\), and adding it to the scores of the alternatives in \(S_j\) takes polynomial time. There are at most \(\tau(m-1)\) score additions. Sorting requires \(O(m\log m)\) exact integer comparisons, also of polynomial bit complexity.

The algorithm never needs to evaluate logarithms or the partition functions. It returns an exact optimizer for every permitted common value of \(\phi\).

⟨structured verdict parsed — rendered above⟩

Verdict: proved. The prover resolves the optimization problem as stated. The probability factorization, reduction to sorting, characterization of all maximizers, and exact polynomial bit complexity are correct. No major or minor mathematical issues were found.

1. Scope and input assumptions

The proof uses exactly the relevant hypotheses: \(m\geq 2\), a common parameter \(0<\phi<1\), and positive rational masses on the explicitly listed support. It does not assume that the masses come from a Mallows distribution or that the size marginals are uniform.

The uniform selection of \(r\) in the model contributes the factor \(1/(m-1)\) to each reported type’s probability. Arbitrary observed size marginals therefore do not invalidate the calculation.

2. Partition functions and probability factorization

The definition of \(Z_k(\phi)\) is valid. Relabeling alternatives by their positions in the centre preserves Kendall-tau distance and gives a bijection to rankings with the identity centre. Thus the partition function depends only on \(k\) and \(\phi\).

For a fixed type \((r,S)\), the decomposition of an admissible ranking into a ranking of \(S\) followed by a ranking of its complement is bijective.

The distance decomposition is also correct:

• Disagreements within \(S\) are counted by \(d_{\mathrm{KT}}(\alpha,\sigma|_S)\).
• Disagreements within the complement are counted by \(d_{\mathrm{KT}}(\beta,\sigma|_{A\setminus S})\).
• Every admissible ranking places all of \(S\) before its complement, so its crossing disagreements are precisely the complement-before-\(S\) pairs in \(\sigma\).

These classes exhaust the unordered pairs without overlap. Consequently, the stated additive distance identity is exact. Summing its exponential over the independent choices of the two internal rankings correctly gives
\[ P_\sigma(r,S)= \frac{Z_r(\phi)Z_{m-r}(\phi)}{(m-1)Z_m(\phi)} \phi^{c_\sigma(S)}. \]
Both internal sets are nonempty because \(1\leq r\leq m-1\); no undefined partition function is required.

3. Calculation of crossing disagreements

For positions \(t_1<\cdots<t_r\), exactly \(i-1\) of the \(t_i-1\) preceding alternatives belong to \(S\). Thus \(t_i-i\) preceding alternatives belong to the complement.

Each crossing disagreement is counted once, at its member of \(S\). The resulting identity
\[ c_\sigma(S)= \sum_{a\in S}\operatorname{pos}_\sigma(a)-\frac{r(r+1)}2 \]
has the correct sign and constant.

4. Reduction of the objective

All probabilities are positive, so taking logarithms is legitimate. The definition of \(b_r\) correctly absorbs every term independent of \(\sigma\).

Exchanging the finite sums gives the stated objective
\[ C+(\log\phi)\sum_{a\in A}w_a\operatorname{pos}_\sigma(a). \]
The coefficient of each position is exactly that alternative’s total approval mass. The constant \(C\) may depend on the observed size marginals, but it remains independent of the proposed ranking.

Since \(\log\phi<0\), maximizing the original objective is exactly equivalent to minimizing \(F\). The direction of this equivalence is correct.

5. Sorting and characterization of all maximizers

The adjacent-swap calculation is correct: swapping \(x,y\) with \(w_x<w_y\) changes \(F\) by \(w_x-w_y<0\).

The subsequent sorting argument is valid. Such swaps terminate in a nonincreasing sequence of scores, and any sequence that is not nonincreasing has an adjacent strict increase. Thus every unsorted ranking admits a strict improvement.

All sorted rankings have the same score sequence at their positions; permutations within equal-score groups leave \(F\) unchanged. This establishes both claims: every sorted ranking is optimal, and every optimal ranking is sorted.

Equal scores and alternatives with zero approval mass are covered by this argument. The case \(m=2\) also satisfies all preceding calculations.

6. Exact polynomial bit complexity

The common-denominator construction is valid even if the input fractions are not reduced. Each \(D/q_j\) is an integer, and \(W_a=Dw_a\), so integer comparisons preserve all score comparisons and ties exactly.

The bit length of \(D\) is bounded by the sum of the denominator bit lengths, hence by \(L\). Positivity and normalization imply \(0\leq w_a\leq1\), so \(0\leq W_a\leq D\). Partial score sums also stay within this bound because every summand is nonnegative.

The required integer products, exact divisions, additions, and comparisons operate on polynomially bounded bit lengths. There are at most \(\tau(m-1)\) score additions and \(O(m\log m)\) sorting comparisons. These bounds establish polynomial running time in \(m,\tau,L\).

The algorithm needs neither numerical logarithms nor evaluation of partition functions. It therefore returns an exact optimizer without any unresolved numerical-comparison issue.

No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩