Algorithmics of Egalitarian versus Equitable Sequences of Committees

Eva Michelle Deltl, Till Fluschnik, Robert BredereckIJCAI 2023 · DOI

TL;DR

This paper delves into the computational complexity of selecting sequences of committees over multiple time periods (or "levels"). It introduces two fairness criteria: "egalitarian" (ensuring a minimum satisfaction for all) and "equitable" (ensuring a precise level of satisfaction for all). The authors analyze the conditions under which finding such committee sequences is computationally feasible, particularly when considering parameters like the number of agents, candidates, and desired satisfaction levels.

What Problem Does This Paper Address?

Imagine you need to form a series of committees over time, perhaps for different stages of a project or different days of an event. Each agent (like a stakeholder or participant) has preferences for candidates in each "level" (time period). The challenge is to select committees that are fair to everyone. The paper defines two fairness notions:

  • Egalitarian: Every agent should be satisfied in at least a certain number of levels. This is like ensuring everyone gets at least a minimum amount of what they want.
  • Equitable: Every agent should be satisfied in exactly a certain number of levels. This aims for perfect fairness, where everyone gets the same precise amount of satisfaction.

The core problem is to determine how computationally difficult it is to find such committee sequences, especially when we consider various parameters like the number of agents, candidates, committee size, number of levels, and the desired satisfaction thresholds. This is crucial because real-world scenarios often involve trade-offs between fairness and computational feasibility.

Methods

The paper employs techniques from parameterized complexity theory to analyze the computational hardness of these problems. This means they investigate how the difficulty of finding a solution changes as specific parameters (like the number of agents, n, or the number of levels, τ) vary.

Key methods include:

  • Reductions: They reduce known hard problems (like 3-SAT and CBVC) to their committee selection problems to prove NP-hardness. Conversely, they reduce their problems to known tractable problems to show polynomial-time solvability.
  • Data Reduction Rules: These are algorithms that simplify an instance of the problem without changing its solution. This is a crucial step in kernelization, where the goal is to shrink the input size based on parameters.
  • Integer Programming: For some cases, they formulate the problem as an integer program, which can then be solved efficiently if certain parameters are small.
  • Dynamic Programming: Used to solve certain variants of the problem efficiently when specific parameters are bounded.

Datasets

Not discussed in the paper. The paper focuses on theoretical complexity analysis and does not use or introduce specific datasets.

Key Insights and Ideas

  • Subtle Differences in Fairness: While "egalitarian" and "equitable" sound similar, they lead to significant differences in computational complexity, particularly in how easily the problem can be simplified (kernelization).
  • The Power of Two Levels: For egalitarian committee selection, just two levels (τ=2) already make the problem NP-hard. However, for equitable selection, two levels are still efficiently solvable. This highlights how strict equality requirements can be harder to satisfy computationally.
  • Parameter Sensitivity: The tractability of these problems is highly sensitive to the chosen parameters. For instance, having a small number of agents (n) makes the problem tractable, but having a small number of candidates (m) does not.
  • Kernelization Trade-offs: The paper shows that egalitarian committee selection can be "kernelized" (reduced to a smaller instance) based on the number of agents and desired satisfaction levels (n+y). However, equitable selection does not seem to admit such a polynomial-sized kernel, suggesting it's harder to preprocess.

Key Results

The paper presents a detailed complexity landscape for Egalitarian Committee Sequence Election (GCSE) and Equitable Committee Sequence Election (QCSE) across various parameters. Some highlights include:

  • Tractability: Both GCSE and QCSE are efficiently solvable (polynomial time) if the number of levels (τ) is 1.
  • NP-Hardness:
    • GCSE becomes NP-hard for τ=2.
  • GCSE and QCSE are NP-hard even for a constant number of agents (n) or a constant number of candidates (m).
  • GCSE is NP-hard for τ ≥ 3.
  • Kernelization:
    • GCSE admits a polynomial kernel for parameters n+y.
  • QCSE does not seem to admit a polynomial kernel for n or n+y, suggesting it's harder to preprocess.
  • Fixed-Parameter Tractability (FPT): Both problems are FPT when parameterized by k+τ (committee size and number of levels), meaning they can be solved efficiently if these parameters are small.

Limitations and Future Work

  • Kernelization for QCSE: A key open question is whether QCSE can be kernelized polynomially with respect to n+y, as it seems unlikely based on current findings.
  • Generalizations: The paper introduces a more general framework (BICMCE) and suggests exploring its parameterized complexity, especially variants that differ from GCSE and QCSE.
  • Budget Constraints: Future work could explore global budget constraints (e.g., total committee size across all levels) instead of level-specific ones.
  • Fairness Beyond Score: Investigating fairness notions where the difference in satisfaction scores between any two agents is bounded by y.
  • Kernel for k: The paper poses the question of whether GCSE or QCSE admit a polynomial kernel for k (committee size) when τ is constant.

Summary updated

BibTeX
@inproceedings{deltl2023algorithmics,
  author = {Eva Michelle Deltl and Till Fluschnik and Robert Bredereck},
  title = {{Algorithmics of Egalitarian versus Equitable Sequences of Committees}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/295},
}
Figure