Multiwinner Voting with Fairness Constraints.

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

TL;DR

This paper introduces a general algorithmic framework for multiwinner voting that can enforce fairness constraints across multiple sensitive attributes, addressing the bias that can arise in traditional voting systems. They provide theoretical guarantees on approximation algorithms and hardness of approximation, showing that fairness can be achieved with a minimal loss in score.

What Problem Does This Paper Address?

Selecting a committee or a subset of items (e.g., candidates for office, movies for a streaming service) based on voter preferences is a common problem. Traditional multiwinner voting rules aim to maximize a collective score based on these preferences. However, these rules can inadvertently lead to biased outcomes, under- or over-representing certain groups (e.g., by gender, ethnicity, or political affiliation). This paper tackles the challenge of designing multiwinner voting systems that not only select a high-scoring committee but also ensure fairness with respect to specified sensitive attributes, even when these attributes are complex and non-disjoint.

Methods

The authors propose a flexible algorithmic framework that allows for the specification of fairness constraints on the selected committee. These constraints can be applied to multiple, potentially overlapping, attributes. They then study the computational complexity of this "constrained multiwinner voting problem," particularly for score functions that are monotone and submodular.

Key techniques include:

  • Multilinear Extension: A standard tool in submodular optimization, used to relax the discrete problem into a continuous one, enabling the use of greedy algorithms.
  • Dependent Rounding: Techniques like randomized swap rounding are employed to convert fractional solutions back into discrete committee selections while preserving approximation guarantees.
  • Reductions: Hardness results are established by reducing known NP-hard problems (like hypergraph matching and set multi-cover) to the constrained voting problem.
  • Bi-criterion Approximation: For certain cases, algorithms are developed that provide a good score while only slightly violating the fairness constraints.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and uses synthetic preference generation for empirical evaluation.

Key Insights and Ideas

  • Generalizing Fairness: The framework is powerful because it can handle complex fairness notions, including multiple, non-disjoint attributes (e.g., ensuring fairness for both gender and ethnicity simultaneously). This moves beyond simpler proportionality constraints.
  • Feasibility is Hard: For more than two attributes or complex group structures ($\Delta \ge 3$), simply checking if a fair committee exists can be NP-hard. This highlights the inherent difficulty of enforcing fairness in complex scenarios.
  • Approximation is Achievable: Despite the hardness results, the authors demonstrate that constant-factor approximation algorithms exist for many settings, meaning we can get close to the optimal fair outcome.
  • "Price of Fairness" is Small: Empirical results suggest that adding fairness constraints doesn't drastically reduce the overall score of the selected committee, often resulting in a score very close to the unconstrained optimal. This implies that fairness and good outcomes are not mutually exclusive.

Key Results

  • Hardness Results: For $\Delta \ge 3$ (where $\Delta$ is the maximum number of groups a candidate can belong to), the feasibility problem is NP-hard. Even for feasible instances, approximating the optimal score is hard, with factors like $\Omega(\log \Delta / \Delta)$ for SNTV.
  • Algorithmic Results:
    • For $\Delta = 1$ (disjoint groups), a $(1 - 1/e)$-approximation algorithm is presented, matching the hardness bound.
  • For $\Delta \ge 2$, a bi-criterion algorithm achieves a score of $(1 - 1/e - o(1))$OPT while satisfying fairness constraints with small multiplicative violations.
  • For cases with only lower bounds ($l_i=0$), a $(1/\Delta+1, 2)$-approximation algorithm is provided.
  • For $\Delta = 2$ and SNTV, an exact polynomial-time algorithm exists.
  • For constant $p$ (number of groups), a $(1 - 1/e)$-approximation algorithm is presented.
  • Empirical Findings: Simulations show that unconstrained voting rules can exhibit significant bias (high Gini index), while the proposed constrained approach effectively eliminates this bias, achieving a Gini index close to zero, with only a minor reduction in the committee's score.

Limitations and Future Work

  • Computational Complexity: While approximation algorithms are provided, the problem remains computationally challenging, especially for complex attribute structures.
  • Specific Voting Rules: The paper focuses on monotone submodular score functions and specific rules like SNTV, $\alpha$-CC, and $\beta$-CC. Extending the framework to other voting rules, especially those that don't rely on score functions (like STV), is left as future work.
  • "Price of Fairness" Quantification: While empirical results suggest the price of fairness is small, a more general theoretical understanding of this trade-off across different settings and rules is an open research direction.
  • Real-world Data: The empirical evaluation uses synthetic data. Applying and validating the framework on real-world datasets would be a valuable next step.

Summary updated

Abstract

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.
BibTeX
@inproceedings{celis2018multiwinner,
  author = {L. Elisa Celis and Lingxiao Huang and Nisheeth K. Vishnoi},
  title = {{Multiwinner Voting with Fairness Constraints.}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/20},
}
Figure