Matroids, Matchings, and Fairness

Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, Sergei Vassilvtiskii
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, PMLR 89:2212-2220, 2019.

Abstract

The need for fairness in machine learning algorithms is increasingly critical. A recent focus has been on developing fair versions of classical algorithms, such as those for bandit learning, regression, and clustering. In this work we extend this line of work to include algorithms for optimization subject to one or multiple matroid constraints. We map out a series of results, showing optimal solutions, approximation algorithms, and hardness proofs depending on the specific flavor of the problem. Our algorithms are efficient and empirical experiments demonstrate that fairness can be achieved with a modest compromise to the overall objective value.

Cite this Paper

BibTeX
@InProceedings{pmlr-v89-chierichetti19a, title = {Matroids, Matchings, and Fairness}, author = {Chierichetti, Flavio and Kumar, Ravi and Lattanzi, Silvio and Vassilvtiskii, Sergei}, booktitle = {Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics}, pages = {2212--2220}, year = {2019}, editor = {Chaudhuri, Kamalika and Sugiyama, Masashi}, volume = {89}, series = {Proceedings of Machine Learning Research}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v89/chierichetti19a/chierichetti19a.pdf}, url = {https://proceedings.mlr.press/v89/chierichetti19a.html}, abstract = {The need for fairness in machine learning algorithms is increasingly critical. A recent focus has been on developing fair versions of classical algorithms, such as those for bandit learning, regression, and clustering. In this work we extend this line of work to include algorithms for optimization subject to one or multiple matroid constraints. We map out a series of results, showing optimal solutions, approximation algorithms, and hardness proofs depending on the specific flavor of the problem. Our algorithms are efficient and empirical experiments demonstrate that fairness can be achieved with a modest compromise to the overall objective value.} }
Endnote
%0 Conference Paper %T Matroids, Matchings, and Fairness %A Flavio Chierichetti %A Ravi Kumar %A Silvio Lattanzi %A Sergei Vassilvtiskii %B Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Masashi Sugiyama %F pmlr-v89-chierichetti19a %I PMLR %P 2212--2220 %U https://proceedings.mlr.press/v89/chierichetti19a.html %V 89 %X The need for fairness in machine learning algorithms is increasingly critical. A recent focus has been on developing fair versions of classical algorithms, such as those for bandit learning, regression, and clustering. In this work we extend this line of work to include algorithms for optimization subject to one or multiple matroid constraints. We map out a series of results, showing optimal solutions, approximation algorithms, and hardness proofs depending on the specific flavor of the problem. Our algorithms are efficient and empirical experiments demonstrate that fairness can be achieved with a modest compromise to the overall objective value.
APA
Chierichetti, F., Kumar, R., Lattanzi, S. & Vassilvtiskii, S.. (2019). Matroids, Matchings, and Fairness. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 89:2212-2220 Available from https://proceedings.mlr.press/v89/chierichetti19a.html.

Related Material