Improved Algorithms for Fair Matroid Submodular Maximization
Authors: Sepideh Mahabadi
Sherry Sarkar
Jakub Tarnawski
Venue: NeurIPS 2025 poster ()
Keywords: fairness
matroid
submodular function
approximation algorithms
Primary area: optimization
TL;DR: We give improved approximation algorithms for fair monotone matroid submodular maximization.

Abstract: Submodular maximization subject to matroid constraints is a central problem with many applications in machine learning. As algorithms are increasingly used in decision-making over datapoints with sensitive attributes such as gender or race, it is becoming crucial to enforce fairness to avoid bias and discrimination. Recent work has addressed the challenge of developing efficient approximation algorithms for fair matroid submodular maximization. However, the best algorithms known so far are only guaranteed to satisfy a relaxed version of the fairness constraints that loses a factor 2, i.e., the problem may ask for $\ell$ elements with a given attribute, but the algorithm is only guaranteed to find $\lfloor \ell/2 \rfloor$. In particular, there is no provable guarantee when $\ell=1$, which corresponds to a key special case of perfect matching constraints.

In this work, we achieve a new trade-off via an algorithm that gets arbitrarily close to full fairness. Namely, for any constant $\varepsilon>0$, we give a constant-factor approximation to fair monotone matroid submodular maximization that in expectation loses only a factor $(1-\varepsilon)$ in the lower-bound fairness constraint. Our empirical evaluation on a standard suite of real-world datasets -- including clustering, recommendation, and coverage tasks -- demonstrates the practical effectiveness of our methods.

Improved Algorithms for Fair Matroid Submodular Maximization
Sepideh Mahabadi
Sherry Sarkar" Carnegie Mellon University sherrys@andrew. cmu, edu
Microsoft Research
smahabadi mondiimmieee crosoft.cooomm
Jakub Tarnawski
Microsoft Research
jakub. tarnawski @mi crosoot..ccomm
Abstract
Submodular maximization subject to matroid constraints is central problem with many applications machine learning. As algorithms are increasingly used decision-makee over datapoints with sensitive attributes such as gender or race, it is becoming crucial to enforce fairness to avoid bias and discrimination. Recent work has addressed the challenge of developing efficient approximation algorithms for fair matroid submodular maximization. However, the best algorithms known so far only guaranteed to satisfy a relaxed version of the fairness constraints that loses a factor 2, i.e., the problem may ask for e elements with given attribute, but the algorithm is only guaranteed to find [e/2]. In particular, there is no provable guarantee when = 1, which corresponds to a key special case of perfect matching. In this work, we achieve new trade-off via an algorithm that gets arbitrarily close full fairness. Namely, for any constant e >> imation to fair monotone matroid submodular maximization that in expectation loses only factor (1 =) in the lower-bound fairesss constraint. Our empirical evaluation standard suite of real-world datasets clustering, recommendation, and coverage tasks demonstrates the practical effectiveness of our methods.
give constant-factor approx-
The code for the paper is available fair-matroid- subbouuu neur ips2025
https://giituu..com///33
Introduction
Machine learning is increasingly deployed in high-stakes decision-making, raising concerns about the propagation of bias and unfairness automated systems. These challenges are especially acute
in domains such education, law enforcement, hiring, and credit [MMD16 Whi22; Eur22]. In response, a growing body of research has focused on developing algorithms that incorporate fairness constraints for core problems including clustering [CKLV17). data summarization [CKSDKVI8) classification [VVGG17) voting [CHVI8). and ranking (CSVI8).
This paper studies fairness in the context of monotone submodular maximization subject to matroid constraints. Submodular functions, which capture the principle of diminishing returns, are funda- mental to range of machine learning applications such as recommender systems [EG1T], feature selection [DKI1], active learning [GKIT], and data summarization [LBI1]. Matroids provide general framework for modeling independence constraints, encompassing cardinality, partition, graph connectivity, and linear independence constraints.
Part of this work was done while an intern at Microsoft Research.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

While numerous fairness definitions have been proposed, we adopt a widely used group faimess model, which partitions the universe into disjoint groups and enforces lower and upper bounds on the representation of each sensitive group in the selected set. See{Section 2.1 for a precise definition. This model generalizes several fairness notions, such as proportional representation [Mon95] [BLS17]. di-
versity constraints [CCRL11] Bid06], and statistical parity (DHPRZ11). It has been used for both sub- modular maximization [CSV18] CHVIS EMNTT20 EFNTT23 WFM21; TY23 YT23
ETNV24
as well as multitude of other optimization problems, such as clustering [CKLV17 KAM19
JNN20
HMV23 voting [CHV18], data summarization [CKSDKV88) matching CKLVI9 or ranking [CHV88
In the absence of fairness constraints, monotone submodular maximization under a single matroid constraint is very well understood, as tight (1-1/e) = 0.63-approximation is achievable [CCPVII Fei98). The intersection of two matroid constraints (which we refer to as "matroid intersection" admits an almost 0. D.S-approximation [LSV1O]. The fair variant has been primarily explored under cardinality constraints [CHV18], where tight (1 (single-pass) streaming setting, there is 0.31 23178-ppproximation [FLNSZ22] for the non-fair matroid version; furthermore, since the intersection of cardinality constraint and fairness can be reduced to a single matroid constraint 2MNTT20], the same approximation factor can be obtained for it.
approxxxxxinnnnnn is also known. In the
However, the intersection of matroid constraint and fairness constraint seems significantly more challenging, and is still poorly understood despite two recent works devoted to studying this problem in the streaming SEFNTT23] and the classic offline V24] settings; our focus on the latter. Following [F33T we refer to the problem as Fair Matroid Monotone Submodular Maximization (FMMSM). To appreciate its difficulty, consider a key special case, Monotone Submodular Perfect Matching (MSPM), i.e., maximizing monotone submodular function over the collection of all perfect matchings in a bipartite graph (Va, E&) This collection of feasible sets is not downward- closed, which invalidates known algorithmic approaches T The best known approximation factor for MSPM is a trivial
one can also apply the framework of [GHIM09) to obtain an ((v[ (Ell approximmaion, which is superior for sparse graphs. In fact, this could possibly even be tight, as it almost matches surprising negative result of [ETNV24] who showed a family of sparse graphs where the standard multilinear relaxation (commonly used in relax-and dllxx-and-roun houndroud approaches for submodular optimization) has an integrality gap of 2 EEl)) The existence of a constant-facee factor approximation to MSPM was posed by [ETNV24) as an exciting open problem.
The algorithms given in EFNTT23 ETNV24] for FMMSM circumvent the difficulty posed by the lower bound constraints by relaxing them. They obtain the following two results:
Theorem 1.1 (Two-pass algorithm of (EENTT23) There is a polynomial-fime algorithm for FMMSM that violates lower bound constraints by a factor and obtains oz /2-approximation, where is the approximation ratio of an algorithm for maximizing monotone submodular function under a matroid intersection constraint.
We can have a be almost 1/2 (LSV10) and thus get an almost 1 1 1/4-apprxximation ( (EFNTT23 work in the streaming setting and instead use the streaming algorithm for matroid intersection of [GIS2T]: this results in a 1/11.66-apppeeeeeeeeee 1.666-ppoooiiittion in two passes.) ) Here, violating lower bound constraints by factor 2 means that, if color has a lower bound of the solution is guaranteed to have least [e/2] elements of that color. Note that in MSPM we have f = 1 and thus [t/2] O.
Theorem 1.2 (ETNV24) There is a polynomial-time algorithm for FMMSM that satisfies lower and upper bound constraints in expectation rather than exactly, and obtains a 1/e) (e0-11/))apppoiinnne approximation in expectation.
"To see why MSPM a special case of FMMSM, set EG as the universe, consider a partition matroid that encodes that every vertex on the left shall have degree at most 1 in the solution, and set fairness constraints so that every vertex on the right shall have degree at least I and at most 1.
'Of course, a proper subset of perfect matching is not perfect matching. But more importantly, the collection of all subsets of perfect matchings (which is wwwnward-closed does not belong to any of the families that are known to make approximate submodular maximization tractable. In particular, is not matroid, an intersection of few matroids, co-called p-extendible system p-system [CCPVII for p O(1).

---

Theorem 1.2
also guarantees certain two-sided tail bounds on the violation of each faimesss constraint which apply if & large enough. It is the only algorithm considered in this paper that violates the upper bounds. The algorithm proceeds by solving and rounding the multilinear relaxation.
If consider relaxed version of MSPM where instead of a perfect matching we want large matching that also has high submodular function value, then a simple greedy algorithm will yield 1/3-approximation (Theorem 2.5p and construct maximal matching, thus getting 1/2 of the maximum possible size. The results in Theorems I.T I.Tand and 1.2 give no improvement upon this. While one can try generalize this simple approach to FMMSM, faces another issue that salient the context of fairness motivations: while at least half of the total lower bound mass will be satisfied, there could be "unlucky" colors (marginalized groups) that never get represented in the solution; this is precisely the reason why we seek fair algorithms in the first place.
1.1 Our contributions
In this work we provide an algorithm that satisfies the fairness constraints within a factor better than 2, while also giving guarantees for every individual group (rather than only in aggregate like the simple greedy strategy discussed above). To achieve the former, we trade off part of the objective value; to achieve the latter, we employ randomization.
Theorem 1.3 (informal version of Theorem 3.4) algorithm for FMMSM whose output
For every e E (0,1) there is a polynomial-time
satisfies the matroid constraint,
satisfies fairness upper bound constraints,
for group with fairness lower bound has in expectation at least (1 E-t elements from that group,
has expected size at least (1 times the maximum size of any feasible solution,
satisfies Chernoff-style high-probability bounds on size, as well as total fairness violation,
has expected submodular function value at least 0.499 E OPP..
Our bound on the submodular function value is actually shown with respect to a more powerful optimum, namely, an optimal set that satisfies the matroid and upper- bound constraints, but not necessarily the lower-bound constraints. If one wants to compare to this optimum, then the O(s) factor loss in value is unavoidable. To see this, consider MSPM in graph P3 N consisting of disjoint union of N paths of length 3, with a linear objective function assigning values 0, 1, 0 to each path's s edges. A perfect matching of size 2N has value, and maximal matching of size N has value N; one can interpolate between these smoothly.
We note that by instantiating bounds by factor 2, which is similar to the bounds of Theorem 1.I [EFNTT23)).
1/2 we obtain an almost 1/4-aproximmation while violating lower
As second contribution, also employ our techniques to obtain a deterministic algorithm. There several variants that we could formulate; we choose to show a general setting of matroid intersection, where the trade-off is between size and objective value. The relation faimess is that algorithm that finds a solution of maximum size that is an a-approximation to the objective value would imply an a-approximation algorithm for FMMSM (see [EFNTT23) Proposition C.6).
Theorem 1.4 For every e (0, 1) there a deterministic polynomial- algorithm for the problem of maximizing a monotone submodular function subject to two matroid constraints whose output has size at least (1 E) times the maximum size of any feasible solution minus one, and obtains (0.499 (1149999)--ppaaee approximmatio to the submodular function value.
Experimental results. We show the effectiveness of our algorithm empirically against prior work and natural baselines on suite of standard benchmarks. We measure the submodular objective value and total fairesss violation. Our algorithms produce solutions whose value is competitive with the highest-value baseline, which completely ignores the lower bound constraints and accordingly has the highest fairness violations. In two out of three scenarios, our algorithms dominate prior work [FFNTT23.. Finally, a key strength of our approach the flexibility given by e, allowing users to tune the balance between utility and fairness.
3

---

Our techniques. Let us begin with the simple setting of perfect matchings (MSPM), Consider the symmetric difference of high-value matching Y and perfect matching P. This decomposes into a collection of vertex-disjoint alternating cycles and augmenting paths.
One possible algorithm is ignore the cycles, and choose some of the augmenting paths to apply Y, so that its size grows to at least (1 - e) We can do this by computing the marginal contribution of the elements that Y would lose each path, and taking the least damaging paths; by submodularity, this loses at most a (1 E) fraction of value in Y.
While this does ensure large matching, some fraction of vertices still be "unlucky" and end up unmatched. Deterministically this would be hard to avoid (short of solving MSPM/FMMMSM completely, with no fairness violation); our next idea is to choose the paths randomly in the above solution. This will work for MSPM, as long as we take care to select a (1 - e) fraction of the P| - -Y many augmenting paths, even if already have YY] 2 (1 E) e Then every vertex that was not matched in Y has a (1 E) probability of being matched in the new solution.
However, there are two main challenges when trying to generalize the above approach to matroid and fairness constraints. Firstly, having fairness bounds with & < Ue means that Y can have fewer elements than P in some colors but more elements in other colors, and can even have [Y] [P] while still violating many fairness lower bounds. This means that we need to find and apply not only augmenting paths, but also alternating paths that exchange element of an oversaturated color for one of an undersaturated color, without increasing the solution size. We show that as long as the total fairness violation is large, there many such disjoint paths, which implies that applying a random fraction of them still retains enough value.
The second, larger obstacle arises due to dealing with general matroids. We are able to use tools from matroid theory to show the existence of many disjoint alternating or augmenting paths in an appropriate matroid intersection exchange graph whose vertices correspond to elements of Y and P (which were edges in the case of MSPM). We need to carefully refine the paths via an asymmetric shorteutting process to ensure that applying them leaves the solution independent in the matroid while also not disrupting the counts of elements in the colors not being exchanged. Moreover, in general, multiple augmenting paths in matroids cannot be applied simultaneously. We deal with this using an iterative framework where we apply a single path, rebuild the exchange graph, and find a new large collection of disjoint paths; then bound the loss in value after each step.
Paper organization. In [Sectiion 2 we introduce all necessary notation, definitions, and useful facts. In Section 3 we describe our algorithms and prove their properties. [Section 4 is devoted to the experimental evaluation. We conclude and discuss the limitations and broader impact our work in Section 5) Additional related work is discussed in Section 1.2 in the full version (in the supplementary materials), which also contains all omitted content and skipped proofs.
2 Preliminaries
We denote the symmetric difference (X UY) \ X) of two sets X and Y by XAY.
Submodular functions. We consider functions f :V + R., defined on a ground set V. We say that is submodular if f(Y U fe)) - f(Y)= 2 f(X U (e)) f(X) for any two sets Y C X C V and any element e E V X. Moreover, ff is monotone if f(Y) S f(X) for any two sets Y C X V. We assume that f is given time of this oracle to be O(1).
oracle that computes f(5) for given S C V; we consider the running
The following fact is folklore. We provide a proof in the full version (see the supplementary material).
Fact 2.1 Let f be a non-negative submodular function and X1, X2, X₃ S X be disjoint subsets of X. Then
Σ f(X (k)
Matroids. A matroid is a set family I C 2V with the properties:
Downward-closednee if X C Y and Y E I, then X e Z:
Augmentation: if X,Y I and |X| |Y], then there exists E Y with X +e I.

---

We abbreviate X [e} as X + and X {et as X We assume that the matroid is given as an oracle that, for a given S V, answers whether Σ: we consider the running time of this oracle to be O(1). We say that set S S V is independent if S E I.
Matroid exchange graph. Let I be matroid universe V and Y, Z be two independent sets.
Definition 2.2 We define the exchange graph for Y and Z with respect to I as the bipartite graph
(Y Z, Z Y, (2),)) Y y IJ).
Lemma 2.3 (Sch03), Corollary 39.12a) If F | = [2], then the exchange graph for and with respect I contains a perfect matching.
2.1 Fair Matroid Monotone Submodular Maximization (FMMSM)
The universe is partitioned into C. sets: V1 u U.. Ve, where Ve denotes elements of color c. Every element has exactly one color. The set of colors is denoted by [C] (1, every color E [C] we have fairness boundy: lower bound l, and upper bound Me-
C). .1. For
The set of upper bounds gives rise to a partition matroid that we will denote by U. That is,
U = (S S V | V.l S Me Vc E [C]}.
It is well-known that such collection of sets forms matroid. We will call set S U upper-fair.
If set satisfies both the lower and the upper bounds, we say that is fair. That is, we define the family of fair sets C as follows:
C (S C 4 SSn ue Vc [C]}.
The FMMSM problem asks find set S InC (i.e., fair and independent S) that maximizes f(S). We use OPT for the optimal value, i.c., OPT = maxsezne f(S). We assume that there exists fair and independent set, i..., I CC C + 0. We say that an algorithm an a-approximation if it outputs set S with S(S) 2 a. OPT.
For any set S C V we define its fairness violation fav( == Σ max - -Me, -ee (e Note that if S is upper-fair, then (Sv(S) E. max{ee -S v..
Lemma 2.4 (EENTT23), Appendix C) There is exact polynomial-time algorithm for FMMSM for the case when f is a linear function.
Matroid intersection. Given two matroids and monotone submodular function f defined on V, we can define the problem of maximizing a submodular function subject to matroid intersection constraint similarly FMMSM. In particular, if ignore the lower bounds completely, FMMSM turns into the above matroid intersection problem for matroids and U.
Theorem 2.5 (CCCPV1))
The greedy algoritlum gives 1/3 j/saapproinnation to this problem.
Theorem 2.6 (LSVIO) For any å > 0 there is polynomial-time algorithm that gives a (0.5 - 6)- approximation this problem.
3 Our algorithm
In this section we describe our algorithms: randomized ( (Theorem 3.4) and deterministic (Section 3.1). We first need to introduce some notions. The proof of Theorem 3.4 will begin by constructing maximum-cardinnliity independent and fair set P, which will stay unchanged throughout the execution. We also construct independent and faper-fair set Y of high f-value. We will use P source of fairness and iteratively trade off Y's value for P's elements in colors that are undersaturated by Y.
Definition 3.1
Given Y and P above, we say that color E [C] is undersaturated YY n Vel <
JP Vel. and oversaturated if n V.l | [P n Val-
The technical crux of the proof Theorem 3.4 is Lemma 3.3 in which we show the existence of many disjoint structures, each of which can be used to advance our fairness objective.
5

---

Definition 3.2 Let Y be an independent and upper-fair set, and let X C V. Define the result Y' of applying X to as the symmetric difference Y' = = 2X. We say that is alternating (with respect to Y) Y is independent (Y' I) and there is exactly one undersaturated color e' E [C] and one oversaturated color d' E [C] such that for all [C].
1
cor for =d, for c x c, d,
We say that X is augmenting if all the above conditions are satisfied, except that there is no color c". In both cases, we say that X increases c'.
Note that we have |Y* | if X alternating and Y YY] + if is augmenting. Also, Y' is upper-fair, since the only color where it has more elements than Y is c', and we have Y'n Vel (Y + < Pn Vol + 1 (and fair).
Lemma 3,3 Let and P be two independent and upper-fair sets with |Y| S [P]. Denote
k
Σ cE(C]
ma |PnV -V (V))
Then we may find in polynomial time a collection XI,..,, of disjoint subsets of YUU,, of which at least IP IY many augmenting and the rest alternating. Moreover, for every undersaturated color c, exactly |P n Val - - n Vel many of the paths increase c.
The full proof can be found in the full version (see the supplementary material).
Proof sketch. We consider the so-called (directed) matroid intersection exchange graph for Y and P with respect to Z and U. Inside this graph we carefully construct a subgraph consisting of two matchings M, and M_. M- is obtained by invoking Lemma 2.3 a subgraph, whereas construct M_, manually by matching elements of the same colors between and P. We then algorithmically construct the h paths between appropriately defined sets of sources and sinks in M U M., Next, we carry out an asymmetric shortcutting process, whose aim to make sure that the new solution will be independent in the matroid, but also not disrupt the color structure. This allows us to prove that the paths following this postprocessing satisfy Definition 3.2
Theorem 3,4 There is randomized polynomial- time algorithm for FMMSM parametrized by E (0. 1) that outputs set S E I In (i.e., independent and upper-fair) such that
[[[S]] 2 (1 - with a high-probability tail bound: for 8 > 0, P[[S| < (1 6) N) & exp(-9x
[[[(S)) Z 0.499 OPT Me MatInt
for every E [C] we have EE[S n Voll 2 (1 (1- E)-
with a high-probability tail bound on the total fairness violation: for > P(fav(S) (1 5)E E. fe] S exp (-52g Ecle)
where is the maximum size of set in I U4 and MP is the maximum f-value of a set in I Eu (clearly we have OPT OPT as C U))
We stress that S faier-fair with probability 1, not only in expectation. We also remark that one can show similar tail bound for every individual &c. though the right-hand side exp(-925(f, may not be meaningful unless is large. On the other hand, no such bound can be shown for the f-value, which in the worst case can be concentrated on single element of the universe.
MatMat The guarantee [S) > 0.499 OPT MatInt of the second bullet point comes from using the
local search algorithm of Theorem 2.6Jas as a subroutine. We can instead use the simpler algorithm of'Thorrm to get slightly worse guarantee of B(((S) > 1/2 OPT do in our experimental evaluation.
We give brief sketch; the full proof can be found in the full version (see the supplementary material).

---

Proof sketch of Theorem 3.4 As the first step, we compute a maximum- maximum-carddinllty cardinality fair and indepen- dent set P. which may be done polynomial time by Lemma 2.4 By invoking Lemma 3.3 we can show that |P] N. As the second step. we compute a high-value independent and upper-fair set Yo- Using the algorithm of Theorem 2.6 ([LSV10) (with = 10-3) we get that f(Y)) 2 0.499 OPT Matint. We denote
k(Y)
(ax - - CE|C]
Σ
for any solution Y, and & := (Yo) to shorten notation. We will perform a number / of iterations
which will be (1 -1==) z)kk in expectation. More precisely, let us set I [(1 -E)k] with probability (1 =)k [(1 - =)k and [(1 - s)k] otherwise.
We perform I iterations. In the i-th iteration, we apply Lemma 3.3 to Y,-1 (and P) to obtain collection X .... x- x of augmenting or alternating sets. We choose one of them, X,, uniformly at random, and apply it to obtain a new solution Y; = i1-1,X Finally, we return S := Y,,
All solutions Yo, .... Y, are independent and upper-fair. The properties of fairness lower bounds intuitively follow because at every iteration one random fairness violation is removed, and the number of iterations is = (1 - times the initial number of faimess violations k k(Y)). Since least PI | of the sets at iteration i are augmenting, the claim about the size of the solution follows similarly. We also show tail bounds by invoking Chernoff- Chernoff-Hoeffding style bounds for hypergeometrie distributions. As for the objective value, we prove that at every step, the expected loss only 1/(k + 1) fraction of the current f-value, we select randomly from among k 1---- --+ 1 disjoint augmenting or alternating sets. After 1 z (1 =) iterations we then end up with a telescoping product that simplifies to gk T f(Y)).
3.1 Deterministic algorithm
Now we turn to our deterministic result, Theorem 1.4 Is powered by lemma that is an analogue of Lemma 3.3. Their proofs are deferred to the full version (in the supplementary material).
Lemma 3.5 For any two matroids I, Iz, let Y, E IIn be two sets in their intersection, with |Y| < |P]. Then we may find in polynomial time collection X ....., X XIP|-IY| of disjoint subsets of Y P such that for each set X; we have Y AXX; E In II and YY AX, = +Y|+1 +1
4 Experimental evaluation
We evaluate the performance of our algorithms empirically against prior work and natural baselines closely following the experimental setup of prior work (EMNTT20) EFNTT23], benchmarks that are standard in the field: graph coverage, clustering, and recommender systems, under different fairness and matroid constraint settings. Our metrics are the submodular objective value f(S) and total fairness violation (Sv( All of the considered algorithms return sets that are independent and faper-fair, the measured fairness violations are all with respect to the lower bounds. LLMs were used to assist in coding. We compare the following algorithms:
suite of
OUR(s)= our algorithm of Theorem 3.4 for range of settings of s {0.2, 0.5, 0.8). To compute a high-value solution Y, we run the natural greedy algorithm, which obtains a 1 1/3-approximation Theorem 2.5), the local search algorithm of Theorem 2.6 impractical. The large fair set P is obtained via augmenting paths, ignoring f-
TwoPASS the algorithm of [EFNTT23] (Theorem I.Ip. Since it was originally developed for the streaming setting, get tair comparison we simplify away the parts (namely the first pass) whose purpose was ensuring low memory usage. The first step of the algorithm obtains a fair set via augmenting paths (ignoring f). This is then divided in two, and each half is extended to independent and upper-fair solution using a matroid intersection subroutine. For this we employ the greedy algorithm (the original implementation of (EFNTT23) used swapping algorithm to ensure low memory and linear runtime, but it obtains inferior values).
LBMI (Lower Bound Matroid Intersection) an algorithm that always returns fair set, with no theoretical guarantee on the value. It starts by building fair set augmenting paths, ignoring f. and then extends to maximal solution using the greedy algorithm.
7

---

Coverage
110
Clustering
x10
Movies
Objective value f(S)
5.0
Our = 0.2)
Our (C 0.5)
LBMI
4.6
Random
TwoPass
0.5-
UBMI
0-
4.2
25
50
75
100
30
40
50
60
50
100
150
200
Faimess violation fav (S)
8-
15-
6-
4-
2-
2
0
25
50
75
100
30
40
50
60
50 100
150
200
r
Figure 1: Our experimental results. Each column corresponds to one experiment; the top plot shows objective value of each algorithm for a range of solution scale factors r, and the bottom plot shows fairness violations. For randomized algorithms report averages, with error bars that correspond to sample standard deviation.
(a) Coverage
K10
(b) Clustering
(c) Movics
5.0
90
Objective value, ((S)
15000
Pareto fronticr
4.9
Our (e = 0.2)
10000
4.8
70
Our (e = 0.5)
Our (e 0.8)
4.7
60
LBMI
5000
4.6
50
Random
TwoPass
4.5
40
UBMI
0
2
10 Fairness violation fav(S)
Fairness violation fav(S)
Fairness violation fav(S)
Figure For each experiment and algorithm we take the average objective value and fairness violation over all r-values, and plot this as single point. For randomized algorithms, the colored rectangles correspond to standard deviations. The dashed line corresponds to the Pareto frontier of the trade-off between objective value and fairness violation.
UBMI (Upper Bound Matroid Intersection) an algorithm that ignores lower bound constraints and just solves the matroid intersection problem for I and 2 (similar in spirit to MATROID- INTERSECTION from EFNTT23)) ), Also here we use the greedy algorithm.
RANDOM algorithm that randomly shuffles the universe and then adds each element if this keeps the solution independent and upper-fair.
For fair comparison of the main underlying ideas, we made sure that the compared algorithms, particularly OUR and TwoPASS, use the same subroutines for similar tasks; the implementations could likely benefit from heuristically taking f into account rather than ignoring f when building large fair sets, or from some local-search based postprocessing of the final solution. the algorithm of [ETNV24] (Theorem 1.2) as solving the multilinear extension makes it impractical. We repeat the randomized algorithms times. All experiments can be run on commodity hardware (CPU only, singeethreeaed, we do not report runtimes) and take several hours to finish.
do not compare to

---

The code for the paper is available at https://gittub..com / fair-matroine submodular--aooooouuuuuuuuraaaae neuripp2222
We outline the experimental scenarios below. In each experiment we vary a solution size scaling factor r, which roughly corresponds to the rank of the matroid I.
Computational complexity. We start with the complexity of the general randomized algorithm of Theorem 3.4 Firstly, the runtime of constructing P (a maximum-cardin cardinallty fair and independent set) via augmenting paths is ((N (by [Sch03], Chapter 41.2 Notes). To construct Y (an upper-fair and independent set of high f-value), we expend ((N time using the greedy algorithm.
Next, each of the I iterations, we must (1) recompute the exchange graph between Y; and P. (2) find M,- and M,, as the subgraph of interest, (3) decompose M,- UM,, into paths, and (4) shortcut these paths. Step (1) takes O(N²) time, since we query if directed edge exists between y and p for all E Y and E P. Finding perfect matchings in step (2) takes at most O(N3) time (in a practical implementation we could use the Hopcroft- Karpp algorithm). Decomposing the resulting subgraph into paths takes at most O(N) time. And lastly, shortcutting the paths again takes at most O(N2) time. Since I can be ((V), the total runtime is at most O(N+).
A more efficient implementation is possible if I is a partition matroid. The intersection of two partition matroids can be naturally interpreted one side, the parts of are the other side, and an element corresponds to an edge between the two parts it belongs to). In this case, we may look at the following exchange graph: direct the edges of Y from left to right, and the edges of P from right to left. This directed graph may be decomposed into paths. These paths are simultaneously feasible, and we do not need to recompute exchange graph at every step (or shortcut). Since there are ONN) edges, the runtime to decompose this directed graph ONN). Over the / iterations, we have total runtime of at most (
bipartite multigraph (the colors, i.e., parts of l are
Graph coverage. We use the Pokec social network [LK14). Given a digraph = -V, E) of users and their friendships. we select subset S S V to maximize coverage, defined by f(S) = Uves (v)). where Nov) is the neighborhood of v. User profiles include age, gender, height, and weight. We impose a partition matroid on body mass index (BMI). Profiles miss- ing height or weight or with implausible data are removed, yielding a graph with 582,289 nodes and 5,834,695 edges. Users are partitioned into four BMI categories (underweight, normal, over- weight, obese), with upper bounds
| for each group Vi. We also enforce fairness by age, with 7 groups: [1, 10), [11, [18, 25], [26, 35], [36, 45), [46+], no age. We set la = [0.9 [ and Me = [1.5 r] We use from 10 to 200.
Exemplar-based clustering. We use dataset of 4521 phone calls from Portuguese bank mar- keting campaign [MCR14]. The goal is to select a representative subset S C V for service quality assessment. Each record E V is represented ing age and account balance. We impose a partition matroid on account balance, with 5 groups: (-oo,0) 0), [0, 2000), [2000, 4000), [4000, 6000), [6000, oo). Each group V, has upper bound r/5. Fair- ness is enforced by age, with 6 groups: [0, 29). [30, 39), [40, 49), (50, 59). [60, 69), [70+]. and bounds l. 0.1r + 2, Ue 0.4r for each We maximize the monotone submodular function [GK10): f(S) = Ee'v (d(e', 0)- mineesu(o) d(e',e)) where d(e',e) e) = || xell2 and xo is the origin. We use from 30 to 60.
2e E R²7 using 7 numeric features, includ-
Recommender system. We simulate a movie recommendation system using the Movielens 1M dataset [HK16], with about one million ratings for 3900 movies by 6040 users. As in prior work [MB] NTC17 NTMZMST8 EMNTT20 EFNTT23) we compute a low-rank completion of the user-movie matrix TCSBHTBAO1] yielding W.,, E 2 for each user and e. E I820 for each movie m. The product w. Um estimates user u's s rating for movie m. For user u, the monotone submodular utility
Vmm) ,0) + (1 (a)) Emes w. Ums for set of movies (S) = a Em'ear max (maxmes (v
with parameter a = 0.85 balancing coverage and personalized user score. We enforce proportional representation of movies by release date using partition matroid with 9 decade groups (1911-19 1-2000),
with upper bounds [1.2 [V| for each decade Va. Movies are also partitioned into 18 genres c
(colors), with fairness bounds f. = [0.8 [Vcl and ua [1.4 [Va r]. We use from 10 to 200. [V

---

4.1 Results and discussion
Our results are depicted in Figs. I and 2 Similarly as prior work, we observe that enforcing fairesss does come at some cost in the utility value, and that the utility values of the algorithms are much better in practice than the theoretical bounds guarantee.
In all three experiments, our algorithms produce solutions whose value is relatively competitive with UBMI, which completely ignores the lower bound constraints and accordingly has the highest fairness violations. In two of the three scenarios (coverage and movies), all OUR algorithms produce higher f-value than all the other baselines (RANDOM, LBMI, and TwOPASS); in particular, TWOPASS is dominated by both OUR (0.2) and (UR(0.5) with respect to both metrics. For clustering the situation is somewhat unclear, but TWOPASS generally does better. In terms of violation of the lower bound fairness constraints, our different settings of E, expected, provide a smooth tradeoff. The baseline that guarantees no fairness violations, LBMI, does relatively poorly in terms of f-value.
This tunability of æ is a key strength our approach, allowing users to select an operating point that best matches their specific requirements for the balance between utility and fairness.
5 Conclusion, limitations, broader impact, and future work
In this work we gave an improved algorithm for FMMSM which, for any e >> 0, returns an approxi- mate solution that satisfies an expected (1 -5) 5) fraction of each fairness lower bound while satisfying the matroid constraint and the fairness upper bound constraints exactly; the returned solution is also large in size and enjoys concenrncntniiioon guarantees. Recent studies have shown that automated algorithms used in decision-making can introduce bias and discrimination. We make progress towards mitigating such effects in problems that can be formulated as submodular maximization under matroid constraint, which are relevant to range of applications such as forming representative committees or curating content for news feeds. We show the strong performance of our algorithm empirically on several real-world tasks. As in prior work, we observe a balance between fairness and utility value; however, this "price of fairness" " should not be interpreted as fairness leading to inferior outcomes, but rather trade-off between two valuable metries. The parametric nature of our algorithm (the tunable parameter) provides a new tool to help in navigating this balance.
Our work leaves open the exciting question of the approximability of FMMSM (without violations of fairness constraints) and MSPM. there a constant- factor approximation algorithm for MSPM? Or is there superconstant hardness of approximation for FMMSM? (As remarked in [ETNV24). the latter result would give a negative answer to a fundamental question posed by Vondrák [Von13..) We also do not consider non-monotone objective functions or the streaming setting in this work. Finally, it is important to note that the fairness notion we employ, though standard and general, does not capture some notions of fairness considered in the literature (see e.g. [CR18] TWRTZ19)). No universal definition of fairness exists; the choice of which definition to apply is application and an active area of research.
References
[Bid06]
Dan Biddle. Adverse impact and test validation: A practitioner's 's guide to valid and defensible employment testing. Gower Publishing, Ltd., 2006.
[BLS17]
Markus Brill, Jean--Jannggeeeee François Laslier, and Piotr Skowron. "Multiwinner Approval Rules as Apportionment Methods". In: AAAI. AAAI Press. 2017, pp- 414 424. Gruia Calinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák. "Maximizing Monotone Submodular Function Subject to a Matroid Constraint". In: SIAM Journal on Computing 40.6 (201 1). pp. 1740-1766. DOI: 10. 10111113770007 1137//80777733 Joanne McGrath Cohoon, James P. Cohoon, Seth Reichelson, and Selwyn Lawrence. "Effective Recruiting for Diversity". In: FIE. IEEE Computer So- ciety, 2013, pp. 1123-1124.
[CCPV1I]
[CCRL13]
1CHV18]
L. Elisa Celis, Lingxiao Huang, and Nisheeth K. Vishnoi. "Multiwinner Voting with Faimess Constraints". In: IJCAL. ijcai.org. 2018, pp. 144-151. Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. "Fair Clustering Through Fairlets". In: NIPS. 2017, pp. 5029-5037.
[CKLV17]
10

---

[C
Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. "Ma- troids, Matchings, and Fairness". In: A/STATS. Vol. 89. Proceedings of Machine Learning Research. PMLR, 2019, pp. 2212-2220.
[CKSDKV18]
L. Elisa Celis, Vijay Keswani, Damian Straszak, Amit Deshpande, Tarun Kathuria, and Nisheeth K. Vishnoi. "Fair and Diverse DPP-Based Data Summarization" In: ICML. Vol. 80. Proceedings of Machine Learning Research, PMLR, 2018,
pp. 715-724.
[CR18]
Alexandra Chouldechova and Aaron Roth. "The frontiers of fairness machine learning". In: arXiv preprint arXiv: 1888.008//// (2018).
[CSV18]
L. Elisa Celis, Damian Straszak, and Nisheeth K. Vishnoi. "Ranking with Fairness Constraints". In: ICALP. Vol. 107. LIPIcs. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2018, 28:1-28:15.
[DHPRZI2]
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. "Faimess through awareness". . In: Proceedings of the 3rd innovations in theoretical computer science conference. 2012, pp. 226-226.
[DK11]
Abhimanyu Das and David Kempe. "Submodular meets Spectral: Greedy Algo- rithms for Subset Selection, Sparse Approximation and Dictionary Selection", In: ICML. Omnipress, 2011, 1, pp. 1057-1064.
[EFNTT23]
Marwa EI Halabi, Federico Fusco, Ashkan Norouzi- Fardd Jakab Tardos, and Jakub Tamawwki. "Fairness in Streaming Submodular Maximization a Matroid Constraint". In: International Conference on Machine Leaminn. PMLR. 2023, pp. 9150-9171.
[EGII]
Khalid El-Arini and Carlos Guestrin. "Beyond keyword search: discovering relevant scientific literature". In: KDD. ACM, 2011, pp. 439-447.
[EMNTT20]
Marwa EI Halabi, Slobodan Mitrovic, Ashkan Norouzi-Fard Jakab Tardos, and Jakub Tarnawski. "Fairness in Streaming Submodular Maximization; Algorithms and Hardness". In: NeurlPS. 2020.
[ETNV24]
Marwa EI Halabi, Jakub Tarnawski, Ashkan Norouzi-Fard, and Thuy-Duong Vuong. "Fairness in Submodular Maximization over a Matroid Constraint". In: International Conference Artificial Intelligence and Statistics, 2-4 May 2024, Palau de Congressos, Valencia, Spain. Ed. by Sanjoy Dasgupta, Stephan Mandt, and Yingzhen Li. Vol. 238. Proceedings of Machine Learning Research. PMLR. 2024, pp. 1027-1035. URL: https: //ppocee///rooeiinggs mlr prwss/ v238/ el halabi24a. htmm124.hhmm html
[Bur22]
European Union FRA. Bias in Algorithms Artificial Intelligence and Dis- crimination. Luxembourg: European Union Agency for Fundamental Rights.
Publications Office of the European Union, 2022.
[Fei98]
Uriel Feige. "A Threshold of In n for Approximating Set Cover", In: ACM 45.4 (1998), pp. 634-652.
[FLNS722]
Moran Feldman, Paul Liu, Ashkan Norouzi-Fard, Ola Svensson, and Rico Zen- klusen. "Streaming Submodular Maximization Under Matroid Constraints". In: ICALP. Vol. 229. LIPlcs. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2022, 59:1-59:20.
[GHIM09]
Michel Goemans, Nicholas J. A. Harvey, Satoru Iwata, and Vahab Mir- rokni. "Approximating submodular functions everywhere", In: Proceedings of the Twentieth Anmual ACM-SIAM Symposium on Discrete Algorithmss, SODA 2009, New York, NY, USA, January 4-6, 2009. Ed. by Claire Mathieu. SIAM.
2009, 335-544. DOI: 10 1137 / 9781611973068 59
URL.: https
//doi. 10///10..00 1117/11 www..9111111166....
[GJS21]
Paritosh Garg, Linus Jordan, and Ola Svensson. "Semi-streaming Algorithms for Submodular Matroid Intersection". In: IPCO. Vol. 12707. Lecture Notes in Computer Science. Springer, 2021, pp. 208-222. Ryan Gomes and Andreas Krause. "Budgeted Nonparametric Learning from Data Streams". In: /CML. Omnipress, 2010, pp. 391-398.
[GK10]
[GK11]
Daniel Golovin and Andreas Krause. "Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization". In: J. Artif. Intell. Res. 42 (2011), pp. 427-486.

---

[6K16]
F Maxwell Harper and Joseph A Konstan. "The MovieLens datasets: History and context". In: ACM Transactions on Interactive Intelligent Systems (TiiS 5.4 (2016), p. 19.
[HMV23]
Sedjro Salomon Hotegni, Sepideh Mahabadi, and Ali Vakilian. "Approxima- tion Algorithms for Fair Range Clustering". In: Proceedings of the 40th In- terationnl Conference Machine Learning. Ed. by Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato. and Jonathan Scarlett. Vol. 202. Proceedings of Machine Learning Research. PMLR, 23 Jul 2023, pp. 13270-13284. URT.: httpps://proceeedingge mlr. press//2ess/ hotegn 123...i23a..0 html]
[JNN20]
Matthew Jones, Huy Nguyen, and Thy Nguyen. "Fair k-Centers via Maximum Matching".. In: Proceedings of the 37th International Conference on Machine Learning. Ed. by Hal Daumé III and Aarti Singh. Vol. 119. Proceedings of Machine Learning Research. PMLR, 13-18 Jul 2020, pp. 4940-4949, URL:
https://proceeddnng mlr www.eeeeesssviveee jotes/o..neeaaa.ee html
[KAM19]
Matthaus Kleindessner, Pranjal Awasthi, and Jamie Morgenstern. "Fair k-Center Clustering for Data Summarization", In: Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA. Ed. Kamalika Chaudhuri and Ruslan Salakhutdinov. Vol. 97. Proceedings Machine Learning Research. PMLR, 2019, pp. 1448-3357 URL: http://proceediings mlr pwwss/vv9..// www.enesseeeeeeeeee html
[LB11]
Hui Lin and Jeff A. Bilmes. "A "A Class of Submodular Functions for Document Summarization". In: ACL. The Association for Computer Linguistics, 2011, pp. 510-520.
[LK14]
Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford Large Network Dataset Collection. http::/snap. stant ord. edu/data June 2014.
[LSVI0]
Jon Lee, Maxim Sviridenko, and Jan Vondrák. "Submodular maximization over multiple matroids via generalized exchange properties". Mathematics of Operations Research 35.4 (2010), pp. 795-806.
[MBNTC17]
Slobodan Mitrović, Ilija Bogunović, Ashkan Norouzi-Fard, Jakub Tamawski,, and Volkan Cevher. "Streemmig Robust Submodular Maximization: A Partitioned Thresholding Approach". In: Advances Neural Information Processing Systems. 2017.
[MCR14]
Sérgio Moro, Paulo Cortez, and Paulo Rita. "A data-driven approach to predict the success of bank telemarketing". In: Decis. Support Syst. 62 (2014), pp. 22-31. Cecilia Munoz, Smith Megan, and DJ Patil. Big data: A report on algorithmic systems, opportunity, and civil rights. Washington, DC: Executive Office of the President. The White House, 2016.
[MMD16]
[Mon95]
Burt L Monroe. "Fully proportional representation". In: American Political Sci- Review 89.4 (1995), pp. 925-940)
[NTMZMS18]
Ashkan Norouzi-Fart Jakub Tarnawski. Slobodan Mitrović, Amir Zandich, Aida Mousavifar, and Ola Svensson. "Beyond 1/2-approximation for submodular maximization on massive data streams". In: ICML (2018).
[Sch03]
Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Vol. B. Jan. 2003.
[TCSBHTBAOL]
Olga Troyanskaya, Michael Cantor, Gavin Sherlock, Pat Brown, Trevor Hastie, Robert Tibshirani, David Botstein, and Russ B Altman. "Missing value estimation methods for DNA microarrays" In: Bioinformatics 17.6 (2001), pp. 520-525.
[TWRTZ19]
Alan Tsang, Bryan Wilder, Eric Rice, Milind Tambe, and Yair Zick. "Group- Fairness in Influence Maximization". In: Proceedings of the Twenty-Fighth Inter- national Joint Conference on Artificial Intelligence, IJCAI-19, International Joint Conferences on Artificial Intelligence Organization, July 2019, pp. 5997-6005. URL: https: doi org/ 24963/
DO1: 10. 24963 ijcai 2019 831 ijcai 2019/831
[TY23]
Shaojie Tang and Jing Yuan. "Beyond submodularity: unified framework of randomized set selection with group fairness constraints". In: Journal of Combi- natorial Optimization 45.4 (2023), p. 102.
12

---

[Von13]
Jan Vondrák. Submodular Functions and Their Applications. Plenary talk at the ACM-SIAM Symposium on Discrete Algorithms (SODA) 2013. 2013, URL: https: // theory stanford. edu / "jvondrak/ / data / SODA pllenay talk.pdt:
[WFM21]
Yanhao Wang, Francesco Fabbri, and Michael Mathioudakis. "Fair and Rep- resentative Subset Selection from Data Streams". In: Proceedings of the Web Conference 2021. WWW '21. Ljubljana, Slovenia: Association for Comput- ing Machinery, 2021, pp. 1340-1350. ISBN: 3781450383127, DOT: 10 1145/ URL.: https://doi ooooorg//// 10. 01144//3443811 3449799 3449999
3442381. 3449799
[Whi22]
White House OSTP. Blueprint for an Al Bill of Rights. Washington, DC: White House Office of Science and Technology Policy, 2022.
[YT23]
Jing Yuan and Shaojie Tang. "Group faimesss in mon-monotone submodular maximization", In: Journal of Combinatorial Optimization 45.3 (2023), p. 88.
[ZVGG17]
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez-Rodriguuz, and Krishna P. Gummadi. "Fairness Constraints: Mechanisms for Fair Classification". In: AISTATS. Vol. 54. Proceedings of Machine Learning Research. PMLR, 2017, 962-970.
13

---

A Supplementary Material
We provide full version of the paper with all omitted content, skipped proofs etc. together with the supplementary material.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's s contributions and scope?
Answer: [Yes]
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Yes, particularly in Section 5
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Guidelines:
15

---

The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Yes. we provide the full source code in the supplementary material, zipped together with all relevant datasets for ease of execution. We will also open-source release the code together with the camera-ready version.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
16

---

Answer: [Yes]
Justification; Yes, we provide the full source code in the supplementary material, zipped together with all relevant datasets for ease of execution. We will also open-source release the code together with the camera-ready version.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
public/guides/Cotenn httpas//ooooSummmmisiooooooo
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to rum to reproduce the results. See the NeurIPS code and data submission guidelines (https http///ooouousssioooooooo
/ ctaips..c/publcc/uuiii
ooiollolicii/ for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Yes, report sample standard deviation error bars in the plots (and in the result files in the supplementary material). These correspond to the randomness used by the algorithm.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
17

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative eπror rates).
show in tables
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
The experiments be commodity hardware (CPU only, single- threaded) and take several hours to finish. We mention this in Section 4]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics htttpp////ooorrrs..ccc/aaa//l/aa
Answer: [Yes]
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Yes, in Section 5
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
18

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system Iearns from feedback over time, improving the efficiency and accessibility ML).
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URI.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwwpppaiithhooeeooopppp wwwode..cod...c. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
19

---

Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We release no new assets (except code, which is discussed elsewhere).
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for rescarch with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsoureing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMSs if it is important, original, or non-standard component of the core methods this research? Note that if the L.M used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Guidelines:
20

---

The answer NA means that the core method development in this research does not involve LLMs as any important. original, non non-standard components.
Please refer to our LLM policy (https://neurip:: /ttp://pp.ccc//offfeeeee//////// for what should or should not be described.
21


Reviews:
[{"review_id": "d8JW9CpsZH", "reviewer": "Reviewer_QVWu", "summary": "This paper considers fair submodular maximization subject to a matroid constraint. This is much more challenging than the simpler cardinality constraint version of the problem, where it has previously been shown that the fairness constraint plus cardinality constraint are equivalent to an instance of submodular maximization with a single matroid constraint. This problem has previously been considered before by [EFNTT23,ETNV24], but an issue with both of these results is that the proposed algorithms do not actually guarantee to meet the bottom fairness constraint (they either only meet them in expectation or by a constant factor).", "questions": "- Is it possible to use concentration bounds and the algorithm of ETNV24 in order to meet the lower bounds with high probability? If so, what is the advantage of your algorithm in terms of meeting the fairness constraints?\n- Related to above question, could you describe the theoretical guarantees of your algorithm compared to ETNV24 in more depth?\n- What do you mean by that you are \"giving guarantees for every individual group rather than only in aggregate\" in contrast to related work?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- The problem is both interesting and challenging.\n- Algorithms and theoretical techniques appear novel to me.\n- Experimental results are included.\n\nWeaknesses\n- I am confused about how the results of this work improve on ETNV24, which from my understanding achieves the bounds on fairness in expectation. In particular, I have listed two questions below that would help clarify the contributions of this work relative to existing work. If this relationship can be better clairified I am willing to increase my score.\n- The experiments do not compare to ETNV24 since they say using the multilinear extension is impractical, but this comparison seems the most important from my perspective since it is the algorithm in the classic offline setting.", "was_revised": true, "final_justification": "Update: After reading the rebuttal and other reviews, I have raised my score to an accept. My primary issue was the theoretical relationship with ETNV24, and the rebuttal of the authors has addressed this.", "rebuttal": "> I am confused about how the results of this work improve on ETNV24, which from my understanding achieves the bounds on fairness in expectation. In particular, I have listed two questions below that would help clarify the contributions of this work relative to existing work. If this relationship can be better clairified I am willing to increase my score.\n\nHappy to clarify; see answers below. Thank you for your thoughtful review and these questions, which will help us improve the writeup for the final version.\n\n> The experiments do not compare to ETNV24 since they say using the multilinear extension is impractical, but this comparison seems the most important from my perspective since it is the algorithm in the classic offline setting.\n\n## Practicality of [ETNV24]:\n\nThe algorithm of [ETNV24] (Theorem 3.3 in that paper) involves first approximately solving the multilinear relaxation (and then applying randomized swap rounding to the approximate fractional solution). This first step is done using the Continuous Greedy algorithm of [CCPV11], which has a very high polynomial running time and is widely regarded as impractical, see below:\n* [CCPV11]: “Our algorithm is conceptually quite simple and easy to implement; however, its running time is a different question. The variant described here would run in time on the order of $O(n^8)$, using $O(n^7)$ oracle queries”\n\n\n* [HKMS19]: “In particular, it is known that the Continuous Greedy algorithm achieves the tight $(1 − 1/e)$ approximation guarantee (...) with a prohibitive query complexity of $O(n^8)$”\n\n\n* [SM25]: “algorithms that … solve a continuous relaxation of the problem based on the multilinear relaxation, which is known to be impractical [5, 9, 15]. These algorithms do not scale to larger problem instances”\n\n\nReferences:\n\n* [CCPV11] Gruia Calinescu, Chandra Chekuri, Martin Pál, Jan Vondrák. Maximizing a Monotone Submodular Function Subject to a Matroid Constraint (SIAM Journal on Computing 2011)\n\n* [ETNV24] Marwa El Halabi, Jakub Tarnawski, Ashkan Norouzi-Fard, Thuy-Duong Vuong. Fairness in Submodular Maximization over a Matroid Constraint (AISTATS 2024)\n\n* [HKMS19] Amin Karbasi, Hamed Hassani, Aryan Mokhtari, Zebang Shen. Stochastic Continuous Greedy ++: When Upper and Lower Bounds Match (NeurIPS 2019)\n\n* [SM25] Fabian Spaeh, Atsushi Miyauchi. An asymptotically optimal approximation algorithm for multiobjective submodular maximization at scale (ICML 2025)\n\n\n> Is it possible to use concentration bounds and the algorithm of ETNV24 in order to meet the lower bounds with high probability? If so, what is the advantage of your algorithm in terms of meeting the fairness constraints? Related to above question, could you describe the theoretical guarantees of your algorithm compared to ETNV24 in more depth?\n\nLet us stress that an algorithm achieving both lower and upper fairness bounds only in expectation is quite a weak guarantee. For clarity let us focus on the MSPM (the bipartite perfect matching) case. There, such an algorithm actually gives no theoretical guarantee. In principle, it could return a solution that, for a vertex $v$, has 0 incident edges with probability 0.99, and 100 incident edges with probability 0.01, and still meet the in-expectation guarantee. If one wants to return a matching (i.e. if the upper bound constraints are hard, as they are for all the other algorithms considered in our paper), one has to then delete 99 of the 100 edges, which will spoil both the objective value and the solution cardinality.\n\nThe [ENTV24] algorithm does satisfy concentration bounds (see Theorem 3.3 there, as well as a slightly better bound in Remark B.1), but as stated, these are only meaningful for large values of $\\ell_c$. By opening up the algorithm and its proof, one can use the bounds for randomized swap rounding [CVZ10, Theorem II.3] to get some meaningful bound: $P(|S \\cap \\delta(v)| \\ge 1) \\ge 1 - e^{-1/2} \\approx 0.4$. This means that, for a bipartite graph with $n+n=2n$ vertices, $0.4n$ right-side vertices will be guaranteed to have an incident edge in $S$; when we select one edge per right-side vertex, we can expect a matching of size $0.4n$, and one can perhaps hope for a similar bound on submodular value, i.e., $0.4 (1-1/e) OPT \\approx 0.25 OPT$. But a simple greedy algorithm gets $0.5 n$ and $OPT/3$ respectively. This is why on line 78 we say that for MSPM, [ENTV24] gives no improvement upon the simple greedy algorithm; we will expand this in the final version.\n\nIt is not clear how one could use concentration bounds to satisfy lower bounds with high probability.\n\nLet us remark that the limitations of the [ENTV24] algorithm are intuitively to be expected, as it is based on the multilinear relaxation, and as such is subject to the $\\Omega(\\sqrt{|E_G|})$ integrality gap proved also in [ENTV24].\n\nReference:\n* [CVZ10] Chandra Chekuri; Jan Vondrak; Rico Zenklusen. Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures (FOCS 2010)\n\n> What do you mean by that you are \"giving guarantees for every individual group rather than only in aggregate\" in contrast to related work?\n\nApologies for the confusion; this is in contrast to the simple greedy strategy discussed on lines 75-82. We will improve the writing there."}, {"review_id": "vzB0HOzwCT", "reviewer": "Reviewer_6JcZ", "summary": "This paper presents an improved algorithm for the Fair Matroid Max-Sum Maximization (FMMSM) problem. For any \\epsilon> 0, the proposed method returns an approximate solution that satisfies the matroid constraint and all fairness upper bound constraints, while ensuring that each fairness lower bound is met in expectation up to a (1 − \\epsilon) factor. The paper is really about constrained submodular maximization with complicated constraints, such as partition matroid and lower fairness constraints.", "questions": "I would really like to see a real application of this setup.", "limitations": "Even though I am not an expert in the fairness literature, I am less convinced that this formulation is the right one.", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "While the theoretical analysis is technically sound, the contribution feels fairly incremental given the existing literature, particularly [EFNTT23] and [ETNV24], which already address many of the core ideas and challenges in this setting. Additionally, I find the problem formulation difficult to justify, I am not really sure why why this setup captures a meaningful or realistic fairness scenario, and it comes across as somewhat ad hoc without a compelling motivating application.\n\nThe experimental results in Section 4, though easy to follow, also feel artificially constructed. The examples, such as exemplar-based clustering and graph coverage, are nearly identical to those commonly seen in the submodular maximization literature. This raises concerns about how well the proposed method generalizes beyond these stylized benchmarks. A broader or more practical evaluation would help establish the real-world relevance of the approach.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review. \n\n\n> While the theoretical analysis is technically sound, the contribution feels fairly incremental given the existing literature, particularly [EFNTT23] and [ETNV24], which already address many of the core ideas and challenges in this setting. \n\nWhile there have indeed been prior attempts at the problem, we would like to stress that none of the prior approaches are able to satisfy more than 1/2 of the fairness lower bound constraint mass, and especially in the crucial special case of bipartite perfect matchings (MSPM), do not guarantee anything for a given vertex (i.e., some unlucky group may never be represented in the solution). In scenarios involving fairness, it is crucial to violate these constraints as little as possible, and this is the focus of our work.\n\n\n> Additionally, I find the problem formulation difficult to justify, I am not really sure why why this setup captures a meaningful or realistic fairness scenario, and it comes across as somewhat ad hoc without a compelling motivating application. (...) Even though I am not an expert in the fairness literature, I am less convinced that this formulation is the right one.\n\nThe problem formulation and the group fairness model are standard in the field, for both submodular maximization [CHV18; EMNTT20; WFM21; TY23; TYM23; YT23; EFNTT23; ETNV24] as well as a multitude of other optimization problems, such as clustering [CKLV17, KAM19, JNN20, HMV23], voting [CHV18], data summarization [CKSDKV18], ranking [CSV18] or matching [CKLV19]. It is important to remember that no universal definition of fairness exists, and the choice of which definition to use is application-dependent and an active area of research. However, our notion of fairness is standard, general, well-studied for many problems, and it also generalizes several other fairness notions, such as proportional representation [Mon95; BLS17], diversity constraints [CCRL13; Bid06], or statistical parity [DHPRZ12]. \n\nReferences not included in the submission:\n\n* [KAM19] Matthäus Kleindessner, Pranjal Awasthi, Jamie Morgenstern. Fair k-Center Clustering for Data Summarization. Proceedings of the 36th International Conference on Machine Learning (ICML), PMLR 97:3448-3457, 2019.\n\n* [JNN20] M. Jones, H. Nguyen, and T. Nguyen. Fair k-centers via maximum matching. In Proceedings of the International Conference on Machine Learning (ICML), pages 4940–4949, 2020.\n\n* [HMV23] Sedjro Salomon Hotegni, Sepideh Mahabadi, Ali Vakilian. Approximation Algorithms for Fair Range Clustering. Proceedings of the 40th International Conference on Machine Learning (ICML), PMLR 202:13270-13284, 2023.\n\n* [TY23] Shaojie Tang and Jing Yuan. Beyond submodularity: a unified framework of randomized set selection with group fairness constraints. Journal of Combinatorial Optimization, 45(4):102, 2023.\n\n* [TYM23] Shaojie Tang, Jing Yuan, and Twumasi Mensah-Boateng. Achieving long-term fairness in submodular maximization through randomization. arXiv preprint arXiv:2304.04700, 2023.\n\n* [YT23] Jing Yuan and Shaojie Tang. Group fairness in non-monotone submodular maximization. Journal of Combinatorial Optimization, 45(3):88, 2023.\n\n* [WFM21] Yanhao Wang, Francesco Fabbri, and Michael Mathioudakis. Fair and representative subset selection from data streams. In Proceedings of the Web Conference 2021, pages 1340–1350, 2021.\n\n> The experimental results in Section 4, though easy to follow, also feel artificially constructed. The examples, such as exemplar-based clustering and graph coverage, are nearly identical to those commonly seen in the submodular maximization literature. This raises concerns about how well the proposed method generalizes beyond these stylized benchmarks. A broader or more practical evaluation would help establish the real-world relevance of the approach.\n\nAlso here, we see it as an asset of our paper that we conform with the standard benchmarks and evaluations in the field. The focus is to evaluate the effectiveness of our proposed algorithm and compare it fairly against prior approaches, rather than to find new applications of the well-established problem setting."}, {"review_id": "3OQSpmlScH", "reviewer": "Reviewer_46DW", "summary": "The authors study the problem of maximizing a submodular function due to two types of constraints, both forming a matroid. The idea is that one type of constraints is standard, due to some structural requirements of the outcome. The second type of constraints comes from the fairness requirements: we want each protected group to be fairly represented in the selected set of elements. The problem has been already studied, and so far an algorithm was known that can violate the fairness constraints by a factor of 2, at the same time obtaining a half of the standard approximation for maximinzing a submodular function. The authors introduce a family of algorithms, parameterised by \\epsilon, which trade objective function for the extent to which fairness constraints are satisfied.", "questions": "* Does it make sense to combine your algorithm with the two-pass, and always pick the solution that achieves better objective?\n* How to set the value of \\epsilon in practice?\n* Since two-pass and your algorithm use different ideas, is it possible to combine the two, and get an even better solution?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 2, "strengths_and_weaknesses": "Strengths:\n* this is an important and well motivated problem,\n* the algorithm outperforms the currently know  solution with respect to both criterion on some datasets. \n\nWeaknesses:\n* the originality is limited since some well-performing algorithm for the exact problem has been already known,\n* while it is good to have a spectrum of algorithms that trade objective function for fairness constraints, it is still unclear how \\epsilon should be set.", "was_revised": true, "final_justification": "Thank you for your your answers!", "rebuttal": "Thank you for your thoughtful review. \n\n\n> the originality is limited since some well-performing algorithm for the exact problem has been already known,\n\nWhile there have indeed been prior attempts at the problem, we would like to stress that none of the prior approaches are able to satisfy more than 1/2 of the fairness lower bound constraint mass, and especially in the crucial special case of bipartite perfect matchings (MSPM), do not guarantee anything for a given vertex (i.e., some unlucky group may never be represented in the solution). In scenarios involving fairness, it is crucial to violate these constraints as little as possible, and this is the focus of our work.\n\n\n> while it is good to have a spectrum of algorithms that trade objective function for fairness constraints, it is still unclear how \\epsilon should be set. How to set the value of \\epsilon in practice?\n\nIn general, a larger epsilon is better if the user considers the objective value more important than the fairness constraints, and a smaller epsilon is better in the opposite case. How exactly to set it is up to the user and will be application-dependent.\n\nWe remark that a single execution of the algorithm can return solutions for all possible epsilon values (as we iteratively apply augmenting or alternating sets, this corresponds to epsilon decreasing). So a user could also, for example, adaptively keep running the algorithm as long as the objective value remains acceptable, and obtain better and better fairness (without paying any extra factor in the running time).\n\n\n> Does it make sense to combine your algorithm with the two-pass, and always pick the solution that achieves better objective? Since two-pass and your algorithm use different ideas, is it possible to combine the two, and get an even better solution?\n\nIt is not clear to us how to combine the ideas of the two algorithms. In practice, one can run the two and select a “better” solution, though care must be taken as to how this is selected so that new bias is not introduced (e.g. if we select the higher objective value, this could risk losing the fairness guarantees)."}, {"review_id": "t7V5deOvHX", "reviewer": "Reviewer_mGZA", "summary": "The paper studies offline monotone submodular maximization subject to a matroid and a fairness constraint, described as follows:\n\nThere is a ground set $V$ partitioned into subsets $V_1, V_2, \\cdots, V_C$. \n\nFor each $c \\in [C]$, there are associated lower and upper bounds $l_c$ and $u_c$, respectively. \n\nWe are given oracle access to a monotone submodular function $f$ and a matroid $\\mathcal{I}$ defined on the ground set $V$. \n\nThe objective is to find a set $S$ that maximizes $f(S)$ subject to satisfying the following properties:\n\n$S$ is independent in the matroid ($S \\in \\mathcal{I}$).\n\nFor each  $c \\in [C]$: $l_c \\le |S \\cap V_c| \\le u_c$. \n\n\n\nIn this paper, the authors develop an algorithm that, for each $\\epsilon \\in (0, 1)$, outputs a solution that satisfies the matroid and upper bound constraints; for each $c \\in [C]$ satisfies a relaxed version of its lower bound constraint ($|S \\cap V_c| \\ge (1 - \\epsilon)l_c$) in expectation; and in expectation obtains a submodular value at least $0.499 \\cdot \\epsilon \\cdot OPT$.", "questions": ".", "limitations": "yes.", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nClarity and completeness in definitions and problem formulation.\n\nThe introduction is informative, it includes insightful discussions about the difficult special case of MSPM, clearly outlines existing results, their limitations and their contribution in comparison. \n\nAlthough, I could not fully read and verify the correctness of the proofs provided in the supplementary material, they seemed detailed. \n\nWeaknesses:\n\nThe approximation ratio of $0.499 \\cdot \\epsilon$ is quite weak.  \nThe fact that authors compare their solution with a stronger notion of OPT, get a weak approximation guarantee and then blame the weakness of their result on this choice is not justified for me. \n\nThe algorithms are not clearly outlined. \n\nThe running time of the algorithm is not mentioned in the paper. [I only noticed a computational complexity paragraph in the experimental section(why?) in the supplementary material. \n\nIt would have been better if you also included your final results when using the greedy algorithm instead of the local search one. (Right now, the algorithm used in experimental section mismatches the one used for theoretical results.)", "was_revised": true, "final_justification": "Regarding approximation ratio: \n\nMy main concern with the result, the weakness of its approximation guarantee, remains a serious issue.\n\nTo further clarify this weakness, it should be noted that in the presence of a multiplicative factor of $\\epsilon$, the term $0.499$ is just a constant that bears no significant meaning.\nI even believe that expressing the guarantee as $0.499 \\cdot \\epsilon \\cdot OPT$, even if correct (with the more accurate form likely being $0.499 \\cdot O(\\epsilon) \\cdot OPT$ according to proof of theorem 3.4), is misleading. It is more transparent to state that the result provides an $O(\\epsilon)$-approximation guarantee.\n\nConcerning the remark about the stronger notion of OPT, I understand your remark and agree with the underlying point you intended to convey. However, the issue remains that, while this remark explains the weakness of your guarantee, it does not justify it, since comparing against a stronger notion of OPT was your own choice.\nAdditionally, regarding your last sentence, I disagree that comparison with a stronger OPT is a plus in your case. Such a comparison is deemed strong as it allows one to argue that the actual ratio is even better than the one stated. \nThis argument could be meaningful and showcase the strength of the algorithm when the provided approximation ratio is already reasonably strong and acceptable, but this is not the case when the provided lower bound is weak. \n\n___\n\nRegarding rest of the comments:\n\nAlthough I am not fully convinced by the space constraint explanation (given the no-limit policy on supplementary material), I appreciate the willingness to incorporate the suggested changes. However, as noted earlier, some of the important parts of the paper are currently missing. It is difficult to follow and verify the ideas of the algorithm and its analysis \nin the current form of the paper, which warrants substantial revisions. Therefore, I believe the paper requires an additional round of reviews after the updates are made.", "rebuttal": "Thank you for your thoughtful review and your comments, which will help us improve the final version of the paper. \n\n> The approximation ratio of 0.499 eps is quite weak. The fact that authors compare their solution with a stronger notion of OPT, get a weak approximation guarantee and then blame the weakness of their result on this choice is not justified for me.\n\nIt is an exciting open problem to obtain stronger approximation guarantees. The main aim of our remark is to point out that in order to do so, one needs to find a way to compare to a more precise bound on OPT. (Though it is also a plus that our guarantee is with respect to a stronger OPT.)\n\n> The algorithms are not clearly outlined.\n> The running time of the algorithm is not mentioned in the paper. [I only noticed a computational complexity paragraph in the experimental section(why?) in the supplementary material.\n> It would have been better if you also included your final results when using the greedy algorithm instead of the local search one. (Right now, the algorithm used in experimental section mismatches the one used for theoretical results.)\n\nMost of the above was due to space constraints; we will implement all of your feedback in the final version of the paper. In particular, we will add pseudocode for the main algorithm, and a version of our results with both Greedy and local search (with Greedy, one gets $1/3$ in place of $0.499$). We do not mention running time in the main body of the paper primarily due to space constraints and because the algorithm clearly runs in polynomial time; these considerations become more important when the implementations are concerned."}, {"review_id": "sal8DGXYvF", "reviewer": "Reviewer_AhMU", "summary": "This paper studies the problem of fair matroid monotone submodular maximization (FMMSM); the objective of this problem must take care of fairness constraints in addition to classic matroid optimization. The main results of this paper (Theorems 1.3 and 1.4) have impressive contributions in addition to earlier results, as their algorithms satisfy the fairness constraints to a tighter extent.", "questions": "N/A", "limitations": "Yes, in Section 5.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. This is a rigorous theoretical paper and the theoretical analysis is sound. It is also well-written in a clear, straight-forward style.\n2. The improvements on tightness are impressive. It never violates the upper bound, and the lower bound violation factor of $1-\\varepsilon$ is substantial, both for the randomized problem (Theorem 1.3) and deterministic solution (Theorem 1.4) with an additional constraint.\n3. The techniques (pages 3-4) are novel to the best of my knowledge, and discussed intuitively and clearly in the section.\n\nWeaknesses:\nN/A. Although the tightness is still not optimal and constraints make the solution not universally applicable, any concrete progress on this difficult problem is meaningful.", "was_revised": true, "final_justification": "The paper is strong due to technical novelty and depth. I maintain my score.", "rebuttal": "Thank you for your thoughtful review."}]

Author rebuttal:

Meta-review: The paper proposes a new algorithm for the matroid submodular optimization problem under matroid constraint, improving previous work on the same problems.

The problem studied in the paper is interesting and clearly improve on previous work. 

Few improvements suggested by multiple reviewers are:
- more in depth description of the novelty of the work, currently the results look a bit incremental
- more in depth comparison with ETNV24
Decision: Accept (poster)