Subset Selection via Implicit Utilitarian Voting

The strongest honest case is a high-multiplicity version of the paper’s regret-minimizing subset problem. It is a genuine mirror, although I expect it to be Class B rather than a case where continuity removes the hardness.

My lead anchor is Theorem 2, proved by the authors—the conference version says that the proof appears in the full version. It states:

Given a preference profile \(\tilde{\sigma}\) and an integer \(k\), computing a \(k\)-subset of alternatives having minimum distortion or minimum regret on \(\tilde{\sigma}\) is NP-hard.

I use the minimum-regret half of this theorem, since the paper gives it the clearest underlying characterization and implements it.

Call the continuous problem Continuous Minimum-Regret \(k\)-Subset Selection. An instance consists of a finite alternative set \(A\), an integer \(k\), and a rational population distribution
\[ \mu=(\mu_\sigma)_{\sigma\in\mathcal L(A)},\qquad \mu_\sigma\ge 0,\qquad \sum_{\sigma}\mu_\sigma=1. \]
A type is a complete ranking \(\sigma\) of \(A\); \(\mu_\sigma\) is the fraction of the population submitting that ranking. The input may be given sparsely by its \(\tau\) occupied ranking types.

The output must be an ordinary, integral \(k\)-subset \(T\subseteq A\), not a fractional committee. For \(S\subseteq A\), let
\[ \sigma(S)=\min_{a\in S}\sigma(a), \]
and write \(S\succ_\sigma T\) when \(\sigma(S)<\sigma(T)\). The per-capita worst-case regret of \(T\) is
\[ \operatorname{Reg}_\mu(T) = \max_{S\in\binom{A}{k}} \sum_{\sigma\in\mathcal L(A)} \mu_\sigma\, \mathbf 1[S\succ_\sigma T]\, \frac{1}{\sigma(S)}. \]
The task is to output
\[ T^\star\in \arg\min_{T\in\binom{A}{k}} \operatorname{Reg}_\mu(T). \]

This is exactly the paper’s robust utilitarian question in continuous-population form. Equivalently, one can define regret by taking the supremum over all measurable assignments of normalized latent utilities \(u_x\) consistent with the ranking of almost every population point \(x\), with \(u_x(S)=\max_{a\in S}u_x(a)\), and replacing the paper’s per-voter average by a population integral. The displayed formula is the resulting closed form, obtained from the paper’s Equation (2).

A plausible regime is a large online or institutional choice process: millions of participants rank a fixed menu of policy packages, courses, restaurants, candidates, or projects, while the number of distinct complete rankings is much smaller. Repeated cohorts, standardized questionnaires, or preference templates can easily produce \(n\) in the millions and \(\tau\) in the hundreds or thousands. Agents sharing a ranking are indistinguishable for this problem: their cardinal utilities are not input data, but adversarial latent utilities constrained only by that ranking. Thus the mirror does not quietly replace the paper’s model by plurality, average utilities, or a different welfare objective.

The authors should recognize this as their problem. The alternatives, the cardinality constraint, deterministic subset selection, and worst-case distortion/regret objective are unchanged. Only the population representation changes: the explicit profile is replaced by its type-mass distribution. This is not a collision with an already continuous-population paper; the paper never formulates \(\mu\), never treats \(\tau\) as the population-complexity parameter, and never studies algorithms on compressed ranking distributions.

The expected classification is hardness transfers. Given any finite profile, set
\[ \mu_\sigma=\frac{|\{i:\sigma_i=\sigma\}|}{n}. \]
Then the continuous regret objective is exactly the discrete per-voter regret objective, and an optimal continuous solution is an optimal discrete \(k\)-subset. Therefore a polynomial-time algorithm for the general rational-mass problem would solve the paper’s NP-hard problem. The likely source of hardness is the combinatorics of choosing \(T\) and \(S\) from the alternatives, not the number of named voters, so this is precisely the kind of hardness expected to survive continuization.

This mirror covers only the regret part of Theorem 2; I would not stretch it to claim coverage of the paper’s empirical comparisons or its full implementation study. It raises useful follow-up questions: is the problem fixed-parameter tractable in the number \(\tau\) of ranking types or in \(k\); does hardness persist when every type has large multiplicity; and what approximation guarantees are possible for the continuous objective?

The weakest point is that \(\mu\) is passive input rather than an optimization variable. A skeptical referee could call this merely a weighted-profile reformulation, especially because the discrete problem embeds exactly into it. The response is that this is nevertheless the paper’s proper high-multiplicity object: the population, rather than named voters, is the primitive society, while the committee remains integral. But this case should not claim a tractability gain. Its honest contribution is to expose a natural continuous-population problem and show that, for this anchor, continuization probably stops helping because the hardness lives in the alternative-selection structure.