Fairness in Submodular Maximization over a Matroid Constraint

Marwa El Halabi, Jakub Tarnawski, Ashkan Norouzi-Fard, Thuy-Duong Vuong
Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, PMLR 238:1027-1035, 2024.

Abstract

Submodular maximization over a matroid constraint is a fundamental problem with various applications in machine learning. Some of these applications involve decision-making over datapoints with sensitive attributes such as gender or race. In such settings, it is crucial to guarantee that the selected solution is fairly distributed with respect to this attribute. Recently, fairness has been investigated in submodular maximization under a cardinality constraint in both the streaming and offline settings, however the more general problem with matroid constraint has only been considered in the streaming setting and only for monotone objectives. This work fills this gap. We propose various algorithms and impossibility results offering different trade-offs between quality, fairness, and generality.

Cite this Paper

BibTeX
@InProceedings{pmlr-v238-el-halabi24a, title = {Fairness in Submodular Maximization over a Matroid Constraint}, author = {El Halabi, Marwa and Tarnawski, Jakub and Norouzi-Fard, Ashkan and Vuong, Thuy-Duong}, booktitle = {Proceedings of The 27th International Conference on Artificial Intelligence and Statistics}, pages = {1027--1035}, year = {2024}, editor = {Dasgupta, Sanjoy and Mandt, Stephan and Li, Yingzhen}, volume = {238}, series = {Proceedings of Machine Learning Research}, month = {02--04 May}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v238/el-halabi24a/el-halabi24a.pdf}, url = {https://proceedings.mlr.press/v238/el-halabi24a.html}, abstract = {Submodular maximization over a matroid constraint is a fundamental problem with various applications in machine learning. Some of these applications involve decision-making over datapoints with sensitive attributes such as gender or race. In such settings, it is crucial to guarantee that the selected solution is fairly distributed with respect to this attribute. Recently, fairness has been investigated in submodular maximization under a cardinality constraint in both the streaming and offline settings, however the more general problem with matroid constraint has only been considered in the streaming setting and only for monotone objectives. This work fills this gap. We propose various algorithms and impossibility results offering different trade-offs between quality, fairness, and generality.} }
Endnote
%0 Conference Paper %T Fairness in Submodular Maximization over a Matroid Constraint %A Marwa El Halabi %A Jakub Tarnawski %A Ashkan Norouzi-Fard %A Thuy-Duong Vuong %B Proceedings of The 27th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2024 %E Sanjoy Dasgupta %E Stephan Mandt %E Yingzhen Li %F pmlr-v238-el-halabi24a %I PMLR %P 1027--1035 %U https://proceedings.mlr.press/v238/el-halabi24a.html %V 238 %X Submodular maximization over a matroid constraint is a fundamental problem with various applications in machine learning. Some of these applications involve decision-making over datapoints with sensitive attributes such as gender or race. In such settings, it is crucial to guarantee that the selected solution is fairly distributed with respect to this attribute. Recently, fairness has been investigated in submodular maximization under a cardinality constraint in both the streaming and offline settings, however the more general problem with matroid constraint has only been considered in the streaming setting and only for monotone objectives. This work fills this gap. We propose various algorithms and impossibility results offering different trade-offs between quality, fairness, and generality.
APA
El Halabi, M., Tarnawski, J., Norouzi-Fard, A. & Vuong, T.. (2024). Fairness in Submodular Maximization over a Matroid Constraint. Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 238:1027-1035 Available from https://proceedings.mlr.press/v238/el-halabi24a.html.

Related Material