Finding a Collective Set of Items: From Proportional Multirepresentation to Group Recommendation (d4-conf-aaai-2015-0060)

Given a finite item set \(A\), an integer \(K\), ranking types \(T=\{t_1,\ellipsis,t_\tau\}\), and rational masses \(\mu_t\ge 0\) with \(\sum_{t\in T}\mu_t=1\), where each type is a complete ranking and \(b_t(a)=m-\operatorname{pos}_t(a)\), output a \(K\)-item set \(W\subseteq A\) maximizing \(\sum_{t\in T}\mu_t\sum_{j=1}^{K-1}b_{t,j}(W)\), where \(b_{t,1}(W)\ge\dots\ge b_{t,K}(W)\) are the selected items' Borda utilities in descending order.

Definitions. Let \(m=|A|\), \(1\le K\le m\), and let each \(t\in T\) be a complete ranking of \(A\), with rational mass \(\mu_t\ge0\) and \(\sum_{t\in T}\mu_t=1\). Set \(b_t(a)=m-\operatorname{pos}_t(a)\). For \(W\subseteq A\) of size \(K\), write its Borda values for type \(t\) as \(b_{t,1}(W)\ge\dots\ge b_{t,K}(W)\). Compute a \(K\)-item set maximizing \(\sum_{t\in T}\mu_t\sum_{j=1}^{K-1}b_{t,j}(W)\).

Target. Is this rational-mass \( (K-1)\)-best Borda OWA-Winner problem solvable in polynomial time, or is it NP-hard?

Nearest known results. The finite-agent version with Borda-based utilities is NP-hard: selecting \(K\) items to maximize each agent's sum of the top \(K-1\) selected Borda utilities is NP-hard.

Conclusion

The rational-mass \((K-1)\)-best Borda OWA-Winner problem is NP-hard, by a polynomial-time reduction from the finite-agent problem stated as NP-hard in the premises. In fact, uniform rational masses suffice.

Reduction and proof

We use the supplied finite-agent hardness result in the following form: given an explicitly listed population of \(n\ge 1\) agents, each with a complete ranking of a common alternative set \(A\), and a committee size \(K\), computing a committee maximizing the sum of the agents’ top \(K-1\) selected Borda utilities is NP-hard.

Take such an instance. For agent \(i\), let \(b_{i,j}(W)\) denote the \(j\)-th largest Borda value among the alternatives in \(W\). Its objective is
\(F(W)=\sum_{i=1}^{n}\sum_{j=1}^{K-1}b_{i,j}(W)\).

Construct an instance of the rational-mass problem as follows:

• Keep the alternative set \(A\) and committee size \(K\).
• Let \(T\) consist of the distinct rankings occurring among the agents.
• For each ranking \(t\), let \(c_t\) be the number of agents with that ranking, and set \(\mu_t=c_t/n\).

These masses are nonnegative rational numbers, and
\(\sum_{t\in T}\mu_t=(\sum_{t\in T}c_t)/n=n/n=1\).
Every type retains a complete ranking of \(A\), so the constructed instance satisfies all the required hypotheses.

For every committee \(W\subseteq A\) with \(|W|=K\), agents with the same ranking have identical selected Borda values. Consequently, the constructed objective satisfies
\(G(W)=\sum_{t\in T}(c_t/n)\sum_{j=1}^{K-1}b_{t,j}(W)=F(W)/n\).

Since \(n>0\), for any two feasible committees \(W,W'\), we have
\(G(W)\ge G(W')\) if and only if \(F(W)\ge F(W')\).
Thus the two instances have exactly the same maximizing committees.

The construction takes polynomial time: distinct rankings and their multiplicities can be computed by comparing the explicitly listed rankings. There are at most \(n\) types, and each numerator and denominator of a mass requires at most \(O(\log(n+1))\) bits. Therefore a polynomial-time algorithm for the rational-mass problem would compute an optimal committee for the finite-agent problem in polynomial time. The supplied hardness theorem proves the claimed NP-hardness.

If repeated rankings are allowed as separately indexed types, one can instead retain all \(n\) agents as types and give each the uniform mass \(1/n\). Even when types must have distinct rankings, this is equivalently the construction above after merging duplicates.

Borda convention

If the supplied finite-agent theorem uses Borda scores \(m-\operatorname{pos}_t(a)+1\) instead of \(m-\operatorname{pos}_t(a)\), subtracting one from every utility subtracts exactly \(K-1\) from each agent’s committee score. The finite-agent objective therefore changes by the committee-independent constant \(n(K-1)\), preserving all maximizing committees. This convention does not affect the reduction.

⟨structured verdict parsed — rendered above⟩

The reduction establishes NP-hardness of the rational-mass problem using the finite-agent hardness result supplied in USER_TASK. The only issue is the unqualified additional claim that uniform rational masses suffice: the construction establishes this only when repeated rankings may appear as separately indexed types.

• Use of the supplied hardness result. The prover states the source problem precisely: an explicitly listed, nonempty population with complete rankings, a common alternative set, and the same committee objective. This matches the supplied finite-agent hardness premise. No independent proof of that premise is required.

• Validity of the constructed instance. Grouping identical rankings gives positive integer multiplicities \(c_t\) whose sum is \(n\). Therefore the masses \(\mu_t=c_t/n\) are nonnegative rationals summing to one. The alternative set, complete rankings, committee size, and feasible committees are preserved.

• Objective identity. For a fixed committee, agents with identical rankings have identical ordered selected Borda values. Grouping their contributions therefore gives exactly \(G(W)=F(W)/n\). This equality holds for every feasible committee.

• Preservation of optimality. Since \(n>0\), division by \(n\) preserves every comparison and tie between committee scores. Consequently, the maximizing committees coincide. Returning the committee produced by a target-problem optimizer solves the source instance directly.

• Polynomial complexity. Comparing and grouping explicitly listed rankings takes polynomial time. There are at most \(n\) output rankings, and each numerator and denominator is at most \(n\), requiring \(O(\log(n+1))\) bits. If reduced fractions are required, reducing these fractions is a routine polynomial-time operation. The construction and output size are polynomial in the source input length.

• Borda convention. Shifting every utility down by one preserves its order and decreases the sum of the top \(K-1\) selected utilities by exactly \(K-1\). The total decrease is therefore \(n(K-1)\), independent of the committee. The convention adjustment is correct.

• Boundary cases. For \(K=1\), the sums are empty and both objectives are zero; the identity and optimizer correspondence remain valid. For \(K=m\), the unique feasible committee is preserved. These easy parameter cases do not undermine hardness for the unrestricted problem.

Minor issue — uniform-mass claim. The conclusion says, “In fact, uniform rational masses suffice.” Retaining agents as separately indexed types does establish this if duplicate rankings are permitted. However, merging duplicates generally produces unequal masses. For example, two occurrences of one ranking and one occurrence of another yield masses \(2/3\) and \(1/3\). Thus the asserted equivalence after merging preserves the objective, but does not preserve uniformity.

The minimum clarification is to qualify the uniform-mass claim by the permission to retain separately indexed duplicate rankings. If types must be distinct rankings, remove that additional claim unless separately justified. This does not affect the main NP-hardness result.

⟨structured verdict parsed — rendered above⟩