Source-linked AI summary
Finding a Collective Set of Items: From Proportional Multirepresentation to Group Recommendation
Piotr Skowron, Piotr Faliszewski, Jerome Lang
TL;DR
The paper asks how to select K shared items when agents’ realized utility depends on each item’s rank among the selected items. It formalizes this rank-sensitive setting through OWA-based utilities, instantiates it across applications, and analyzes its complexity and approximability. The results show broad hardness, a (1−1/e) greedy guarantee for nonincreasing OWAs, and strong dependence on the utility and OWA classes.
Problem
Selecting K shared items is difficult because agents’ derived utility can be only a rank-dependent fraction of intrinsic item utility.
Method
The paper defines OWA-Winner, models agents’ rank-sensitive utilities with ordered weighted averages, and applies the model to voting, unavailable items, and assignment uncertainty.
Results
OWA-Winner is NP-hard in broad nonconstant nonincreasing cases, while nonincreasing OWAs admit a (1−1/e) greedy approximation guarantee.
Takeaways & Limitations
The model unifies several selection and voting settings, with computational behavior varying substantially by OWA vector and utility representation.
Takeaways & Limitations
For unrestricted OWA-Winner with nonincreasing OWA, no polynomial-time algorithm can improve on approximately 63% unless P = NP.
Abstract
from arXiv · showhide
We consider the following problem: There is a set of items (e.g., movies) and a group of agents (e.g., passengers on a plane); each agent has some intrinsic utility for each of the items. Our goal is to pick a set of $K$ items that maximize the total derived utility of all the agents (i.e., in our example we are to pick $K$ movies that we put on the plane's entertainment system). However, the actual utility that an agent derives from a given item is only a fraction of its intrinsic one, and this fraction depends on how the agent ranks the item among the chosen, available, ones. We provide a formal specification of the model and provide concrete examples and settings where it is applicable. We show that the problem is hard in general, but we show a number of tractability results for its natural special cases.
1 Introduction
The paper studies selecting a size-K item set for agents whose utility depends on both intrinsic item values and item ranks within the selected set. It formalizes this broad setting, illustrates its applications, and analyzes its computational tractability.
- Many real-world problems require selecting a shared set of items for a group, including movies, journals, facilities, and representatives.
- The selection is constrained because only K items can typically be provided, funded, built, or elected.
- An agent’s utility from a selected item can depend on that item’s rank among the selected items, with possible schemes ranging from best-only to more complex rank-sensitive rules.
- The paper formally defines a model covering these scenarios, gives application examples, and derives efficient algorithms, approximation results, and hardness results.
- The paper develops the model in stages, including formalization, applications, exact complexity, approximation with general utilities, and approximation for non-finicky utilities.
2 The Model
The model selects K items for agents with separable intrinsic utilities and evaluates each selected set using ordered weighted averages of agent-specific item utilities. It supports explicit numerical, approval-based, and Borda-based utilities, with tractability depending strongly on the utility representation.
- Assumptions: Agents have separable preferences: an item’s intrinsic utility is independent of other selected items, although its perceived utility depends on its rank within the selected set.
- Assumptions: The social objective is utilitarian, summing agents’ perceived utilities, while egalitarian variants are left for future research.
- Formal setting: The OWA-Winner problem computes a size-K item set maximizing the agents’ aggregate OWA-based utility.
- Formal setting: An OWA operator sorts K utilities in nonincreasing order and combines them using a nonnegative K-number weight vector.
- Utility representations: Approval-based utilities encode liked items as 1 and others as 0, whereas Borda-based utilities derive values from ordinal rankings using ui(aj) = m −k.
- Utility representations: Borda-based cases are generally easier to approximate than approval-based cases because Borda utilities give relatively high values to a relatively large fraction of items.
- Utility representations: Approval-based utilities can also be non-finicky when each agent approves at least a γ fraction of items, yielding (1, γ)-non-finicky utilities.
3 Applications of the Model
The OWA model represents diverse applications by matching rank weights to how agents receive, enjoy, or evaluate selected items. Examples include voting rules, unavailable items, uncertain consumption, and assignment uncertainty.
- Generalizing Voting Rules: Chamberlin–Courant corresponds to 1-best-OWA-Winner with Borda utilities, while K-best-OWA-Winner with Borda utilities corresponds to K-Borda.
- Generalizing Voting Rules: Proportional Approval Voting corresponds to α-OWA-Winner with the harmonic OWA and approval-based utilities.
- Malfunctioning Items or Unavailable Candidates: When each selected item is independently available with probability p, the expected best available item is modeled by a geometric-progression OWA with initial value p and coefficient 1 −p.
- Uncertainty Regarding How Many Items a User Enjoys: If the number of items an agent enjoys is uniformly distributed, the corresponding OWA weights form an arithmetic progression αi = K −i+1, ignoring normalization.
- Ignorance About Which Item Will Be Assigned to a User: Under complete ignorance about assignment, Wald uses the worst selected item and Hurwicz combines the worst and best outcomes.
- Ignorance About Which Item Will Be Assigned to a User: If assignment probabilities depend on rank, the OWA weights can encode those decreasing probabilities; equal probabilities over the top i items yield i-best OWA.
4 Overview of the Results
The paper finds that OWA-Winner is broadly computationally difficult, while approximation depends on the OWA vector’s monotonicity. Nonincreasing OWAs admit a general greedy guarantee, whereas nonincreasing restrictions are important for hardness and approximation behavior.
- OWA-Winner is NP-hard without restrictions, and remains NP-hard for every nonconstant, nonincreasing family of OWA vectors.
- Polynomial-time solvability without utility restrictions occurs when K is constant or the OWA vector is constant, but hardness begins already for (K −1)-best OWA.
- For nonincreasing OWA vectors, the standard greedy algorithm for submodular optimization achieves approximation ratio (1−1/e), regardless of the agents’ utilities.
- For OWA vectors that are not nonincreasing, the paper presents evidence that good approximation algorithms are unlikely.
5 Computing Exact Solutions
The paper establishes broad hardness results for exact OWA-Winner computation, while identifying polynomial-time cases for fixed K and K-best OWAs. The hardness persists across approval-based and Borda-based utilities in key variants.
- NP-hardness holds for any nonincreasing, nonconstant OWA family, even with approval-based utilities.
- The reductions encode VertexCover and CubicVertexCover instances using vertex items, edge agents, and specially constructed dummy items.
- (K −1)-best-OWA-Winner is NP-complete for approval-based utilities and NP-hard for Borda-based utilities.
- For each fixed k, k-best-OWA-Winner and k-med-OWA-Winner are NP-complete under approval-based or Borda-based utilities.
- OWA-Winner is polynomial-time solvable when K is fixed, when the number of available items is fixed, and for K-best OWAs.
- The paper gives an integer-linear-program formulation of OWA-Winner using item-selection and agent-specific rank-indicator variables.
6 Approximation: General Utilities and Approval Utilities
For nonincreasing OWA vectors, greedy optimization yields a (1−1/e)-approximation regardless of utility representation, while non-nonincreasing vectors can be substantially harder to approximate. Several special cases nevertheless admit positive results, including PTAS and constant-factor guarantees.
- General utilities: (1−1/e) is achieved by a polynomial-time greedy algorithm for nonincreasing OWAs, regardless of the agents’ utility functions.The analysis uses submodularity and nondecreasingness of the induced utility function.
- Approval utilities: Approval-based utilities connect the greedy algorithm with established multiwinner rules, including Sequential Proportional Approval Voting and Proportional Approval Voting.For approval-based utilities, the harmonic OWA corresponds to Proportional Approval Voting.
- Hardness boundaries: The (1−1/e) guarantee is best possible for unrestricted nonincreasing OWAs unless P=NP, because 1-best-OWA-Winner captures MaxCover.The resulting guarantee is approximately 63% of maximum possible satisfaction.
- Hardness boundaries: For OWAs that are not nonincreasing, induced utility functions may fail to be submodular, and several families appear resistant to constant-factor approximation.The paper gives an explicit 2-med-OWA counterexample and relates some OWA families to Densest-K-Subgraph.
- Hardness boundaries: K-med-OWA-Winner has strong conditional inapproximability, while Hurwicz[λ]-OWA-Winner is NP-hard but admits approximation guarantees derived from 1-best-OWA-Winner.A β-approximation for 1-best-OWA-Winner yields a λ·β approximation for Hurwicz[λ]-OWA-Winner.
- Positive special cases: A PTAS exists for (K−f(K))-best OWA-Winner when f(K)=o(K), contrasting with the hardness suggested for OWAs that place zero weight on top positions.The comparison highlights the importance of whether the OWA is nonincreasing.
7 Approximation: Non-Finicky Utilities
For non-finicky utilities and OWAs concentrating weight on a constant number of top positions, the paper develops Algorithm 2 and obtains efficient, strong approximation guarantees, including PTAS results for several natural utility classes.
- Algorithm 2: Algorithm 2 selects K items greedily, prioritizing items highly ranked by agents with remaining free slots among their top x = γm items.Each agent initially receives ℓ free slots, and selecting a sufficiently highly ranked item consumes a slot.
- Setting: The algorithm targets nonincreasing OWAs with at most ℓ nonzero top coefficients and (β, γ)-non-finicky utilities.The non-finicky condition supplies enough sufficiently valuable items for the selection process to maintain flexibility.
- Approximation guarantees: β(1 − exp(−γK/ℓ)) is the approximation guarantee established for Algorithm 2 when γm ≥ ℓ.The theorem applies to a nonincreasing OWA whose first ℓ entries may be nonzero.
- Approximation guarantees: The guarantee is particularly useful when K is large relative to ℓ, while brute-force search for small K combined with Algorithm 2 yields a PTAS.The paper uses this combination to obtain polynomial-time approximation schemes in selected settings.
- PTAS results: For Borda-based utilities and (1, γ)-non-finicky utilities with constant γ, the paper proves a PTAS for OWAs supported on the top ℓ positions.The result is stated for fixed ℓ and includes the corresponding geometric-progression OWA case.
- Conclusion: The paper concludes that natural utility and OWA classes remain efficiently and accurately solvable despite the intrinsic hardness of OWA-Winner.It also notes that Borda-based utilities generally admit better approximation results than approval-based utilities because many items receive relatively high utility.
8 Related Work
The paper situates OWA-Winner among group recommendation, facility location, voting, social choice, decision theory, and related OWA-based approaches, while emphasizing differences in how utilities are aggregated.
- Decision-theoretic connections: OWA operators also appear in multicriteria decision making, social choice, and rank-dependent expected utility, although the paper notes that its selection setting does not directly transfer to those fields.The authors explicitly caution that applicability is not obvious because those settings do not select criteria, agents, or consequences in the same way.
- OWA-based voting work: Several voting studies use OWAs to aggregate voter or candidate scores, whereas this paper uses OWAs to weight an agent’s item utilities by their ranks among selected items.The shared high-level idea is that OWAs interpolate between sum, minimum, and maximum aggregation rules.
- Voting and social choice: The model recovers established settings including Chamberlin–Courant proportional representation, Proportional Approval Voting, and variants of budgeted social choice.These connections are presented as particular cases of the general model.
- Group recommendation: Group recommender systems recommend item sets or sequences to groups using the preferences of all group members.The paper identifies average-user and preference-aggregation approaches as two mainstream directions.
- Facility location: Facility location is closely related to 1-best-OWA-Winner, but typically minimizes dissatisfaction rather than maximizing satisfaction and often evaluates the worst-off agent.Its utilitarian variant is called k-median.
9 Summary
The paper presents a broad collective-item selection model and studies how utility assumptions and OWA choices affect computational feasibility. It identifies non-finicky utilities as a setting with especially favorable approximation results, while leaving several approximation questions open.
- The model is general, covers known frameworks, and applies to committee elections, group recommendation, and other collective-item domains.
- Non-finicky utilities model agents that are relatively “easy to please” and may apply beyond this framework.
- Approximation results vary with utility assumptions and OWA-vector choices, with especially positive results for non-finicky utilities.
- SPAV is shown to be a greedy approximation algorithm for the Proportional Approval Voting election rule.
- The approximability of arithmetic-progression OWAs remains an open problem, including whether PTASs exist under non-finicky utilities.
A Proofs of Theorem 7
The proof establishes NP-hardness for (K −1)-best-OWA-Winner with Borda-based utilities by reducing VertexCover to a constructed winner-selection instance. The construction forces optimal solutions to exclude auxiliary items and include both dummy items, making the selected vertices encode a vertex cover.
- Theorem 7 states that (K −1)-best-OWA-Winner is NP-hard even for Borda-based utilities.
- The reduction maps a VertexCover instance with graph G and integer K to an instance I′ of (K −1)-best-OWA-Winner.
- The constructed item set contains graph vertices, two dummy items d1 and d2, and auxiliary items H.
- The agents comprise edge-associated pairs NE and paired dummy agents in N1 through Ny, whose preference orders encode the reduction.
- Replacing any selected auxiliary item h ∈ H with a vertex increases the total utility of the corresponding dummy agents, so an optimum excludes H.
- Replacing a selected vertex with d1, and analogously with d2, increases utility, forcing both dummy items into every optimal solution.
- Thus every optimal winner set consists of d1, d2, and K vertices, while dummy-agent utility is invariant over the selected vertices.
- A vertex cover yields utility at least nx(K + 4), while failure to cover an edge yields a lower bound contradiction, completing the equivalence.