Individually Fair Diversity Maximization

We consider the problem of diversity maximization from the perspective of individual fairness: given a set P of n points in a metric space, we aim to extract a subset S of size k from P so that (1) the diversity of S is maximized and (2) S is individually fair in the sense that every point in P has at least one of its nk -nearest neighbors as its “representative” in S . We propose ( O (1) , 3) -bicriteria approximation algorithms for the individually fair variants of the three most common diversity maximization problems, namely, max-min diversification, max-sum diversification, and sum-min diversification. Specifically, the proposed algorithms provide a set of points where every point in the dataset finds a point within a distance at most 3 times its distance to its nk -nearest neighbor while achieving a diversity value at most O (1) times lower than the optimal solution. Numerical experiments on real-world and synthetic datasets demonstrate that the proposed algorithms generate solutions that are individually fairer than those produced by unconstrained algorithms and incur only modest losses in diversity.