  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.
