| paper | Finding a Collective Set of Items: From Proportional Multirepresentation to Group Recommendation |
| authors | P. Skowron, Piotr Faliszewski, J. Lang |
| venue | AAAI 2015 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: NP-hard · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 7
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.
A common-catalogue group-recommendation model with complete ranking types \(t\), population masses \(\mu_t\), an integral committee decision \(W\) of size \(K\), and objective \(F_\mu(W)=\sum_t\mu_t\sum_{j=1}^{K-1}b_{t,j}(W)\). The continuum is in the population distribution, not in the catalogue or committee.
The mirrors cover exact winner determination for Theorem 7 with Borda-based utilities and Theorem 6 with approval-based utilities. They leave approximation results such as Theorem 13's \(1-1/e\) guarantee, the ILP formulation, and other OWA families unmirrored.
The strongest honest case is a Class B mirror: the population becomes continuous, but the selected committee remains an integral \(K\)-subset. This is not a claim that OWA-Winner becomes an LP; it is a claim that the paper’s computational problem survives as a high-multiplicity problem over population types.
My lead anchor is Theorem 7, proved in the paper’s appendix. It states that \((K-1)\)-best-OWA-Winner is NP-hard even when all utilities are Borda-based. Concretely, given rankings of \(m\) items, one must choose \(K\) items maximizing the sum over agents of the \(K-1\) largest Borda utilities they assign to the chosen items.
The corresponding problem is Continuous-\((K-1)\)-Borda-OWA-Winner. An instance consists of an item set \(A\), an integer \(K\), finitely many ranking types \(T=\{t_1,\ldots,t_\tau\}\), and rational masses \(\mu_t\ge 0\) summing to \(1\). Type \(t\) is a complete ranking, with Borda utility \(b_t(a)=m-\operatorname{pos}_t(a)\). For every \(K\)-set \(W\), sort its Borda utilities for type \(t\) as \(b_{t,1}(W)\ge\cdots\ge b_{t,K}(W)\), and define
\[ F_\mu(W)=\sum_{t\in T}\mu_t\sum_{j=1}^{K-1}b_{t,j}(W). \]
The task is to output a \(K\)-set \(W\) maximizing \(F_\mu(W)\). Every member of the population receives the whole common set \(W\); only the population proportions are continuous.
A natural regime is group recommendation for a very large recurring population: airline passengers, subscribers, or library users are drawn from a modest number of preference segments. Each segment contains many users with the same ranking over the catalogue. Thus \(N\) may be millions while \(\tau\) is hundreds or thousands. This is exactly the paper’s group-recommendation interpretation, not an invented election story.
The finite-to-continuous correspondence is exact. If a finite profile has \(n_t\) voters of type \(t\), set \(\mu_t=n_t/n\); then \(F_\mu(W)\) is precisely the paper’s total score divided by \(n\). Conversely, rational masses can be expanded into a finite profile using a common denominator. We can also replicate every type \(R\) times, making \(N\gg\tau\) without changing the objective. Hence Theorem 7 yields NP-hardness for the continuous problem. The hardness is Class B: its combinatorics live in the item set and ranking interactions, not in the number of named agents. The natural exact question therefore expects hardness transfer, although Theorem 13’s greedy \(1-1/e\) approximation also extends immediately because the mass-weighted objective remains monotone and submodular.
A useful second anchor is Theorem 6, proved in Section 5. It states that \((K-1)\)-best-OWA-Winner is NP-complete even for approval-based utilities. For an agent approving \(S\subseteq A\), the contribution of a committee \(W\) is \(\min(|S\cap W|,K-1)\).
Its continuous counterpart is Continuous-\((K-1)\)-Approval-OWA-Winner. The input is \(A\), \(K\), approval types \(S_t\subseteq A\), and rational masses \(\mu_t\). The goal is to choose \(|W|=K\) maximizing
\[ \sum_t \mu_t\min(|S_t\cap W|,K-1). \]
This is the same common-catalogue recommendation problem for users who provide approval sets rather than rankings. Normalizing the agents in the theorem’s discrete reduction gives an identical weighted objective, so NP-hardness transfers; for the rational decision version, membership in NP is also immediate. This second mirror is worth keeping because it shows that the case is not dependent on Borda’s numerical encoding.
The scope is deliberately narrow: exact winner determination for these OWA families under Borda or approval type distributions. It does not claim to continuize the paper’s entire approximation section, nor does it fractionalize the selected items.
The weakest point is that population mass is an input coefficient rather than an optimization variable. These mirrors are therefore compressed, weighted versions of discrete committee selection, not continuum-specific optimization phenomena. They also do not establish hardness when \(\tau\) is fixed; the support may grow with the number of items, while high multiplicity comes from many repeated copies of each type. Still, that is a legitimate high-multiplicity regime, and the paper’s authors should recognize both stated problems as their OWA-Winner question with the electorate represented by a distribution rather than a list of individuals.
The strongest negative case is that both anchors admit a valid high-multiplicity encoding, but neither yields a genuinely population-level computational problem. In the paper, agents never interact, are never assigned different outcomes, and are never constrained individually. The population enters only through an additive sum.
For Theorem 7, the proposed objective is
\[ F_\mu(W)=\sum_t \mu_t\sum_{j=1}^{K-1}b_{t,j}(W). \]
With \(\mu_t=n_t/n\), this is exactly the finite objective divided by \(n\). Thus rational-mass instances are merely weighted instances of the original committee problem. The same is true of every approximation argument: Theorem 13’s submodularity proof carries over by replacing an unweighted sum with a weighted sum. The continuum supplies compression of repeated utility rows, but no new constraint, decision variable, or computational phenomenon.
Theorem 6 is even less promising. Its proposed mirror is
\[ G_\mu(W)=\sum_t\mu_t\min\bigl(|S_t\cap W|,K-1\bigr), \]
which is simply weighted capped coverage. A large recommender population with repeated approval sets is a plausible story, but the distribution again functions only as a list of coefficients. If one instead lets different types receive different committees, imposes type-level quotas, or optimizes over fractional recommendations, one obtains an interesting problem—but it is no longer the paper’s OWA-Winner problem, and in the last case it continuizes the outcome rather than the population.
The proponent is also right that these mirrors are not invalid: rankings and approval sets are legitimate complete types, and rational masses give an exact finite-to-continuous dictionary. Replication can produce arbitrarily large populations with few repeated types. Existing high-multiplicity work would support this regime rather than undermine it.
Consequently, I cannot honestly defeat the anchors universally. The best objection is that they are shallow weighted-profile reformulations rather than worthwhile ChoCo problems. That may justify a low novelty assessment, especially since neither theorem studies fixed \(\tau\), population-dependent constraints, or a continuum-specific algorithmic effect. But under the programme’s stated standard, the two anchors survive: they are sensible Class B mirrors, and the negative case is weak.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.