Multiwinner Voting with Fairness Constraints
Multiwinner voting rules are used to select a small representative subset of candidates or items from a larger set given the preferences of voters. However, if candidates have sensitive attributes such as gender or ethnicity (when selecting a committee), or specified types such as political leaning (when selecting a subset of news items), an algorithm that chooses a subset by optimizing a multiwinner voting rule may be unbalanced in its selection -- it may under or over represent a particular gender or political orientation in the examples above. We introduce an algorithmic framework for multiwinner voting problems when there is an additional requirement that the selected subset should be "fair" with respect to a given set of attributes. Our framework provides the flexibility to (1) specify fairness with respect to multiple, non-disjoint attributes (e.g., ethnicity and gender) and (2) specify a score function. We study the computational complexity of this constrained multiwinner voting problem for monotone and submodular score functions and present several approximation algorithms and matching hardness of approximation results for various attribute group structure and types of score functions. We also present simulations that suggest that adding fairness constraints may not affect the scores significantly when compared to the unconstrained case.
Code (1)
Tasks
AttributeFairnessSimilar Papers 제목 키워드 기반
On the Complexity of Finding a Diverse and Representative Committee using a Monotone, Separable Positional Multiwinner Voting Rule
Fairness in multiwinner elections, a growing line of research in computational social choice, primarily concerns the use of constraints to ensure fairness. Recent work proposed a model to find a diverse \emph{and} repres…
FairnessSubset Selection Based On Multiple Rankings in the Presence of Bias: Effectiveness of Fairness Constraints for Multiwinner Voting Score Functions
We consider the problem of subset selection where one is given multiple rankings of items and the goal is to select the highest ``quality'' subset. Score functions from the multiwinner voting literature have been used to…
FairnessTemporal Fairness in Multiwinner Voting
Multiwinner voting captures a wide variety of settings, from parliamentary elections in democratic systems to product placement in online shopping platforms. There is a large body of work dealing with axiomatic character…
FairnessFairly Allocating Utility in Constrained Multiwinner Elections
Fairness in multiwinner elections is studied in varying contexts. For instance, diversity of candidates and representation of voters are both separately termed as being fair. A common denominator to ensure fairness acros…
DiversityFairnessUtilitarian Welfare and Representation Guarantees of Approval-Based Multiwinner Rules
To choose a suitable multiwinner voting rule is a hard and ambiguous task. Depending on the context, it varies widely what constitutes the choice of an ``optimal'' subset of alternatives. In this paper, we provide a quan…