Multiwinner Voting with Fairness Constraints

By L. Elisa Celis, Lingxiao Huang, Nisheeth K. Vishnoi. 2017

121 citations recorded by the source corpus.

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.

Subfields: Computational Theory and Mathematics, Economics and Econometrics, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Economics and Econometrics

In Management Science and Operations Research

Citations in the corpus

Stable and Fair Classification (2019, background): “Another potential direction is to study stability and fairness in other automated decision-making tasks, e.g., ranking [17], personalization [15], data summarization [16], and multiwinner voting [14].”
Algorithmic Fairness (2020, background): “[31] and [22] use similar notions for fairness in multiwinner voting.”
A Review on Fairness in Machine Learning (2022, background): “Celis et al. [39] and Bredereck et al. [30] use similar notions for fairness in multiwinner voting.”
Fair Algorithms for Clustering (2019, background): “Many works in fairness [13, 14,18,37] work within the disparate impact (DI) doctrine [23].”
Classification with Fairness Constraints: A Meta-Algorithm with Provable Guarantees (2018, unknown): “To handle this problem, we consider linear fairness constraints, which have been considered in other fundamental algorithmic problems including sampling [11, 10, 13], ranking [14], voting [12], and personalization [15].”
Toward Controlling Discrimination in Online Ad Auctions (2019, methodology): “Finally, a framework approach to fairness constraints has shown to be effective in various other applications such as classification [8,32,56], selection of representatives [9], and personalization [14].”