  Individual preference (IP) stability, introduced by Ahmadi et al. (ICML
2022), is a natural clustering objective inspired by stability and fairness
constraints. A clustering is $\alpha$-IP stable if the average distance of
every data point to its own cluster is at most $\alpha$ times the average
distance to any other cluster. Unfortunately, determining if a dataset admits a
$1$-IP stable clustering is NP-Hard. Moreover, before this work, it was unknown
if an $o(n)$-IP stable clustering always \emph{exists}, as the prior state of
the art only guaranteed an $O(n)$-IP stable clustering. We close this gap in
understanding and show that an $O(1)$-IP stable clustering always exists for
general metrics, and we give an efficient algorithm which outputs such a
clustering. We also introduce generalizations of IP stability beyond average
distance and give efficient, near-optimal algorithms in the cases where we
consider the maximum and minimum distances within and between clusters.
