Finding a collective set of items: from proportional multirepresentation to group recommendation
From MaRDI portal
Publication:334810
DOI10.1016/J.ARTINT.2016.09.003zbMATH Open1406.91135arXiv1402.3044OpenAlexW2521628013MaRDI QIDQ334810FDOQ334810
Authors: Piotr Skowron, Piotr Faliszewski, Jérôme Lang 
Publication date: 1 November 2016
Published in: Artificial Intelligence (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1402.3044
Recommendations
computational complexityelectionsapproximationvotingChamberlin-Courant ruleordered weighted averageproportional representation
Cites Work
- A threshold of ln n for approximating set cover
- Title not available (Why is that?)
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- Some APX-completeness results for cubic graphs
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- On ordered weighted averaging aggregation operators in multicriteria decisionmaking
- Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
- On the Structure of Polynomial Time Reducibility
- Title not available (Why is that?)
- Improved approximation algorithms for capacitated facility location problems
- On solving linear programs with the ordered weighted averaging objective.
- An analysis of approximations for maximizing submodular set functions—I
- The Santa Claus problem
- An axiomatic characterization of Borda's \(k\)-choice function
- On the approximability of Dodgson and Young elections
- Facility location problems: a parameterized view
- On the complexity of achieving proportional representation
- The complexity of fully proportional representation for single-crossing electorates
- Approval balloting for multi-winner elections
- On the computation of fully proportional representation
- Graph expansion and the unique games conjecture
- PTAS for minimax approval voting
- OWA-based extensions of the Chamberlin-Courant rule
- Title not available (Why is that?)
- Socially desirable approximations for dodgson’s voting rule
- Polynomial integrality gaps for strong SDP relaxations of densest \(k\)-subgraph
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
Uses Software
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)
