A New Notion of Individually Fair Clustering: $α$-Equitable $k$-Center

Darshan Chakrabarti, John P. Dickerson, Seyed A. Esmaeili, Aravind Srinivasan, Leonidas Tsepenekas
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:6387-6408, 2022.

Abstract

Clustering is a fundamental problem in unsupervised machine learning, and due to its numerous societal implications fair variants of it have recently received significant attention. In this work we introduce a novel definition of individual fairness for clustering problems. Specifically, in our model, each point $j$ has a set of other points $\mathcal{S}_j$ that it perceives as similar to itself, and it feels that it is being fairly treated if the quality of service it receives in the solution is $\alpha$-close (in a multiplicative sense, for some given $\alpha \geq 1$) to that of the points in $\mathcal{S}_j$. We begin our study by answering questions regarding the combinatorial structure of the problem, namely for what values of $\alpha$ the problem is well-defined, and what the behavior of the Price of Fairness (PoF) for it is. For the well-defined region of $\alpha$, we provide efficient and easily-implementable approximation algorithms for the $k$-center objective, which in certain cases also enjoy bounded-PoF guarantees. We finally complement our analysis by an extensive suite of experiments that validates the effectiveness of our theoretical results.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-chakrabarti22a, title = { A New Notion of Individually Fair Clustering: $α$-Equitable $k$-Center }, author = {Chakrabarti, Darshan and Dickerson, John P. and Esmaeili, Seyed A. and Srinivasan, Aravind and Tsepenekas, Leonidas}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {6387--6408}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/chakrabarti22a/chakrabarti22a.pdf}, url = {https://proceedings.mlr.press/v151/chakrabarti22a.html}, abstract = { Clustering is a fundamental problem in unsupervised machine learning, and due to its numerous societal implications fair variants of it have recently received significant attention. In this work we introduce a novel definition of individual fairness for clustering problems. Specifically, in our model, each point $j$ has a set of other points $\mathcal{S}_j$ that it perceives as similar to itself, and it feels that it is being fairly treated if the quality of service it receives in the solution is $\alpha$-close (in a multiplicative sense, for some given $\alpha \geq 1$) to that of the points in $\mathcal{S}_j$. We begin our study by answering questions regarding the combinatorial structure of the problem, namely for what values of $\alpha$ the problem is well-defined, and what the behavior of the Price of Fairness (PoF) for it is. For the well-defined region of $\alpha$, we provide efficient and easily-implementable approximation algorithms for the $k$-center objective, which in certain cases also enjoy bounded-PoF guarantees. We finally complement our analysis by an extensive suite of experiments that validates the effectiveness of our theoretical results. } }
Endnote
%0 Conference Paper %T A New Notion of Individually Fair Clustering: $α$-Equitable $k$-Center %A Darshan Chakrabarti %A John P. Dickerson %A Seyed A. Esmaeili %A Aravind Srinivasan %A Leonidas Tsepenekas %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-chakrabarti22a %I PMLR %P 6387--6408 %U https://proceedings.mlr.press/v151/chakrabarti22a.html %V 151 %X Clustering is a fundamental problem in unsupervised machine learning, and due to its numerous societal implications fair variants of it have recently received significant attention. In this work we introduce a novel definition of individual fairness for clustering problems. Specifically, in our model, each point $j$ has a set of other points $\mathcal{S}_j$ that it perceives as similar to itself, and it feels that it is being fairly treated if the quality of service it receives in the solution is $\alpha$-close (in a multiplicative sense, for some given $\alpha \geq 1$) to that of the points in $\mathcal{S}_j$. We begin our study by answering questions regarding the combinatorial structure of the problem, namely for what values of $\alpha$ the problem is well-defined, and what the behavior of the Price of Fairness (PoF) for it is. For the well-defined region of $\alpha$, we provide efficient and easily-implementable approximation algorithms for the $k$-center objective, which in certain cases also enjoy bounded-PoF guarantees. We finally complement our analysis by an extensive suite of experiments that validates the effectiveness of our theoretical results.
APA
Chakrabarti, D., Dickerson, J.P., Esmaeili, S.A., Srinivasan, A. & Tsepenekas, L.. (2022). A New Notion of Individually Fair Clustering: $α$-Equitable $k$-Center . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:6387-6408 Available from https://proceedings.mlr.press/v151/chakrabarti22a.html.

Related Material