Finding a collective set of items: from proportional multirepresentation to group recommendation

DOI10.1016/j.artint.2016.09.003zbMath1406.91135arXiv1402.3044OpenAlexW2521628013MaRDI QIDQ334810

Jérôme Lang, Piotr Faliszewski, Piotr Skowron

Publication date: 1 November 2016

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1402.3044

zbMATH Keywords

electionscomputational complexityapproximationvotingChamberlin-Courant ruleordered weighted averageproportional representation

Mathematics Subject Classification ID

Integer programming (90C10) Voting theory (91B12) Utility theory (91B16) Group preferences (91B10)

Related Items

Properties of multiwinner voting rules ⋮ Justified representation in approval-based committee voting ⋮ Weighted representative democracy ⋮ FPT approximation schemes for maximizing submodular functions ⋮ Multiwinner analogues of the plurality rule: axiomatic and algorithmic perspectives ⋮ Even more effort towards improved bounds and fixed-parameter tractability for multiwinner rules ⋮ Phragmén's voting methods and justified representation ⋮ Core-stable committees under restricted domains ⋮ More effort towards multiagent knapsack ⋮ The maximin support method: an extension of the d'Hondt method to approval-based multiwinner elections ⋮ Approval-based apportionment ⋮ Interactive optimization of submodular functions under matroid constraints ⋮ Axiomatic characterization of committee scoring rules ⋮ Multi-attribute proportional representation ⋮ Proportional Approval Voting, Harmonic k-median, and Negative Association ⋮ Consistent approval-based multi-winner rules ⋮ Parameterized shifted combinatorial optimization ⋮ Preference elicitation and robust winner determination for single- and multi-winner social choice ⋮ Robustness of approval-based multiwinner voting rules ⋮ Utilitarian welfare and representation guarantees of approval-based multiwinner rules ⋮ Unnamed Item ⋮ Computing a small agreeable set of indivisible items

Uses Software

• PrefLib

Cites Work

• An axiomatic characterization of Borda's \(k\)-choice function
• Some APX-completeness results for cubic graphs
• On the approximability of Dodgson and Young elections
• Improved approximation algorithms for capacitated facility location problems
• On solving linear programs with the ordered weighted averaging objective.
• 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
• Detecting high log-densities
• Graph expansion and the unique games conjecture
• The Santa Claus problem
• PTAS for Minimax Approval Voting
• A threshold of ln n for approximating set cover
• OWA-Based Extensions of the Chamberlin–Courant Rule
• 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
• On the Structure of Polynomial Time Reducibility
• An analysis of approximations for maximizing submodular set functions—I
• Socially desirable approximations for dodgson’s voting rule
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item