Identifying Rank-Happiness Maximizing Sets Under Group Fairness Constraints

The happiness or regret based query has been another important tool in multi-dimensional decision-making besides the top-k and skyline queries. To avoid the happiness ratio being perceived as “made up” numbers which are often confused by users, we merge the concept rank into happiness ratio and study the rank-happiness maximizing set problem (RHMS). Also, it is crucial for RHMS to fairly represent different groups of candidates without bias and discrimination. In this paper, we solve the rank-happiness maximizing set problem under group fairness constraints (FairRHMS) from a submodular perspective. By introducing the concept of rank-happiness ratio and modeling the group fairness constraint proportionally along with upper and lower bounds for each group, we convert the FairRHMS problem into a submodular maximization problem under matroid constraints. Further, a bi-criteria approximation algorithm with multiple rounds of greedy processes named BMGreedy is proposed to solve the problem. Experiments on real and synthetic datasets confirm the effectiveness and efficiency of our BMGreedy algorithm.