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:
- 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.
- 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.
- 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.
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.
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