Fairness in Submodular Maximization over a Matroid Constraint

Abstract

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

1 Introduction

Machine learning algorithms are increasingly used in decision-making processes.
This can potentially lead to the introduction or perpetuation of bias and discrimination in automated decisions. Of particular concern are sensitive areas such as education, hiring, credit access, bail decisions, and law enforcement Munoz et al. (2016); White House OSTP (2022); European Union FRA (2022).
There has been a growing body of work
attempting to mitigate these risks
by
developing fair algorithms
for fundamental problems
including
classification Zafar et al. (2017), ranking Celis et al. (2018c), clustering Chierichetti et al. (2017), voting Celis et al. (2018a), matching Chierichetti et al. (2019), influence maximization Tsang et al. (2019), data summarization Celis et al. (2018b), and many others.

In this work, we address fairness in the fundamental problem of submodular maximization over a matroid constraint, in the offline setting.
Submodular functions model a diminishing returns property that naturally occurs in a variety of machine learning problems
such as active learning Golovin and Krause (2011), data summarization Lin and Bilmes (2011), feature selection Das and Kempe (2011), and recommender systems El-Arini and Guestrin (2011).
Matroids represent a popular and expressive notion of independence systems that encompasses a broad spectrum of useful constraints, e.g. cardinality, block cardinality, linear independence, and connectivity constraints.

Several definitions of algorithmic fairness have been proposed in the literature,
but no universal metric exists.
Here we adopt the common notion used in many prior studies Celis et al. (2018a); Celis et al. (2018b); Celis et al. (2018c); Chierichetti et al. (2017); Chierichetti et al. (2019)
that requires a solution to be fair with respect to a sensitive attribute such as race or gender.
Formally, given a set V of n items, each item is associated with a color c representing a sensitive attribute. Let V_{1},\ldots,V_{C} denote the corresponding C disjoint groups of items of the same color.
A set S\subseteq V is fair if \ell_{c}\leq|S\cap V_{c}|\leq u_{c} for all c, for some chosen lower and upper bounds \ell_{c},u_{c}\in\mathbb{N}.
This notion subsumes several other fairness definitions, e.g. diversity rules Cohoon et al. (2013); Biddle (2006), statistical parity Dwork et al. (2012),
or proportional representation rules Monroe (1995); Brill et al. (2017).
See Celis et al. (2018a, Section 4) for a more detailed overview.

Without fairness, the problem of maximizing a submodular function over a matroid constraint in the offline setting has been studied extensively. For monotone objectives, a tight (1-1/e)-approximation is known Calinescu et al. (2011b); Feige (1998), while for non-monotone objectives the best known approximation is 0.401 given in Buchbinder and Feldman (2023). An information-theoretic hardness of 0.478 was also shown for the non-monotone case in Oveis Gharan and Vondrák (2011).

Fair submodular maximization has been considered under a cardinality constraint, in both the offline and streaming models. Celis et al. (2018a) presented a tight (1-1/e)-approximation to the problem in the offline setting with monotone objectives. In the streaming setting,
El Halabi et al. (2020) gave a one-pass 0.3178-approximation algorithm in the monotone case, and a one-pass 0.1921q-approximation algorithm in the non-monotone case, where q=1-\max_{c}\tfrac{\ell_{c}}{|V_{c}|}. They also showed that achieving a better than q-approximation in this case requires \Omega(n) memory.

Fair submodular maximization under a general matroid constraint was only studied in the streaming setting, and only for monotone objectives. El Halabi et al. (2023) provided a one-pass {}1/2-approximation algorithm that uses time and memory exponential in the rank of the matroid; this factor is tight Feldman et al. (2020).
They also gave a polynomial-time two-pass {}1/11.656-approximation
which uses O(k\cdot C) memory and violates the fairness lower bounds by a factor 2.

While some applications necessitate algorithms that use small memory compared to the data size, others can afford a larger memory budget.
In this work, we focus on the classic offline setting, which has not yet been studied despite being more basic than streaming.
Our results show that it is possible to obtain stronger performance guarantees in this case.
We also consider both monotone and non-monotone objectives, which cover a wider range of applications.

1.1 Our contributions

We present several algorithms and impossibility results for fair matroid submodular maximization (FMSM) in the offline setting, with trade-offs between quality, fairness, and generality. Table 1 summarizes our approximation results and prior ones for this problem.

Table 1: Summary of results for FMSM in the offline setting (only polynomial-time algorithms with respect to n,k and C are included). In the “Fairness Approx.” column, a (\theta_{1},\theta_{2}) entry means the algorithm’s output satisfies |S\cap V_{c}|\in[\theta_{1}\ell_{c},\theta_{2}u_{c}]. The parameters \epsilon>0, \beta\in[0,1/2] are arbitrary constants, and r=\min_{x\in P_{\mathcal{F}}\cup(\mathds{1}-P_{\mathcal{F}})}\|x\|_{\infty}.

Function
Matroid
Approx. Ratio
Fairness Approx.

Monotone
General
{}1-1/e (Thm. 3.3)
(1,1) in expectation

Non-monotone
General
(1-r-\epsilon)/4 (Thm. 3.3)
(1-\sqrt{3{\ln(2C)}/{\ell_{c}}},1+\sqrt{3{\ln(2C)}/{u_{c}}})

Monotone
General
{}1/(4+\epsilon) El Halabi et al. (2023)
(1/2,1)

Non-monotone
General
(1-\beta)/(8+\epsilon) (Thm. 3.1)
(\beta,1)

Monotone
Uniform
{}1-1/e (Celis et al., 2018a)
(1,1)

Non-monotone
Uniform
{}0.401(1-r) (Thm. 3.6)
(1,1)

Monotone decomposable
General
{}1-1/e (Thm. 4.4)
(1,1)

Non-monotone decomposable
General
(1-r-\epsilon)/4 (Thm. 4.4)
(1,1)

First, we observe that the streaming algorithms of El Halabi et al. (2023) for monotone objectives apply in the offline setting. This yields a {}1/2-approximation in exponential time with respect to the rank of the matroid. And, with a slight modification, the two-pass algorithm therein achieves a {}1/(4+\epsilon)-approximation in polynomial time, with a factor-2 violation of the fairness lower bounds.
We extend the latter result to non-monotone objectives, obtaining a (1-\beta)/(8+\epsilon)-approximation with a {}1/\beta violation of the fairness lower bounds, for any \beta\in[0,1/2] (Theorem 3.1).

It is of course preferable to obtain algorithms that satisfy the fairness constraints exactly.
However, we give strong evidence that this is very challenging in general.
A commonly used approach for submodular maximization problems is relax-and-round,
which consists of first solving a continuous relaxation of the problem obtained using the multilinear extension (see definition in Section 2) of the objective over the convex hull P_{\mathcal{F}} of the domain, then rounding the fractional solution.
Most studied submodular maximization problems
that admit a constant-factor approximation algorithm
also admit one based on the relax-and-round approach.
Unfortunately,
we show that for FMSM,
this approach cannot yield a better than O(1/\sqrt{n})-approximation in general (Theorem 3.2),
even for monotone objectives.

Yet,
if we allow the fairness constraint to be satisfied only in expectation, we can adapt this approach to obtain a tight (1-1/e)-approximation in expectation for monotone objectives. For non-monotone objectives, the approximation becomes (1-r-\epsilon)/4 where r is the minimum \ell_{\infty}-norm of any vector in P_{\mathcal{F}} or its complement. Both algorithms are also guaranteed to only violate the fairness constraints by a multiplicative factor expected to be small in practice (Theorem 3.3).

In fact,
the factor r is closely tied to the hardness of non-monotone FMSM.
We show that no algorithm can achieve a better than (1-r)-approximation in sub-exponential time, even without the matroid constraint (Theorem 3.7). In the case of uniform or no matroid, {}1-r coincides with the notion of excess ratio q=1-\max_{c}\tfrac{\ell_{c}}{|V_{c}|} studied by El Halabi et al. (2020). As such, this inapproximability result extends the one provided therein for the streaming setting.

While the (1-r) factor in the approximation for non-monotone FMSM cannot be improved even for the uniform matroid, we show that the {}1/4 factor can be improved to 0.401 in this case (Theorem 3.6). This improves over the 0.1921q-approximation of El Halabi et al. (2020) in the streaming setting.

Finally, we study an interesting subclass of FMSM, which we call decomposable FMSM, where the objective decomposes into submodular functions on the equivalence classes of the matroid (see Definition 2.3) or on the color groups of the fairness constraint. This subclass enables us to consider fairness in the important submodular welfare problem (see Section 2). We provide a tight (1-1/e)-approximation to decomposable FMSM for monotone objectives and a (1-r-\epsilon)/4 for non-monotone objectives, in expectation, without violating the fairness constraint (Corollary 4.4).

1.2 Additional related work

Before this paper, non-monotone FMSM was only studied in the offline setting in the special case of cardinality constraint
by Yuan and Tang (2023), who obtained a 0.2005-approximation for a specific setting of fairness bounds where \tfrac{\ell_{c}}{|V_{c}|}=a and \tfrac{u_{c}}{|V_{c}|}=b for all c, for some constants a,b\in[0,1]. Our results recover their guarantee (see Theorem 3.6 and the discussion below it).

Several works have studied other special cases and variants of FMSM.
Wang et al. (2021) studied a special case of monotone FMSM in the streaming setting, where fairness lower and upper bounds are equal for each color, i.e., \ell_{c}=u_{c} for all c and without any matroid constraint.
Tang et al. (2023) and Tang and Yuan (2023) studied a randomized variant of FMSM with cardinality constraint in the offline setting, where fairness constraint only needs to be satisfied in expectation.

A closely related problem to FMSM is submodular maximization over two matroid constraints; FMSM reduces to this problem when \ell_{c}=0 for all c.
Lee et al. (2010) gave a {}1/(2+\epsilon)-approximation for this problem for monotone objectives, and a {}1/(4+\epsilon)-approximation for non-monotone objectives.

An important special case of decomposable FMSM arises by considering fairness in the submodular welfare problem. Without fairness, this is a well-studied problem for which a tight (1-1/e)-approximation is known Vondrák (2008); Khot et al. (2005). The submodular welfare problem has many practical applications, including resource allocation in wireless networks, budget allocation in advertising campaigns, and division of resources among multiple stakeholders. In several of these applications, it is important to ensure that the selected allocation is fair. Fairness in the submodular welfare problem has been studied by Benabbou et al. (2021), Aziz et al. (2023), and Sun et al. (2023).
However, these works consider different notions of fairness than we do: fairness is imposed on the value received by each individual in the selected allocation, instead of the size of the allocation assigned to each group of individuals.

In this work, we focus on the case where the color groups are disjoint. The case where groups can overlap was considered in Celis et al. (2018a) for the special case of monotone FMSM with cardinality constraint. They show that when elements can be assigned to 3 or more colors, even determining feasibility is NP-hard. But if fairness constraints are allowed to be violated, they give a (1-1/e-o(1))-approximation algorithm, which satisfies the fairness constraint in expectation. Our result for general monotone FMSM (Theorem 3.3) is based on the same tools used for this result.

Fairness in submodular maximization has also been studied under a different notion of fairness Wang et al. (2024); Tsang et al. (2019); Tang and Yuan (2023) which imposes a lower bound on the value that each group derives from the solution, where groups are not necessarily subsets of V, and the value is modeled by a monotone submodular function. Both the variant of fair submodular maximization considered in this line of work and our work can be formulated as variants of multi-objective submodular maximization problems Krause et al. (2008); Udwani (2018); Chekuri et al. (2010); see Appendix C for details.

2 Preliminaries

Consider a ground set V with n items and a non-negative set function f:2^{V}\to\mathbb{R}_{+}. We say that f is submodular if f(Y\cup\{e\})-f(Y)\geq f(X\cup\{e\})-f(X)
for any two sets Y\subseteq X\subseteq V and any element e\in V\setminus X. Moreover, f is monotone if f(Y)\leq f(X) for any two sets Y\subseteq X\subseteq V,
and non-monotone otherwise. Throughout the paper, we assume that f is given as a value oracle that computes f(S) given S\subseteq V.

Matroids.

A matroid is a family of sets \mathcal{I}\subseteq 2^{V} with the following properties:

• •

if X\subseteq Y and Y\in\mathcal{I}, then X\in\mathcal{I};

• •

if X,Y\in\mathcal{I} with |X|<|Y|, then there exists e\in Y such that X+e\in\mathcal{I}.

We use X+e for X\cup\{e\}. We assume that the matroid is given as an independence oracle. We call a set X\subseteq V independent if X\in\mathcal{I} and a base if it is also maximal with respect to inclusion. All the bases of a matroid share the same cardinality k, referred to as the rank of the matroid.
Partition matroids are an important class of matroids where V is partitioned into \bigcup_{i}G_{i}, where each block G_{i} has an upper bound k_{i}\in\mathbb{N}, and a set X is independent if |X\cap G_{i}|\leq k_{i} for all i.

Fair Matroid Submodular Maximization (FMSM).

Let V be partitioned into C sets, where V_{c} denotes items of color c for all c\in[C]=\{1,\cdots,C\}. Given fairness bounds (\ell_{c},u_{c})_{c\in[C]} and a matroid \mathcal{I}\subseteq 2^{V} of rank k, the collections of fair sets \mathcal{C} and feasible sets \mathcal{F} are defined as:

\displaystyle\mathcal{C} \\ \displaystyle=\{S\subseteq V\mid\ell_{c}\leq|S\cap V_{c}|\leq u_{c}\;\ \forall c\in[C]\}\,, \\ \displaystyle\mathcal{F} \\ \displaystyle=\mathcal{I}\cap\mathcal{C}\,.

In FMSM, the goal is to find a set S\in\mathcal{F} that maximizes f(S). We use \operatorname{OPT} to refer to the optimal value, i.e., \operatorname{OPT}=\max_{S\in\mathcal{F}}f(S). We assume a feasible solution exists, i.e., \mathcal{F}\neq\emptyset. An algorithm is an α-approximation to FMSM if it outputs a set S\in\mathcal{F} such that f(S)\geq\alpha\cdot\operatorname{OPT}.

We denote the convex hull of indicator vectors of fair sets by P_{\mathcal{C}}=\mathrm{conv}(\{\mathds{1}_{S}\mid S\in\mathcal{C}\}) (fairness polytope),
of independent sets by P_{\mathcal{I}}=\mathrm{conv}(\{\mathds{1}_{S}\mid S\in\mathcal{I}\}) (matroid polytope),
and of feasible sets by P_{\mathcal{F}}=\mathrm{conv}(\{\mathds{1}_{S}\mid S\in\mathcal{F}\}) (feasible polytope). We also define the complement of P_{\mathcal{F}} as \mathds{1}-P_{\mathcal{F}}=\{x\in[0,1]^{n}\mid\mathds{1}-x\in P_{\mathcal{F}}\},
where \mathds{1} is the all-ones vector.
We recall in the following lemma some useful properties shown by El Halabi et al. (2023, Lemma C.1, Corollary C.4, Theorem C.5).

Lemma 2.1.

The following hold:

• a.

P_{\mathcal{C}}=\{x\in[0,1]^{n}:\sum_{i\in V_{c}}x_{i}\in[\ell_{c},u_{c}]\;\forall c\in[C]\}.

• b.

P_{\mathcal{F}} corresponds to the intersection of the matroid and fairness polytopes: P_{\mathcal{F}}=P_{\mathcal{I}}\cap P_{\mathcal{C}}.

• c.

P_{\mathcal{F}} is solvable, i.e., linear functions can be maximized over it in polynomial time.

The following lemma from (Buchbinder et al., 2014, Lemma 2.2) will be useful in the non-monotone case.

Lemma 2.2.

Let g be a non-negative submodular function and let B be a random subset of V containing every element of V with probability at most p (not necessarily independently). Then \operatorname{\mathbb{E}}[g(B)]\geq(1-p)g(\emptyset).

Multilinear extension.

An important concept in submodular maximization is the multilinear extension F:[0,1]^{n}\to\mathbb{R}_{+} of a submodular function f:

F(x)=\operatorname{\mathbb{E}}[f(R(x))]=\sum_{S\subseteq V}f(S)\prod_{i\in S}x_{i}\prod_{j\in V\setminus S}(1-x_{j}),

where R(x) is the set obtained by independently selecting each element i\in V with probability x_{i}.

Decomposable FMSM.

We also study a subclass of the FMSM problem where the objective decomposes into submodular functions on the equivalence classes of the matroid or on the color groups of the fairness constraint.
We recall the notion of equivalent elements in a matroid (Chekuri et al., 2010, Definition I.3).

Definition 2.3.

Two elements i,j\in V are equivalent in a matroid \mathcal{I} if for any set S\in\mathcal{I} not containing i and j, S+i\in\mathcal{I} if and only if S+j\in\mathcal{I}.

This defines an equivalence relation.
For example, the equivalence classes of a partition matroid are the partition groups G_{i}.

Definition 2.4.

Let \mathcal{G}\subseteq 2^{V} be the equivalence classes of the matroid \mathcal{I}. We say that f is a decomposable submodular function over \mathcal{F} if

f(S)=\sum_{G\in\mathcal{G}}f_{1,G}(S\cap G)+\sum_{c=1}^{C}f_{2,c}(S\cap V_{c}),

where f_{1,G},f_{2,c} are submodular functions.

Submodular welfare problem.

One noteworthy example of decomposable submodular functions arises from the submodular welfare problem.
In this problem, we are given a set of items B and a set of agents A each with a monotone submodular utility function w_{i}:2^{B}\to\mathbb{R}_{+}. The goal is to distribute the items among the agents to maximize the social welfare \sum_{i\in A}w_{i}(S_{i}), where (S_{i})_{i\in A} are the disjoint sets of items assigned to each agent. It is known that this problem can be written as a monotone submodular maximization over a partition matroid constraint by defining the ground set as V=A\times B, the objective as f(S)=\sum_{i\in A}w_{i}(S_{i}) where S_{i}=\{e\in B\mid(i,e)\in S\},
and using the partition matroid \mathcal{I}=\{S\subseteq V\mid(\forall e\in B)\ |S\cap(A\times\{e\})|\leq 1\} Lehmann et al. (2006). In certain applications, it is important to ensure that each group of agents receives a fair allocation of items. To that end, we introduce the fair submodular welfare problem, where each agent is assigned exactly one color c\in[C]; A_{c} is the set of agents of color c. Let V_{c}=A_{c}\times B and f_{c}(S)=\sum_{i\in A_{c}}w_{i}(S_{i}), then f_{c} is monotone submodular and f(S)=\sum_{c=1}^{C}f_{c}(S\cap V_{c}) is a monotone decomposable submodular function over \mathcal{F}. The fair submodular welfare problem is then a special case of monotone decomposable FMSM.

3 General case

In this section, we provide algorithms and impossibility results for FMSM with general submodular objectives.

3.1 Algorithms with lower bounds violation

We start by providing constant-factor approximation algorithms for FMSM that violate the fairness lower bounds by a constant factor.
Such an algorithm can be directly obtained in the monotone case from the two-pass streaming algorithm of El Halabi et al. (2023, Section 4).
In the first pass, their algorithm finds a feasible set S; in the second pass, S is extended to an \alpha/2-approximate solution which violates the lower bounds by a factor 2, using an α-approximation algorithm \mathcal{A} for monotone submodular maximization over the intersection of two matroids.
Using the state-of-the-art offline {}1/(2+\epsilon)-approximation algorithm of Lee et al. (2010, Theorem 3.1) as \mathcal{A}, instead of a streaming algorithm,
directly yields an improved {}1/(4+\epsilon)-approximation ratio.

We adapt this algorithm to non-monotone objectives by randomly dropping an appropriate number of elements from S to balance the loss in objective value and the violation of the fairness lower bounds.
We defer the details to Appendix A.

Theorem 3.1.

There exists a polynomial-time algorithm for non-monotone FMSM, which outputs a set S such that (i) S\in\mathcal{I}, (ii) \lfloor\beta\ell_{c}\rfloor\leq|V_{c}\cap S|\leq u_{c} for any color c\in[C], and (iii) \operatorname{\mathbb{E}}[f(S)]\geq(1-\beta)\mathrm{OPT}/(8+\epsilon) for any \beta\in[0,1/2] and \epsilon>0.

Proof sketch.

We extend the result of El Halabi et al. (2023, Lemma 4.3 and 4.4) to non-monotone objectives; showing that dropping elements from S allows us to only lose a factor (1-\beta), in expectation, in the objective value by Lemma 2.2, while keeping at least \lfloor\beta\ell_{c}\rfloor elements from each color.
Plugging in the state-of-the-art {}1/(4+\epsilon)-approximation algorithm of Lee et al. (2010, Theorem 4.1) as \mathcal{A} directly yields a (1-\beta)/(8+\epsilon)-approximation, in expectation.
∎

For example, if we accept a factor 2 violation of the fairness lower bounds (\beta=1/2), Theorem 3.1 gives a {}1/(16+\epsilon)-approximation for non-monotone FMSM.

Note that if we use a streaming algorithm for \mathcal{A}, the adapted algorithm becomes a two-pass streaming algorithm, as in the monotone case. In particular, using the state-of-the-art {}1/7.464-approximation algorithm by Garg et al. (2021, Theorem 19) yields a (1-\beta)/14.928-approximation in the streaming setting (Theorem A.3).

3.2 Hardness of rounding

The optimal approximation algorithms for maximizing a submodular function over a matroid constraint in Calinescu et al. (2011b); Feldman et al. (2011) rely on first approximately solving a continuous relaxation of the problem obtained by replacing f by its multilinear extension and the matroid constraint by its convex hull, then rounding the solution, which can be done without any loss of utility using pipage or swap rounding Calinescu et al. (2011b); Chekuri et al. (2010). It is then natural to attempt a similar relax-and-round approach here:
first approximately solve the continuous relaxation of FMSM,

\max_{x\in P_{\mathcal{F}}}F(x),

and then round the obtained solution to a set in \mathcal{F}.
Unfortunately, this approach fails in the presence of the fairness constraint! In particular, we show that the integrality gap of Problem (1)
is \Omega(\sqrt{n}), even for a monotone objective and a partition matroid. Hence, it is not possible to obtain better than O(1/\sqrt{n})-approximation using this approach.

Theorem 3.2.

There is a family of FMSM instances where f is monotone and \mathcal{I} is a partition matroid, for which the integral optimum solution has value 1, but the multilinear extension admits a fractional solution of value \Omega(\sqrt{n}).

Proof sketch.

We encode bipartite perfect matching as an instance of \mathcal{F} where \mathcal{I} is a partition matroid. Then we construct an instance where the objective is monotone and the bipartite graph has \Theta(\sqrt{n}) perfect matchings each of value 1, while taking x\in P_{\mathcal{F}} as the average of the indicator vectors of the perfect matchings yields F(x)=\Theta(\sqrt{n}).
∎

3.3 Algorithms with expected fairness

Motivated by Theorem 3.2, we adapt the relax-and-round approach to ignore the fairness constraints during the rounding phase.
This allows us to use the randomized swap rounding algorithm of Chekuri et al. (2010, Section IV)
to obtain an independent-set solution which preserves the same utility as the fractional solution,
and which satisfies the fairness constraints in expectation. This solution is further guaranteed, with constant probability, to
violate the fairness bounds by at most a multiplicative factor, expected to be small in practice.
This approach is inspired from Celis et al. (2018a, Theorem 14), who considered a special case of FMSM with a monotone objective and a uniform matroid, but with possibly non-disjoint color groups. Theorem 3.3 extends their result to any matroid and non-monotone objectives.
The non-monotone case is more challenging than the monotone case; we show in Section 3.5 that it is impossible to obtain an approximation better than (1-\min_{x\in P_{\mathcal{F}}\cup(\mathds{1}-P_{\mathcal{F}})}\|x\|_{\infty}) for non-monotone FMSM in sub-exponential time, even for solving the continuous Problem (1).

Theorem 3.3.

There exists a polynomial-time algorithm for FMSM which outputs a solution S\in\mathcal{I} such that \operatorname{\mathbb{E}}[|S\cap V_{c}|]\in[\ell_{c},u_{c}] and \operatorname{\mathbb{E}}[f(S)]\geq\alpha\operatorname{OPT},
where \alpha=1-1/e if f is monotone and \alpha=(1-\min_{x\in P_{\mathcal{F}}\cup(\mathds{1}-P_{\mathcal{F}})}\|x\|_{\infty}-\epsilon)/4 otherwise, for any \epsilon>0.
Moreover, the solution satisfies with constant probability the following for all c\in[C],

\left(1-\sqrt{\tfrac{3\ln(2C)}{\ell_{c}}}\right)\ell_{c}\leq|S\cap V_{c}|\leq\left(1+\sqrt{\tfrac{3\ln(2C)}{u_{c}}}\right)u_{c}.

Proof.

We first obtain an α-approximation fractional solution x\in P_{\mathcal{F}} for \max_{x\in P_{\mathcal{F}}}F(x). For monotone objectives, we can use the continuous greedy algorithm of Calinescu et al. (2011a, Section 3.1 and Appendix A), which achieves a (1-1/e)-approximation for maximizing the multilinear extension over any integral polytope, with high probability. Note that P_{\mathcal{F}} is integral as it is the convex hull of integral points.

For non-monotone objectives, we can use the Frank-Wolfe type algorithm of Du (2022, Sections 3.5 and 4.5) which achieves a (1-\min_{x\in P}\|x\|_{\infty}-\epsilon)/4-approximation for maximizing the multilinear extension over any polytope P, with high probability — see also (Mualem and Feldman, 2023, Section 3) for an explicit variant of the algorithm and its analysis.
To obtain the approximation ratio (1-\min_{x\in P_{\mathcal{F}}\cup\mathds{1}-P_{\mathcal{F}}}\|x\|_{\infty}-\epsilon)/4, we apply the algorithm of Du (2022) to both Problem (1) and its complement: \max_{x\in\mathds{1}-P_{\mathcal{F}}}\bar{F}(x), where \bar{F} is the multilinear extension of the complement \bar{f} of f; \bar{f}(S)=f(V\setminus S).
Both the continuous greedy and the Frank-Wolfe type algorithms run in polynomial time if the constraint polytope is solvable,
which is the case for P_{\mathcal{F}} and \mathds{1}-P_{\mathcal{F}} by Lemma 2.1-c.

Next we round the fractional solution x to an independent (but not necessarily feasible) set S\in\mathcal{I} using the randomized swap rounding scheme of Chekuri et al. (2010, Section IV). The rounded solution is guaranteed to satisfy \operatorname{\mathbb{E}}[|S\cap V_{c}|]=x(V_{c})\in[\ell_{c},u_{c}], \operatorname{\mathbb{E}}[f(S)]\geq F(x)\geq\alpha\operatorname{OPT} (see Theorem II.1 therein). The rest of the claim follows from the concentration bounds given in (Chekuri et al., 2010, Theorem II.1) and union bound.
See details in Section B.2.
∎

As discussed in Celis et al. (2018a) – see discussion under Theorem 14 therein – the violation of the fairness constraints in the above theorem is expected to be small, i.e., \sqrt{3\ln(2C)/u_{c}}\leq\sqrt{3\ln(2C)/\ell_{c}}\ll 1, in typical fairness applications.
However, in general, this violation can be arbitrarily bad. In particular, when \mathcal{F} encodes a bipartite perfect matching constraint, as in the proof of Theorem 3.2, we have C=\Theta(\sqrt{n}) and u_{c}=\ell_{c}=1, hence \sqrt{3\ln(2C)/u_{c}}=\sqrt{3\ln(2C)/\ell_{c}}\gg 1.

Note that the approximation ratio for non-monotone objectives in Theorem 3.3 can be as good as {}1/4 in some cases (for example if \ell_{c}=0 for all c or u_{c}=|V_{c}| for all c), but it can also be arbitrarily bad. To illustrate this,
we compute below the minimum \ell_{\infty}-norm of P_{\mathcal{F}} and its complement for two special cases of P_{\mathcal{F}}. See Section B.2 for the full proofs.

Example 3.4 (Uniform matroid).

Let \mathcal{I} be the uniform matroid with rank k. We order the color groups such that \tfrac{\ell_{1}}{|V_{1}|}\leq\cdots\leq\tfrac{\ell_{C}}{|V_{C}|} and let t be the largest index t\in[C] such that \tfrac{\ell_{t}}{|V_{t}|}\sum_{c=1}^{t}|V_{c}|+\sum_{c=t+1}^{C}\ell_{c}\leq k (t\geq 1 is well-defined since \mathcal{F}\not=\emptyset). Then \min_{x\in P_{\mathcal{F}}\cup(\mathds{1}-P_{\mathcal{F}})}\|x\|_{\infty}=\min\{\max_{c}\tfrac{\ell_{c}}{|V_{c}|},1-\min\{\tau,\min_{c\leq t}\tfrac{u_{c}}{|V_{c}|}\}\}, where \tau=\tfrac{k-\sum_{c=t+1}^{C}\ell_{c}}{\sum_{c=1}^{t}|V_{c}|}.

Proof sketch.

We construct closed-form solutions to \min_{x\in P_{\mathcal{F}}}\|x\|_{\infty} and \min_{x\in\mathds{1}-P_{\mathcal{F}}}\|x\|_{\infty} with \ell_{\infty}-norms \max_{c}\tfrac{\ell_{c}}{|V_{c}|} and {}1-\min\{\tau,\min_{c\leq t}\tfrac{u_{c}}{|V_{c}|}\}, respectively.
∎

The fairness bounds are often set such that the representation of color groups in a fair set is proportional to their representation in the ground set, i.e., \ell_{c},u_{c}\propto k|V_{c}|/n. If in particular \ell_{c}\leq k|V_{c}|/n for all c, we get in Example 3.4 t=C,\tau=k/n and \min_{x\in P_{\mathcal{F}}\cup(\mathds{1}-P_{\mathcal{F}})}\|x\|_{\infty}\leq\min\{k/n,1-k/n\}\leq 1/2. The corresponding approximation ratio in Theorem 3.3 for non-monotone objectives is then at least {}1/8-\epsilon.

Example 3.5 (Bipartite perfect matching).

Let \mathcal{F} be the feasible set
arising from the bipartite perfect matching problem
in the proof of the integrality gap Theorem 3.2.
We have \min_{x\in P_{\mathcal{F}}\cup(\mathds{1}-P_{\mathcal{F}})}\|x\|_{\infty}=1-\Theta(1/\sqrt{n}).

Proof sketch.

We show that the point x used in the proof of Theorem 3.2 is a solution of \min_{x\in P_{\mathcal{F}}\cup(\mathds{1}-P_{\mathcal{F}})}\|x\|_{\infty} with \|x\|_{\infty}=\|\mathds{1}-x\|_{\infty}=1-\Theta(1/\sqrt{n}).
∎

The corresponding approximation factor for Example 3.5 in Theorem 3.3 for non-monotone objectives is then O(1/\sqrt{n}). So relaxing the fairness constraints was not helpful in this case!

Recall that the (1-1/e)-approximation for monotone objectives in Theorem 3.3 is tight even without the fairness constraint Feige (1998). For non-monotone objectives,
the {}1/4 factor is also tight for maximizing the multilinear extension of a submodular function
over a general polytope (Mualem and Feldman, 2023, Theorem 5.1); so improving it, if possible, would require more specialized algorithms for solving Problem (1).

3.4 Uniform matroid case

In the special case of the uniform matroid, both the fairness violation and the approximation ratio for non-monotone objectives given in Theorem 3.3 can be improved.
In particular,
recall that a (1-1/e)-approximation can be obtained in this case for monotone objectives, without any violation of the fairness constraint (Celis et al., 2018a, Theorem 18). For non-monotone objectives, we show that a {}0.401(1-\min_{x\in P_{\mathcal{F}}\cup(\mathds{1}-P_{\mathcal{F}})}\|x\|_{\infty})-approximation can be obtained in expectation, also without any violation of the fairness constraint.

Theorem 3.6.

There exists a polynomial-time algorithm for non-monotone FMSM where \mathcal{I} is a uniform matroid, which achieves
{}0.401(1-\min_{x\in P_{\mathcal{F}}\cup(\mathds{1}-P_{\mathcal{F}})}\|x\|_{\infty})-approximation in expectation.

Proof sketch.

El Halabi et al. (2020, Theorem 5.2) presented a polynomial-time algorithm with an expected (1-\max_{c}\tfrac{\ell_{c}}{|V_{c}|})\alpha-approximation for non-monotone FMSM over a uniform matroid, given any α-approximation algorithm for non-monotone submodular maximization over a matroid constraint.
Plugging in the state-of-the-art 0.401-approximation of Buchbinder and Feldman (2023, Corollary 1.3) then yields a {}0.401(1-\max_{c}\tfrac{\ell_{c}}{|V_{c}|})-approximation in expectation.
Recall from Example 3.4 that \min_{x\in P_{\mathcal{F}}}\|x\|_{\infty}=\max_{c}\tfrac{\ell_{c}}{|V_{c}|}.

To obtain the potentially better approximation factor {}0.401(1-\min_{x\in\mathds{1}-P_{\mathcal{F}}}\|x\|_{\infty}), we solve (as in Theorem 3.3) the complement problem \max_{V\setminus S\in\mathcal{F}}\bar{f}(S).

We follow a similar strategy as El Halabi et al. (2020). Namely, we first drop the lower bounds from the constraint. The resulting problem \max_{S\subseteq V}\{\bar{f}(S):|S\cap V_{c}|\leq|V_{c}|-\ell_{c},~\forall c\in[C]\} is a non-monotone submodular maximization problem over a partition matroid. Hence, a solution S with an expected 0.401-approximation can be obtained for it.
Next, we augment S to a feasible solution by carefully sampling enough random elements from each color to satisfy the lower bounds. Each element e\in V\setminus S is added with probability at most \bar{x}_{e}, where \bar{x} is a solution of \min_{x\in\mathds{1}-P_{\mathcal{F}}}\|x\|_{\infty} as in Example 3.4. Finally, we use Lemma 2.2 to bound the loss in value resulting from the additional elements.
The sampling step is more involved here than in the original problem because \bar{x} is non-integral. See details in Section B.3.
∎

Theorem 3.6 recovers the result of Yuan and Tang (2023) for the special case where \tfrac{\ell_{c}}{|V_{c}|}=a and \tfrac{u_{c}}{|V_{c}|}=b for all c\in[C], for some constants a,b\in[0,1].2 Indeed, in that case t=C and \tau=k/n\geq a in Example 3.4, and \min_{x\in P_{\mathcal{F}}\cup(\mathds{1}-P_{\mathcal{F}})}\|x\|_{\infty}=\min\{a,1-\min\{k/n,b\}\}, so the resulting approximation ratio is at least
{}0.401\max\{1-a,a\}\geq 0.2005.

More generally, for the typical choice of fairness bounds discussed earlier in Section 3.3, where \ell_{c}\leq k|V_{c}|/n for all c, the resulting approximation ratio is also at least {}0.401/2=0.2005.

3.5 Non-monotone hardness

In this section, we show that no approximation ratio better than (1-\min_{x\in P_{\mathcal{F}}\cup(\mathds{1}-P_{\mathcal{F}})}\|x\|_{\infty}) can be obtained for non-monotone FMSM in sub-exponential time, even without the matroid constraint.

Theorem 3.7.

For any r in the form r=1-\tfrac{1}{t} with t\geq 2 and any \epsilon>0, a (1-r+\epsilon)-approximation for FMSM that works for instances where \min_{x\in P_{\mathcal{F}}\cup(\mathds{1}-P_{\mathcal{F}})}\|x\|_{\infty}\leq r requires an exponential number of value queries.
This is also the case for the continuous relaxation of FMSM, \max_{x\in P_{\mathcal{F}}}F(x). Furthermore, this is true even in the two special cases where (i) C=2 and \mathcal{I}=2^{V} (no matroid constraint), (ii) C=1 and \mathcal{I} is a partition matroid.

Proof sketch.

The proof follows from the hardness results given in (Vondrák, 2013, Theorem 1.2 and 1.9) for non-monotone submodular maximization over the bases of a matroid, by showing that the hard instance used therein is an instance of both special cases (i) and (ii) of FMSM. See Section B.4.
∎

Theorem 3.7 implies that any constant-factor approximation for FMSM or its continuous relaxation requires an exponential number of value queries in general.

Note that a uniform matroid with k=n is equivalent to having no matroid constraint. In that case, Example 3.4 shows that \min_{x\in P_{\mathcal{F}}\cup(\mathds{1}-P_{\mathcal{F}})}\|x\|_{\infty}=\min\{\max_{c}\tfrac{\ell_{c}}{|V_{c}|},1-\min_{c}\tfrac{u_{c}}{|V_{c}|}\}, since t=C and \tau=1.
Hence, Example 3.4 and Theorem 3.7 yield a lower bound of \max\{1-\max_{c}\tfrac{\ell_{c}}{|V_{c}|},\min_{c}\tfrac{u_{c}}{|V_{c}|}\} for the fairness constraint alone. This matches the lower bound given in (El Halabi et al., 2020, Theorem 5.1) for FMSM in the streaming setting – the bound therein is {}1-\max_{c}\tfrac{\ell_{c}}{|V_{c}|} and is stated for the uniform matroid, but the hard instance used in the proof does not use any matroid and has \min_{c}\tfrac{u_{c}}{|V_{c}|}=0.

On the other hand, note that Example 3.5 does not necessarily imply a hardness of O(1/\sqrt{n}) for the bipartite perfect matching constraint, since the hard instance in Theorem 3.7 is not an instance of that.

4 Decomposable case

In this section, we study a special case of FMSM where f is a decomposable submodular function over \mathcal{F} (Definition 2.4). We follow the relax-and-round approach discussed in Section 3.2. Unlike the general case, this approach works here; we show that the integrality gap of Problem (1) is 1 in this case. To that end, we show that the randomized swap rounding algorithm proposed in (Chekuri et al., 2010, Section V) for the intersection of two matroids can be applied to \mathcal{F}.

We achieve this by reducing rounding on \mathcal{F} to rounding on the intersection of two matroids, one with the same equivalence classes (Definition 2.3) as \mathcal{I} and the other with the color groups V_{c} as equivalence classes.
Our reduction uses the following simple observation.

Fact 4.1.

Given any family of sets \mathcal{J}\subseteq 2^{V},
let \tilde{\mathcal{J}} denote the family of extendable sets: \tilde{\mathcal{J}}=\{S\subseteq V\mid\text{ there exists }S^{\prime}\in\mathcal{J}\text{ such that }S\subseteq S^{\prime}\}. Then \mathcal{J} and \tilde{\mathcal{J}} have the same maximal sets.

When the matroid in \mathcal{F} is the uniform matroid, \tilde{\mathcal{F}} was shown to form a matroid (El Halabi et al., 2020, Lemma 4.1). We can then view any fair set as a base in a matroid, as shown by the following lemma. See Section B.5 for the proofs of this section.

Lemma 4.2.

Let \tilde{\mathcal{C}}_{k}:=\{S\subseteq V\mid\text{ there exists }S^{\prime}\in\mathcal{C},|S^{\prime}|\leq k\text{ such that }S\subseteq S^{\prime}\}. Then any fair set S\in\mathcal{C} is a base of the matroid \tilde{\mathcal{C}}_{k} with k=|S| and vice versa.

We are now ready to give our reduction.

Theorem 4.3.

There exists a polynomial-time rounding scheme which, given x\in P_{\mathcal{F}}, returns a feasible set S\in\mathcal{F} that for any decomposable submodular function f over \mathcal{F} satisfies
\operatorname{\mathbb{E}}[f(S)]\geq F(x).

Proof sketch.

Since P_{\mathcal{F}} is solvable (Lemma 2.1-c), we can write x as a convex combination of sets in \mathcal{F} in strongly polynomial time (Schrijver, 2003, Theorem 5.15); i.e., x=\sum_{t}\alpha_{t}\mathds{1}_{I_{t}} for some I_{t}\in\mathcal{F},\alpha_{t}\geq 0,\sum_{t}\alpha_{t}=1. Lemma 4.2 implies that every set I_{t} is in the intersection of the matroids \mathcal{I} and \tilde{\mathcal{C}}_{k}, where k is the size of the largest set I_{t}. Then x is a valid input for swap rounding. If all sets I_{t} have the same size k, then the returned rounded solution S\in\mathcal{I}\cap\tilde{\mathcal{C}}_{k} will also have size k,
and thus is a base of \tilde{\mathcal{C}}_{k}.
By Lemma 4.2, S is then also a fair set.
The claim then follows from (Chekuri et al., 2010, Theorem II.3) by noting that the equivalence classes of \tilde{\mathcal{C}}_{k} are the color groups V_{c}, and thus any decomposable submodular function over \mathcal{F} is also decomposable over \mathcal{I}\cap\tilde{\mathcal{C}}_{k}.
If sets I_{t} do not have the same size, we reduce to the equal-sizes case by adding dummy elements. ∎

Theorem 4.3 allows us to obtain the same approximation factors as in Theorem 3.3 but without violating the fairness constraint.

Corollary 4.4.

There exists a polynomial-time algorithm for decomposable FMSM which achieves, in expectation, (1-1/e)-approximation if f is monotone and (1-\min_{x\in P_{\mathcal{F}}\cup(\mathds{1}-P_{\mathcal{F}})}\|x\|_{\infty}-\epsilon)/4-approximation otherwise, for any \epsilon>0.

Proof.

This follows directly from the proof of Theorem 3.3 and Theorem 4.3. Note also that both the continuous greedy and the Frank Wolfe type algorithms used to solve Problem (1) return a fractional solution x which is already a convex combination of sets in \mathcal{F}. So this step can be skipped in the proof of Theorem 4.3.
∎

Recall that the fair submodular welfare problem (c.f., Section 2) is a special case of monotone decomposable FMSM. Corollary 4.4 then gives a (1-1/e)-approximation for it.

In the special cases where C=1 or \mathcal{I} is the uniform matroid, Corollary 4.4 applies to any submodular objective, since V_{1}=V in the first case and all elements are equivalent in the second case, i.e., \mathcal{G}=\{V\} in Definition 2.3. Hence, Corollary 4.4 recovers the result of Celis et al. (2018a, Theorem 18) for monotone objectives.
For non-monotone objectives, the approximation guarantee in Corollary 4.4 can be of course improved to the one given in Theorem 3.6.

It follows also that the hardness result in Theorem 3.7 applies to decomposable FMSM too.

Corollary 4.5.

For any r of the form r=1-\tfrac{1}{t} with t\geq 2 and any \epsilon>0, a (1-r+\epsilon)-approximation for decomposable FMSM that works for instances where \min_{x\in P_{\mathcal{F}}\cup(\mathds{1}-P_{\mathcal{F}})}\|x\|_{\infty}\leq r requires an exponential number of value queries.
This is also the case for the continuous relaxation of FMSM, \max_{x\in P_{\mathcal{F}}}F(x). Furthermore, this is true even in the two special cases where (i) C=2 and \mathcal{I}=2^{V} (no matroid constraint), (ii) C=1 and \mathcal{I} is a partition matroid.

Proof.

This follows directly from the proof of Theorem 3.7, by noting that any submodular function is decomposable over \mathcal{F} in both special cases; in (i) \mathcal{I} is a n-uniform matroid and in (ii) C=1.
∎

5 Future directions

Our work leaves the following
tantalizing question open:
is there a constant-factor approximation to monotone FMSM
(without fairness violations)?
Even more fundamentally:
is there a constant-factor approximation to the problem of maximizing a monotone submodular function over the set of perfect matchings in a bipartite graph?
On one hand,
given our integrality gap in Theorem 3.2 for the multilinear extension,
a positive answer would require novel algorithmic techniques.
On the other hand,
in a plenary SODA talk, Vondrák (2013) stated the following as a fundamental question:
“Can we approximate every maximization problem with a
monotone submodular objective (up to constant factors)
if we can approximate it with a linear objective?”
As maximum-weight perfect matching is in P,
a superconstant hardness of approximation for the submodular perfect matching problem would imply a negative answer to Vondrák’s question.

Acknowledgements

We thank Rico Zenklusen, Jakab Tardos, and Moran Feldman for helpful discussions.

References

• Aziz et al. (2023)

Haris Aziz, Xin Huang, Nicholas Mattei, and Erel Segal-Halevi.

Computing welfare-maximizing fair allocations of indivisible goods.

European Journal of Operational Research, 307(2):773–784, 2023.

• Benabbou et al. (2021)

Nawal Benabbou, Mithun Chakraborty, Ayumi Igarashi, and Yair Zick.

Finding fair and efficient allocations for matroid rank valuations.

ACM Transactions on Economics and Computation, 9(4):1–41, 2021.

• Biddle (2006)

Dan Biddle.

Adverse impact and test validation: A practitioner’s guide to
valid and defensible employment testing.

Gower Publishing, Ltd., 2006.

• Brill et al. (2017)

Markus Brill, Jean-François Laslier, and Piotr Skowron.

Multiwinner approval rules as apportionment methods.

In AAAI, pages 414–420. AAAI Press, 2017.

• Buchbinder et al. (2014)

N. Buchbinder, M. Feldman, J. Naor, and R. Schwartz.

Submodular maximization with cardinality constraints.

SIAM, 2014.

• Buchbinder and Feldman (2019)

Niv Buchbinder and Moran Feldman.

Constrained submodular maximization via a nonsymmetric technique.

Mathematics of Operations Research, 44(3):988–1005, 2019.

• Buchbinder and Feldman (2023)

Niv Buchbinder and Moran Feldman.

Constrained submodular maximization via new bounds for dr-submodular
functions.

arXiv preprint arXiv: 2311.01129, 2023.

• Calinescu et al. (2011a)

Gruia Calinescu, Chandra Chekuri, Martin Pal, and Jan Vondrák.

Maximizing a monotone submodular function subject to a matroid
constraint.

SIAM Journal on Computing, 40(6):1740–1766, 2011a.

• Calinescu et al. (2011b)

Gruia Calinescu, Chandra Chekuri, Martin Pal, and Jan Vondrák.

Maximizing a monotone submodular function subject to a matroid
constraint.

SIAM Journal on Computing, 40(6):1740–1766, 2011b.

• Celis et al. (2018a)

L. Elisa Celis, Lingxiao Huang, and Nisheeth K. Vishnoi.

Multiwinner voting with fairness constraints.

In IJCAI, pages 144–151. ijcai.org, 2018a.

• Celis et al. (2018b)

L. Elisa Celis, Vijay Keswani, Damian Straszak, Amit Deshpande, Tarun Kathuria,
and Nisheeth K. Vishnoi.

Fair and diverse dpp-based data summarization.

In ICML, volume 80 of Proceedings of Machine Learning
Research, pages 715–724. PMLR, 2018b.

• Celis et al. (2018c)

L. Elisa Celis, Damian Straszak, and Nisheeth K. Vishnoi.

Ranking with fairness constraints.

In ICALP, volume 107 of LIPIcs, pages 28:1–28:15.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018c.

• Chekuri et al. (2009)

Chandra Chekuri, Jan Vondrák, and Rico Zenklusen.

Dependent randomized rounding for matroid polytopes and applications.

arXiv preprint arXiv:0909.4348, 2009.

• Chekuri et al. (2010)

Chandra Chekuri, Jan Vondrák, and Rico Zenklusen.

Dependent randomized rounding via exchange properties of
combinatorial structures.

In FOCS, pages 575–584. IEEE Computer Society, 2010.

• Chierichetti et al. (2017)

Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii.

Fair clustering through fairlets.

In NIPS, pages 5029–5037, 2017.

• Chierichetti et al. (2019)

Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii.

Matroids, matchings, and fairness.

In AISTATS, volume 89 of Proceedings of Machine
Learning Research, pages 2212–2220. PMLR, 2019.

• Cohoon et al. (2013)

Joanne McGrath Cohoon, James P. Cohoon, Seth Reichelson, and Selwyn Lawrence.

Effective recruiting for diversity.

In FIE, pages 1123–1124. IEEE Computer Society, 2013.

• Das and Kempe (2011)

Abhimanyu Das and David Kempe.

Submodular meets spectral: Greedy algorithms for subset selection,
sparse approximation and dictionary selection.

In ICML, pages 1057–1064. Omnipress, 2011.

• Du (2022)

Donglei Du.

Lyapunov function approach for approximation algorithm design and
analysis: with applications in submodular maximization.

arXiv preprint arXiv:2205.12442, 2022.

• Dwork et al. (2012)

Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel.

Fairness through awareness.

In Proceedings of the 3rd innovations in theoretical computer
science conference, pages 214–226, 2012.

• El-Arini and Guestrin (2011)

Khalid El-Arini and Carlos Guestrin.

Beyond keyword search: discovering relevant scientific literature.

In KDD, pages 439–447. ACM, 2011.

• El Halabi et al. (2020)

Marwa El Halabi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Jakab Tardos, and
Jakub Tarnawski.

Fairness in streaming submodular maximization: Algorithms and
hardness.

In NeurIPS, 2020.

• El Halabi et al. (2023)

Marwa El Halabi, Federico Fusco, Ashkan Norouzi-Fard, Jakab Tardos, and Jakub
Tarnawski.

Fairness in streaming submodular maximization over a matroid
constraint.

In International Conference on Machine Learning, pages
9150–9171. PMLR, 2023.

• European Union FRA (2022)

European Union FRA.

Bias in Algorithms –– Artificial Intelligence and
Discrimination.

European Union Agency for Fundamental Rights. Publications Office of
the European Union, Luxembourg, 2022.

• Feige (1998)

Uriel Feige.

A threshold of ln n for approximating set cover.

J. ACM, 45(4):634–652, 1998.

• Feldman et al. (2011)

Moran Feldman, Joseph Naor, and Roy Schwartz.

A unified continuous greedy algorithm for submodular maximization.

In Foundations of Computer Science (FOCS), 2011 IEEE 52nd
Annual Symposium on, pages 570–579. IEEE, 2011.

• Feldman et al. (2020)

Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson, and Rico Zenklusen.

The one-way communication complexity of submodular maximization with
applications to streaming and robustness.

In STOC, pages 1363–1374. ACM, 2020.

• Feldman et al. (2021)

Moran Feldman, Paul Liu, Ashkan Norouzi-Fard, Ola Svensson, and Rico Zenklusen.

Streaming submodular maximization under matroid constraints.

arXiv preprint arXiv:2107.07183, 2021.

• Garg et al. (2021)

Paritosh Garg, Linus Jordan, and Ola Svensson.

Semi-streaming algorithms for submodular matroid intersection.

In IPCO, volume 12707 of Lecture Notes in Computer
Science, pages 208–222. Springer, 2021.

• Golovin and Krause (2011)

Daniel Golovin and Andreas Krause.

Adaptive submodularity: Theory and applications in active learning
and stochastic optimization.

J. Artif. Intell. Res., 42:427–486, 2011.

• Hartley and Rao (1962)

HO Hartley and JNK Rao.

Sampling with unequal probabilities and without replacement.

The Annals of Mathematical Statistics, pages 350–374, 1962.

• Khot et al. (2005)

Subhash Khot, Richard J Lipton, Evangelos Markakis, and Aranyak Mehta.

Inapproximability results for combinatorial auctions with submodular
utility functions.

In Internet and Network Economics: First International
Workshop, WINE 2005, Hong Kong, China, December 15-17, 2005. Proceedings 1,
pages 92–101. Springer, 2005.

• Krause et al. (2008)

Andreas Krause, H Brendan McMahan, Carlos Guestrin, and Anupam Gupta.

Robust submodular observation selection.

Journal of Machine Learning Research, 9(Dec):2761–2801, 2008.

• Lee et al. (2010)

Jon Lee, Maxim Sviridenko, and Jan Vondrák.

Submodular maximization over multiple matroids via generalized
exchange properties.

Mathematics of Operations Research, 35(4):795–806, 2010.

• Lehmann et al. (2006)

Benny Lehmann, Daniel Lehmann, and Noam Nisan.

Combinatorial auctions with decreasing marginal utilities.

Games and Economic Behavior, 55(2):270–296, 2006.

• Lin and Bilmes (2011)

Hui Lin and Jeff A. Bilmes.

A class of submodular functions for document summarization.

In ACL, pages 510–520. The Association for Computer
Linguistics, 2011.

• Monroe (1995)

Burt L Monroe.

Fully proportional representation.

American Political Science Review, 89(4):925–940, 1995.

• Mualem and Feldman (2023)

Loay Mualem and Moran Feldman.

Resolving the approximability of offline and online non-monotone
dr-submodular maximization over general convex sets.

In Francisco Ruiz, Jennifer Dy, and Jan-Willem van de Meent, editors,
Proceedings of The 26th International Conference on Artificial
Intelligence and Statistics, volume 206 of Proceedings of Machine
Learning Research, pages 2542–2564. PMLR, 25–27 Apr 2023.

• Munoz et al. (2016)

Cecilia Munoz, Smith Megan, and DJ Patil.

Big data: A report on algorithmic systems, opportunity, and
civil rights.

Executive Office of the President. The White House, Washington, DC,
2016.

• Oveis Gharan and Vondrák (2011)

Shayan Oveis Gharan and Jan Vondrák.

Submodular maximization by simulated annealing.

In SODA, pages 1098–1116. SIAM, 2011.

• Schrijver (2003)

Alexander Schrijver.

Combinatorial optimization: polyhedra and efficiency.

Springer Science & Business Media, 2003.

• Sun et al. (2023)

Ankang Sun, Bo Chen, and Xuan Vinh Doan.

Equitability and welfare maximization for allocating indivisible
items.

Autonomous Agents and Multi-Agent Systems, 37(1):8, 2023.

• Tang and Yuan (2023)

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.

• Tang et al. (2023)

Shaojie Tang, Jing Yuan, and Twumasi Mensah-Boateng.

Achieving long-term fairness in submodular maximization through
randomization.

arXiv preprint arXiv:2304.04700, 2023.

• Tsang et al. (2019)

Alan Tsang, Bryan Wilder, Eric Rice, Milind Tambe, and Yair Zick.

Group-fairness in influence maximization.

In IJCAI, pages 5997–6005. ijcai.org, 2019.

• Udwani (2018)

Rajan Udwani.

Multi-objective maximization of monotone submodular functions with
cardinality constraint.

Advances in Neural Information Processing Systems, 31, 2018.

• Vondrák (2008)

Jan Vondrák.

Optimal approximation for the submodular welfare problem in the value
oracle model.

In Proceedings of the fortieth annual ACM symposium on Theory
of computing, pages 67–74, 2008.

• Vondrák (2013)

Jan Vondrák.

Symmetry and approximability of submodular maximization problems.

SIAM Journal on Computing, 42(1):265–304,
2013.

• Vondrák (2013)

Jan Vondrák.

Submodular functions and their applications, 2013.

URL
https://theory.stanford.edu/~jvondrak/data/SODA-plenary-talk.pdf.

Plenary talk at the ACM-SIAM Symposium on Discrete Algorithms (SODA)
2013.

• Wang et al. (2021)

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.

• Wang et al. (2024)

Yanhao Wang, Yuchen Li, Francesco Bonchi, and Ying Wang.

Balancing utility and fairness in submodular maximization.

In Proceedings of the 27th International Conference on
Extending Database Technology, EDBT, pages 1–14, 2024.

• White House OSTP (2022)

White House OSTP.

Blueprint for an AI Bill of Rights.

White House Office of Science and Technology Policy, Washington, DC,
2022.

• Yuan and Tang (2023)

Jing Yuan and Shaojie Tang.

Group fairness in non-monotone submodular maximization.

Journal of Combinatorial Optimization, 45(3):88, 2023.

• Zafar et al. (2017)

Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez-Rodriguez, and Krishna P.
Gummadi.

Fairness constraints: Mechanisms for fair classification.

In AISTATS, volume 54 of Proceedings of Machine
Learning Research, pages 962–970. PMLR, 2017.

Appendix A Algorithms for non-monotone FMSM with lower bounds violation

In this section, we present a constant-factor approximation algorithm for FMSM, where the function f is non-monotone, which violates the fairness lower bounds by a constant factor. The algorithm is a simple adaptation of the two-pass streaming algorithm in El Halabi et al. (2023), with both a streaming and offline variant.
The first pass of our algorithm is the same (Algorithm 1). It collects a maximal independent set I_{c}\in\mathcal{I} for each color independently and then constructs a feasible solution S in \cup_{c}I_{c}.

Algorithm 1 Fair-Reservoir in El Halabi et al. (2023)

1:

I_{c}\leftarrow\emptyset for all c=1,...,C

2:

for each element e on the stream do

3:

Let c be the color of e

4:

If I_{c}+e\in\mathcal{I} then I_{c}\leftarrow I_{c}+e

5:

S\leftarrow a max-cardinality subset of \bigcup_{c}I_{c} in \mathcal{I}\cap\mathcal{I}_{C}, where \mathcal{I}_{C}=\{S\subseteq V\mid|V_{c}\cap S|\leq\ell_{c}\;\ \forall c\in[C]\}

6:

Return S

Fair-Reservoir runs in polynomial time, uses O(k\cdot C) memory, and is guaranteed to return a feasible solution (El Halabi et al., 2023, Theorem 4.2).
Step 5 consists in invoking any offline polynomial-time max-cardinality matroid intersection algorithm (note that \mathcal{I}_{C} is a partition matroid).

The second pass of our algorithm is very similar to El Halabi et al. (2023) (Algorithm 2). The feasible set S output by Fair-Reservoir is again divided into sets S_{1} and S_{2}. But instead of assigning elements deterministically to S_{1} or S_{2} in such a way that each lower bound is violated by at most a factor two, we randomly assign, for each c\in[C], \lfloor\beta\ell_{c}\rfloor elements from S\cap V_{c} to S_{1}, and \lfloor\beta\ell_{c}\rfloor from (S\setminus S_{1})\cap V_{c} to S_{2}, where \beta\in[0,1/2] is a user-defined parameter which controls the trade-off between fairness and objective value. This is possible since S is feasible so it has at least \ell_{c} elements of each color c. Note that both S_{1} and S_{2} are independent in \mathcal{I} and satisfy \lfloor\beta\ell_{c}\rfloor=|S_{i}\cap V_{c}|\leq\ell_{c}\leq u_{c}.

The goal of the second pass is to extend S_{1} and S_{2} into high-value independent sets while still satisfying the fairness upper bounds and the relaxed lower bounds. To that end, similarly as El Halabi et al. (2023), we define the following matroids:

\displaystyle\mathcal{I}^{C} \\ \displaystyle=\{X\subseteq V\mid|X\cap V_{c}|\leq u_{c}\;\ \forall c\in[C]\}\,, \\ \displaystyle\mathcal{I}_{1} \\ \displaystyle=\{X\subseteq V\mid X\cup S_{1}\in\mathcal{I}\}\,, \\ \displaystyle\mathcal{I}_{2} \\ \displaystyle=\{X\subseteq V\mid X\cup S_{2}\in\mathcal{I}\}.

Then we use any algorithm \mathcal{A} that maximizes a non-monotone submodular function over two matroid constraints, and run two copies of it in parallel, one with matroids \mathcal{I}^{C},\mathcal{I}_{1} and one with matroids \mathcal{I}^{C},\mathcal{I}_{2}. Let R_{1},R_{2} be their respective outputs. We add to R_{i} as many elements as necessary
from S_{i} to satisfy the relaxed lower bounds, and return the better of the two resulting solutions.

Algorithm 2 Randomized-Fair-Streaming

1:

Input: Set S from Fair-Reservoir, routine \mathcal{A}, and \beta\in[0,1/2]

2:

S_{1}\leftarrow\emptyset, S_{2}\leftarrow\emptyset

3:

for each color c do

4:

Let B^{c}_{1},B^{c}_{2} be sets of \lfloor\beta\ell_{c}\rfloor random elements from S\cap V_{c} and (S\cap V_{c})\setminus B^{c}_{1}, respectively

5:

S_{1}\leftarrow S_{1}\cup B^{c}_{1}

6:

S_{2}\leftarrow S_{2}\cup B^{c}_{2}

7:

Define matroids \mathcal{I}^{C}, \mathcal{I}_{1},\mathcal{I}_{2} as in 2

8:

Run two copies of \mathcal{A}, one for \mathcal{I}^{C},\mathcal{I}_{1} and one for \mathcal{I}^{C},\mathcal{I}_{2}, and let R_{1} and R_{2} be their outputs

9:

for i=1,2 do

10:

S^{\prime}_{i}\leftarrow R_{i}

11:

for e in S_{i} do

12:

Let c be the color of e

13:

If $|S_{i}^{\prime}\cap V_{c}|then S_{i}^{\prime}\leftarrow S_{i}^{\prime}+e

14:

Return S^{\prime}=\arg\max(f(S^{\prime}_{1}),f(S^{\prime}_{2}))

Randomized-Fair-Streaming only differs from the second-pass algorithm in (El Halabi et al., 2023, Algorithm 2) by the way elements in S are assigned to S_{1} and S_{2}, and the requirement that \mathcal{A} works for non-monotone objectives.
Let us analyze its performance.

Lemma A.1.

The output S^{\prime} of Randomized-Fair-Streaming satisfies (i) S^{\prime}\in\mathcal{I}, (ii) |S^{\prime}\cap V_{c}|\leq u_{c}, and (iii) |S^{\prime}\cap V_{c}|\geq\lfloor\beta\ell_{c}\rfloor for any color c\in[C].

Proof.

The proof follows in a similar way to (El Halabi et al., 2023, Lemma 4.3). For i\in\{1,2\}, we have:

• (i)

By the definition of \mathcal{I}_{i} in 2 the set R_{i} output by \mathcal{A} satisfies R_{i}\cup S_{i}\in\mathcal{I}. Hence, S^{\prime}_{i}\in\mathcal{I} by downward-closedness since S^{\prime}_{i}\setminus R_{i}\subseteq S_{i}.

• (ii)

Since R_{i}\in\mathcal{I}^{C} and the elements added to it in the for loop on Line 11 never violate the upper bounds, we have S^{\prime}_{i}\in\mathcal{I}^{C}.

• (iii)

By construction S_{i} has at least \lfloor\beta\ell_{c}\rfloor elements of each color c. And for any color c such that $|S^{\prime}{i}\cap V{c}|∎

Lemma A.2.

Assume that \mathcal{A} is an α-approximation algorithm for non-monotone submodular maximization over the intersection of two matroids. Then the output S^{\prime} of Randomized-Fair-Streaming satisfies \operatorname{\mathbb{E}}[f(S)]\geq\frac{(1-\beta)\alpha}{2}\operatorname{OPT}.

Proof.

We first give a lower bound on \max(f(R_{1}),f(R_{2})) in the same way as in (El Halabi et al., 2023, Lemma 4.4).
Let O be an optimal solution of FMSM.
From Lemma 2.1 in El Halabi et al. (2023), we know that O can be partitioned into two sets O_{1},O_{2} such that O_{1}\cup S_{1}\in\mathcal{I} and O_{2}\cup S_{2}\in\mathcal{I}. Therefore O_{i}\in\mathcal{I}^{C}\cap\mathcal{I}_{i} for i\in\{1,2\} by definition of \mathcal{I}_{i} and downward-closedness of \mathcal{I}^{C}. Since \mathcal{A} is an α-approximation algorithm, we have that

\displaystyle\max(f(R_{1}),f(R_{2}))\geq \\ \displaystyle\frac{f(R_{1})+f(R_{2})}{2} \\ \displaystyle\geq \\ \displaystyle\frac{\alpha}{2}(f(O_{1})+f(O_{2})) \\ \displaystyle\geq \\ \displaystyle\frac{\alpha}{2}(f(O_{1}\cup O_{2})+f(O_{1}\cap O_{2})) \\ \displaystyle\geq \\ \displaystyle\frac{\alpha}{2}f(O)=\frac{\alpha}{2}\operatorname{OPT}.

It remains to compare f(R_{i}) with f(S^{\prime}_{i}) for i\in\{1,2\}. To that end we define two non-negative submodular functions g_{1},g_{2} as follows:

g_{i}(W)=f(W\cup R_{i})\quad\quad\text{ for all }W\subseteq S\text{ and }i\in\{1,2\}.

For any i\in\{1,2\}, we show that the set S^{\prime}_{i}\setminus R_{i} of elements added to S^{\prime}_{i} in the for loop on Line 11 contains each element of S with probability at most β. By construction of S_{1},S_{2}, we have for any color c and any e\in S\cap V_{c},

\displaystyle P(e\in(S^{\prime}_{1}\setminus R_{1})\cap V_{c}) \\ \displaystyle\leq P(e\in S_{1}\cap V_{c})=\frac{\lfloor\beta\ell_{c}\rfloor}{|S\cap V_{c}|}\leq\frac{\lfloor\beta\ell_{c}\rfloor}{\ell_{c}}\leq\beta

and

\displaystyle P(e\in(S^{\prime}_{2}\setminus R_{2})\cap V_{c}) \\ \displaystyle\leq P(e\in S_{2}\cap V_{c}) \\ \displaystyle=P(e\not\in S_{1}\cap V_{c})P(e\in S_{2}\cap V_{c}\mid e\not\in S_{1}\cap V_{c}) \\ \displaystyle=(1-\frac{\lfloor\beta\ell_{c}\rfloor}{|S\cap V_{c}|})\frac{\lfloor\beta\ell_{c}\rfloor}{|S\cap V_{c}|-\lfloor\beta\ell_{c}\rfloor} \\ \displaystyle=\frac{\lfloor\beta\ell_{c}\rfloor}{|S\cap V_{c}|} \\ \displaystyle\leq\frac{\lfloor\beta\ell_{c}\rfloor}{\ell_{c}}\leq\beta.

We apply Lemma 2.2 to submodular functions g_{1} and g_{2}. We get that

\operatorname{\mathbb{E}}[f(S^{\prime}_{i})]=\operatorname{\mathbb{E}}[g_{i}(S^{\prime}_{i}\setminus R_{i})]\geq(1-\beta)g_{i}(\emptyset)=(1-\beta)f(R_{i}).

Combining that with 3, we get

\displaystyle\operatorname{\mathbb{E}}[f(S^{\prime})]= \\ \displaystyle\operatorname{\mathbb{E}}[\max(f(S^{\prime}_{1}),f(S^{\prime}_{2}))] \\ \displaystyle\geq \\ \displaystyle\max(\operatorname{\mathbb{E}}[f(S^{\prime}_{1})],\operatorname{\mathbb{E}}[f(S^{\prime}_{2})]) \\ \displaystyle\geq \\ \displaystyle(1-\beta)\max(f(R_{1}),f(R_{2})) \\ \displaystyle\geq \\ \displaystyle\frac{(1-\beta)\alpha}{2}\operatorname{OPT}.

∎

In the offline setting, we can use the state-of-the-art {}1/(4+\epsilon)-approximation algorithm
of Lee et al. (2010, Theorem 4.1) as \mathcal{A}. Theorem 3.1 then follows from Lemma A.1 and Lemma A.2.
See 3.1

In the streaming setting, we can use the state-of-the-art {}1/7.464-approximation algorithm of Garg et al. (2021, Theorem 19) as \mathcal{A}. Theorem A.3 then also follows from Lemma A.1 and Lemma A.2.

Theorem A.3.

There exists a polynomial-time two-pass streaming algorithm for non-monotone FMSM, which uses O(k\cdot C) memory, and outputs a set S such that (i) S\in\mathcal{I}, (ii) \lfloor\beta\ell_{c}\rfloor\leq|V_{c}\cap S|\leq u_{c} for any color c\in[C], and (iii) \operatorname{\mathbb{E}}[f(S)]\geq(1-\beta)\mathrm{OPT}/14.928 for any \beta\in[0,1/2].

Appendix B Missing proofs

In this section, we present the proofs that were omitted from the main text. We restate claims for convenience.

B.1 Proofs of Section 3.2

See 3.2

Proof.

We will encode bipartite perfect matching as an intersection of matroid and fairness constraints.
Given a bipartite graph (A\cup B,E), we set up a partition matroid to enforce that every vertex in A has at most one adjacent edge in the solution, and fairness constraints to enforce that every vertex in B has exactly one adjacent edge in the solution (we assign color b to every edge (a,b)).
We then have k=|A|=|B|=C.

To define an instance, we then need to describe a bipartite graph and a monotone submodular function defined on its edges.
For parameters t,s\geq 1 we define the graph as follows:
there are two special vertices 1 and 2;
and
for i=1,...,t we add a path from 1 to 2 of length {}2s+1 to the graph (thus inserting 2s new vertices).
Note that this graph is bipartite.
Let O_{i} be the set of the s+1 “odd” edges on the i-th path.
We define the submodular objective function as f(S)=\sum_{i=1}^{t}\mathds{1}_{S\cap O_{i}\neq\emptyset}.

Note that the graph has exactly t perfect matchings.
Indeed, the choice of mate for vertex 1 determines the entire perfect matching, which must then be the union of O_{i} (for some i) and the even edges from all the other paths.
In particular, for each i there is only one perfect matching that intersects O_{i}.
Therefore the integral optimum is 1.

However, if we take x to be the average of the indicator vectors of the t matchings,
then we get x\in P_{\mathcal{F}} and

F(x)=\sum_{i=1}^{t}\left(1-\prod_{e\in O_{i}}(1-x_{e})\right)=t\cdot\left(1-\left(1-\frac{1}{t}\right)^{s+1}\right)\,.

If we set s=t, then F(x)=\Omega(t), which is \Omega(\sqrt{n}) as n=|E|=\Theta(s\cdot t).
∎

B.2 Proofs of Section 3.3

We start by giving the full proof of Theorem 3.3.

See 3.3

Proof.

We first obtain an α-approximation fractional solution x\in P_{\mathcal{F}} for \max_{x\in P_{\mathcal{F}}}F(x). For monotone objectives, we can use the continuous greedy algorithm of Calinescu et al. (2011a, Section 3.1 and Appendix A), which achieves a (1-1/e)-approximation for maximizing the multilinear extension over any integral polytope, both in expectation and with high probability.3
Note that P_{\mathcal{F}} is integral as it is the convex hull of integral points.

For non-monotone objectives, we can use the Frank-Wolfe type algorithm of Du (2022, Sections 3.5 and 4.5) which achieves a (1-\min_{x\in P}\|x\|_{\infty}-\epsilon)/4-approximation for maximizing the multilinear extension over any polytope P, both in expectation and with high probability — see also (Mualem and Feldman, 2023, Section 3) for an explicit variant of the algorithm and its analysis. Applying this algorithm to Problem (1) then yields a (1-\min_{x\in P_{\mathcal{F}}}\|x\|_{\infty}-\epsilon)/4-approximation.

To obtain the potentially better approximation ratio (1-\min_{x\in\mathds{1}-P_{\mathcal{F}}}\|x\|_{\infty}-\epsilon)/4, we solve the complement of Problem (1): \max_{x\in\mathds{1}-P_{\mathcal{F}}}\bar{F}(x), where \bar{F} is the multilinear extension of the complement \bar{f} of f; \bar{f}(S)=f(V\setminus S).
It is easy to verify that the complement of a submodular function is also submodular. So we can indeed use the Frank-Wolfe type algorithm on the complement problem, which yields (1-\min_{x\in\mathds{1}-P_{\mathcal{F}}}\|x\|_{\infty}-\epsilon)/4 approximation for it. Given an α-approximate solution \bar{x} for the complement problem, {}1-\bar{x} is an α-approximate solution to the original problem. To see this, we show that \bar{F}(x)=F(\mathds{1}-x):

\displaystyle\bar{F}(x) \\ \displaystyle=\sum_{S\subseteq V}\bar{f}(S)\prod_{i\in S}x_{i}\prod_{j\in V\setminus S}(1-x_{j}) \\ \displaystyle=\sum_{S^{\prime}\subseteq V}{f}(S^{\prime})\prod_{i\in V\setminus S^{\prime}}x_{i}\prod_{j\in S^{\prime}}(1-x_{j}) \\ \displaystyle=F(\mathds{1}-x).\vskip-10.0pt

Hence, \max_{x\in P_{\mathcal{F}}}F(x)=\max_{x\in P_{\mathcal{F}}}\bar{F}(\mathds{1}-x)=\max_{x^{\prime}\in\mathds{1}-P_{\mathcal{F}}}\bar{F}(x^{\prime}). Running the Frank-Wolfe type algorithm on both the original problem and its complement and picking the better solution then yields a (1-\min_{x\in P_{\mathcal{F}}\cup\mathds{1}-P_{\mathcal{F}}}\|x\|_{\infty}-\epsilon)/4-approximation to Problem (1).

Both the continuous greedy and the Frank-Wolfe type algorithms run in polynomial time if the constraint polytope is solvable,
which is the case for P_{\mathcal{F}} and \mathds{1}-P_{\mathcal{F}} by Lemma 2.1-c.

Next we round the fractional solution x to an independent (but not necessarily feasible) set S\in\mathcal{I} using the randomized swap rounding scheme of Chekuri et al. (2010, Section IV). The rounded solution is guaranteed to satisfy (see Theorem II.1 therein) \operatorname{\mathbb{E}}[|S\cap V_{c}|]=x(V_{c})\in[\ell_{c},u_{c}], \operatorname{\mathbb{E}}[f(S)]\geq F(x)\geq\alpha\operatorname{OPT}, and
for any c\in[C], \delta_{1}\geq 0, and \delta_{2}\in[0,1],

\displaystyle\operatorname{\mathbb{P}}\left[|S\cap V_{c}|\geq(1+\delta_{1})u_{c}\right] \\ \displaystyle\leq\left(\frac{e^{\delta_{1}}}{(1+\delta_{1})^{(1+\delta_{1})}}\right)^{u_{c}} \\ \displaystyle\leq e^{-0.38u_{c}\delta_{1}^{2}} \\ \displaystyle\text{ and }\operatorname{\mathbb{P}}\left[|S\cap V_{c}|\leq(1-\delta_{2})\ell_{c}\right] \\ \displaystyle\leq e^{-\ell_{c}\delta_{2}^{2}/2}.

Then, by choosing \delta_{1}=\sqrt{3\ln(2C)/u_{c}} and \delta_{2}=\sqrt{3\ln(2C)/\ell_{c}},
we get by union bound that S satisfies |S\cap V_{c}|\in[(1-\sqrt{3\ln(2C)/{\ell_{c}}})\ell_{c},(1+\sqrt{3\ln(2C)/{u_{c}}})u_{c})] for all c\in[C], with probability at least {}1-1/(2C)^{1.14}-1/(2C)^{1.5}\geq 1-1/2^{1.14}-1/2^{1.5}>0.19.

Remark B.1.

If f is monotone, we can further guarantee that for any \delta>0, the solution in Theorem 3.3 satisfies with constant probability the following for all c\in[C],

\left(1-\sqrt{\tfrac{3\ln(2C/(1-e^{-\delta^{2}/16}))}{\ell_{c}}}\right)\ell_{c}\leq|S\cap V_{c}|\leq\left(1+\sqrt{\tfrac{3\ln(2C/(1-e^{-\delta^{2}/16}))}{u_{c}}}\right)u_{c}

and f(S)\geq(1-1/e-\delta)\operatorname{OPT}.

Proof.

If f is monotone, we can apply the lower-tail
concentration bound in (Chekuri et al., 2010, Theorem II.2). To that end, we assume without loss of generality that for any i\in V, there exists a feasible set S^{\prime}\in\mathcal{F} containing i, otherwise we can simply ignore such element. Note that we can easily check if an element i satisfies this assumption, by maximizing a linear function over \mathcal{F}, which assigns zero weights to all elements except i and a non-zero weight to i. This can be done efficiently by Lemma 2.1-c.
Under this assumption, the marginal values of f are in [0,\operatorname{OPT}], since for any i\in V, we have f(i\mid S)\leq f(i)\leq f(S^{\prime})\leq\operatorname{OPT} by submodularity and monotonicity.
Scaling f by {}1/\operatorname{OPT}, we obtain

\displaystyle\operatorname{\mathbb{P}}\left[f(S)\leq(1-\delta)F(x)\right] \\ \displaystyle\leq e^{-F(x)\delta^{2}/(8OPT)} \\ \displaystyle\leq e^{-\delta^{2}/16},

for any \delta>0, since F(x)\geq(1-1/e)\operatorname{OPT} with high probability.
Hence, S is guaranteed to satisfy f(S)\geq(1-\delta)F(x)\geq(1-1/e-\delta)\operatorname{OPT} with probability {}1-e^{-\delta^{2}/16}.

Then we again use the concentration bounds in (Chekuri et al., 2010, Theorem II.1) but now choosing \delta_{1}=\sqrt{\tfrac{3\ln({2C}/{(1-e^{-\delta^{2}/16})})}{u_{c}}} and \delta_{2}=\sqrt{\tfrac{3\ln({2C}/{(1-e^{-\delta^{2}/16})})}{\ell_{c}}}. We get by union bound that S satisfies all the bounds in the claim with probability at least (1-e^{-\delta^{2}/16})(1-1/(2C)^{1.14}-1/(2C)^{1.5})>0.19(1-e^{-\delta^{2}/16}).
∎

∎

Next, we prove the statements of Example 3.4 and Example 3.5.

See 3.4

Proof.

First we compute \min_{x\in P_{\mathcal{F}}}\|x\|_{\infty}.
For any x\in P_{\mathcal{F}}, we have \ell_{c}\leq\sum_{i\in V_{c}}x_{i}\leq\|x\|_{\infty}|V_{c}| for all c\in[C], hence \|x\|_{\infty}\geq\max_{c}\tfrac{\ell_{c}}{|V_{c}|}. We show that this lower bound is achieved at a feasible vector x\in P_{\mathcal{F}}.
Let x\in[0,1]^{n} such that x_{i}=\frac{\ell_{c}}{|V_{c}|} for all i\in V_{c} and c\in[C], then \|x\|_{\infty}=\max_{c}\tfrac{\ell_{c}}{|V_{c}|} and x\in P_{\mathcal{F}} since \sum_{i\in V_{c}}x_{i}=\ell_{c}\in[\ell_{c},u_{c}] and \sum_{i\in V}x_{i}=\sum_{c}\ell_{c}\leq k by the assumption that \mathcal{F}\not=\emptyset. Hence \min_{x\in P_{\mathcal{F}}}\|x\|_{\infty}=\max_{c}\tfrac{\ell_{c}}{|V_{c}|}.

Next we compute \min_{x\in\mathds{1}-P_{\mathcal{F}}}\|x\|_{\infty}=\min_{x\in P_{\mathcal{F}}}\|\mathds{1}-x\|_{\infty}=1-\max_{x\in P_{\mathcal{F}}}\min_{i\in V}x_{i}.
Let x\in[0,1]^{n} such that

x_{i}=\begin{cases}\tfrac{\ell_{c}}{|V_{c}|}&\text{for all i\in V_{c},c>t}\\ \min\{\tau,\tfrac{u_{c}}{|V_{c}|}\}&\text{for all i\in V_{c},c\leq t}.\end{cases}

We argue that x\in P_{\mathcal{F}}. We have x(V_{c})=\ell_{c}\in[\ell_{c},u_{c}] for all c>t and x(V_{c})=\min\{u_{c},\tau|V_{c}|\} for all c\leq t. By definition of t and \tau, we have \tau\geq\tfrac{\ell_{t}}{|V_{t}|}. Hence x(V_{c})\geq\min\{u_{c},\tfrac{\ell_{t}}{|V_{t}|}|V_{c}|\}\geq\ell_{c} for all c\leq t. By definition of \tau, we also have x(V)\leq\tau\sum_{c=1}^{t}|V_{c}|+\sum_{c=t+1}^{C}\ell_{c}=k.
We show next that \min_{i\in V}x_{i}=\min\{\tau,\min_{c\leq t}\tfrac{u_{c}}{|V_{c}|}\}. This holds trivially if t=C. Otherwise, by definition of $t

k\leq\tfrac{\ell_{t+1}}{|V_{t+1}|}\sum_{c=1}^{t+1}|V_{c}|+\sum_{c=t+2}^{C}\ell_{c}=\tfrac{\ell_{t+1}}{|V_{t+1}|}\sum_{c=1}^{t}|V_{c}|+\sum_{c=t+1}^{C}\ell_{c},

hence \tau\leq\tfrac{\ell_{t+1}}{|V_{t+1}|}=\min_{i\in\cup_{c>t}V_{c}}x_{i}.
Thus \min_{i\in V}x_{i} is attained at some color c\leq t.
This proves that \max_{x\in P_{\mathcal{F}}}\min_{i\in V}x_{i}\geq\min\{\tau,\min_{c\leq t}\tfrac{u_{c}}{|V_{c}|}\}.
To prove the upper bound, we observe that for any x^{\prime}\in P_{\mathcal{F}}, we have \min_{i\in V}x^{\prime}_{i}|V_{c}|\leq x^{\prime}(V_{c})\leq u_{c}
for every c\in[C]
and k\geq x^{\prime}(V)\geq\sum_{c=t+1}^{C}\ell_{c}+\min_{i\in V}x^{\prime}_{i}\sum_{c=1}^{t}|V_{c}|. Thus by definition of \tau, we get

\min_{i\in V}x^{\prime}_{i}\leq\min\{\tau,\min_{c\in[C]}\tfrac{u_{c}}{|V_{c}|}\}\leq\min\{\tau,\min_{c\leq t}\tfrac{u_{c}}{|V_{c}|}\}.

Hence, \min_{x\in\mathds{1}-P_{\mathcal{F}}}\|x\|_{\infty}=1-\min\{\tau,\min_{c\leq t}\tfrac{u_{c}}{|V_{c}|}\} achieved at \bar{x}=\mathds{1}-x.∎

See 3.5

Proof.

We prove that \min_{x\in P_{\mathcal{F}}\cup(\mathds{1}-P_{\mathcal{F}})}\|x\|_{\infty}=1-1/t (recall that t=\Theta(\sqrt{n}) in Theorem 3.2).
The point x used in the proof of Theorem 3.2 puts {}1/t value on the “odd” edges, and {}1-1/t value on the “even” edges (each of which belongs to all perfect matchings but one). Thus it has \|x\|_{\infty}=\|\mathds{1}-x\|_{\infty}=1-1/t. This proves the ≤ direction. For the ≥ direction, consider any x\in P_{\mathcal{F}}. The point x must satisfy \sum_{e\in\delta(1)}x_{e}=1, where \delta(1) is the set of edges incident on the special vertex 1. As |\delta(1)|=t, we must have x_{e}\leq 1/t for some e\in\delta(1). Then consider the path from vertex 1 to 2 containing e, and let e^{\prime} be the next edge after e on that path. The common endpoint of e and e^{\prime} has degree two, thus x_{e^{\prime}}=1-x_{e}\geq 1-1/t. Hence \min\{\|x\|_{\infty},\|\mathds{1}-x\|_{\infty}\}\geq 1-1/t.
∎

B.3 Proofs of Section 3.4

In this section, we expand on some details that were omitted from the proof of Theorem 3.6.

See 3.6

Proof.

El Halabi et al. (2020, Theorem 5.2) presented a polynomial-time algorithm with an expected (1-\max_{c}\tfrac{\ell_{c}}{|V_{c}|})\alpha-approximation for non-monotone FMSM over a uniform matroid, given any α-approximation algorithm for non-monotone submodular maximization over a matroid constraint.5
Plugging in the state-of-the-art 0.401-approximation of Buchbinder and Feldman (2019, Theorem 1.1) then yields a {}0.401(1-\max_{c}\tfrac{\ell_{c}}{|V_{c}|})-approximation in expectation.
Recall from Example 3.4 that \min_{x\in P_{\mathcal{F}}}\|x\|_{\infty}=\max_{c}\tfrac{\ell_{c}}{|V_{c}|}.

To obtain the potentially better approximation factor {}0.401(1-\min_{x\in\mathds{1}-P_{\mathcal{F}}}\|x\|_{\infty}), we solve (as in Theorem 3.3) the complement problem \max_{V\setminus S\in\mathcal{F}}\bar{f}(S), where \bar{f}(S)=f(V\setminus S).
We follow a similar strategy as El Halabi et al. (2020). Namely, we first drop the lower bounds from the constraint. The resulting problem \max_{S\subseteq V}\{\bar{f}(S):|S\cap V_{c}|\leq|V_{c}|-\ell_{c},~\forall c\in[C]\} is a non-monotone submodular maximization problem over a partition matroid. Hence, a solution S with an expected 0.401-approximation can be obtained for it.

Next, we augment the solution S to a feasible one that we will denote S^{+}.
Let \bar{x} be a solution of \min_{x\in\mathds{1}-P_{\mathcal{F}}}\|x\|_{\infty}, which has a closed form as shown in Example 3.4.
For each color c, we sample a set B_{c}\subseteq V_{c} of elements so that:

• 1.

\operatorname{\mathbb{P}}\left[e\in B_{c}\right]=\bar{x}_{e} for all e\in V_{c},

• 2.

|B_{c}| is \lfloor\bar{x}(V_{c})\rfloor or \lceil\bar{x}(V_{c})\rceil for all c\in[C],

• 3.

\sum_{c}|B_{c}| is \lfloor\bar{x}(V)\rfloor or \lceil\bar{x}(V)\rceil.

This can be done as follows, inspired by (Hartley and Rao, 1962, Section 2.1).
Assign consecutive disjoint intervals on the real line to elements, of length \bar{x}_{e} for each e\in V, grouped by colors;
e.g., if V_{1}=\{e_{1},e_{2},...\}, the first two intervals would be [0,\bar{x}_{e_{1}}) and [\bar{x}_{e_{1}},\bar{x}_{e_{1}}+\bar{x}_{e_{2}}).
Now sample a random offset \alpha\in[0,1), and define B_{c} to be those elements of V_{c} whose interval contains a point in \mathbb{Z}+\alpha.
Property 1 follows directly. For property 2, note that the union of intervals of all e\in V_{c} is also an interval (as elements of the same color are grouped together), of length \bar{x}(V_{c}); its intersection with \mathbb{Z}+\alpha must thus be of size either \lfloor\bar{x}(V_{c})\rfloor or \lceil\bar{x}(V_{c})\rceil,
and every point in this intersection adds exactly one new element to B_{c} since \bar{x}_{e}\leq 1 for all e. Property 3 follows likewise.

Then, for every color such that |S\cap V_{c}|<|B_{c}|, add any |B_{c}|-|S\cap V_{c}| elements from B_{c}\setminus S to S.
This obtains S^{+}.
We argue that the augmented set S^{+} is feasible
(for the complement problem \max_{V\setminus S\in\mathcal{F}}\bar{f}(S)).
Note that |B_{c}|\in\{\lfloor\bar{x}(V_{c})\rfloor,\lceil\bar{x}(V_{c})\rceil\}\subseteq[|V_{c}|-u_{c},|V_{c}|-\ell_{c}], since \bar{x}\in\mathds{1}-P_{\mathcal{F}} and the bounds are integral.
For the lower bounds, we have |S^{+}\cap V_{c}|\geq|B_{c}|\geq|V_{c}|-u_{c}.
For the upper bounds, note that |S^{+}\cap V_{c}|=\max\{|S\cap V_{c}|,|B_{c}|\}\leq|V_{c}|-\ell_{c}, since by definition of S, |S\cap V_{c}|\leq|V_{c}|-\ell_{c}.
Moreover, |S^{+}|\geq\sum_{c}|B_{c}|\geq\lfloor\bar{x}(V)\rfloor\geq n-k, since \bar{x}\in\mathds{1}-P_{\mathcal{F}} and n-k is an integer.

To bound the loss in value resulting from the additional elements, we make use of Lemma 2.2.
Note that for any e\in V_{c}, \operatorname{\mathbb{P}}\left[e\in S^{+}\setminus S\right]\leq\operatorname{\mathbb{P}}\left[e\in B_{c}\right]=\bar{x}_{e}\leq\|\bar{x}\|_{\infty}.
Lemma 2.2 and the definitions of S and \bar{x} then imply that

\operatorname{\mathbb{E}}[\bar{f}(S^{+})]\geq(1-\|\bar{x}\|_{\infty})\operatorname{\mathbb{E}}[\bar{f}(S)]\geq 0.401(1-\min_{x\in\mathds{1}-P_{\mathcal{F}}}\|x\|_{\infty})\max_{V\setminus S\in\mathcal{F}}\bar{f}(S).

Finally, taking the complement V\setminus S^{+} yields a {}0.401(1-\min_{x\in\mathds{1}-P_{\mathcal{F}}}\|x\|_{\infty})-approximation to the original problem, in expectation.
∎

B.4 Proofs of Section 3.5

In this section, we give the full proof of Theorem 3.7.
See 3.7

Proof.

Vondrák (2013, Theorem 1.2, 1.9 and Section 2) showed that any algorithm achieving a better than (1-r)-approximation for the problem of maximizing a non-monotone submodular function over the bases of a matroid \mathcal{I}, where \min_{x\in P_{\mathcal{I}}:\sum_{i}x_{i}=k}\|x\|_{\infty}\leq r, requires exponentially many value queries. This holds also for the continuous relaxation of the problem (see Theorem 1.9 and Section 2 therein).

We show that the hard instance used in the proofs of the lower bounds in Vondrák (2013) is a special case of FMSM with \min_{x\in P_{\mathcal{F}}\cup(\mathds{1}-P_{\mathcal{F}})}\|x\|_{\infty}\leq r.
In particular, the hard instance uses a ground set V=A\cup B, where A and B are two disjoint sets, each of size t\times m, for some large number m, and a partition matroid base constraint \mathcal{B}=\{S:|S\cap A|=m\text{ and }|S\cap B|=(t-1)m\} (see Section 2, Theorems 1.8 and 1.9 therein).

We can express this matroid base constraint via \mathcal{F} in two ways. First, any matroid base constraint is a special case of \mathcal{F} where C=1, V=V_{1}, and \ell_{1}=u_{1}=k (the rank of the matroid), i.e., the fairness constraint reduces to |S|=k. In the case of \mathcal{B}, we have k=t\times m and \min_{x\in P_{\mathcal{F}}\cup(\mathds{1}-P_{\mathcal{F}})}\|x\|_{\infty}=\min_{x\in P_{\mathcal{I}}:\sum_{i}x_{i}=k}\|x\|_{\infty}=1-\tfrac{1}{t}.
Alternatively, we can express \mathcal{B} with a fairness constraint alone, with two color groups V_{1}=A, V_{2}=B, \ell_{1}=u_{1}=m, and \ell_{2}=u_{2}=(t-1)m. ∎

B.5 Proofs of Section 4

In this section, we prove Lemma 4.2 and Theorem 4.3.

See 4.2

Proof.

Note that any fair set is a maximal set of the k-truncation of \mathcal{C} given by \mathcal{C}_{k}:=\{S\in\mathcal{C}\mid|S|\leq k\} with k=|S|. The family \mathcal{C}_{k} is a special case of \mathcal{F} where \mathcal{I} is the k-uniform matroid, so the corresponding family of extendable set \tilde{\mathcal{C}}_{k} is a matroid (El Halabi et al., 2020, Lemma 4.1).
The claim then follows from Fact 4.1.
∎

See 4.3

Proof.

The randomized rounding scheme of Chekuri et al. (2010, Section V) takes as input a fractional solution x^{\prime}\in P_{\mathcal{I}_{1}}\cap P_{\mathcal{I}_{2}}, where \mathcal{I}_{1} and \mathcal{I}_{2} are two matroids, expressed as
a convex combination of sets in \mathcal{I}_{1}\cap\mathcal{I}_{2},
and returns a set S^{\prime}\in\mathcal{I}_{1}\cap\mathcal{I}_{2} such that \operatorname{\mathbb{E}}[f^{\prime}(S^{\prime})]\geq F^{\prime}(x^{\prime}) for any submodular function f^{\prime} which decomposes over the equivalence classes of \mathcal{I}_{1} or \mathcal{I}_{2},
i.e., f^{\prime}(S)=\sum_{G\in\mathcal{G}_{1}}f^{\prime}_{1,G}(S\cap G)+\sum_{G\in\mathcal{G}_{2}}f^{\prime}_{2,G}(S\cap G), where f^{\prime}_{1,G},f^{\prime}_{2,G} are submodular functions and \mathcal{G}_{1},\mathcal{G}_{2} are the respective families of equivalence classes of \mathcal{I}_{1} and \mathcal{I}_{2} (see Theorem II.3 therein). If the sets in the input convex combination are all of the same size k, then the returned set will have size k too.

Given x\in P_{\mathcal{F}}, since P_{\mathcal{F}} is solvable (Lemma 2.1-c), we can write x as a convex combination of sets in \mathcal{F} in strongly polynomial time (Schrijver, 2003, Theorem 5.15); i.e., x=\sum_{t}\alpha_{t}\mathds{1}_{I_{t}} for some I_{t}\in\mathcal{F},\alpha_{t}\geq 0,\sum_{t}\alpha_{t}=1.

Let k be the size of the largest set I_{t}. Lemma 4.2 implies that every set I_{t} is in the intersection of the matroids \mathcal{I} and \tilde{\mathcal{C}}_{k}, where \tilde{\mathcal{C}}_{k} is defined as in the lemma.
Then x is already a valid input for swap rounding. If all sets I_{t} have the same size, then the returned rounded solution S\in\mathcal{I}\cap\tilde{\mathcal{C}}_{k} is a base of \tilde{\mathcal{C}}_{k}, and thus also a fair set by Lemma 4.2. So S is feasible. Otherwise, S is not necessarily feasible. In that case, we first need to
add dummy elements to make all sets I_{t} of equal size.

Let E be a set of k new dummy elements (not in V). For every t, we add enough dummy elements from E to I_{t} to obtain a set I^{\prime}_{t} of size k. We also extend the matroid \mathcal{I} to \mathcal{I}^{+}=\{S\subseteq V\cup E\mid S\setminus E\in\mathcal{I}\} and the collection of fair sets \mathcal{C} to \mathcal{C}^{+}=\{S\subseteq V\cup E\mid S\setminus E\in\mathcal{C}\}. It is easy to verify that \mathcal{I}^{+} is also a matroid. Observe that \mathcal{C}^{+} is also a collection of fair sets over the extended ground set, since \mathcal{C}^{+}=\{S\subseteq V\cup E\mid|S\cap V_{c}|\in[\ell_{c},u_{c}]~\forall c\in[C],|S\cap E|\in[0,|E|]\}, so Lemma 4.2 applies to it. Moreover, \tilde{\mathcal{C}}^{+}_{k}=\{S\subseteq V\cup E\mid\text{ there exists }S^{\prime}\in\mathcal{C}^{+},|S^{\prime}|\leq k\text{ such that }S\subseteq S^{\prime}\} is a matroid
of rank k, since any set in \tilde{\mathcal{C}}^{+}_{k} has size at most k and there exists I_{t}\in\tilde{\mathcal{C}}^{+}_{k} with size k for some t.

Let x^{\prime}=\sum_{t}\alpha_{t}\mathds{1}_{I^{\prime}_{t}}. Since every set I^{\prime}_{t} is in the intersection of the matroids \mathcal{I}^{+} and \tilde{\mathcal{C}}^{+}_{k}, x^{\prime} is a valid input to swap rounding. And since all I^{\prime}_{t} have size k, the returned rounded solution S^{\prime}\in\mathcal{I}^{+}\cap\tilde{\mathcal{C}}^{+}_{k} will also have size k. Hence, S^{\prime} is a base of \tilde{\mathcal{C}}^{+}_{k}, and thus S^{\prime}\in\mathcal{C}^{+} by Lemma 4.2.
Removing the dummy elements from S^{\prime} then yields a feasible solution S=S^{\prime}\setminus E\in\mathcal{I}\cap\mathcal{C}.

It remains to show that the solution S preserves the value of F(x) for any decomposable submodular function f over \mathcal{F}. Define f^{\prime}:2^{V\cup E}\to\mathbb{R}_{+} as f^{\prime}(S)=f(S\setminus E), then its multilinear extension F^{\prime}:[0,1]^{n+k}\to\mathbb{R}_{+} is given by F^{\prime}(x^{\prime})=F(x^{\prime}_{V}) where x^{\prime}_{V}\in[0,1]^{n} is the vector corresponding to the entries of x^{\prime} in V.
We observe that f^{\prime} decomposes over the equivalence classes of \mathcal{I}^{+} or \tilde{\mathcal{C}}^{+}_{k}, with f^{\prime}_{1,G}(S)=f_{1,G}(S\setminus E) and f^{\prime}_{2,c}(S)=f_{2,c}(S\setminus E), where f_{1,G},f_{2,c} are the functions in the decomposition of f (Definition 2.4). One can verify that f^{\prime},f^{\prime}_{1,G},f^{\prime}_{2,c} are submodular since f,f_{1,G},f_{2,c} are submodular.
The solution S returned by swap rounding then satisfies \operatorname{\mathbb{E}}[f^{\prime}(S^{\prime})]=\operatorname{\mathbb{E}}[f(S)]\geq F^{\prime}(x^{\prime})=F(x).
∎

It is worth mentioning that El Halabi et al. (2023, Appendix C.2) have already shown a reduction of FMSM to submodular maximization over the intersection of two matroid bases. However, their result cannot be used to prove Theorem 4.3, since the matroids in their reduction have different equivalence classes than the ones of \mathcal{I} and the color groups. Using their reduction in Theorem 4.3 would require considering a much more restricted class of decomposable submodular functions (ones which are completely separable over V, or over subgroups of colors obtained by splitting each color group into two).

Appendix C Relation to multi-objective submodular maximization

In this section, we discuss the connection of FMSM to multi-objective submodular maximization, where given m submodular functions f_{i}, the goal is to maximize their minimum \min_{i\in[m]}f_{i}(S).

We can write FMSM as a multi-objective submodular maximization problem over two matroids:

\max_{S\subseteq V}\{\min_{i\in[C+1]}f_{i}(S):S\in\mathcal{I},|S\cap V_{c}|\leq u_{c}\quad\forall c\in[C]\},

where f_{C+1}=f/\operatorname{OPT} and f_{c}=|S\cap V_{c}|/\ell_{c} for all c\in[C].
Recall that \operatorname{OPT} is the optimal value of FMSM, which can be guessed.
A solution S of Problem (4) is then also an optimal solution to FMSM.
To the best of our knowledge, there are no existing work on multi-objective submodular maximization over two matroids.

In the special cases where there are no upper bounds (u_{c}=|V_{c}|) or \mathcal{I} is the uniform matroid, and f is monotone, one can apply the result of (Chekuri et al., 2009, Theorem 7.2) on multi-objective submodular maximization over a single matroid to obtain a (1-1/e)-approximation for monotone FMSM.
But the resulting runtime will be exponential in \sum_{c}\ell_{c} as the algorithm requires guessing the \ell_{c} elements belonging to the optimal solution for each group c, by brute force enumeration.
Recall though that when \mathcal{I} is the uniform matroid, a polynomial time (1-1/e)-approximation for monotone FMSM was provided in (Celis et al., 2018a, Theorem 18) under the assumption that the groups are disjoint, which is not assumed in (Chekuri et al., 2010). Celis et al. (2018a) also provided a (1-1/e)-approximation algorithm for the overlapping groups case, but its runtime is also exponential in C (see Theorem 20 therein).

Finally, if there are no upper bounds (u_{c}=|V_{c}|), \mathcal{I} is the uniform matroid, and f is monotone, then the constraint in Problem (4) becomes a simple cardinality constraint. In this case, a (1-1/e-o(1))-approximation for monotone FMSM can be obtained
in polynomial-time if k=o(n), even with overlapping groups Udwani (2018); Tsang et al. (2019).

The line of work Wang et al. (2024); Tsang et al. (2019); Tang and Yuan (2023) which studied submodular maximization under a different notion of fairness can all be formulated as a monotone multi-objective submodular maximization problem over a cardinality constraint.

Where this page came from

This page was imported from arXiv. “Fairness in Submodular Maximization over a Matroid Constraint” by Marwa El Halabi, Jakub Tarnawski, Ashkan Norouzi-Fard et al., arXiv:2312.14299 (2023), published under CC BY 4.0. Changed here: set as a page from arXiv's HTML version; footnotes and author notes left out; figures the paper marks as under other terms left out.

Nobody has written it yet — it is the source material at a new address, which is why search engines are asked to skip it and why no one earns from it. It is up for grabs: take it on, and it is yours to rewrite and to earn from.