Matchings with Group Fairness Constraints: Online and Offline Algorithms

We have a set $A$ of items and a set $P$ of platforms, and these sets form the two parts of a bipartite graph. The presence of an edge $(a,p)$ indicates that item $a$ can be matched to platform $p$. Let $N(p)$ denote the neighborhood of $p$. Each platform $p$ has a collection of classes $\mathcal{C}_{p}\subseteq 2^{N(p)}$, i.e., each item in $N(p)$ may belong to some of the classes in $\mathcal{C}_{p}$. Each class $C\in\mathcal{C}_{p}$ has an associated quota $q_{p}^{C}$ denoting the maximum number of items from $C$ that can be assigned to $p$. In addition, each platform $p$ has a quota $q_{p}$, which is an upper bound on the total number of items it can serve. Our goal is to compute an assignment of items to platforms so as to maximize the number of items assigned, while satisfying all the quotas.

Classes allow platforms to specify group fairness constraints – for instance the classes can be seen as properties or categories and the quotas impose the constraints that not too many items from one category are assigned to a platform. These types of fairness constraints have been studied in many practical applications. In  [AS03], the authors address the school choice problem where fairness constraints are imposed to achieve racial, ethnic, and gender balance. In the assignment of medical residents to hospitals in Japanese Residency Matching Program (JRMP), regional quotas are introduced to ensure fairness amongst urban and rural hospitals [KK12, KK15]. Huang [Hua10] motivates classifications from the perspective of enabling diversity in academic hiring. Apart from matchings, group fairness constraints have also been studied for many other problems like the knapsack problem [PKL21], and clustering problems [BCFN19], to name a few.

Some recent pre-prints have discussed fairness in matching problems. Soriano and Bonchi [GSB20] study a different notion of individual fairness that they call maxmin-fairness. Their goal is to output a solution such that the satisfaction of one agent cannot be improved without making another agent worse-off. Ma and Xu [MX20] measure fairness by the ratio of expected number of agents matched from a particular group to the expected number of agents from that group and their goal is to maximize the minimum of this ratio over all groups. Basu et al. [BDLK20] also measure fairness based on metrics involving the ratio of agents across groups and the utility they provide. While qualitatively similar, our constraints can be seen as being orthogonal to such notions of fairness.

In different applications, the fairness constraints can have a different structure. In [KK12, KK15], each hospital belongs to exactly one region, hence fairness constraints partition the set of hospitals. On the other hand, in the school choice problem in [AS03], a student belongs to multiple constraints. The structure of the constraints crucially affects the computational complexity of finding a fair allocation. This has been illustrated in the context of bipartite matchings where one or both sides of the bipartition express preferences over the other side. Huang [Hua10] and Fleiner and Kamiyama [FK12], address the CMM problem when both sides of the bipartition have preferences over each other and the notion of optimality is stability, whereas [NNP19] study the CMM problem under the optimality criteria of rank-maximality and popularity. In all these cases, it has been shown that the CMM problem can be efficiently solved if the constraints have a laminar²²2 A family $\mathcal{C}$ of subsets of a set $S$ is laminar if, for every pair of sets $X,Y\in\mathcal{C}$, either $X\subseteq Y$ or $Y\subseteq X$ or $X\cap Y=\emptyset$. structure, and is NP-hard in general [NNP19]. Such a restriction has been considered before in the literature, such as in the hospital-resident problem [KK12] or the college admissions problem [BFIM10, GIK⁺16]. However, a finer relation between the structure of the class constraints and the computational efficiency has not received much attention in literature. In this paper, we address this issue by focusing on a quantification of non-laminarity in the classes and its effect on computational efficiency. We strengthen the hardness results in [NNP19] and obtain new approximation algorithms for the CMM problem in the offline setting.

Next, we turn our attention to the online version of the problem. Online matching problems have numerous practical applications, such as in ad-allocations [MSVV07], resource allocations [DJSW11], etc. See [Meh13] for a survey on online bipartite matchings. Fairness has also been studied in online settings such as online learning [GJKR18] or ride-hailing platforms [SBZ⁺19]. ‘Fairness’ in another form has been considered previously in the online literature. For example, the ‘frequency caps’ mentioned in [FMMM09] places a restriction on the total number of ads that are shown to the same user, or users from a particular demographic. We study some natural online versions of the CMM problem. We first show that one of our approximation algorithms for the offline non-laminar case also works as an online algorithm, regardless of the input model. For the setting where we restrict classes to be laminar, we show that existing algorithms for online bipartite matching carry over to our setting.

Given a hypergraph $H=(V,E)$, and a function $f:E\to\mathbb{Z}^{+}$, compute the largest set of vertices $S$ such that for every $e\in E$, $|S\cap e|\leq f(e)$. We note that when $f(e)=1\$ for each edge $e$, this is the problem of computing the strong maximum independent set and when $f(e)=|e|-1$, this is the weak maximum independent set problem. These problems are well-studied for bounded-degree hypergraphs; [HL09] describe algorithms achieving factors of $\frac{1}{\Delta}$ and $\frac{5}{\Delta+3}$ for the strong and weak cases respectively, where $\Delta$ denotes the maximum degree of a vertex in $H$. For the weak independent set, this was further improved to $O\left(\frac{\log\Delta}{\Delta\log\log\Delta}\right)$ in [AHL13]. However, to the best of our knowledge, there is no known approximation algorithm for the case when $f(e)$ is an arbitrary value – we call this the generalized maximum independent set  on hypergraphs. We state our approximation result for independent sets on hypergraphs below, which is a consequence of Theorem 2.

For the case when average degree of the vertices is $\Delta$, we get the following:

For the CMM problem, this implies an $\frac{OPT}{4\Delta n}$ approximation algorithm when we only have an upper bound on the average number of laminar families of classes an item belongs to, and there is only one platform.

In an apparently different model, Celis et al. [CSV18] consider ranking $n$ items from a universe of $m$ items, where $n\ll m$. Items are assigned properties, and upper quotas for the number of items from any property in the top $k$ ranks. When items have at most $\Delta$ properties each, they give a $\frac{1}{\Delta+2}$ approximation while allowing constraints to be violated by a factor of $2$. This problem can be reduced to the CMM problem and our algorithm from Theorem 2 achieves the same approximation factor without violating any class constraints.

We now show a reduction from their problem to the CMM problem. The fair rankings problem is defined as follows: Given a set of $m$ items, our objective is to choose $n$ among them and rank them. Every item $i$ has a value $W_{ij}$ when ranked in the $j^{th}$ position. Every item also has some properties, and every property can be represented as a subset of the $m$ items that share that property. The objective is to rank them such that this the total value is maximized, subject to some fairness constraints on the properties. A fairness constraint corresponding to the property $p$ is set of values $U_{1}^{p},U_{2}^{p},\ldots,U_{n}^{p}$ such that $U_{k}^{p}$ is the maximum number of items with property $p$ that can be ranked in the top $k$ positions.

In the reduction, we create one platform $p$. For every item $i$ in the ranking instance we have $n$ items $(i,1),(i,2),\ldots,(i,n)$ in the CMM instance. The item $(i,j)$ being matched to $p$ will be equivalent to ranking the $i^{th}$ item in the $j^{th}$ position. Then our classes are

• •

  One class for every item to ensure that an item is ranked at most once. That is, $\forall\ i\in\{1,2,\ldots,m\}$, we have the class

  $$C=\{(i,1),(i,2),(i,3)\ldots(i,n)\}\quad q(C)=1$$

• •

  One class for every rank to ensure that at most one item is ranked in one position. That is, $\forall\ j\in\{1,2,\ldots,n\}$, we have the class

  $$C=\{(1,j),(2,j),(3,j)\ldots(m,j)\}\quad q(C)=1$$

• •

  One laminar family of classes for every property $p$ with constraints $U_{1}^{p},U_{2}^{p},\ldots,U_{n}^{p}$. There are $n$ constraints, one for each position in the ranking. Let $p=\{i_{1},i_{2},\ldots,i_{k}\}$ be the items with property $p$. Then $\forall\ p,\forall j\in\{1,2,\ldots,n\}$ we have

  	$\displaystyle C_{j}^{p}=\{(i_{1},j),(i_{2},j),(i_{3},j)\ldots(i_{k},j)\}\cup C_{j-1}^{p}$
  	$\displaystyle q(C_{j}^{p})=U_{j}^{p}$

  where $C_{0}^{p}=\{\}$. It is easily seen that this is a laminar family.

Thus, for an item $i$ in the ranking instance that belongs to $\Delta$ properties, for any $j\in\{1,2,\ldots,n\}$, $(i,j)$ in the constructed CMM instance belongs to $\Delta+2$ laminar families of classes. Using the algorithm from Theorem 2, we get a $\frac{1}{\Delta+2}$ approximation without any violation in quotas. However, it has to be noted that in [CSV18], they insist on finding a ranking with $n$ elements whereas we may output a possibly smaller ranking. We also note that this reduction immediately gives a better hardness of approximation of $O\left(\frac{\log\Delta}{\Delta}\right)$ for the setting where every item lies in $\Delta$ laminar families of classes per platform.

Kutz et al. [KEKM08] study the problem called simultaneous matchings which is defined as follows: given a bipartite graph $G=(X\cup D,E)$ and a collection $\mathcal{F}\subseteq 2^{X}$, find the largest solution $M\subseteq E$ such that $\forall\ C\in\mathcal{F},M\cap(C\times D)$ is a matching. This problem can be reduced to the CMM problem where every vertex $d$ in $D$ has constraints $\mathcal{F}$ (excluding vertices to which $d$ has no edge), and each class has quota $1$. The approximation factor in [KEKM08] is better but the constraints are significantly more restricted than ours.

Subject to

Subject to

Now, we need to set the dual variables so that the dual constraints have a lower bound of $F$. Let $g:[0,1]\to[0,1]$ be a monotonically increasing function to be fixed later. Initially, all dual variables are zero. When a new item arrives, we update the primal solution based on whether we matched the item or now, and update the dual solution as follows.

• •

  If an edge $(i,j)$ is chosen by the algorithm (i.e. $x_{ij}=1$) then set $\alpha_{i}^{(j)}:=1$, where $\alpha_{i}^{(j)}$ is the dual variable corresponding to the class $C_{i}^{(j)}=\{p_{j}\}$.

• •

  If any class $C^{(k)}_{j}$ of platform $j$ is tight then for all items $a_{i}$ in the class $C_{j}^{(k)}$ set $\alpha_{i}^{(j)}=g(y_{i})$ if we had that $\alpha_{i}^{(j)}=1$ before the new item arrived. Fix $\beta_{j}^{(k^{\prime})}=0$ for all $k^{\prime}$ such that $C_{j}^{(k^{\prime})}\subset C_{j}^{(k)}$. Let it remain unchanged henceforth. Also set

  $$\beta_{j}^{(k)}:=1-\frac{\sum_{i:i\in C_{j}^{(k)},\alpha_{i}\neq 0}g(y_{i})}{q(C_{j}^{(k)})}\geq 1-\max_{i\in C_{j}^{(k)},\alpha_{i}\neq 0}g(y_{i}).$$

• •

  If any class $C_{i}^{(k)}$ of item $a_{i}$ is tight then set

  $$\alpha_{i}^{(k)}:=\frac{1}{q(C_{j}^{(k)})}\sum_{k^{\prime}:C_{i}^{(k^{\prime})}\subset C_{i}^{(k)}}\alpha_{i}^{(k^{\prime})}q(C_{i}^{(k^{\prime})})\geq g(y_{i}).$$

  Fix $\alpha_{i}^{k^{\prime}}=0$ for all $k^{\prime}$ such that $C_{i}^{(k^{\prime})}\subset C_{i}^{(k)}$. Let it remain unchanged henceforth.

It can be easily seen that the dual objective function is equal to the primal objective function. It remains to be shown that the dual constraints are always greater than some $F$ in expectation.

The following is the key lemma in analyzing how the algorithm behaves depending on $\vec{y}$. Although it is inspired by [DJK13, HKT⁺18, GM08], our many-to-many model (Model 2) is more complicated in that moving one vertex up the ranking can cause more changes to the matching because an item can match to multiple platforms. Even apart from the platform classes, we must take care of item classes as well. To that end, we show the following lemma.

Once we have the lemma, we show Theorem 4 the following way. Let $\alpha\geq 1$ be such a dual constraint. We want to show that $\mathop{\mathbb{E}}\left[\alpha\right]\geq F$ or equivalently, $\mathop{\mathbb{E}}_{y_{-i}}\left[\mathop{\mathbb{E}}_{y_{i}}\left[\alpha\right]\right]\geq F$. We look at the inner expectation. We fix $y_{-i}$ and vary $y_{i}$ from 0 to 1, and show using dual-fitting arguments and Lemma 3 that $\mathop{\mathbb{E}}\left[\alpha\right]\geq\left(1-\frac{1}{e}\right)$. From Fact 1, this completes the proof of Theorem 4.