Group Fairness in Non-monotone Submodular Maximization

• •

  Our study breaks new ground by examining the classic (non-monotone) submodular maximization problem under $(\alpha,\beta)$-fairness constraints. Our model offers flexibility in capturing varying degrees of fairness as desired by the decision maker, by adjusting the values of $\alpha$ and $\beta$.

• •

  We develop the first constant-factor approximation algorithm for this problem. We observe that the parameter $\alpha$ is closely linked to the complexity of solving the $(\alpha,\beta)$-fair non-monotone submodular maximization problem. In particular, when $\alpha\leq 1/2$, we design a $\frac{\gamma}{2}$-approximation algorithm and when $\alpha>1/2$, we develop a $\frac{\gamma}{3}$-approximation algorithm, where $\gamma$ is the approximation ratio of the current best algorithm for matroid-constrained submodular maximization. We also extend the basic model to incorporate an additional global size constraint on the total number of selected items. We provide approximation algorithms that have a constant-factor approximation ratio for this extended model.

In recent years, there has been a growing awareness of the importance of fair and unbiased decision-making systems. This has led to an increased interest in the development of fair algorithms in a wide range of applications, including influence maximization [25], classification [26], voting [4], bandit learning [15], and data summarization [3]. Depending on the specific context and the type of bias that one is trying to mitigate, existing studies adopt different metrics of fairness. This can lead to different optimization problems and different fair algorithms that are tailored to the specific requirements of the application. Our notation of fairness is general enough to capture many existing notations such as the $80\%$-rule [1], statistical parity [8] and proportional representation [17]. Unlike most of existing studies on fair submodular maximization [4] whose objective is to maximize a monotone submodular function, [10] develop fair algorithms in the context of streaming non-monotone submodular maximization. Their proposed notation of fairness is more general than ours, leading to a more challenging optimization problem which does not admit any constant-factor approximation algorithms. [24, 23] aim to develop randomized algorithms that satisfy average fairness constraints. Very recently, [22] extend the studies of fair algorithms to a more complicated adaptive setting and they propose a new metric of fairness called group equality.

In the scenario where $\alpha\leq 1/2$, we use the solution of P.1 as a building block to construct our algorithm. First, it is easy to verify that P.1 is a relaxed version of P.0 with lower bound constraints $\lfloor\alpha|V_{i}|\rfloor\leq|S\cap V_{i}|$ in P.0 being removed. Because $f$ is a submodular function, P.1 is a classic problem of maximizing a (non-monotone) submodular function subject to matroid constraints. There exist effective solutions for P.1. Now we are ready to present the design of our algorithm as below.

1. 1.

   Apply the state-of-the-art algorithm $\mathcal{A}$ for matroid constrained submodular maximization to solve P.1 and obtain a solution $A^{P.1}$.

2. 2.

   Note that $A^{P.1}$ is not necessarily a feasible solution to P.0 because it might violate the lower bound constraints $\lfloor\alpha|V_{i}|\rfloor\leq|S\cap V_{i}|$ for some groups. To make it feasible, we add additional items to $A^{P.1}$. Specifically, for each group $i\in[m]$ such that $|A^{P.1}\cap V_{i}|<\lfloor\alpha|V_{i}|\rfloor$, our algorithm selects a backup set $B_{i}$ of size $\lfloor\alpha|V_{i}|\rfloor-|A^{P.1}\cap V_{i}|$, by randomly sampling $\lfloor\alpha|V_{i}|\rfloor-|A^{P.1}\cap V_{i}|$ items from $V_{i}\setminus A^{P.1}$. Define $B_{i}=\emptyset$ if $|A^{P.1}\cap V_{i}|\geq\lfloor\alpha|V_{i}|\rfloor$.

3. 3.

   At the end, add $\cup_{i\in[m]}B_{i}$ to $A^{P.1}$ to build the final solution $A^{approx}$, i.e., $A^{approx}=A^{P.1}\cup(\cup_{i\in[m]}B_{i})$.

The pseudocode of this approximation algorithm is given as Algorithm 1. Observe that $A^{P.1}$ is a feasible solution to P.1, hence, $A^{P.1}$ satisfies upper bound constraints of P.1 and hence P.0, i.e., $|S\cap V_{i}|\leq\lfloor\beta|V_{i}|\rfloor,\forall i\in[m]$. According to the construction of $B_{i}$, it is easy to verify that adding $\cup_{i\in[m]}B_{i}$ to $A^{P.1}$ does not violate the upper bound constraints because $\cup_{i\in[m]}B_{i}$ are only supplemented to those groups which do not satisfy the lower bound constraints of P.0, i.e., $\lfloor\alpha|V_{i}|\rfloor\leq|S\cap V_{i}|$. Moreover, adding $\cup_{i\in[m]}B_{i}$ to $A^{P.1}$ makes it satisfy lower bound constraints of P.0. Hence, $A^{approx}$ is a feasible solution to P.0.

We next consider the case when $\alpha>1/2$. We first introduce a new utility function $g:2^{V}\rightarrow\mathbb{R}_{+}$ as below:

We first present a well-known result, which states that submodular functions maintain their submodularity property when taking their complement.

With utility function $g$, we present a new optimization problem P.2 as below:

  P.2 $\max g(S)$
subject to:
$|V_{i}|-\lfloor\beta|V_{i}|\rfloor\leq|S\cap V_{i}|\leq|V_{i}|-\lfloor\alpha|V_{i}|\rfloor,\forall i\in[m]$.

P.2 is a flipped version of the original problem P.0 in the sense that if there is a $\gamma$-approximate solution $A^{P.2}$ to P.2, it can be easily verified that $V\setminus A^{P.2}$ is a $\gamma$-approximate solution to P.0. As a result, we will focus on solving P.2 for the rest of this section.

To solve P.2, we introduce another problem (labeled as P.3) as follows:

  P.3 $\max g(S)$
subject to:
$|S\cap V_{i}|\leq|V_{i}|-\lfloor\alpha|V_{i}|\rfloor,\forall i\in[m]$.

P.3 is relaxed version of P.2 with lower bound constraints $|V_{i}|-\lfloor\beta|V_{i}|\rfloor\leq|S\cap V_{i}|$ in P.2 being removed. Because $g$ is a submodular function, P.3 is a classic problem of maximizing a submodular function subject to matroid constraints. Now we are ready to present the design of our algorithm.

1. 1.

   Apply the state-of-the-art algorithm $\mathcal{A}$ for matroid constrained submodular maximization to solve P.3 and obtain a solution $A^{P.3}$.

2. 2.

   Note that $A^{P.3}$ is not necessarily a feasible solution to P.2 because it might violate the lower bound constraints $|V_{i}|-\lfloor\beta|V_{i}|\rfloor\leq|S\cap V_{i}|$ for some groups. We add additional items to $A^{P.3}$ to make it feasible. Specifically, for each group $i\in[m]$ such that $|A^{P.3}\cap V_{i}|<|V_{i}|-\lfloor\beta|V_{i}|\rfloor$, our algorithm selects a backup set $B_{i}$ of size $|V_{i}|-\lfloor\beta|V_{i}|\rfloor-|A^{P.3}\cap V_{i}|$, by randomly sampling $|V_{i}|-\lfloor\beta|V_{i}|\rfloor-|A^{P.3}\cap V_{i}|$ items from $V_{i}\setminus A^{P.3}$. Define $B_{i}=\emptyset$ if $|A^{P.1}\cap V_{i}|\geq|V_{i}|-\lfloor\beta|V_{i}|\rfloor$.

3. 3.

   Add $\cup_{i\in[m]}B_{i}$ to $A^{P.3}$ to build $A^{approx}$, i.e., $A^{approx}=A^{P.3}\cup(\cup_{i\in[m]}B_{i})$. Return $V\setminus A^{approx}$ as the final solution.

The pseudocode of this approximation algorithm is given as Algorithm 2. Observe that $A^{P.3}$ satisfies upper bound constraints of P.3 and hence P.2 because $A^{P.3}$ is a feasible solution to P.3. According to the construction of $B_{i}$, adding $\cup_{i\in[m]}B_{i}$ to $A^{P.1}$ does not violate the upper bound constraints because $\cup_{i\in[m]}B_{i}$ are added to meet the lower bound constraints of P.2 if necessary. Moreover, adding $\cup_{i\in[m]}B_{i}$ to $A^{P.3}$ makes it satisfy lower bound constraints of P.2. Hence, $A^{approx}$ is a feasible solution to P.2.

We first consider the case when $\alpha\leq 1/2$. We introduce a new optimization problem P.B as follows:

  P.B $\max f(S)$
subject to:
$|S\cap V_{i}|\leq\lfloor\beta|V_{i}|\rfloor,\forall i\in[m]$.
$\sum_{i\in[m]}\max\{\lfloor\alpha|V_{i}|\rfloor,|S\cap V_{i}|\}\leq c$.

It is easy to verify that P.B is a relaxation of P.A in the sense that every feasible solution to P.A is also a feasible solution to P.B. Hence, we have the following lemma.

It has been shown that the constraints in P.B gives rise to a matroid [10]. This, together with the assumption that $f$ is a submodular function, implies that P.B is a classic problem of maximizing a submodular function subject to matroid constraints. Now we are ready to present the design of our algorithm.

1. 1.

   Apply the state-of-the-art algorithm $\mathcal{A}$ for matroid constrained submodular maximization to solve P.B and obtain a solution $A^{P.B}$.

2. 2.

   Note that $A^{P.B}$ is not necessarily a feasible solution to P.A because it might violate the lower bound constraints $\lfloor\alpha|V_{i}|\rfloor\leq|S\cap V_{i}|$ for some groups. To make it feasible, we add additional items to $A^{P.B}$. Specifically, for each group $i\in[m]$ such that $|A^{P.B}\cap V_{i}|<\lfloor\alpha|V_{i}|\rfloor$, our algorithm selects a backup set $B_{i}$ of size $\lfloor\alpha|V_{i}|\rfloor-|A^{P.B}\cap V_{i}|$, by randomly sampling $\lfloor\alpha|V_{i}|\rfloor-|A^{P.B}\cap V_{i}|$ items from $V_{i}\setminus A^{P.B}$. Define $B_{i}=\emptyset$ if $|A^{P.1}\cap V_{i}|\geq\lfloor\alpha|V_{i}|\rfloor$.

3. 3.

   At the end, add $\cup_{i\in[m]}B_{i}$ to $A^{P.B}$ to build the final solution $A^{approx}$, i.e., $A^{approx}=A^{P.B}\cup(\cup_{i\in[m]}B_{i})$.

The pseudocode of this approximation algorithm is given as Algorithm 3. Observe that $A^{P.B}$ satisfies the group-wise upper bound constraints of P.A because $A^{P.B}$ meets the first set of constraints in P.B. According to the construction of $B_{i}$, adding $\cup_{i\in[m]}B_{i}$ to $A^{P.B}$ does not violate the group-wise upper bound constraints of P.A because $\cup_{i\in[m]}B_{i}$ are added to meet the lower bound constraints of P.A if necessary. Moreover, adding $\cup_{i\in[m]}B_{i}$ to $A^{P.B}$ does not violate the global cardinality constraint of P.A because $A^{P.B}$ meets the second set of constraints in P.B. At last, it is easy to verify that adding $\cup_{i\in[m]}B_{i}$ to $A^{P.B}$ makes it satisfy the lower bound constraints of P.A. Hence, $A^{approx}$ is a feasible solution to P.A.

Following the same proof of Theorem 3.1, we have the following theorem.

We next consider the case when $\alpha>1/2$. Recall that $g(\cdot)=f(V\setminus\cdot)$. We first present a flipped formation of P.A as below:

  P.C $\max g(S)$
subject to:
$|V_{i}|-\lfloor\beta|V_{i}|\rfloor\leq|S\cap V_{i}|\leq|V_{i}|-\lfloor\alpha|V_{i}|\rfloor,\forall i\in[m]$.
$|S|\geq n-c$.

Suppose there is a $\gamma$-approximate solution $A^{P.C}$ to P.C, it is easy to verify that $V\setminus A^{P.C}$ is a $\gamma$-approximate solution to P.A. We focus on solving P.C in the rest of this section. We first introduce a new optimization problem (labeled as P.D) as follows:

  P.D $\max g(S)$
subject to:
$|S\cap V_{i}|\leq|V_{i}|-\lfloor\alpha|V_{i}|\rfloor,\forall i\in[m]$.

P.D is relaxed version of P.C with both group-wise lower bound constraints $|V_{i}|-\lfloor\beta|V_{i}|\rfloor\leq|S\cap V_{i}|$ and global lower bound constraints $|S|\geq n-c$ in P.C being removed. Hence, we have the following lemma.

Recall that if $f$ is submodular, $g$ must be submodular (by Lemma 6). Hence, P.D is a classic problem of maximizing a submodular function subject to matroid constraints. We next present the design of our algorithm.

1. 1.

   Apply the state-of-the-art algorithm $\mathcal{A}$ for matroid constrained submodular maximization to solve P.D and obtain a solution $A^{P.D}$.

2. 2.

   Note that $A^{P.D}$ is not necessarily a feasible solution to P.C because it might violate the group-wise or the global lower bound constraints of P.C. We add additional items to $A^{P.D}$ to make it feasible. Specifically, for each group $i\in[m]$, our algorithm selects a backup set $B_{i}$ of size $|V_{i}|-\lfloor\alpha|V_{i}|\rfloor-|A^{P.D}\cap V_{i}|$, by randomly sampling $|V_{i}|-\lfloor\alpha|V_{i}|\rfloor-|A^{P.D}\cap V_{i}|$ items from $V_{i}\setminus A^{P.D}$. Define $B_{i}=\emptyset$ if $|V_{i}|-\lfloor\alpha|V_{i}|\rfloor-|A^{P.D}\cap V_{i}|=0$.

3. 3.

   Add $\cup_{i\in[m]}B_{i}$ to $A^{P.D}$ to build $A^{approx}$, i.e., $A^{approx}=A^{P.D}\cup(\cup_{i\in[m]}B_{i})$. Return $V\setminus A^{approx}$ as the final solution.