Finding a collective set of items: from proportional multirepresentation to group recommendation
From MaRDI portal
(Redirected from Publication:334810)
Abstract: 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 items that maximize the total derived utility of all the agents (i.e., in our example we are to pick 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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 2079405 (Why is no real title available?)
- scientific article; zbMATH DE number 1559542 (Why is no real title available?)
- A threshold of ln n for approximating set cover
- An analysis of approximations for maximizing submodular set functions—I
- An axiomatic characterization of Borda's k-choice function
- Approval balloting for multi-winner elections
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
- Facility location problems: a parameterized view
- Graph expansion and the unique games conjecture
- Improved approximation algorithms for capacitated facility location problems
- OWA-based extensions of the Chamberlin-Courant rule
- On ordered weighted averaging aggregation operators in multicriteria decisionmaking
- On solving linear programs with the ordered weighted averaging objective.
- On the Structure of Polynomial Time Reducibility
- On the approximability of Dodgson and Young elections
- On the complexity of achieving proportional representation
- On the computation of fully proportional representation
- PTAS for minimax approval voting
- Polynomial integrality gaps for strong SDP relaxations of densest \(k\)-subgraph
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- Socially desirable approximations for dodgson’s voting rule
- Some APX-completeness results for cubic graphs
- The Santa Claus problem
- The complexity of fully proportional representation for single-crossing electorates
Cited in
(23)- Justified representation in approval-based committee voting
- Consistent approval-based multi-winner rules
- Axiomatic characterization of committee scoring rules
- Multi-attribute proportional representation
- Properties of multiwinner voting rules
- Proportional approval voting, harmonic \(k\)-median, and negative association
- Multiwinner analogues of the plurality rule: axiomatic and algorithmic perspectives
- Core-stable committees under restricted domains
- More effort towards multiagent knapsack
- Multicriteria decision making
- Group recommendations: axioms, impossibilities, and random walks
- Even more effort towards improved bounds and fixed-parameter tractability for multiwinner rules
- Utilitarian welfare and representation guarantees of approval-based multiwinner rules
- Weighted representative democracy
- Preference elicitation and robust winner determination for single- and multi-winner social choice
- Justified representation in multiwinner voting: axioms and algorithms
- Sum-of-squares lower bounds for densest \(k\)-subgraph
- Interactive optimization of submodular functions under matroid constraints
- Robustness of approval-based multiwinner voting rules
- Phragmén's voting methods and justified representation
- Approval-based apportionment
- The maximin support method: an extension of the d'Hondt method to approval-based multiwinner elections
- Computing a small agreeable set of indivisible items
This page was built for publication: Finding a collective set of items: from proportional multirepresentation to group recommendation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q334810)
