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.