# Individual Preference Stability for Clustering

arXiv: https://arxiv.org/abs/2207.03600 · HTML: https://mlsanity.com/paper/2207.03600/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 69 references that are in the map.
- First posted on arXiv 7 Jul 2022.

## Builds on (most cited first, 30 of 30)

- [Certifying and removing disparate impact](https://mlsanity.com/paper/1412.3756/) (2014)
- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Fairness in Learning: Classic and Contextual Bandits](https://mlsanity.com/paper/1605.07139/) (2016)
- [Scalable Fair Clustering](https://mlsanity.com/paper/1902.03519/) (2019)
- [Guarantees for Spectral Clustering with Fairness Constraints](https://mlsanity.com/paper/1901.08668/) (2019)
- [Proportionally Fair Clustering](https://mlsanity.com/paper/1905.03674/) (2019)
- [Fair k-Center Clustering for Data Summarization](https://mlsanity.com/paper/1901.08628/) (2019)
- [Online Learning with an Unknown Fairness Metric](https://mlsanity.com/paper/1802.06936/) (2018)
- [Individual Fairness for k-Clustering](https://mlsanity.com/paper/2002.06742/) (2020)
- [Metric Learning for Individual Fairness](https://mlsanity.com/paper/1906.00250/) (2019)
- [Coresets for Clustering with Fairness Constraints](https://mlsanity.com/paper/1906.08484/) (2019)
- [Clustering without Over-Representation](https://mlsanity.com/paper/1905.12753/) (2019)
- [On the cost of essentially fair clusterings](https://mlsanity.com/paper/1811.10319/) (2018)
- [Fair clustering via equitable group representations](https://mlsanity.com/paper/2006.11009/) (2020)
- [Improved Approximation Algorithms for Individually Fair Clustering](https://mlsanity.com/paper/2106.14043/) (2021)
- [Probabilistic Fair Clustering](https://mlsanity.com/paper/2006.10916/) (2020)
- [Better Algorithms for Individually Fair k-Clustering](https://mlsanity.com/paper/2106.12150/) (2021)
- [Fair Correlation Clustering](https://mlsanity.com/paper/2002.02274/) (2020)
- [A Center in Your Neighborhood: Fairness in Facility Location](https://mlsanity.com/paper/1908.09041/) (2019)
- [A Pairwise Fair and Community-preserving Approach to k-Center Clustering](https://mlsanity.com/paper/2007.07384/) (2020)
- [Fair Hierarchical Clustering](https://mlsanity.com/paper/2006.10221/) (2020)
- [Approximation Algorithms for Socially Fair Clustering](https://mlsanity.com/paper/2103.02512/) (2021)
- [Fairness, Semi-Supervised Learning, and More: A General Framework for Clustering with Stochastic Pairwise Constraints](https://mlsanity.com/paper/2103.02013/) (2021)
- [Distributional Individual Fairness in Clustering](https://mlsanity.com/paper/2006.12589/) (2020)
- [Approximating Fair Clustering with Cascaded Norm Objectives](https://mlsanity.com/paper/2111.04804/) (2021)
- [KFC: A Scalable Approximation Algorithm for k-center Fair Clustering](https://mlsanity.com/paper/2010.13949/) (2020)
- [Envy-Free Classification](https://mlsanity.com/paper/1809.08700/) (2018)
- [Metric Perturbation Resilience](https://mlsanity.com/paper/1607.06442/) (2016)
- [Principal Fairness: Removing Bias via Projections](https://mlsanity.com/paper/1905.13651/) (2019)
- [Tree Embeddings for Hop-Constrained Network Design](https://mlsanity.com/paper/2011.06112/) (2020)

## Built on by (most cited first, 8 of 8)

- [Proportional Fairness in Clustering: A Social Choice Perspective](https://mlsanity.com/paper/2310.18162/) (2023)
- [Approximation Algorithms for Fair Range Clustering](https://mlsanity.com/paper/2306.06778/) (2023)
- [Doubly Constrained Fair Clustering](https://mlsanity.com/paper/2305.19475/) (2023)
- [Proportional Fairness in Non-Centroid Clustering](https://mlsanity.com/paper/2410.23273/) (2024)
- [Constant Approximation for Individual Preference Stable Clustering](https://mlsanity.com/paper/2309.16840/) (2023)
- [Optimization of Inter-group Criteria for Clustering with Minimum Size Constraints](https://mlsanity.com/paper/2401.07091/) (2024)
- [Scalable Algorithms for Individual Preference Stable Clustering](https://mlsanity.com/paper/2403.10365/) (2024)
- [A Polynomial-Time Approximation for Pairwise Fair k-Median Clustering](https://mlsanity.com/paper/2405.10378/) (2024)

## Abstract (arXiv)

In this paper, we propose a natural notion of individual preference (IP) stability for clustering, which asks that every data point, on average, is closer to the points in its own cluster than to the points in any other cluster. Our notion can be motivated from several perspectives, including game theory and algorithmic fairness. We study several questions related to our proposed notion. We first show that deciding whether a given data set allows for an IP-stable clustering in general is NP-hard. As a result, we explore the design of efficient algorithms for finding IP-stable clusterings in some restricted metric spaces. We present a polytime algorithm to find a clustering satisfying exact IP-stability on the real line, and an efficient algorithm to find an IP-stable 2-clustering for a tree metric. We also consider relaxing the stability constraint, i.e., every data point should not be too far from its own cluster compared to any other cluster. For this case, we provide polytime algorithms with different guarantees. We evaluate some of our algorithms and several standard clustering approaches on real data sets.