Subset Selection via Implicit Utilitarian Voting (d4-conf-ijcai-2016-0612)

Given a finite alternative set \(A\), an integer \(k\), and a rational sparse distribution \(\mu=(\mu_\sigma)\) over complete rankings \(\sigma\in\mathcal{L}(A)\), output an integral \(k\)-subset \(T\) minimizing \(\operatorname{Reg}_\mu(T)=\max_{S\in\binom{A}{k}}\sum_{\sigma}\mu_\sigma\mathbf{1}[S\succ_\sigma T]/\sigma(S)\).

Definitions

For a complete ranking \(\sigma\), let \(\sigma(a)\) be the position of \(a\), with \(1\) best; for nonempty \(S\subseteq A\), let \(\sigma(S)=\min_{a\in S}\sigma(a)\). Write \(S\succ_\sigma T\) when \(\sigma(S)<\sigma(T)\).
The input distribution has finite support, with rational \(\mu_\sigma\geq0\) and \(\sum_\sigma\mu_\sigma=1\). For \(T\in\binom{A}{k}\), define \(\operatorname{Reg}_\mu(T)=\max_{S\in\binom{A}{k}}\sum_\sigma\mu_\sigma\mathbf{1}[S\succ_\sigma T]/\sigma(S)\).

Target

Is computing an integral \(k\)-subset \(T\) minimizing \(\operatorname{Reg}_\mu(T)\) solvable in polynomial time, or is it NP-hard?

Nearest known results

For finite preference profiles, computing a \(k\)-subset minimizing the corresponding deterministic regret objective is NP-hard.
This result uses voter multiplicities rather than rational masses.

Result. Computing an optimal integral \(k\)-subset is NP-hard, using the deterministic-regret hardness result supplied in the question. Normalizing voter multiplicities preserves every optimal solution.

Hardness premise. Write a finite preference profile as rankings \(\sigma_1,\ldots,\sigma_r\) with positive integer multiplicities \(m_1,\ldots,m_r\). The supplied hardness result concerns minimizing the corresponding objective
\[ D(T)=\max_{S\in\binom{A}{k}}\sum_{i=1}^{r}m_i \frac{\mathbf{1}[S\succ_{\sigma_i}T]}{\sigma_i(S)} \]
over \(T\in\binom{A}{k}\). If that objective is defined using the average over voters, it differs from \(D\) only by a positive constant, so its minimizers are identical.

Reduction. Keep \(A\) and \(k\) unchanged. Set \(M=\sum_{i=1}^{r}m_i\) and define
\[ \mu_\sigma=\frac{\sum_{i:\sigma_i=\sigma}m_i}{M}. \]
These masses are nonnegative rationals summing to \(1\), so they define a valid target instance.

This construction takes polynomial time. For explicitly listed voters, count occurrences of each ranking. For binary-encoded multiplicities, if each multiplicity has at most \(b\) bits, then \(M\) has at most \(b+\lceil\log_2 r\rceil+1\) bits. Every numerator is at most \(M\), and at most \(r\) distinct rankings appear. Thus the resulting distribution has polynomial encoding length, even when multiplicities are encoded succinctly.

Preservation of the objective. For every feasible \(T\),
\[ \begin{aligned} \operatorname{Reg}_\mu(T) &=\max_{S\in\binom{A}{k}} \sum_{i=1}^{r}\frac{m_i}{M} \frac{\mathbf{1}[S\succ_{\sigma_i}T]}{\sigma_i(S)}\\ &=\frac{1}{M}\max_{S\in\binom{A}{k}} \sum_{i=1}^{r}m_i \frac{\mathbf{1}[S\succ_{\sigma_i}T]}{\sigma_i(S)}\\ &=\frac{D(T)}{M}. \end{aligned} \]
The second equality holds because \(M\) is positive and independent of \(S\). Consequently, for any feasible \(T,U\),
\[ \operatorname{Reg}_\mu(T)\leq\operatorname{Reg}_\mu(U) \quad\Longleftrightarrow\quad D(T)\leq D(U). \]
Hence the two instances have exactly the same minimizing committees.

A polynomial-time algorithm computing a minimizing \(T\) for rational input distributions would therefore compute a minimizing committee for the NP-hard deterministic problem: perform the normalization, call the algorithm, and return its committee. This proves the claimed NP-hardness. The only external hardness premise used is the corresponding deterministic result stated in the question.

⟨structured verdict parsed — rendered above⟩

The argument is correct under the deterministic-regret hardness premise supplied in USER_TASK. It gives a polynomial-time reduction preserving every optimal committee.

Step-by-step verification

• Use of the hardness premise. The prover explicitly states the deterministic objective being used. This is the multiplicity-weighted counterpart of the objective in USER_TASK, consistent with the supplied “corresponding deterministic regret objective” premise. No stronger external theorem is needed. The observation about averaging is correct: dividing the objective by the positive total number of voters does not change its minimizers.

• Validity of the constructed distribution. For a nonempty profile with positive integer multiplicities, \(M=\sum_{i=1}^{r}m_i>0\). Aggregating repeated rankings and dividing their total multiplicities by \(M\) produces nonnegative rational masses whose sum is exactly \(1\). Keeping \(A\) and \(k\) unchanged preserves the feasible committees and competitors.

The argument operates on the meaningful domain of the stated problem: \(1\leq k\leq |A|\) and nonempty preference profiles. Outside this domain, the given objectives or normalization need not be defined; this does not affect the reduction on valid instances.

• Polynomial construction and encoding size. The stated bound of \(b+\lceil\log_2 r\rceil+1\) bits for \(M\) is valid, although conservative. Every aggregated numerator is at most \(M\), and there are at most \(r\) distinct rankings. Counting and aggregating rankings, adding the multiplicities, and writing the rational masses all take polynomial time in the source encoding length. Explicitly listed voters and binary-encoded multiplicities are both covered.

• Equality of objectives. The first displayed equality correctly expands the aggregated distribution back into the original indexed profile: identical rankings contribute identical comparison indicators and denominators. Because \(M>0\) is independent of the competing committee \(S\), it can be factored out of the maximum. Thus the claimed identity \(\operatorname{Reg}_{\mu}(T)=D(T)/M\) holds for every feasible \(T\).

• Preservation of minimizers. Multiplication by the positive constant \(1/M\) preserves all pairwise objective comparisons, including ties. Consequently, the two instances have exactly the same minimizing committees. This establishes the necessary preservation for a search reduction, not merely preservation of optimal values.

• Hardness conclusion. A polynomial-time algorithm returning an optimal target committee would, after the polynomial normalization, return an optimal committee for the supplied NP-hard deterministic problem. The returned committee requires no further transformation. The NP-hardness conclusion follows. The prover does not claim membership in NP or NP-completeness, so no decision-problem certificate argument is required.

Issues and repair feedback

No major or minor issues were found. No additional clarification or repair is required relative to the hardness premise explicitly supplied in USER_TASK.

⟨structured verdict parsed — rendered above⟩