Fair Representation in Submodular Subset Selection: A Pareto Optimization Approach

Abstract

Many machine learning applications, such as feature selection, recommendation, and social advertising, require the joint optimization of the global utility and the representativeness for different groups of items or users. To meet such requirements, we propose a novel multi-objective combinatorial optimization problem called Submodular Maximization with Fair Representation (SMFR), which selects subsets from a ground set, subject to a knapsack or matroid constraint, to maximize a submodular (utility) function $f$ as well as a set of $d$ submodular (representativeness) functions $g_1, \dots, g_d$. We show that the maximization of $f$ might conflict with the maximization of $g_1, \dots, g_d$, so that no single solution can optimize all these objectives at the same time. Therefore, we propose a Pareto optimization approach to SMFR, which finds a set of solutions to approximate all Pareto-optimal solutions with different trade-offs between the objectives. Our method converts an instance of SMFR into several submodular cover instances by adjusting the weights of the objective functions; then it computes a set of solutions by running the greedy algorithm on each submodular cover instance. We prove that our method provides approximation guarantees for SMFR under knapsack or matroid constraints. Finally, we demonstrate the effectiveness of SMFR and our proposed approach in two real-world problems: maximum coverage and recommendation.