Fairness in Submodular Maximization over a Matroid Constraint
Marwa El Halabi Jakub Tarnawski Ashkan Norouzi-Fard Thuy-Duong Vuong
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.