Individually Fair Diversity Maximizaion

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 \(\textit{individually fair}\) in the sense that every point in \(P\) has at least one of its \(\frac{n}{k}\)-nearest neighbors as its “representative” in \(S\). We propose \(\left(O(1), 3\right)\)-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 \(\frac{n}{k}\)-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 individually fairer solutions than non-private ones and incur only a modest utility loss for diversity maximization.