Matroids, Matchings, and Fairness

The desire to use machine learning to assist in human decision making has spawned a large area of research in understanding the impact of such systems not only on the society as a whole, but also the specific impact on different subpopulations. Recent work has shown that while there are several natural ways to quantify the fairness of a particular system, none of them are universal, and except for trivial cases, satisfying one means violating another~\citet{Kleinberg, Goel, Kleinberg2}. In parallel to understanding the interplay between different definitions of fairness, researchers have looked to develop algorithms for finding fair solutions to specific classes of problems. For example, there is recent work on fair regression, fair clustering, fair bandit algorithms and many others. In this work we tackle another large class of problems that form a useful primitive in machine learning and optimization, that of optimizing a set function subject to a set of matroid constraints. A matroid is a combinatorial object that generalizes linear independence between vectors and is general enough to encode cardinality constraints (e.g. selecting at most $k$ elements), connectivity constraints (e.g. selecting a spanning tree of a graph), or matching constraints (ensuring a subgraph has a perfect matching).

• Machine Intelligence

• Responsible AI