Max-Min Diversification with Fairness Constraints: Exact and Approximation Algorithms

This has raised concerns about the possibility that algorithms may produce unfair and discriminatory decisions for specific population groups, particularly in sensitive socio-computational domains such as voting, hiring, banking, education, and criminal justice [12, 25]. To alleviate such concerns, there has been a lot of research devoted to incorporating fairness into the algorithms for automated decision tasks, including classification [14], clustering [10], ranking [24, 32], matching [28], and data summarization [8, 20]. This paper considers the diversity maximization problem and addresses its fairness-aware variant. The problem consists in selecting a diverse subset of items from a given dataset and is encountered in data summarization [8, 23], web search [2], recommendation [21], feature selection [31], and elsewhere [34]. Existing literature on the problem of diversity maximization primarily focuses on two objectives, namely max-min diversification (MMD), which aims to maximize the minimum distance between any pair of selected items, and max-sum diversification (MSD), which seeks to maximize the sum of pairwise distances between selected items. As shown in Figure 1, MMD tends to cover the data range uniformly, while MSD tends to pick "outliers" and may include highly similar items in the solution. Since the notion of diversity captured by MMD better represents the property that data summarization, feature selection, and many other tasks target with their solutions, we will only consider MMD in this paper. To be precise, given a set V of n items in a metric space and a positive integer k n, MMD asks for a size-k subset S of V to maximize the minimum pairwise distance within S. In particular, we study the fair max-min diversification (FMMD) problem, a variant of MMD that aims not only to maximize the diversity measure defined above but also to guarantee the satisfaction of group fairness constraints as described below.