Electing a committee with dominance constraints

DOI10.1007/S10479-021-04128-7MaRDI QIDQ2095947zbMATH OpenOpenAlexFDO

Authors Egor Ianovski

Publication date 15 November 2022

Published in Annals of Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

computational social choicediversity constraintsmultiwinner electionsvoting

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Social choice (91B14)

Abstract: We consider the problem of electing a committee of $k$ candidates, subject to some constraints as to what this committee is supposed to look like. In our framework, the candidates are given labels as an abstraction of a politician's religion, a film's genre, a song's language, or other attribute, and the election outcome is constrained by interval constraints -- of the form "Between 3 and 5 candidates with label X" -- and dominance constraints -- "At least as many candidates with label X as with label Y". The problem is, what shall we do if the committee selected by a given voting rule fails these constraints? In this paper we argue how the logic underlying weakly-separable and best-$k$ rules can be extended into an ordering of committees, and study the question of how to select the best valid committee with respect to this order. The problem is NP-hard, but we show the existence of a polynomial time solution in the case of tree-like constraints, and a fixed-parameter tractable algorithm for the general case.

Recommendations

• Committee Selection with a Weight Constraint Based on Lexicographic Rankings of Individuals
• Consensus rules for committee elections
• How hard is it to tell which is a Condorcet committee?
• Committee selection under weight constraints
• Committee selection with multimodal preferences

Cites work

• An Analysis of Simple Voting Systems for Electing Committees
• An axiomatic characterization of Borda's k-choice function
• Approval balloting for multi-winner elections
• How to choose a non-controversial list with \(k\) names
• Integer Programming with a Fixed Number of Variables
• Majority committees
• Multi-attribute proportional representation
• Multiwinner analogues of the plurality rule: axiomatic and algorithmic perspectives
• On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
• On stable rules for selecting committees
• Preference extension rules for ranking sets of alternatives with a fixed cardinality
• Properties of multiwinner voting rules
• Scoring rules over subsets of alternatives: consistency and paradoxes
• Some startling inconsistencies when electing committees
• The Condorcet criterion and committee selection

Cited in

(15)

• The Condorcet criterion and committee selection
• Consensus rules for committee elections
• Democracy for polarized committees: the tale of Blotto's lieutenants
• Some startling inconsistencies when electing committees
• Maximizing single attribute diversity in group selection
• Selecting diverse committees with candidates from multiple categories
• Committee Selection with a Weight Constraint Based on a Pairwise Dominance Relation
• Committee Selection with a Weight Constraint Based on Lexicographic Rankings of Individuals
• Committee selection under weight constraints
• How hard is it to tell which is a Condorcet committee?
• Committee selection with multimodal preferences
• Multi-winner approval voting with grouped voters
• On the price of diversity for multiwinner elections under (weakly) separable scoring rules
• Participatory budgeting with project groups
• Cooperative games with diversity constraints

This page was built for publication: Electing a committee with dominance constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2095947)