Happiness Maximizing Sets under Group Fairness Constraints (Technical Report)

Jiping Zheng, Yuan Ma, Wei Ma, Yanhao Wang, Xiaoyang Wang

TL;DR

This paper introduces "FairHMS," a novel approach to selecting representative subsets of data that not only maximize overall "happiness" (utility) but also ensure fair representation across predefined demographic groups. They developed an exact algorithm for 2D data and an approximation algorithm for higher dimensions, demonstrating their effectiveness in real-world scenarios where fairness is critical.

What Problem Does This Paper Address?

In many data-driven applications, like hiring or admissions, we need to select a small, representative subset of candidates (tuples) from a larger database. The "Happiness Maximizing Set" (HMS) problem aims to find a subset that best represents diverse user preferences (utility functions). However, existing HMS methods can inadvertently lead to biased selections, under-representing certain demographic groups (e.g., by gender or race). This can perpetuate societal biases and lead to unfair outcomes. This paper tackles this critical gap by proposing "FairHMS," which explicitly incorporates group fairness constraints into the HMS problem, ensuring that selected subsets are both utility-maximizing and demographically balanced.

Methods

The authors propose two main algorithmic approaches:

  • INTCOV (Exact Algorithm for 2D): For two-dimensional data, they transform the FairHMS problem into an "interval cover" problem. This involves mapping data points to intervals representing their utility across different preference angles and then using a dynamic programming approach to find a fair interval cover.
  • BIGREEDY (Approximation Algorithm for Multi-dimensional Data): For higher dimensions, FairHMS is NP-hard. They tackle this by transforming the problem into a multi-objective submodular maximization problem under a matroid constraint. BIGREEDY uses a bicriteria approximation algorithm, leveraging concepts like $\delta$-nets to approximate the utility space and a greedy strategy to build the fair subset. They also introduce an adaptive sampling strategy to improve BIGREEDY's practical efficiency by dynamically adjusting the sample size of utility vectors.

Datasets

The authors evaluated their algorithms on a combination of synthetic and real-world datasets:

  • Synthetic: Anti-Correlated datasets (varying dimensions, group counts, and sizes).
  • Real-world:
    • Lawschs (LSAT and GPA scores, gender, race)
    • Adult (demographic and socio-economic attributes, grouped by gender and race)
    • Compas (criminal recidivism data, grouped by gender and recidivism status)
    • Credit (German credit data, grouped by job, housing, and employment years)

Key Insights and Ideas

  • The "Price of Fairness" is Often Low: Experiments show that enforcing group fairness constraints typically leads to only a small decrease in the overall "happiness" (MHR) of the selected subset, suggesting that fair solutions are often achievable without significant utility loss.
  • Existing Methods Fail on Fairness: Baseline HMS algorithms, when applied without fairness considerations, consistently produce unfair results, significantly under-representing certain groups.
  • Approximation is Necessary for High Dimensions: While an exact algorithm (INTCOV) works for 2D data, the NP-hardness of FairHMS in higher dimensions necessitates approximation algorithms like BIGREEDY.
  • Adaptive Sampling Boosts Efficiency: The adaptive sampling strategy in BIGREEDY+ significantly speeds up the process, especially for high-dimensional data, by intelligently adjusting the number of utility vectors considered.

Key Results

  • Fairness Guaranteed: INTCOV and BIGREEDY/BIGREEDY+ consistently achieve zero fairness violations on all tested datasets, unlike baseline algorithms.
  • High Utility: INTCOV provides optimal MHRs for 2D data. BIGREEDY and BIGREEDY+ achieve near-optimal MHRs, often outperforming adapted baseline algorithms.
  • Efficiency: INTCOV is exact but slower. BIGREEDY and BIGREEDY+ offer a good balance of solution quality and efficiency, with BIGREEDY+ being notably faster due to adaptive sampling. For instance, BIGREEDY+ can run up to 5 times faster than BIGREEDY.
  • Scalability: The proposed algorithms demonstrate good scalability with respect to dataset size and number of groups, though performance can degrade with very high dimensionality due to the complexity of $\delta$-nets.

Limitations and Future Work

  • High Dimensionality Challenges: While BIGREEDY and BIGREEDY+ handle higher dimensions, performance can degrade with extremely high dimensionality due to the exponential growth of $\delta$-net sizes. The authors suggest using larger $\delta$ values as a practical trade-off, which can lead to slight losses in solution quality.
  • Parameter Sensitivity: The performance of BIGREEDY and BIGREEDY+ is influenced by parameters like $\epsilon$ and $\lambda$. The paper provides experimental insights into optimal settings, suggesting $\epsilon=0.02$ and $\lambda=0.04$ offer a good balance.
  • Future Work: The paper suggests exploring more advanced techniques for $\delta$-net computation and potentially developing algorithms that can handle non-linear utility functions while maintaining fairness. Further research into the theoretical bounds of approximation for FairHMS in high dimensions could also be beneficial.

Summary updated

Abstract

Finding a happiness maximizing set (HMS) from a database, i.e., selecting a small subset of tuples that preserves the best score with respect to any nonnegative linear utility function, is an important problem in multi-criteria decision-making. When an HMS is extracted from a set of individuals to assist data-driven algorithmic decisions such as hiring and admission, it is crucial to ensure that the HMS can fairly represent different groups of candidates without bias and discrimination. However, although the HMS problem was extensively studied in the database community, existing algorithms do not take group fairness into account and may provide solutions that under-represent some groups. In this paper, we propose and investigate a fair variant of HMS (FairHMS) that not only maximizes the minimum happiness ratio but also guarantees that the number of tuples chosen from each group falls within predefined lower and upper bounds. Similar to the vanilla HMS problem, we show that FairHMS is NP-hard in three and higher dimensions. Therefore, we first propose an exact interval cover-based algorithm called IntCov for FairHMS on two-dimensional databases. Then, we propose a bicriteria approximation algorithm called BiGreedy for FairHMS on multi-dimensional databases by transforming it into a submodular maximization problem under a matroid constraint. We also design an adaptive sampling strategy to improve the practical efficiency of BiGreedy. Extensive experiments on real-world and synthetic datasets confirm the efficacy and efficiency of our proposal.
BibTeX
@article{zheng2022happiness,
  author = {Jiping Zheng and Yuan Ma and Wei Ma and Yanhao Wang and Xiaoyang Wang},
  title = {{Happiness Maximizing Sets under Group Fairness Constraints (Technical Report)}},
  journal = {Proc. VLDB Endow.},
  year = {2022},
  url = {https://openreview.net/forum?id=ZnAG7a5zfE},
}
Figure