Individually Fair Diversity Maximization

⋅ NeurIPS ⋅ Project Page ⋅Slides ⋅Poster ⋅OpenReview

Abstract

We consider the problem of diversity maximization from the perspective of individual fairness: given a set

P

n

points in a metric space, we aim to extract a subset

S

of size

k

from

P

so that:

the diversity of $S$ is maximized and
$S$ is 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

(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

\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 solutions that are individually fairer than those produced by unconstrained algorithms and incur only modest losses in diversity.