DiRe Committee : Diversity and Representation Constraints in Multiwinner Elections

Kunal ReliaIJCAI 2022 · DOI

TL;DR

This paper introduces a novel framework, DiRe Committee Winner Determination (DRCWD), to select committees in multiwinner elections that balance both candidate diversity and voter representation. It addresses the critical issue that existing models often overlook the distinct attributes of voters, potentially under-representing certain populations. The authors demonstrate the computational hardness of this problem and propose an efficient heuristic algorithm that performs well in practice.

What Problem Does This Paper Address?

Selecting a committee in multiwinner elections is a common task, from political appointments to movie recommendations. Traditionally, fairness in these elections has focused on ensuring diversity among candidates (e.g., gender, ethnicity). However, this paper highlights a crucial oversight: voters themselves can be segmented into distinct populations based on attributes (e.g., geographic location, demographics). Models that solely consider candidate attributes can inadvertently marginalize smaller voter populations. For instance, a committee that is diverse in terms of candidate attributes might not adequately represent the preferences of a specific voter group. This paper aims to bridge this gap by developing a model that explicitly considers both candidate diversity and voter representation constraints simultaneously, recognizing that these are distinct, albeit related, concepts.

Methods

The core contribution is the formalization of the DiRe Committee Winner Determination (DRCWD) problem. This model incorporates:

  • Candidate Attributes and Diversity Constraints: Groups of candidates are defined based on attributes (e.g., gender), with lower bounds (lδ) specifying the minimum number of candidates required from each group.
  • Voter Attributes and Representation Constraints: Voters are segmented into populations based on their attributes (e.g., state). Crucially, the model uses pre-computed "winning committees" (Wp) for each population and imposes lower bounds (lβ) on how many candidates from these Wp must be included in the final committee. This distinguishes it from proportional representation schemes that dynamically group voters.
  • Computational Complexity Analysis: The authors prove that the DRCDW problem is NP-hard under various settings, using reductions from the vertex cover problem. They also investigate inapproximability and parameterized complexity.
  • Heuristic Algorithm: To address the computational hardness, a two-stage heuristic algorithm is proposed. This algorithm uses a DiReGraph representation to model constraints and candidates, followed by a backtracking search with heuristics like "minimum-remaining-values" and "most-favorite-candidates" to efficiently find feasible committees.

Datasets

The paper evaluates its heuristic algorithm on:

  • Real Datasets:
    • Eurovision Dataset: 26 countries ranking songs, with candidate attributes (song region, language) and voter attributes (voter region).
  • United Nations Resolutions Dataset: 193 countries voting on resolutions, with candidate attributes (resolution topic, significance) and voter attributes (continent).
  • Synthetic Datasets:
    • SynData 1: Generated complete preferences using the Mallows model, varying the number of candidate (μ) and voter (π) attributes, and the number of partitions within attributes.
  • SynData 2: Similar to SynData 1, but varying voter cohesiveness (Φ) while keeping μ and π fixed.

Key Insights and Ideas

  • Diversity vs. Representation are Distinct: A key insight is that having a diverse set of candidates (e.g., a female candidate) does not automatically imply representation for a specific voter group (e.g., female voters). These are separate goals that need explicit modeling.
  • Voter Attributes Matter: Ignoring voter attributes can lead to systematic under-representation of smaller populations, even if candidate diversity is achieved.
  • Computational Hardness: The introduction of representation constraints, in addition to diversity constraints, significantly increases the computational complexity of committee selection, making it NP-hard in many realistic scenarios.
  • Heuristic Efficiency: Despite the theoretical hardness, the proposed heuristic algorithm demonstrates practical efficiency, finding feasible committees quickly on tested datasets, often outperforming brute-force or ILP approaches.
  • Cohesiveness and Feasibility: Voter cohesiveness (how similar voters' preferences are) plays a significant role. Higher cohesiveness generally leads to more feasible committees and easier constraint satisfaction.

Key Results

  • NP-Hardness: The DRCDW problem is proven to be NP-hard for various combinations of candidate/voter attributes and scoring rules, even when constraints are minimal (e.g., requiring at least one from each group/population).
  • Heuristic Performance: The heuristic algorithm successfully finds feasible DiRe committees for a significant portion of instances. For example, on synthetic data, it timed out on only 18.90% of instances within 2000 seconds, compared to 93.71% for a brute-force approach.
  • Constraint Impact: As the number of candidate and voter attributes increases, the proportion of feasible instances decreases.
  • Utility Trade-off: Enforcing constraints can lead to a loss in utility, with the mean utility ratio of constrained to unconstrained committees ranging from 0.43 to 0.99 depending on the dataset and constraints.
  • Monroe and B-CC Superiority: The Monroe and B-CC rules generally perform better at satisfying representation constraints compared to k-Borda, as they are designed with voter representation in mind.

Limitations and Future Work

  • Constraint Setting: The paper acknowledges that the way diversity and representation constraints are set can significantly impact fairness, and determining "fair" constraint settings remains an open challenge.
  • Mathematical Guarantees: Providing stronger mathematical guarantees for the existence of DiRe committees is an area for future work.
  • Correlation vs. Causation: Further research is needed to formally establish when diversity implies representation, or vice versa.
  • Voter Preference Structure: The impact of voter preference structures (e.g., cohesiveness, single-peakedness) on the complexity and tractability of the model needs further exploration.
  • Complexity Classification: A complete classification of the complexity of DRCDW with respect to different committee selection rules (beyond monotone, separable, and submodular) remains an open question.
  • Real-world Stipulations: The current hardness proofs often rely on simplified assumptions about attribute partitions (e.g., allowing a single group per attribute). Future work could address more realistic scenarios where attributes partition candidates/voters into multiple groups.

Summary updated

BibTeX
@inproceedings{relia2022dire,
  author = {Kunal Relia},
  title = {{DiRe Committee : Diversity and Representation Constraints in Multiwinner Elections}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/714},
}
Figure