Multiwinner Voting with Fairness Constraints

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

Introduction

Multiwinner voting is a cornerstone of collective decision-making, used to select a fixed-size committee of $k$ candidates from a larger pool based on voter preferences. Beyond political elections, this problem appears in diverse contexts such as product recommendation systems, news aggregation, and hiring committees. While traditional voting rules aim to maximize total voter satisfaction, they often fail to ensure fair representation for minority groups, particularly when candidates possess multiple overlapping attributes like gender, ethnicity, and political affiliation.

The Challenge of Overlapping Attributes

Most existing "proportional representation" methods are designed for single, disjoint attributes (e.g., party lists). However, real-world candidates are intersectional; a candidate might belong to several groups simultaneously. This paper addresses the Constrained Monotone Submodular (MS) Multiwinner Voting Problem, which seeks to maximize a score function while satisfying lower and upper representation bounds for various, potentially overlapping, groups.

The complexity of this task is fundamentally tied to the parameter $\Delta$, defined as the maximum number of groups to which any single candidate belongs. When groups are disjoint ($\Delta = 1$), the problem is relatively tractable. However, as the degree of overlap increases ($\Delta \geq 3$), even finding a committee that satisfies all fairness constraints becomes NP-hard.

Algorithmic Framework

The authors propose a robust framework capable of handling a wide class of monotone submodular score functions—a category that includes diminishing-return objectives like the Chamberlin-Courant rule and various Ordered Weighted Averaging (OWA) rules.

Key Approaches:

  1. Continuous Greedy and Rounding: For general constraints, the authors utilize a multilinear extension to transform the discrete selection problem into a continuous optimization space. A continuous greedy process finds a fractional solution, which is then rounded back to a discrete committee.
  2. Dependent Rounding: In the case of disjoint groups ($\Delta = 1$), a randomized rounding technique yields a $(1 - 1/e)$-approximation, which is theoretically optimal for submodular maximization.
  3. Bi-criterion Approximation: For overlapping groups ($\Delta \geq 2$), the authors develop a bi-criterion algorithm. This approach guarantees a high voting score (near-optimal) while allowing for a small, controlled violation of the fairness constraints.

Theoretical Guarantees

The theoretical landscape of the problem is summarized in the table below, showing how approximation ratios and computational hardness shift with the complexity of group overlaps.

Theoretical approximation guarantees and hardness results for common multiwinner voting rules under varying degrees of group overlap ($\Delta$).

Empirical Evaluation

To test the framework, the authors conducted synthetic simulations using a 2D Euclidean model. In this model, 400 voters and 120 candidates are placed in a 2D square, with voter preferences determined by their proximity to candidates. To simulate real-world bias, candidates were sampled non-uniformly across quadrants.

The results demonstrate that unconstrained voting rules often exacerbate inequality, producing high Gini indices (a measure of inequality). In contrast, the proposed constrained framework effectively reduces inequality while maintaining high voter satisfaction.

Experimental results comparing Gini index (inequality) and percentage of optimal score across different voting rules and constraint types.

A significant finding is the low "price of fairness." As shown in the empirical results, constrained versions of rules like $\alpha$-CC and $\beta$-CC often achieved 100% of the optimal unconstrained score while simultaneously reducing the Gini index to zero. This suggests that fair representation can often be achieved without sacrificing the overall quality of the selected committee.

Conclusion

This research provides the first comprehensive algorithmic framework for multiwinner voting with multiple overlapping fairness constraints. By demonstrating that the "price of fairness" is often negligible in practice, the authors offer a powerful tool for policy-makers and system designers to ensure diverse and equitable representation in automated and human-led decision-making processes.

Reference: Celis, L. E., Huang, L., & Vishnoi, N. K. (2018). Multiwinner Voting with Fairness Constraints. Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18).

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