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 framework for selecting representative subsets from a database that maximize user "happiness" while strictly adhering to group fairness constraints (e.g., gender or racial quotas). The authors provide an exact algorithm for 2D data and a scalable bicriteria approximation algorithm for higher dimensions, demonstrating that fairness can be achieved with only a marginal impact on overall utility.

What Problem Does This Paper Address?

In multi-criteria decision-making, we often need to select a small, representative subset of items (like job applicants or products) from a large database. The goal is to find a Happiness Maximizing Set (HMS): a subset that contains a "good" option for any possible user, regardless of how that user weights different attributes (e.g., a recruiter who values GPA over experience vs. one who values the opposite).

The challenge is that standard HMS algorithms are "fairness-blind." They might select a set that perfectly represents all attribute trade-offs but consists entirely of one demographic group, leading to systemic bias in automated hiring or admissions.

The authors address this by formalizing the FairHMS problem. They add constraints ensuring that the number of items selected from each group (e.g., Race, Gender) falls within specific lower and upper bounds. The goal is to maximize the Minimum Happiness Ratio (MHR)—the worst-case satisfaction level across all possible linear utility functions—while staying within these fairness "quotas."

Table 1: Example of tuples in the LSAC database

Methods

The paper proves that FairHMS is NP-hard in three or more dimensions, leading them to propose different strategies based on data dimensionality:

  1. IntCov (2D Exact Algorithm): For two-dimensional databases, the authors transform the problem into a geometric Interval Cover problem. They map points to line segments in a preference space and use dynamic programming to find the optimal fair subset that "covers" the entire range of possible user preferences. The IntCov algorithm transforms 2D points into intervals to solve the decision version of FairHMS.
Figure 1: Illustration of the IntCov algorithm in R2. We show the transformation from points to intervals and draw a 𝜏-envelope w.r.t. a minimum happiness ratio 𝜏= 0.9 in Figure (a). We then convert the decision version of FairHMS when 𝜏= 0.9 into an interval cover problem in Figure (b): for FairHMS with 𝑘= 3 and 𝑙𝑐= 1, ℎ𝑐= 2, 𝑆= {𝑝1, 𝑝4, 𝑝5} covers the interval [0, 1] and thus the answer is yes when 𝜏= 0.9.
  1. BiGreedy (Multi-D Approximation): For higher dimensions, they use $\delta$-nets to discretize the infinite space of possible utility functions into a finite set of representative vectors. They then transform FairHMS into a multi-objective submodular maximization problem under a matroid constraint (which elegantly models the group fairness bounds). Illustration of a $\delta$-net used to approximate the infinite utility space.
Illustration of a $\delta$-net used to approximate the infinite utility space.
  1. BiGreedy+ (Adaptive Sampling): To improve efficiency, they introduce an adaptive sampling strategy. Instead of starting with a massive $\delta$-net, the algorithm starts small and increases the sample size only until the solution quality stabilizes, significantly reducing computation time.

Datasets

The authors evaluated their algorithms on one synthetic and four real-world datasets:

  • Anti-Correlated (Synthetic): Used to test scalability across dimensions ($d=2$ to 8) and group sizes.
  • Lawschs (LSAC): 2D data (LSAT, GPA) with Gender and Race attributes.
  • Adult: 5D dataset regarding census data, grouped by Gender and Race.
  • Compas: 9D dataset used for recidivism risk, grouped by Gender and prior record.
  • Credit: 7D German credit data, grouped by housing and employment status.

Key Insights and Ideas

  • The "Price of Fairness" is Low: A major takeaway is that imposing fairness constraints typically only reduces the Minimum Happiness Ratio by a very small margin (often less than 0.02). You can be fair without significantly sacrificing the representativeness of your subset.
  • Matroids are the Key to Fairness: By framing group quotas as a matroid constraint, the authors could leverage powerful existing tools from submodular optimization to provide theoretical guarantees.
  • Discretization Works: While the space of user preferences is infinite, the $\delta$-net approach proves that you only need a relatively small number of representative "viewpoints" to guarantee a high-quality solution for everyone.

Key Results

  • Fairness Compliance: Standard HMS algorithms (like DMM or Greedy) frequently violated fairness constraints in experiments. The proposed FairHMS algorithms maintained zero violations by design.
  • Efficiency: BiGreedy+ was up to 5x faster than the standard BiGreedy while maintaining nearly identical solution quality.
  • Scalability: The algorithms scaled linearly with the number of tuples ($n$) and handled multi-dimensional data ($d=9$) effectively, finishing within seconds for most datasets.
  • Optimality: In 2D, IntCov consistently found the mathematically optimal fair solution, serving as a benchmark for the approximation algorithms.

Limitations and Future Work

  • Dimensionality Curse: While BiGreedy+ is efficient, the size of the required $\delta$-net grows exponentially with the number of attributes ($d$). The current approach is best suited for databases with a moderate number of scoring criteria (e.g., $d < 10$).
  • Linear Utility Assumption: The paper focuses on linear utility functions. Future work could explore more complex, non-linear models of user preference.
  • Dynamic Data: The current algorithms are designed for static databases. Adapting FairHMS for streaming data or frequently updated databases remains an open challenge.

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