In this paper, we study the classic submodular maximization problem subject to a group fairness constraint under both non-adaptive and adaptive settings. It has been shown that the utility function of many machine learning applications, including data summarization, influence maximization in social networks, and personalized recommendation, satisfies the property of submodularity. Hence, maximizing a submodular function subject to various constraints can be found at the heart of many of those applications. On a high level, submodular maximization aims to select a group of most representative items (e.g., data points). However, the design of most existing algorithms does not incorporate the fairness constraint, leading to under- or over-representation some particular groups. This motivates us to study the fair submodular maximization problem, where we aim to select a group of items to maximize a (possibly non-monotone) submodular utility function subject to a group fairness constraint. To this end, we develop the first constant-factor approximation algorithm for this problem. The design of our algorithm is robust enough to be extended to solving the submodular maximization problem under a more complicated adaptive setting. Moreover, we further extend our study to incorporating a global cardinality constraint.

翻译：在本文中,我们研究了在非适应性和适应性环境下受群体公平制约的典型亚模块最大化问题。已经表明,许多机器学习应用的实用功能,包括数据总和、影响社交网络中的最大化以及个性化建议,满足亚模块特性的特性。因此,在许多这些应用中,可以发现,将受各种制约的亚模块功能最大化是这些应用的核心。在高水平上,亚模块最大化的目的是选择一组最具代表性的项目(例如,数据点)。然而,大多数现有算法的设计并不包含公平性制约,导致某些特定群体的代表性不足或过多。这促使我们研究公平的亚模块最大化问题,以便选择一组项目最大限度地实现(可能非模块化的)亚模块效用功能,但受群体公平性制约。我们为此开发了第一个关于这一问题的恒定要素近似算法。我们的算法设计足够稳健,足以在更复杂的全球适应性设定下解决亚模式最大化问题。此外,我们进一步扩展了我们的基本适应性研究。