# Individual Fairness under Varied Notions of Group Fairness in Bipartite
Matching - One Framework to Approximate Them All

Atasi Panda
<EMAIL_ADDRESS>
Indian Institute of Science  Anand Louis 111These two authors contributed
equally
<EMAIL_ADDRESS>
Indian Institute of Science  Prajakta Nimbhorkar ††footnotemark:
<EMAIL_ADDRESS>
Chennai Mathematical Institute

We study the probabilistic assignment of items to platforms that satisfies
both group and individual fairness constraints. Each item belongs to specific
groups and has a preference ordering over platforms. Each platform enforces
group fairness by limiting the number of items per group that can be assigned
to it. There could be multiple optimal solutions that satisfy the group
fairness constraints, but this alone ignores item preferences. Our approach
explores a ‘best of both worlds fairness’ solution to get a randomized
matching, which is ex-ante individually fair and ex-post group-fair. Thus, we
seek a ‘probabilistic individually fair’ distribution over ‘group-fair’
matchings where each item has a ‘high’ probability of matching to one of its
top choices. This distribution is also ex-ante group-fair. Users can customize
fairness constraints to suit their requirements. Our first result is a
polynomial-time algorithm that computes a distribution over ‘group-fair’
matchings such that the individual fairness constraints are approximately
satisfied and the expected size of a matching is close to OPT. We empirically
test this on real-world datasets. We present two additional polynomial-time
bi-criteria approximation algorithms that users can choose from to balance
group fairness and individual fairness trade-offs.

For disjoint groups, we provide an exact polynomial-time algorithm adaptable
to additional lower ‘group fairness’ bounds. Extending our model, we encompass
‘maxmin group fairness,’ amplifying underrepresented groups, and ‘mindom group
fairness,’ reducing the representation of dominant groups.’

##  1 Introduction

Matching is a foundational concept in theoretical computer science, well-
studied over several years. Maximum bipartite matching finds applications in
real-world scenarios, such as ad-auctions [49, 50], resource allocation [37],
scheduling [48], school choice [6, 42], and healthcare rationing [2, 30]. In
this paper, we refer to the two partitions of the underlying bipartite graph
as items and platforms. A matching is an allocation of items to platforms,
allowing multiple assignments for each item and platform. Real-world items
often have diverse attributes, leading to their categorization into different
groups. To ensure equitable representation among these groups, it is natural
to enforce group fairness constraints [Definition 3.1], which limit the number
of items per group assigned to a platform by enforcing upper bounds. Also, one
can specify lower bounds on the number of items from each group that need to
be assigned to a platform, so as to ensure a minimum representation from each
group among the items matched to a platform. The above constraints thus
achieve Restricted Dominance introduced in [9], which asserts that the
representation from any group on any platform does not exceed a user-specified
cap, and Minority Protection [9], which asserts that the representation from
any group, among the items matched to any platform is at least a user-
specified bound [Definition 3.2].

Both the definitions of group fairness are well-motivated by various
applications like school choice, formation of committees in an organization,
or teams to work on projects. For instance, in school choice, group-fairness
constraints can promote diversity among students assigned to each school based
on attributes like ethnicity and socioeconomic background, as observed in
practical implementations [18]. Similarly, in project teams, group fairness
constraints ensure the inclusion of experts from all required fields. Both
definitions of group fairness are motivated by the Disparate Impact doctrine
[24] which broadly posits addressing unintentional bias which leads to widely
different outcomes for different groups.

However, since items have preferences over platforms, a matching meeting group
fairness constraints alone may not be fair to individual items. The exclusive
use of group fairness constraints can lead to sub-optimal outcomes for
individuals. Furthermore, deterministic algorithms for matching assign top
choices to some individuals while assigning less preferred choices to others.
This necessitates the introduction of individual fairness constraints. In this
paper, we consider probabilistic individual fairness constraints, first
introduced in robust clustering [1, 38]. Instead of a single matching, the
goal is to generate a distribution on group-fair matchings such that, in a
matching sampled from the said distribution, the probability of each item
being matched to one of its top choices is within the user-specified bounds
[Definition 3.3]. Thus, this approach, known as the best of both worlds
fairness approach in literature, aims to compute an outcome with both ex-ante
and ex-post fairness guarantees.

In this paper, the central objective is to design efficient algorithms that
compute an ex-ante probabilistic individually fair distribution over
deterministic group-fair matchings.

###  1.1 An overview of our results and techniques

Our approach revolves around formulating various notions of individual and
group fairness using linear programming (LP). The key idea is to represent the
LP’s optimal solution as a convex combination of integer group-fair matchings,
enabling the satisfaction of probabilistic individual fairness constraints
through sampling. However, depending on the structure of the groups, it may
not be possible to express the LP optimum as an exact convex combination of
integral group-fair matchings. Nonetheless, our algorithms express an
approximate LP optimum as a convex combination of integer matchings.

Our technique leads to a unified framework for different group fairness
notions beyond fixed upper and lower bound constraints on the number of items
from each group that can be matched to a platform. Two such notions, referred
to as maxmin group fairness and mindom group fairness in this paper, are
discussed in a later section (see Section 3). In maxmin group fairness, the
goal is to maximize the minimum number of items that get matched to any
platform from any one group. In mindom group fairness, the goal is to minimize
the maximum number of items that get matched to any platform from any one
group. Informally, both these notions aim to get a matching with nearly equal
representation from all groups. (See Section 3 Definitions 3.9 and 3.10 for
formal definitions). In a similar spirit, for individual fairness, one can aim
to provide the strongest possible guarantee simultaneously to all individuals
in terms of the probability of being matched. We refer to this as maxmin
individual fairness [Definition 3.8].

##  2 Related Work

Several allocation problems like resource allocation [37], kidney exchange
programs [26], school choice [6], candidate selection [15], summer internship
programs [3], and matching residents to hospitals [32] are modeled as matching
problems. [47] extensively examines preference-based matching in the stable
marriage and roommates problems, hospitals/residents matching, and the house
allocation problem. Since the people/items to be matched may belong to
different groups, bipartite matchings under various notions of group fairness
have been studied and their significance has been emphasized in literature
[20, 46, 21, 16, 56, 43, 10]. [4] survey the developments in the field of
matching with constraints, including those based on regions, diversity, multi-
dimensional capacities, and matroids. The fairness constraints are captured by
upper and lower bounds [40, 33], justified envy-freeness [6], or in terms of
proportion of the final matching size [15]. Historically, discriminated groups
in India are protected with vertical reservations implemented as set-asides,
and other disadvantaged groups are protected with horizontal reservations
implemented as minimum guarantees(lower bounds) [59].

In some applications, the items could belong to multiple groups as well. [58]
present a polynomial-time algorithm with an approximation ratio of
$\frac{1}{\Delta+1}$ where each item belongs to at most $\Delta$ laminar
families of groups per platform, and [51] show the NP-hardness of the problem
without a laminar structure. While both papers focus only on group-fairness
upper bounds, [45] primarily focus on proportional diversity constraints with
an emphasis on lower bounds in the general context. However, group fairness
constraints alone do not account for individual preferences. Our work aims to
introduce individual fairness considerations into the problem and explore both
upper and lower bounds for specific scenarios.

The notions of maxmin individual fairness, maxmin group fairness, and mindom
group fairness are motivated by existing literature. Maxmin individual
fairness, originally termed as the ”distributional maxmin fairness” framework
in [34], was further explored in group-fair ranking problems by [28]. Their
distribution is only over maximum matchings, and we extend this idea to a
distribution over maximum group-fair matchings and a stronger notion of
individual fairness. Maxmin group fairness is a natural extension of Maxmin
fairness, initially introduced as a network design objective by [13](Section
6.5.2) and extensively studied in various areas of networking [54, 35]. Mindom
group fairness has been studied in network load distribution [29],
transmission cost sharing [7], and other network applications [54]. This
concept of probabilistic individual fairness also has applications in fair-
ranking [28, 31] and graph-cut problems [22].

[57] study individual fairness in ranking under uncertainty, extending
fairness definitions by explicitly modeling incomplete information. Their
approach mirrors [53] but assumes a posterior distribution over candidates’
merits. Similarly, we assume that the individual and group fairness parameters
are given. They express a distribution $\pi$ over rankings as a bistochastic
matrix, where each entry denotes the probability of a candidate’s position
under $\pi$. They use an LP to maximize utility while enforcing fairness
constraints and ensure marginal probabilities form a doubly stochastic matrix.
The optimal solution is then decomposed as a distribution over rankings using
the Birkhoff-von Neumann algorithm [14]. Though we use a similar approach for
Theorems 3.5, 3.4 and 3.7, we have both group and individual fairness
constraints. Our marginal probabilities do not form a doubly stochastic
matrix, so we cannot use the Birkhoff-von Neumann decomposition [14] directly,
and hence need a different approach for Theorem 3.4. Similar to our group and
individual fairness constraints (Definitions 3.2 and 3.3), [31] address a
related problem in fair ranking, particularly addressing laminar set
structures using techniques akin to the Birkhoff-von Neumann decomposition.

Fairness constraints with bounds on the number of items with each attribute
are also studied in ranking and multi-winner voting [19, 17]. Among other
notions of fairness, [55] propose a fairness notion for ride-hailing platforms
that distributes fairness over time, ensuring benefits proportional to
drivers’ platform engagement duration. Kletti et al. [44] present an algorithm
for optimizing rankings to maximize consumer utility while minimizing
producer-side individual exposure unfairness. [28] explore maxmin fair
distributions in general search problems with group fairness constraints,
while [23] examine Rawlsian fairness(maxmin fairness) in online bipartite
matching, considering both group and individual fairness. [23] simultaneously
address two-sided fairness but treat group and individual fairness separately.
In contrast, we handle both individual and group fairness on the item side
within a single bipartite matching instance, which has not been explored in
the existing literature to the best of our knowledge.

Our solution fits into the best of both worlds (BoBW) fairness paradigm, which
is gaining attention in the fair allocation of indivisible items [5, 11, 27,
8]. In literature, popular target fairness properties have been envy-freeness,
envy-freeness up to one item [27, 8], proportionality, and proportionality up
to one item [5, 39, 61]. Other than these, [11] study truncated proportional
share. [27] showed that ex-ante envy-freeness (EF) and ex-post envy-freeness
up to one item (EF1) BoBW outcomes are achievable for any allocation problem
instance. [5] studied BoBW outcomes based on envy-based fairness in allocating
indivisible items to agents with additive valuations and weighted
entitlements. [11] approach BoBW fairness from a fair-share guarantee
perspective. While our target fairness properties are group fairness and
probabilistic individual fairness, our technique, in essence, resembles that
of [8], where a randomized EF allocation is first generated and then
decomposed as the convex combination of EF1 deterministic allocations.

Fairness constraints, with various notions of fairness, have been considered
in preference-based matchings, e.g. for kidney-exchange [26], for rank-
maximality and popularity [51], stability [40], stability under matroid
constraints [25], and in various settings of two-sided matching markets [12],
[52], [36].

##  3 Preliminaries

Our problem: The input instance consists of a bipartite graph denoted as
$G=(A\cup P,E)$. Here $A$ denotes the set of items and $P$ is the set of
platforms. There is an edge, $(a,p)\in E$ if $a$ can be assigned to $p$. The
items are grouped into possibly non-disjoint subsets
$A_{1},A_{2},\ldots,A_{\chi}$ for an integer $\chi\geq 1$ such that
$\cup_{h\in[\chi]}A_{h}=A$. Here $\chi$ denotes the total number of groups.
Let $|A|=n$, $|P|=m$, $\Delta$ denote the maximum number of distinct groups to
which any item belongs, and $N(v)$ denote the neighborhood of any node $v\in
A\cup P$. Each item $a\in A$ has a preference list $R_{a}$, which contains a
ranking of platforms, and let $R_{a,k}$ denote the set of top $k$ preferred
platforms of $a$.

We define the group fairness and individual fairness notions below, these
constraints are also part of the input.

######  Definition 3.1 (Group fairness).

Each platform, $p$, has upper bounds, $u_{p,h}$, for all $h\in[\chi]$ denoting
the maximum number of items from group $h$ that can be assigned to $p$. These
are referred to as group fairness constraints in this paper. For each
$h\in[\chi]$, let $E_{p,h}$ denote the set of edges $\\{(a,p):a\in A_{h}\\}$.
A matching $M\subseteq E$ is said to be group-fair if and only if

$|E_{p,h}\cap M|\leq u_{p,h}\text{ }\forall p\in P,h\in[\chi].$ (1)

This notion of group fairness is also known as Restricted Dominance,
introduced in [9].

######  Definition 3.2 (Strong group fairness).

Along with upper bounds, each platform, $p$, has lower bounds, $l_{p,h}$, for
all $h\in[\chi]$ denoting the minimum number of items from group $h$ that
should be assigned to $p$. A matching $M\subseteq E$ is said to be strong
group-fair if and only if

$l_{p,h}\leq|E_{p,h}\cap M|\leq u_{p,h}\text{ }\forall p\in P,h\in[\chi].$ (2)

This notion of group fairness encompasses Minority Protection, also introduced
in [9], along with Restricted Dominance.

######  Definition 3.3 (Probabilistic individual fairness).

In addition to the group fairness constraints, the input also contains
individual fairness parameters, $L_{a,k},U_{a,k}\in[0,1]$ for each item $a$
and $k\in[m]$. A distribution $\mathcal{D}$ on matchings in $G$ is
probabilistic individually fair if and only if $\forall a\in A,k\in[m]$

$\displaystyle L_{a,k}\leq\Pr_{M\sim\mathcal{D}}[\exists p\in R_{a,k}\textrm{
s.t. }(a,p)\in M]\leq U_{a,k}\text{ }$ (3)

It is easy to see how Equation 3 can capture the requirement that items are
matched to a high-ranking platform in their preference list with high
probability and a low-ranking platform in their preference list with low
probability. Our model allows users to set individual fairness constraints
based on their requirements.

Objective: Let $\mathcal{I}=(G,A_{1}\cdots
A_{\chi},\vec{l},\vec{u},\vec{L},\vec{U})$ denote an instance of our problem.
Our objective is to calculate a probabilistic individually fair distribution
over a set of group-fair matchings, aiming to maximize the expected matching
size when a matching is sampled from this distribution.

Note that our model provides a generic framework that accommodates various
fairness settings, elaborated in Section 3.2.

###  3.1 Results

We provide four different algorithms under different settings to compute a
distribution over matchings. The support of the distribution is of size
polynomial in the size of the instance, and is in fact of the same size as the
number of iterations in the algorithms. Below, we list some known hardness
results.

####  3.1.1 Known hardness results

Even without individual fairness constraints, finding a maximum size group-
fair matching [Definition 3.1] is NP-hard [51]. Additionally, when there is a
single platform and each item appears in at most $\Delta$ classes, the group
fairness problem with only upper bounds is NP-hard to approximate within a
factor of $\mathcal{O}(\frac{\log^{2}\Delta}{\Delta})$ [58].

When an item can belong to multiple groups, determining if a feasible solution
exists for group fairness constraints even with lower bounds alone is NP-hard
[45], making the computation of a strong group-fair matching [Definition 3.2]
NP-hard.

####  3.1.2 Algorithmic results

Our first contribution is an algorithm that computes a distribution over
group-fair matchings such that the individual fairness constraints are
approximately satisfied and the expected size of a matching is close to OPT.
Throughout the paper, OPTrepresents the maximum expected size of a group-fair
matching across all probabilistic individually fair distributions over such
matchings.

######  Theorem 3.4 ($O(\Delta\log n)$ bicriteria approximation (Informal
version of Theorem 4.1)).

For any $\epsilon>0$, there is a polynomial-time algorithm that outputs a
distribution over group-fair matchings with the following properties: The
expected size of a matching is at least $\frac{1}{f_{\epsilon}}\left({\sf
OPT}+\epsilon\right)$, where
$f_{\epsilon}=\mathcal{O}(\Delta\log(n/\epsilon))$, and the individual
fairness constraints are satisfied within additive and multiplicative factors
of at most $\epsilon$ and $\frac{1}{f_{\epsilon}}$ respectively. Here $\Delta$
denotes the maximum number of classes an item belongs to. The algorithm
reports infeasibility if no such distribution exists.

For a platform $p$, let $g_{p}$ denote the number of distinct groups that have
a non-empty intersection with $N(p)$, and let $g=max_{p\in P}g_{p}$. Next, we
present an algorithm where the approximation guarantees are dependent on $g$,
where each upper bound in the group fairness constraints is at least $g$.

######  Theorem 3.5 (Informal version of Theorem 6.1).

When all the group fairness upper bounds are at least $g$, there is a
polynomial-time algorithm that computes a distribution over group-fair
matchings, with the following properties: The expected size of a matching is
at least $\frac{{\sf OPT}}{2g}$, and the individual fairness constraints are
satisfied up to a multiplicative factor of at most $\frac{1}{2g}$. The
algorithm reports infeasibility if no such distribution exists.

Our next algorithm improves the multiplicative factor for violation of
individual fairness constraints, and also the expected size of a matching, at
the cost of an additive violation of group fairness constraints.

######  Theorem 3.6 (Informal version of Theorem 6.8).

When all the group fairness upper bounds are at least $g$, there is a
polynomial-time algorithm that computes a distribution over matchings, with
the following properties: The expected size of a matching is at least
$\frac{{\sf OPT}}{g}$, the matchings satisfy group fairness up to an additive
factor of at most $\Delta$, and the individual fairness constraints up to a
multiplicative factor of at most $\frac{1}{g}$. The algorithm reports
infeasibility if no such distribution exists.

Table 1 shows a comparison of the results in Theorem 3.4, Theorem 3.5, and
Theorem 3.6. We give a polynomial-time exact algorithm for strong group
fairness, when the groups are disjoint.

######  Theorem 3.7.

Given an instance of our problem where each item belongs to exactly one group,
there is a polynomial-time algorithm that either computes a probabilistic
individually fair distribution over a set of strong group-fair matchings or
reports infeasibility if no such distribution exists.

|  Theorem 3.4(Algorithm 1) | Theorem 3.5 | Theorem 3.6
---|---|---|---
Size-approximation | $\frac{1}{f_{\epsilon}}\left({\sf OPT}+\epsilon\right)$ | $\frac{{\sf OPT}}{2g}$ | $\frac{{\sf OPT}}{g}$
Group Fairness Violation | None | None |  $\Delta$-additive
Individual Fairness Violation |  $\frac{1}{f_{\epsilon}}$-multiplicative, $\frac{\epsilon}{f_{\epsilon}}$-additive |  $\frac{1}{2g}$-multiplicative |  $\frac{1}{g}$-multiplicative

Table 1: Comparison of Approximation Algorithms.
$f_{\epsilon}=\mathcal{O}(\Delta\log(n/\epsilon)$)

.

###  3.2 Extension to Other Fairness Notions

Our results can be extended to accommodate other fairness notions mentioned
below.

######  Definition 3.8 (Maxmin individual fairness).

Let $\mathcal{D}[a]$ denote $\Pr_{M\sim\mathcal{D}}[\exists p\in P\text{ s.t
}(a,p)\in M]$. A distribution, $\mathcal{D}$, over matchings is Maxmin
individually fair if for all distributions $\mathcal{F}$ over matchings and
all $a\in A$,

$\displaystyle\mathcal{F}[a]>\mathcal{D}[a]\implies\exists a^{\prime}\in
A\text{ s.t }\mathcal{D}[a^{\prime}]>\mathcal{F}[a^{\prime}]$

We refer to the goal of maximizing the representation of the worst-off groups
as maxmin group fairness, defined below.

######  Definition 3.9 (Maxmin group fairness).

Let $X^{M}_{h,p}$ denote the total number of items matched under a feasible
matching, $M\subseteq E$, from group $h$ to platform $p$. The matching $M$ is
said to be maxmin group-fair if, for any other feasible matching $M^{\prime}$,
if $\exists p\in P,h\in[\chi]$ such that $X^{M^{\prime}}_{h,p}>X^{M}_{h,p}$,
then there is some $p^{\prime}\in P$, $h^{\prime}\in[\chi]$ with
$X^{M}_{h,p}\geq X^{M}_{h^{\prime},p^{\prime}}$ and
$X^{M}_{h^{\prime},p^{\prime}}>X^{M^{\prime}}_{h^{\prime},p^{\prime}}$. Here
at least $p^{\prime}\neq p$, or $h^{\prime}\neq h$.

In mindom group fairness, defined below, the goal is to minimize the
representation of the most dominant groups. This is a dual to maxmin group
fairness

######  Definition 3.10 (Mindom group fairness).

Let $X^{M}_{h,p}$ denote the total number of items matched under a feasible
matching, $M\subseteq E$, from group $h$ to platform $p$. $M$ is said to be
mindom group-fair if, for any other feasible matching $M^{\prime}$, if
$\exists p\in P,h\in[\chi]$ such that $X^{M^{\prime}}_{h,p}<X^{M}_{h,p}$, then
there is some $p^{\prime}\in P$, $h^{\prime}\in[\chi]$ with $X^{M}_{h,p}\leq
X^{M}_{h^{\prime},p^{\prime}}$ and
$X^{M}_{h^{\prime},p^{\prime}}<X^{M^{\prime}}_{h^{\prime},p^{\prime}}$. Here
at least $p^{\prime}\neq p$, or $h^{\prime}\neq h$.

####  3.2.1 Extension of Results

######  Theorem 3.11.

Given a bipartite graph with disjoint groups and a lower bound on the expected
matching size, our framework and the polynomial-time algorithm from Theorem
3.7 can be extended to compute the following:

  1. 1.

A probabilistic individually fair distribution over a set of maxmin or mindom
group-fair matchings, with probabilistic individual fairness constraints.

  2. 2.

A maxmin individually fair distribution over strong group-fair matchings.

######  Theorem 3.12.

Given a bipartite graph and a lower bound on the expected matching size, say
$lb$, our framework and the polynomial-time algorithm from Theorems 3.4, 3.5
and 3.6 can be extended to compute the following:

  1. 1.

A distribution over mindom group-fair or group-fair matchings, ensuring an
expected matching size of at least
$\frac{1}{f_{\epsilon}}\left(lb+\epsilon\right)$, with $f_{\epsilon}$ and the
violation of probabilistic individual fairness or maxmin individual fairness
as in Theorem 3.4.

  2. 2.

A distribution over mindom group-fair or group-fair matchings, guaranteeing an
expected matching size of at least $\frac{lb}{2g}$, and a violation of
probabilistic individual constraints or maxmin individual fairness by at most
$\frac{1}{2g}$.

  3. 3.

A distribution over matchings, guaranteeing an expected matching size of at
least $\frac{lb}{g}$, and a violation of probabilistic individual constraints
or maxmin individual fairness by at most $\frac{1}{g}$. The mindom group-
fairness or group-fairness is violated by an additive factor of at most
$\Delta$.

The proof of Theorems 3.11 and 3.12, and details of how to extend our results
to these settings are in Appendix B.

##  4 $O(\Delta\log n)$ bicriteria approximation algorithm

In this section, our focus is on computing a probabilistic individually fair
distribution over an instance of a bipartite graph $G=(A\cup P,E)$, where any
arbitrary item, $a\in A$, can belong to at most $\Delta$ distinct groups. Our
objective is to maximize the expected size of any matching sampled from this
distribution while ensuring that the matching satisfies group fairness
constraints. Within this context, we design a polynomial-time algorithm that
provides an approximation factor dependent on $O(\Delta)$ and prove our main
result, Theorem 3.4, formally stated below.

######  Theorem 4.1 (Formal version of Theorem 3.4).

Given any $\epsilon>0$, and an instance of our problem where each item can
belong to at most $\Delta$ groups, there is a polynomial-time algorithm that
computes a distribution $\mathcal{D}$ over a set of group-fair matchings such
that the expected size is at least
$\frac{1}{f_{\epsilon}}\left(OPT+\epsilon\right)$ where
$f_{\epsilon}=\mathcal{O}(\Delta\log(n/\epsilon))$ and $n$ is the total number
of items. Given the individual fairness parameters, $L_{a,k},U_{a,k}\in[0,1]$,
for each item $a\in A$ and subset $R_{a,k}$ $\forall$ $k\in[n]$,

$\displaystyle\frac{1}{f_{\epsilon}}\left(L_{a,k}-\epsilon\right)\leq\Pr_{M\sim\mathcal{D}}[\exists
p\in R_{a,k}\textrm{ s.t. }(a,p)\in M]$
$\displaystyle\leq\frac{1}{f_{\epsilon}}\left(U_{a,k}+\epsilon\right).$

Note that if we set $\epsilon=\displaystyle\min_{a\in
A,k\in[n]}\frac{L_{a,k}}{2}$ in Theorem 4.1, then $\forall a\in A,k\in[n]$,

$\displaystyle\frac{L_{a,k}}{2f_{\epsilon}}\leq\frac{1}{f_{\epsilon}}(L_{a,k}-\epsilon)\leq\Pr_{M\sim\mathcal{D}}[\exists
p\in R_{a,k}\textrm{ s.t. }(a,p)\in M]$
$\displaystyle\leq\frac{1}{f_{\epsilon}}(U_{a,k}+\epsilon)\leq\frac{3U_{a,k}}{2f_{\epsilon}}$

Therefore, we only get a multiplicative violation of individual fairness for
$\epsilon=\displaystyle\min_{a\in A,k\in[n]}\frac{L_{a,k}}{2}$.

###  4.1 Model Formulation

We begin by formulating a Linear Programming (LP) model for our problem,
specifically tailored to address Theorem 4.1. A more extensive LP formulation,
applicable to all our theorems, including Theorem 3.7, which integrates
additional lower group fairness constraints, is detailed in Section 5, 5.1.
Since items are assumed to be indivisible, we assume that the group fairness
bounds are integers.

######  LP 4.2.

$\displaystyle\max\sum_{(a,p)\in E}x_{ap}$ (4) such that $\displaystyle
L_{a,k}\leq\sum_{p\in R_{a,k}}x_{ap}\leq U_{a,k},$ $\displaystyle\forall a\in
A,\forall k\in[m]$ (5) $\displaystyle\sum_{a\in A_{h}}x_{ap}\leq u_{p,h},$
$\displaystyle\forall p\in P,\forall h\in[\chi]$ (6) $\displaystyle 0\leq
x_{ap}\leq 1$ $\displaystyle\forall a\in A,\;\forall p\in P$ (7)

4.2 is a relaxation of the Integer Linear Programming formulation of the
problem addressing group and individual fairness constraints. In the Integer
Programming version, $x_{ap}=1$ iff the edge connecting item $a$ to the
platform $p$ is picked in the matching and $0$ otherwise. Constraints 5 and 6
capture the individual fairness and group fairness requirements, respectively.

Before delving into the algorithm, it is essential to note that 4.2 may become
infeasible if the fairness constraints are inconsistent. This is possible due
to the individual fairness constraints. To address this, one solution is to
introduce a variable to calculate the smallest multiplicative relaxation of
the fairness constraints required to ensure the feasibility of 4.2. This
method is detailed in the section titled ‘Dealing with infeasibility’ (Section
A.1).

###  4.2 Algorithm

Input : $\mathcal{I}$, $\epsilon$

Output : Distribution over matchings satisfying the guarantees in Theorem 4.1.

1 Solve 4.2 on $G$ with the parameters in the input instance, $\mathcal{I}$,
and store the result in $x$.

2 $i\leftarrow 0,\alpha^{(0)}\leftarrow 0,G^{(0)}\leftarrow
G,x^{(0)}\leftarrow x,sum\leftarrow 0,\mathcal{D}\leftarrow\phi$

3 while  _$\lVert x^{(i)}\rVert_{1}\geq\epsilon$_ do

4 $i\leftarrow i+1,G^{(i)}\leftarrow
G^{(i-1)}-\\{(a,p)\;\lvert\;x^{(i-1)}_{ap}=0\\}$

5 Greedily find a Maximal Matching $M^{(i)}$ in $G^{(i)}$ such that
constraints $(\ref{LP-20})$ are not violated.

6 $\alpha^{(i)}\leftarrow\min_{(a,p)\in M^{(i)}}\\{x^{(i-1)}_{ap}\\}$

7 $sum\leftarrow
sum+\alpha^{(i)},\mathcal{D}\leftarrow\mathcal{D}\cup(M^{(i)},\alpha^{(i)})$

8 $x^{(i)}\leftarrow x^{(i-1)}-\alpha^{(i)}\cdot M^{(i)}$

9

10 end while

11for  _$D^{(i)}\in\mathcal{D}$_ do

12 $D^{(i)}\leftarrow(M^{(i)},\frac{\alpha^{(i)}}{sum})$

13 end for

14if  _$\mathcal{D}==\phi$_ then

15 Return ‘Infeasible’

16 end if

Return $\mathcal{D}$

Algorithm 1 $\mathcal{O}(\Delta\log
n)$-BicriteriaApprox$(\mathcal{I}=(G,A_{1}\cdots
A_{\chi},\vec{l},\vec{u},\vec{L},\vec{U}),\epsilon)$

First, we informally describe our algorithm (Algorithm 1) and the intuition
behind the same. The key idea in our approach is to express a feasible
solution, $x$, of 4.2 as a convex combination of integer group-fair matchings.
Achieving this allows us to satisfy our probabilistic individual fairness
constraints by sampling from the probability distribution corresponding to
this convex combination. If the groups are not disjoint, as is the case in our
problem, then it is not known whether such a convex combination exists.
Therefore, we show that $\frac{x-x^{{\dagger}}}{f}$ can be written as a convex
combination of integer group-fair matchings, where $\lVert
x^{{\dagger}}\rVert_{1}<\epsilon$ for some $\epsilon>0$ and
$f=\mathcal{O}(\Delta\log n)$. Algorithm 1 computes such a convex combination.

The algorithm begins with a feasible solution of 4.2 solved on the input
instance $\mathcal{I}$, denoted by variable $x$. At round $i$ of the while
loop (step 1), $\mathbf{G^{(i)}}$ denotes the state of the input graph after
the $i^{th}$ iteration. It is a graph where edges with a corresponding zero
value in $x^{(i-1)}$ are discarded in Step 1. $\mathbf{M^{(i)}}$ represents a
group-fair maximal matching computed on $G^{(i)}$ in step 1, and
$\mathbf{x^{(i)}}$ denotes the state of $x$ after $i$ rounds. It is the
residue after a scaled down $M^{(i)}$ is “deducted” from $x^{(i-1)}$ in step
1. $\mathbf{\alpha^{(i)}}$, denoting the minimum non-zero value associated
with any edge in $x^{(i-1)}$ (step 1), is used to scale down $M^{(i)}$ before
“deducting” it from $x^{(i-1)}$ to ensure non-negative values in $x^{(i)}$.
The algorithm terminates when the value of $||x^{(i)}||_{1}$ goes below
$\epsilon$. $\mathcal{D}$ returned by Algorithm 1 consists of tuples, and each
tuple consists of a group-fair matching because $M^{(i)}$ is group-fair and
its corresponding coefficient, $\frac{\alpha^{(i)}}{sum}$. If the loop
terminates after $k$ rounds, $sum=\sum_{i=1}^{k}\alpha^{(i)}$. Clearly,
$\sum_{i=1}^{k}\frac{\alpha^{(i)}}{sum}=1$, therefore, $\mathcal{D}$ is a
distribution over group-fair matchings.

One key intuition behind Algorithm 1 is that in every iteration, we start with
a solution, $x^{(i-1)}$, that satisfies group-fairness constraints (Equation
6), which allows us to greedily compute a group-fair matching $M^{(i)}$ in the
support of $x^{(i-1)}$ (step 1 of Algorithm 1). This ensures that step 1
always returns a non-empty group-fair matching as long as $x^{(i-1)}$ has non-
zero entries.

Next, we provide the proof of Theorem 4.1 using Algorithm 1.

###  4.3 Proof of Theorem 4.1

The proof of Theorem 4.1 is based on a careful analysis of our simple (and
fast) greedy algorithm (Algorithm 1). We first construct an LP formulation for
our problem, concentrating solely on group-fairness constraints [Definition
3.1], excluding individual fairness constraints. This LP, denoted as 4.3,
along with its dual counterpart 4.4, is introduced to facilitate our analysis.
This choice is made because, instead of grounding our analysis on 4.2, it
suffices to focus on 4.3. 4.5 provides clarification on why that is.

######  LP 4.3.

$\displaystyle\max\sum_{(a,p)\in E}x_{ap}$ (8) such that
$\displaystyle\sum_{a\in A_{h}}x_{ap}\leq u_{p,h}\;,$ $\displaystyle\forall
h\in[\chi],\;\forall p\in P$ (9) $\displaystyle 0\leq x_{ap}\leq 1$
$\displaystyle\forall(a,p)\in E$ (10)

######  LP 4.4.

$\displaystyle\min\sum_{p\in P}\sum_{h\in[\chi]}u_{p,h}w_{p,h}+\sum_{(a,p)\in
E}y_{ap}$ (11) such that $\displaystyle 1\leq\sum_{h:a\in
A_{h}}w_{p,h}+y_{ap}\qquad\forall(a,p)\in E$ (12)

We show that the size of the matching $M^{(i)}$, in the $i^{th}$ round of
Algorithm 1, is at least $\frac{\lVert x^{(i-1)}\rVert_{1}}{\Delta+1}$ using
dual fitting analysis technique [62, 60, 41] in Lemma 4.7. We update the LP
solution to $x^{(i)}$ by “removing” $\alpha^{(i)}M^{(i)}$ from $x^{(i-1)}$
(step 1 of Algorithm 1). $\alpha^{(i)}$ is the largest possible value such
that the remaining LP solution is still a feasible solution of 4.3 after step
1. Therefore, if a “large” mass of the LP solution remains in the $i^{th}$
iteration, i.e., $\lVert x^{(i-1)}\rVert_{1}$ is large, then we make “large”
progress in the current iteration. This can essentially be used to show that
$\sum_{i=1}^{k}\alpha^{(i)}$ is bounded by
$f_{\epsilon}=2(\Delta+1)(\log(n/\epsilon)+1)$ when $\lVert
x^{(i)}\rVert_{1}<\epsilon$ (Lemma 4.11). Here, $k$ is the total number of
iterations by Algorithm 1. Finally, setting
$\hat{x}=\frac{x-x^{(k)}}{f_{\epsilon}}$, $t=f_{\epsilon}$, and
$\delta=\frac{\epsilon}{f_{\epsilon}}$ in Lemma 4.12, proves the approximation
guarantee on probabilistic individual fairness given by Theorem 4.1.

We first prove that any greedy maximal matching computed in step 1 of
Algorithm 1 is a $(\Delta+1)$-approximation of any feasible solution of 4.3
using dual fitting analysis technique in Lemmas 4.6 and 4.7. First, let us
look at the following observation.

######  Observation 4.5.

Any feasible solution of LP 4.3 augmented with constraint 5 is also a feasible
solution of LP 4.3

######  Lemma 4.6.

Let $M$ be a greedy maximal matching computed in step 1 of Algorithm 1. Let
$y$ be an ordered set such that $\forall(a,p)\in E$, $y_{ap}$ is set to $1$
iff $M_{ap}=1$, and $w$ be an ordered set such that $\forall p\in
P,h\in[\chi]$, $w_{p,h}$ is set to $1$ iff $\sum_{a\in A_{h}}M_{ap}=u_{p,h}$.
Then, $y$ and $w$ are a feasible solution of 4.4.

###### Proof.

Let us fix an arbitrary edge, say $(a,p)\in E$. If $M_{ap}=1$, $y_{ap}=1$ by
definition. Therefore constraint $(\ref{LP-19})$ is satisfied. Let $C_{ap}$
denote a set of groups such that $a\in A_{h}$ and $A_{h}\cap N(p)\neq\phi$,
$\forall h\in C_{ap}$, where $N(p)$ is the neighborhood of platform $p\in P$.
If $M_{ap}=0$, we will show that there exists at least one group, say
$h^{\prime}\in C_{ap}$, such that $w_{p,h^{\prime}}=1$. Suppose $\forall h\in
C_{ap}$, $w_{p,h}=0$. This implies that $\forall h\in C_{ap}$, $\sum_{b\in
A_{h}}M_{bp}<u_{p,h}$, by definition of $w$, therefore the edge, $(a,p)$ can
be included in the matching without violating the group fairness constraint 9,
which is a contradiction since $x$ is a maximal matching. Hence, there exists
at least one group, say $h^{\prime}\in C_{ap}$ such that $\sum_{a\in
A_{h^{\prime}}}M_{ap}=u_{p,h^{\prime}}$, which in turn implies that there
exists at least one group, $h^{\prime}\in C_{ap}$, such that
$w_{p,h^{\prime}}=1$. Therefore, constraint $(\ref{LP-19})$ is not violated
and $y$ and $w$ are a feasible solution to 4.4. ∎

######  Lemma 4.7.

If $M$ is a greedy maximal matching computed in step 1 of Algorithm 1, then
$\displaystyle\sum_{(a,p)\in E}M_{ap}\geq\frac{\sum_{(a,p)\in
E}\Psi_{ap}}{\Delta+1}$, where $\Psi$ is any feasible solution of 4.2.

###### Proof.

Let $y$ be an ordered set such that $\forall(a,p)\in E$, $y_{ap}$ is set to
$1$ iff $M_{ap}=1$, and $w$ be an ordered set such that $\forall p\in
P,h\in[\chi]$, $w_{p,h}$ is set to $1$ iff $\sum_{a\in A_{h}}M_{ap}=u_{p,h}$.
From Lemma 4.6, we know that $y$ and $w$ are a feasible solution of 4.4. Let
$\hat{\psi}$ be the dual objective function evaluated at $y$ and $w$ and
$\psi$ be the primal objective function evaluated at $M$. Note that by
definition of $y$, $\sum_{(a,p)\in E}y_{ap}$ is equal to the number of edges
in the maximal matching, which is $\psi$. Since $w_{p,h}$ is set to $1$ iff
$\sum_{a\in A_{h}}M_{ap}=u_{p,h}$,

$\sum_{p\in P}\sum_{h\in[\chi]}u_{p,h}w_{p,h}=\sum_{p\in
P}\sum_{h\in[\chi]}\sum_{a\in A_{h}}M_{ap}.$

Since any item, say $a\in A$, can belong to at most $\Delta$ groups, any edge,
$(a,p)$, such that $x_{ap}=1$, can contribute to at most $\Delta$ many tight
upper bounds, therefore,

$\sum_{p\in P}\sum_{h\in[\chi]}\sum_{a\in A_{h}}M_{ap}\leq\Delta\psi.$

Hence,

$\hat{\psi}=\sum_{p\in
P}\sum_{h\in[\chi]}u_{p,h}w_{p,h}+\psi\leq\Delta\psi+\psi=(\Delta+1)\psi.$

Let $\psi^{*}$ and $\hat{\psi}^{*}$ be the optimal objective costs of 4.3 and
4.4, respectively, since 4.3 is a maximization, we get

$(\Delta+1)\psi\geq\hat{\psi}\geq\hat{\psi}^{*}\geq\psi^{*}\implies\sum_{(a,p)\in
E}M_{ap}\geq\frac{\psi^{*}}{(\Delta+1)}$

By 4.5, $\psi^{*}\geq\sum_{(a,p)\in E}\Psi_{ap}$, therefore,

$\sum_{(a,p)\in E}M_{ap}\geq\frac{\sum_{(a,p)\in E}\Psi_{ap}}{(\Delta+1)}$

∎

In the rest of the section, $x^{(i)}$ denotes the state of $x^{(0)}$ after the
$i^{th}$ round of the while loop in Algorithm 1, where $x^{(0)}$ is an optimal
solution of 4.2 (Step 1), $M^{(i)}$ denotes the greedy maximal group-fair
matching computed in step 1 of the $i^{th}$ round and $\alpha^{(i)}$ denotes
the coefficient being computed in step 1 of the $i^{th}$ round.

######  Lemma 4.8.

The run-time of Algorithm 1 is polynomial in the number of nodes, $|V|$, and
the number of edges, $|E|$, of the input graph, $G$.

###### Proof.

Let $i$ denote an arbitrary iteration of the while loop in Algorithm 1. Since
$\alpha^{(i)}=\min_{(a,p)\in M^{(i)}}x^{(i-1)}_{ap}$, as seen in step 1, at
least one edge is removed from the support of the solution, in each iteration.
Hence the norm can go to zero in $|E|=O(|V|^{2})$ iterations, and since the
algorithm exits once $\lVert x\rVert_{1}<\epsilon$, it runs for at most $|E|$
rounds, therefore, the while loop in Algorithm 1 terminates in $O(|V|^{2})$
time.

The LP in step 1 (4.2) has $|E|$ variables and $2nm+\chi m$ constraints where
$\chi$ is the total number of groups, $n$ is the total number of items and $m$
is the total number platforms in the input instance, $\mathcal{I}$. $|V|=n+m$,
therefore, the runtime of 4.2 and, as a result, that of Algorithm 1 is
polynomial in the number of nodes, $|V|$, and the number of edges, $|E|$, of
the input graph, $G$. ∎

######  Observation 4.9.

Let Algorithm 1 terminate in $k$ iteration, then, $\forall
i\in\\{0\\}\cup[k]$, $x_{ap}^{(i)}\geq 0$, $\forall(a,p)\in E$.

###### Proof.

We will use induction to show this. For the base case, $i=0$, since $x$ is a
feasible solution of LP 4.2, $x_{ap}^{(0)}=x_{ap}\geq 0$, $\forall(a,p)\in E$
because of constraint 7. For the induction step let us assume that
$x_{ap}^{(i-1)}\geq 0$, $\forall(a,p)\in E$. Since no edge, say $(a,p)$, such
that $x_{ap}^{(i-1)}=0$, will be picked in the maximal matching, $M^{(i)}$,
$x_{ap}^{(i)}=x_{ap}^{(i-1)}-\min_{(a,p)\in M^{(i)}}\\{x_{ap}^{(i-1)}\\}$, iff
$x_{ap}^{(i-1)}\neq 0$. Therefore, $x_{ap}^{(i)}\geq 0$, $\forall(a,p)\in E$.
∎

######  Claim 4.10.

Let Algorithm 1 terminate in $k$ iterations, then, $\forall i\in[k-1]$,

$\Big{\lVert}\sum_{j=i}^{k}\alpha^{(j)}M^{(j)}\Big{\rVert}_{1}\leq\big{\lVert}x^{(i-1)}\big{\rVert}_{1}$

###### Proof.

If Algorithm 1 terminates in $k$ rounds, from step 1 of Algorithm 1 we know
that $\forall(a,p)\in E$, either $x_{ap}^{(k)}=0$ or

$x_{ap}^{(k)}=x_{ap}^{(k-1)}-\alpha^{(k)}M_{ap}^{(k)}$ (13)

Let us consider an integer, $i\leq k-1$, then, recursively replacing
$x_{ap}^{(k-1)}$ on the RHS of Equation 13 until the index reaches $i-1$, we
have

$x_{ap}^{(k)}=x_{ap}^{(i-1)}-\sum_{j=i}^{k}\alpha^{(j)}M_{ap}^{(j)}$

Since $x_{ap}^{(k)}\geq 0$, $\forall(a,p)\in E$, from 4.9, $\forall(a,p)\in
E$, $\sum_{j=i}^{k}\alpha^{(j)}M_{ap}^{(j)}\leq x_{ap}^{(i-1)}$. Therefore,
$\forall i\in[k-1]$,

$\Big{\lVert}\sum_{j=i}^{k}\alpha^{(j)}M^{(j)}\Big{\rVert}_{1}\leq\big{\lVert}x^{(i-1)}\big{\rVert}_{1}$

∎

######  Lemma 4.11.

Let $i_{c}$ denote the first iteration of the while loop in Algorithm 1 such
that $\big{\lVert}x-\sum_{j=1}^{i_{c}}\alpha^{(j)}\cdot
M^{(j)}\big{\rVert}_{1}<\frac{\lVert x\rVert_{1}}{2^{c}}$, then
$\sum_{j=1}^{i_{c}}\alpha^{(j)}\leq 2c(\Delta+1)$.

###### Proof.

Let Algorithm 1 terminate in $k$ rounds. Since $\forall i\in\\{0\\}\cup[k]$,
$x^{(i)}_{ap}\geq 0$ $\forall(a,p)\in E$, from 4.9, it is easy to see that
$\alpha^{(i)}=\min_{(a,p)\in M^{(i)}}\\{x_{ap}^{(i-1)}\\}>0$, $\forall
i\in[k]$. Hence $\sum_{a\in A_{h}}x^{(i)}_{ap}\leq u_{p,h}$ $\forall
h\in[\chi],\forall p\in P$, and $x^{(i)}$ is a feasible solution of 4.3.
Therefore, using Lemma 4.7, we have

$\lVert
M^{(i)}\rVert_{1}\geq\frac{\big{\lVert}x-\sum_{j=1}^{i-1}\alpha^{(j)}\cdot
M^{(j)}\big{\rVert}_{1}}{\Delta+1}$ (14)

Now, we will prove the Lemma by induction on $c$. Let’s first look at the base
case where $c=1$. By definition,

$\Big{\lVert}x-\sum_{j=1}^{i_{1}}\alpha^{(j)}\cdot
M^{(j)}\Big{\rVert}_{1}<\frac{\big{\lVert}x\big{\rVert}_{1}}{2}$

Since, $\forall j\leq i_{1}$, $\lVert x^{(j)}\rVert_{1}\geq\frac{\lVert
x\rVert_{1}}{2}$, from Equation 14 we have $\lVert
M^{(j)}\rVert_{1}\geq\frac{\lVert x^{(j)}\rVert_{1}}{\Delta+1}\geq\frac{\lVert
x\rVert_{1}}{2(\Delta+1)}$, $\forall j\leq i_{1}$. From 4.10, we know that
$\big{\lVert}\sum_{j=1}^{k}\alpha^{(j)}\cdot M^{(j)}\big{\rVert}_{1}\leq\lVert
x^{(0)}\rVert_{1}=\lVert x\rVert_{1}$. Since $i_{1}\leq k$,
$\lVert\sum_{j=1}^{i_{1}}\alpha^{(j)}\cdot M^{(j)}\rVert_{1}\leq\lVert
x\rVert_{1}$. Therefore,

$\lVert x\rVert_{1}\geq\Big{\lVert}\sum_{j=1}^{i_{1}}\alpha^{(j)}\cdot
M^{(j)}\Big{\rVert}_{1}\geq\sum_{j=1}^{i_{1}}\alpha^{(j)}\cdot\frac{\lVert
x\rVert_{1}}{2(\Delta+1)}$ $\implies\sum_{j=1}^{i_{1}}\alpha^{(j)}\leq
2(\Delta+1)$ (15)

For the induction step, let us assume that for some iteration $i_{c-1}$,

$\sum_{j=1}^{i_{c-1}}\alpha^{(j)}\leq 2(c-1)(\Delta+1)$ (16)

By definition, $\lVert x-\sum_{j=1}^{i_{c}}\alpha^{(j)}\cdot
M^{(j)}\rVert_{1}<\frac{\lVert x\rVert_{1}}{2^{c}}$, therefore, $\forall j\leq
i_{c}$, $\lVert x^{(j)}\rVert_{1}\geq\frac{\lVert x\rVert_{1}}{2^{c}}$. From
Equation 14, we get $\forall j\leq i_{c}$, $\lVert
M^{(j)}\rVert_{1}\geq\frac{\lVert x^{(j)}\rVert_{1}}{\Delta+1}\geq\frac{\lVert
x\rVert_{1}}{2^{c}(\Delta+1)}$. Therefore,

$\Big{\lVert}\sum_{j=i_{c-1}+1}^{i_{c}}\alpha^{(j)}\cdot
M^{(j)}\Big{\rVert}_{1}\geq\sum_{j=i_{c-1+1}}^{i_{c}}\alpha^{(j)}\cdot\frac{\lVert
x\rVert_{1}}{2^{c}(\Delta+1)}$ (17)

From 4.10, we know that $\big{\lVert}\sum_{j=i_{c-1}+1}^{k}\alpha^{(j)}\cdot
M^{(j)}\big{\rVert}_{1}\leq\lVert x^{(i_{c-1})}\rVert_{1}$. Since, $i_{c}\leq
k$,

$\displaystyle\Big{\lVert}\sum_{j=i_{c-1}+1}^{i_{c}}\alpha^{(j)}\cdot
M^{(j)}\Big{\rVert}_{1}\leq\lVert x^{(i_{c-1})}\rVert_{1}$
$\displaystyle=\Big{\lVert}x-\sum_{j=1}^{i_{c-1}}\alpha^{(j)}M^{(j)}\Big{\rVert}_{1}<\frac{\lVert
x\rVert_{1}}{2^{c-1}}.$

Therefore, using Equation 17, we have $\frac{\lVert
x\rVert_{1}}{2^{c-1}}>\sum_{j=i_{c-1}+1}^{i_{c}}\alpha^{(j)}\cdot\frac{\lVert
x\rVert_{1}}{2^{c}(\Delta+1)}$, hence,

$\sum_{j=i_{c-1}+1}^{i_{c}}\alpha^{(j)}<2(\Delta+1)$ (18)

Combining Equation 16 and Equation 18,

$\displaystyle\sum_{j=1}^{i_{c}}\alpha^{(j)}=\sum_{j=1}^{i_{c-1}}\alpha^{(j)}+\sum_{j=i_{c-1}+1}^{i_{c}}\alpha^{(j)}$
$\displaystyle<2(c-1)(\Delta+1)+2(\Delta+1)=2c(\Delta+1)$

∎

###### Proof.

Proof of Theorem 4.1 We know that each matching in the distribution is group-
fair because, in each iteration, the matching being computed in step 1 is a
group-fair maximal matching. Let $x^{(i)}$ be the state of $x$ after $i$
rounds of the loop in Algorithm 1. Let $M^{(i)}$ and $\alpha^{(i)}$ be the
greedy maximal matching and it’s coefficient being calculated in the $i^{th}$
round of the loop in Algorithm 1. Let Algorithm 1 terminate after $k$
iterations, then
$x^{(k)}=x-\displaystyle\sum_{\begin{subarray}{c}(M^{(i)},\alpha^{(i)})\in\mathcal{D}\end{subarray}}\alpha^{(i)}M^{(i)}$.
Therefore,

$\displaystyle
x-x^{(k)}=\displaystyle\sum_{\begin{subarray}{c}(M^{(i)},\alpha^{(i)})\in\mathcal{D}\end{subarray}}\alpha^{(i)}M^{(i)}\implies\frac{x-x^{(k)}}{\sum_{i=1}^{k}\alpha^{(i)}}$
$\displaystyle=\displaystyle\sum_{\begin{subarray}{c}(M^{(i)},\alpha^{(i)})\in\mathcal{D}\end{subarray}}\frac{\alpha^{(i)}}{\sum_{i=1}^{k}\alpha^{(i)}}M^{(i)}$

In other words, $\frac{x-x^{(k)}}{\sum_{i=1}^{k}\alpha^{(i)}}$ can be written
as a convex combination of group-fair greedy maximal matchings.

We will first find an upper bound for $\sum_{i=1}^{k}\alpha^{(i)}$. Let
$c^{\prime}$ be such that $\frac{\lVert
x\rVert_{1}}{2^{c^{\prime}}}<\epsilon$, by Lemma 4.11,

$\sum_{j=1}^{i_{c^{\prime}}}\alpha^{(j)}\leq 2c^{\prime}(\Delta+1).$

Since $\lVert x\rVert_{1}\leq n$, setting $\lVert x\rVert_{1}=n$, we have
$\frac{n}{2^{c^{\prime}}}<\epsilon$. Setting $c^{\prime}=\log(n/\epsilon)+1$,
we have

$\sum_{i=1}^{c^{\prime}}\alpha^{(i)}<2(\Delta+1)(\log(n/\epsilon)+1).$

Let $f_{\epsilon}=2(\Delta+1)(\log(n/\epsilon)+1)$, then
$\frac{x-x^{(k)}}{f_{\epsilon}}$ can be written as a convex combination of
group-fair integer matchings. Setting
$\hat{x}=\frac{x-x^{(k)}}{f_{\epsilon}}$, $t=f_{\epsilon}$, and
$\delta=\frac{\epsilon}{f_{\epsilon}}$ in Lemma 4.12, we have for each item
$a\in A$ and subset $R_{a,k}$ $\forall$ $k\in[m]$,

$\displaystyle\frac{1}{f_{\epsilon}}\left(L_{a,k}-\epsilon\right)\leq\Pr_{M\sim\mathcal{D}}[\exists
p\in R_{a,k}\textrm{ s.t. }(a,p)\in M]$
$\displaystyle\leq\frac{1}{f_{\epsilon}}\left(U_{a,k}+\epsilon\right).$

The run time has been shown to be polynomial in Lemma 4.8. This proves the
theorem. ∎

Now we prove Lemma 4.12, stated below. We use Lemma 4.12 to prove the
individual fairness guarantees provided not just in Theorem 4.1 but also in
the rest of the theorems.

######  Lemma 4.12.

Let us consider a set of tuples,
$\mathcal{D}=\\{(M^{(i)},\beta^{(i)})\\}_{i\in[k]}$, where $M^{(i)}$ is an
integer matching and $\beta^{(i)}$ is a scalar, $\forall i\in[k]$, where
$k\in\mathbb{Z}$. Let $\hat{x}=\sum_{i=1}^{k}\beta^{(i)}M^{(i)}$ such that
$\sum_{i=1}^{k}\beta^{(i)}=1$, and
$\lVert\hat{x}-\frac{x}{t}\rVert_{1}\leq\delta$ where $x$ is any feasible
solution of 5.1, $\delta\in[0,1)$, and $t\geq 1$. The probability that an
item, $a\in A$, is matched to a platform $p\in S$, where $S\subseteq N(a)$, in
a matching sampled from the support of $\mathcal{D}$ is

$\frac{L_{a,S}}{t}-\delta\leq\Pr_{M\sim\mathcal{D}}[M\text{ matches }a\text{
to some platform in }S]\leq\frac{U_{a,S}}{t}+\delta.$

###### Proof.

Given that $\lVert\vec{\hat{x}}-\frac{x}{t}\rVert_{1}\leq\delta$, therefore,

$\displaystyle\sum\limits_{(a,p)\in
E}\left\lvert\left(\hat{x}_{ap}-\frac{x_{ap}}{t}\right)\right\rvert\leq\delta$
(19)

Let’s fix an arbitrary item $a\in A$, and let $S$ be an arbitrary subset of
$N(a)$, then from Equation 19,

$\displaystyle\sum\limits_{p\in
S}\left\lvert\left(\hat{x}_{ap}-\frac{x_{ap}}{t}\right)\right\rvert\leq\delta\implies\left\lvert\displaystyle\sum\limits_{p\in
S}\left(\hat{x}_{ap}-\frac{x_{ap}}{t}\right)\right\rvert\leq\delta$

The last inequality holds due to triangle inequality. Therefore,

$\frac{1}{t}\displaystyle\sum\limits_{p\in
S}x_{ap}-\delta<\displaystyle\sum\limits_{p\in
S}\hat{x}_{ap}<\frac{1}{t}\displaystyle\sum\limits_{p\in S}x_{ap}+\delta$ (20)

Since $\vec{\hat{x}}=\sum_{i=1}^{k}\beta^{(i)}\vec{M}^{(i)}$, the probability
that an item $a\in A$ is matched to a platform $p\in S$, where $S\subseteq
N(a)$, in a matching sampled from $\mathcal{D}$ is

$\displaystyle\begin{split}&\Pr_{\vec{M}\sim\mathcal{D}}[\vec{M}\text{ matches
}a\text{ to a platform in
}S]=\displaystyle\sum_{\begin{subarray}{c}i:M^{(i)}\text{ matches }\\\ a\text{
to }p\in S\end{subarray}}\beta^{(i)}\\\ &=\displaystyle\sum\limits_{p\in
S}\displaystyle\sum\limits_{\begin{subarray}{c}i:M^{(i)}\text{ matches }\\\
a\text{ to }p\in S\end{subarray}}\beta^{(i)}=\displaystyle\sum\limits_{p\in
S}\hat{x}_{ap}\end{split}$

Therefore, from constraint 5 and Equation 20, we have

$\displaystyle\begin{split}&\frac{L_{a,S}}{t}-\delta\leq\Pr_{\vec{M}\sim\mathcal{D}}[\vec{M}\text{
matches }a\text{ to a platform in }S]\\\
&\leq\frac{U_{a,S}}{t}+\delta.\end{split}$

∎

##  5 Algorithm for Disjoint Groups

In this section, we prove Theorem 3.7 by working with an instance of a
bipartite graph where each item belongs to exactly one group; that is, all the
groups are disjoint. We first establish the fundamental module necessary for
computing a probabilistic individually fair distribution over a set of integer
group-fair matchings on a bipartite graph with disjoint groups. To prove
Theorems 3.5 and 3.6, we first need to reduce the problem instance to one
where $\Delta=1$. Therefore, this module is key to proving Theorems 3.6, and
3.5 as well. Theorem 3.7 is restated below:

See 3.7

######  LP 5.1.

$\displaystyle\max\sum_{(a,p)\in E}x_{ap}$ (21) such that $\displaystyle
L_{a,k}\leq\sum_{p\in R_{a,k}}x_{ap}\leq U_{a,k},$ $\displaystyle\forall a\in
A,\forall k\in[m]$ (22) $\displaystyle l_{p}\leq\sum_{a\in N(p)}x_{ap}\leq
u_{p},$ $\displaystyle\forall p\in P$ (23) $\displaystyle
l_{p,h}\leq\sum_{a\in A_{h}}x_{ap}\leq u_{p,h},$ $\displaystyle\forall p\in
P,\forall h\in[\chi]$ (24) $\displaystyle 0\leq x_{ap}\leq 1$
$\displaystyle\forall a\in A,\;\forall p\in P$ (25)

We first give a sketch for the proof of Theorem 3.7 using 5.1, Algorithm 2 and
$GFLP$ before providing a detailed proof of Theorem 3.7. Let us first look at
the LP $GFLP$.

######  Definition 5.2 (Group Fair Maximum Matching LP($GFLP$)).

This LP aims to find a maximum matching that does not violate any group or
platform bounds. It is the same as the 5.1 without constraint 5.

######  Observation 5.3.

Any feasible solution of 5.1 lies inside the polytope of $GFLP$(Definition
5.2).

######  Lemma 5.4 ([51]).

Any vertex in the polytope of $GFLP$ is integral if $\forall p\in P$, $\forall
h\in[\chi]$, the $l_{p}$, $u_{p}$, $l_{p,h}$ and $u_{p,h}$ values are
integers.

The proof of Lemma 5.4 is in the appendix. Let us first look at Algorithm
2(Distribution-Calculator), which is an adaptation of the Birkhoff-von-Neumann
algorithm([14]) to our setting. Birkhoff’s Theorem states that the set of
doubly stochastic matrices forms a convex polytope whose vertices are
permutation matrices, and the Birkhoff-von-Neumann algorithm decomposes a
bistochastic matrix into a convex combination of permutation matrices.

##### Distribution-Calculator:

By 5.3 and Carathéodory’s theorem, any feasible solution of 5.1 can be written
as a convex combination of extremal points in $GFLP$. Algorithm 2 takes an
optimal solution of 5.1, which maximizes the matching size and computes the
above-mentioned convex combination over corner points of $GFLP$. Algorithm 2
first removes all edges $e\in E$ that have $x_{e}=0$. The algorithm adjusts
the upper and lower bounds to obtain an integer matching from $GFLP$.
Specifically, it rounds up and down, respectively, the sum of $x_{e}$ values
linked to edges in the vicinity of each platform or group-platform
combination. Next, Algorithm 3[Find-Coefficient] is used to compute an
appropriate coefficient for the resulting integral matching. The coefficient
should be such that after step 2 of Algorithm 2, the resulting point should
lie within the polytope of $GFLP$ and either there is at least one edge
$(a,p)$ such that $x_{ap}=0$ or at least one constraint becomes tight. We use
this fact and induction to show that the integer matching being computed in
step 2 of Algorithm 2 is group-fair (Lemma 5.5) and $\mathcal{D}$ returned by
Algorithm 2 is a distribution of said matchings (Lemma 5.9). This is also
important to show that the algorithm terminates in polynomial time (Lemma
5.7). Finally, it is scaled to ensure that all the coefficients sum up to $1$.
These steps are repeated until there are no edges left.

Input : $\mathcal{I}$, $x$, $LP$

Output : Distribution $\mathcal{D}$ over integer matchings

1 $G^{(0)}\leftarrow G,x^{(0)}\leftarrow
x,\mathcal{D}\leftarrow\phi,\alpha^{(0)}\leftarrow 0,\Gamma^{0}\leftarrow
1,\beta^{(0)}\leftarrow 1$

2 while  _$x^{(i)}\neq\mathbf{0}$_ do

3 $i\leftarrow i+1,G^{(i)}\leftarrow
G^{(i-1)}-\\{(a,p)\;\lvert\;x^{(i-1)}_{ap}=0\\}$

4 $l^{(i)}_{p}\leftarrow\lfloor\sum_{a\in N(p)}x^{(i-1)}_{ap}\rfloor$,
$u^{(i)}_{p}\leftarrow\lceil\sum_{a\in N(p)}x^{(i-1)}_{ap}\rceil$, $\forall
p\in P$

5 $l^{(i)}_{p,h}\leftarrow\lfloor\sum_{a\in
A_{h}}x^{(i-1)}_{ap}\rfloor,u^{(i)}_{p,h}\leftarrow\lceil\sum_{a\in
A_{h}}x^{(i-1)}_{ap}\rceil$, $\forall p\in P$, $h\in[\chi]$

6 $M^{(i)}\leftarrow$ Matching returned by solving $LP$ on $G^{(i)}$ with
$l^{(i)}_{p},u^{(i)}_{p},l^{(i)}_{p,h},u^{(i)}_{p,h}$ as the bounds.

7 $\alpha^{(i)}\leftarrow$ Find-Coefficient($G^{(i)},A_{1}\cdots
A_{\chi},x^{(i-1)},M^{(i)}$)

8 $x^{(i)}\leftarrow\frac{x^{(i-1)}-\alpha^{(i)}M^{(i)}}{1-\alpha^{(i)}}$

9
$\beta^{(i)}\leftarrow\Gamma^{(i-1)}\cdot\alpha^{(i)},\mathcal{D}\leftarrow\mathcal{D}\cup(M^{(i)},\beta^{(i)})$

10 $\Gamma^{(i)}\leftarrow\Gamma^{(i-1)}\cdot(1-\alpha^{(i)})$

11 end while

12if  _$\mathcal{D}==\phi$_ then

13 Return ‘Infeasible’

14 end if

Return $\mathcal{D}$

Algorithm 2 Distribution-Calculator$(\mathcal{I}=(G,A_{1}\cdots
A_{\chi},\vec{l},\vec{u},\vec{L},\vec{U}),x,LP)$

Input : Graph $G^{\prime}$, Groups $A_{1}\cdots A_{\chi}$, $x$, $M$

Output : Scalar $\alpha$

1 $\alpha\leftarrow\min_{(a,p)\in M}x_{ap}$

2 for  _$p\in P$_ do

3 if  _$\sum_{a\in N(p)}M_{ap}==\lceil\sum_{a\in N(p)}x_{ap}\rceil$_ then
$temp\leftarrow\sum_{a\in N(p)}x_{ap}-\lfloor\sum_{a\in N(p)}x_{ap}\rfloor$ ;

4 else $temp\leftarrow\lceil\sum_{a\in N(p)}x_{ap}\rceil-\sum_{a\in
N(p)}x_{ap}$ ;

5 if  _$temp <\alpha\text{ and }temp>0$_ then $\alpha\leftarrow temp$ ;

6 for  _$h\in[\chi]$_ do

7 if  _$\sum_{a\in A_{h}}M_{ap}==\lceil\sum_{a\in A_{h}}x_{ap}\rceil$_ then
$temp\leftarrow\sum_{a\in A_{h}}x_{ap}-\lfloor\sum_{a\in A_{h}}x_{ap}\rfloor$
;

8 else $temp\leftarrow\lceil\sum_{a\in A_{h}}x_{ap}\rceil-\sum_{a\in
A_{h}}x_{ap}$ ;

9 if  _$temp <\alpha\text{ and }temp>0$_ then $\alpha\leftarrow temp$ ;

10

11 end for

12

13 end for

14Return $\alpha$

Algorithm 3 Find-Coefficient($G^{\prime},A_{1}\cdots A_{\chi},x,M$)

Input : $\mathcal{I}$

Output : Distribution over matchings satisfying the guarantees in Theorem 3.7.

1 Solve 5.1 on $G$ with the parameters in the input instance, $\mathcal{I}$,
and store the result in $x$

Return Distribution-Calculator$(\mathcal{I},x,GFLP)$

Algorithm 4 Exact Algorithm$(\mathcal{I}=(G,A_{1}\cdots
A_{\chi},\vec{l},\vec{u},\vec{L},\vec{U}),x))$

In this section, we show that given an instance $\mathcal{I}$ of our problem,
an optimal solution of 5.1, and the LP $GFLP$ as input, Algorithm 2 is a
polynomial-time algorithm that returns a distribution over a set of group-fair
matchings. Finally, by substituting $\hat{x}=x$, $\delta=0$, and $t=1$ in
Lemma 4.12, we show that $\mathcal{D}$ is a probabilistic individually fair
distribution. Given any feasible solution of 5.1, say $x$, we use Algorithm 4
and $GFLP$ to compute a convex combination of integer matchings and prove that
$x$ can be written as the same.

######  Lemma 5.5.

$x^{(i)}$ always lies within the polytope of $GFLP$, where $i+1$ denotes an
arbitrary iteration of the while loop in Algorithm 2.

###### Proof.

We will prove this using induction. For the base case, $i+1=1$, $x^{(0)}=x$.
Since $x$ is an optimal solution of 5.1, the Lemma holds by 5.3. Let us assume
that the Lemma holds for $x^{(i-1)}$ where $i$ denotes an arbitrary iteration
of the while loop in Algorithm 2. Now, we will show that the Lemma also holds
for $x^{(i)}$. If $x^{(i-1)}$ is non zero, then there exists at least one
$p\in P,h\in[\chi]$, such that $u_{p}^{(i)}$ and $u_{p,h}^{(i)}$ values are at
least one. Therefore, $\vec{M}^{(i)}$ is a non empty matching on $G^{(i)}$,
since $GFLP$ returns a maximum matching that satisfies the updated group
fairness constraints. First let us look at constraint 23 for an arbitrary
platform, $p\in P$. Let $m^{(i)}_{p}$ be the number of edges picked in
$\vec{M}^{(i)}$ for platform $p$. From steps 2 to 2 in Algorithm 2, we know
that we can have one of the following cases:

  1. 1.

$\displaystyle\sum_{a\in N(p)}x^{(i-1)}_{ap}$ is an integer in which case
$l_{p}^{(i)}=u_{p}^{(i)}=\displaystyle\sum_{a\in N(p)}x^{(i-1)}_{ap}$. Since
$\vec{M}^{(i)}$ is an integer matching by Lemma 5.4,
$m^{(i)}_{p}=l_{p}^{(i)}=u_{p}^{(i)}=\displaystyle\sum_{a\in
N(p)}x^{(i-1)}_{ap}$. Therefore, for all values of $\alpha^{(i)}\in(0,1]$,

$\displaystyle\sum_{a\in N(p)}x^{(i)}=\frac{\sum_{a\in
N(p)}x^{(i-1)}_{ap}-\alpha^{(i)}\cdot
m^{(i)}_{p}}{1-\alpha^{(i)}}=\displaystyle\sum_{a\in
N(p)}x^{(i-1)}_{ap}=l_{p}^{(i)}=u_{p}^{(i)}$

  2. 2.

$\displaystyle\sum_{a\in N(p)}x^{(i-1)}_{ap}$ is fractional in which case
$u_{p}^{(i)}-l_{p}^{(i)}=1$. Since $\vec{M}^{(i)}$ is an integer matching by
Lemma 5.4, $m^{(i)}_{p}=u_{p}^{(i)}$ or $m^{(i)}_{p}=l_{p}^{(i)}$. Therefore,
we can have the following sub cases:

    1. (a)

$m^{(i)}_{p}=l_{p}^{(i)}$: It is easy to see that for all values of
$\alpha^{(i)}\in(0,1]$, the lower bound is always satisfied. Based on step 3
of the Routine Find-Coefficient that is called in step 2 of Algorithm 2, we
know that $\alpha^{(i)}\leq\lceil\sum_{a\in
N(p)}x_{ap}^{(i-1)}\rceil-\sum_{a\in
N(p)}x_{ap}^{(i-1)}=u_{p}^{(i)}-\sum_{a\in N(p)}x^{(i-1)}_{ap}$. Therefore,

$\displaystyle\begin{split}&\sum_{a\in N(p)}x^{(i-1)}_{ap}\leq
u_{p}^{(i)}-\alpha^{(i)}(u_{p}^{(i)}-l_{p}^{(i)})\\\ &\implies\frac{\sum_{a\in
N(p)}x^{(i-1)}_{ap}-\alpha^{(i)}\cdot l^{(i)}_{p}}{1-\alpha^{(i)}}\leq
u_{p}^{(i)}\end{split}$

Hence constraint 23 is not violated.

    2. (b)

$m^{(i)}_{p}=u_{p}^{(i)}$: It is easy to see that for all values of
$\alpha^{(i)}\in(0,1]$, the upper bound is always satisfied. Based on step 3
of the Routine Find-Coefficient, we know that $\alpha^{(i)}\leq\sum_{a\in
N(p)}x_{ap}^{(i-1)}-\lfloor\sum_{a\in N(p)}x_{ap}^{(i-1)}\rfloor=\sum_{a\in
N(p)}x^{(i-1)}_{ap}-l_{p}^{(i)}$. Following steps similar to the above sub
case, we have

$l_{p}^{(i)}\leq\frac{\sum_{a\in N(p)}x^{(i-1)}_{ap}-\alpha^{(i)}\cdot
u^{(i)}_{p}}{1-\alpha^{(i)}}=\sum_{a\in N(p)}x^{(i)}$

Hence constraint 23 is not violated.

Similar arguments can be used to show that constraint 24 is also not violated.
Constraint 25 is satisfied trivially. Therefore, $x^{(i)}$ also satisfies all
the constraints of $GFLP$ and hence lies within the polytope of $GFLP$. ∎

######  Claim 5.6.

In an arbitrary iteration of the while loop in Algorithm 2, say $i^{th}$
iteration, if there is an edge, $(a,p)$, such that $\sum_{a\in
A_{h}}x^{(i)}_{ap}=u_{p,h}^{(i)}$ or $\sum_{a\in
A_{h}}x^{(i)}_{ap}=l_{p,h}^{(i)}$ for some $h\in[\chi]$, then,
$l_{p,h}^{(j)}=\sum_{a\in A_{h}}x^{(j-1)}_{ap}=u_{p,h}^{(j)}$, $\forall
j\in\mathbb{Z}$ such that $j\geq i+1$. If Algorithm 2 completes in $k$
iterations, then $j\in\mathbb{Z}\cap[i+1,k]$. Similarly, for constraint 23.

###### Proof.

We can prove this by a simple induction on $j$ where $j\in\mathbb{Z}$ such
that $j\geq i+1$. In this proof, we will make the implicit assumption that
$j\leq k$ if Algorithm 2 completes in $k$ iterations. For the base case,
$j=i+1$, $l_{p,h}^{(i+1)}=\lfloor\sum_{a\in A_{h}}x^{(i)}_{ap}\rfloor$, and
$u_{p,h}^{(i+1)}=\lceil\sum_{a\in A_{h}}x^{(i)}_{ap}\rceil$. Since $\sum_{a\in
A_{h}}x^{(i)}_{ap}=u_{p,h}^{(i)}=\lceil\sum_{a\in A_{h}}x^{(i-1)}_{ap}\rceil$
or $\sum_{a\in A_{h}}x^{(i)}_{ap}=l_{p,h}^{(i)}=\lfloor\sum_{a\in
A_{h}}x^{(i-1)}_{ap}\rfloor$ by the assumption in the lemma, $\sum_{a\in
A_{h}}x^{(i)}_{ap}$ is an integer, therefore,

$l_{p,h}^{(i+1)}=\lfloor\sum_{a\in A_{h}}x^{(i)}_{ap}\rfloor=\lceil\sum_{a\in
A_{h}}x^{(i)}_{ap}\rceil=u_{p,h}^{(i+1)}$

For the induction step let’s assume that for some arbitrary integer $j>i+1$,
$\sum_{a\in A_{h}}x^{(j)}_{ap}=u_{p,h}^{(j)}=\lceil\sum_{a\in
A_{h}}x^{(j-1)}_{ap}\rceil$, therefore, $\sum_{a\in A_{h}}x^{(j)}_{ap}$ is an
integer by the induction hypothesis and hence

$u_{p,h}^{(j+1)}=\lceil\sum_{a\in A_{h}}x^{(j)}_{ap}\rceil=\sum_{a\in
A_{h}}x^{(j)}_{ap}=\lfloor\sum_{a\in
A_{h}}x^{(j)}_{ap}\rfloor=l_{p,h}^{(j+1)}$

∎

######  Lemma 5.7.

Algorithm 4 terminates in polynomial time.

###### Proof.

We will show that in each iteration, at least an edge is removed, or at least
one constraint becomes tight. From 5.6, we know that once a constraint becomes
tight, it stays so in the rest of the rounds. Therefore, we get a polynomial
bound on the total number of iterations since the total number of constraints
and edges is polynomial. Let us look at an arbitrary iteration, say $i^{th}$
iteration. If $\alpha^{(i)}=\min_{e\in\vec{M}^{(i)}}x^{(i-1)}_{e}$, then there
is at least one edge, say $(a,p)\in E$, such that $x^{(i)}_{ap}=0$. Otherwise,
there is some platform, say $p\in P$, such that
$\alpha^{(i)}=\min\big{(}\sum_{a\in
N(p)}x_{ap}^{(i-1)}-l_{p}^{(i)},u_{p}^{(i)}-\sum_{a\in
N(p)}x_{ap}^{(i-1)}\big{)}$, or there is some platform, say $p^{\prime}\in P$,
with some group, say $h\in[\chi]$, such that
$\alpha^{(i)}=\min\big{(}\sum_{a\in
A_{h}}x_{ap^{\prime}}^{(i-1)}-l_{p^{\prime},A_{h}}^{(i)},u_{p^{\prime},A_{h}}^{(i)}-\sum_{a\in
A_{h}}x_{ap^{\prime}}^{(i-1)}\big{)}$. Let $\alpha^{(i)}=\sum_{a\in
N(p)}x_{ap}^{(i-1)}-l_{p}^{(i)}$, then from step 3 of Routine 3 we know that
$m_{p}^{(i)}=u_{p}^{(i)}$ where $m_{p}^{(i)}$ is the number of edges picked in
$\vec{M}^{(i)}$ for platform $p$. Therefore,

$\begin{split}&\sum_{a\in N(p)}x^{(i)}=\frac{\sum_{a\in
N(p)}x^{(i-1)}_{ap}-\alpha^{(i)}\cdot m^{(i)}_{p}}{1-\alpha^{(i)}}=\\\
&\frac{\sum_{a\in N(p)}x^{(i-1)}_{ap}-(\sum_{a\in
N(p)}x_{ap}^{(i-1)}-l_{p}^{(i)})\cdot u_{p}^{(i)}}{1-(\sum_{a\in
N(p)}x_{ap}^{(i-1)}-l_{p}^{(i)})}\end{split}$ (26)

Note that $\sum_{a\in N(p)}x_{ap}^{(i-1)}$ must be fractional if
$\alpha^{(i)}=\sum_{a\in N(p)}x_{ap}^{(i-1)}-l_{p}^{(i)}$ based on step 3 of
Routine 3. Therefore, $l_{p}^{(i)}=\lfloor\sum_{a\in
N(p)}x_{ap}^{(i-1)}\rfloor=\lceil\sum_{a\in
N(p)}x_{ap}^{(i-1)}\rceil-1=u_{p}^{(i)}-1$. Hence, from Equation 26,
$\sum_{a\in N(p)}x^{(i)}=$

$\displaystyle\begin{split}&\frac{\sum_{a\in N(p)}x^{(i-1)}_{ap}-(1+\sum_{a\in
N(p)}x_{ap}^{(i-1)}-u_{p}^{(i)})\cdot u_{p}^{(i)}}{1-(1+\sum_{a\in
N(p)}x_{ap}^{(i-1)}-u_{p}^{(i)})}\\\
&=\frac{(u_{p}^{(i)}-1)(u_{p}^{(i)}-\sum_{a\in
N(p)}x_{ap}^{(i-1)})}{(u_{p}^{(i)}-\sum_{a\in
N(p)}x_{ap}^{(i-1)})}=l_{p}^{(i)}\end{split}$

Similarly, we can show that if

  1. 1.

$\alpha^{(i)}=u_{p}^{(i)}-\sum_{a\in N(p)}x_{ap}^{(i-1)}$, then $\sum_{a\in
N(p)}x_{ap}^{(i)}=u_{p}^{(i)}$.

  2. 2.

$\alpha^{(i)}=\sum_{a\in
A_{h}}x_{ap^{\prime}}^{(i-1)}-l_{p^{\prime},A_{h}}^{(i)}$, then $\sum_{a\in
A_{h}}x_{ap^{\prime}}^{(i)}=l_{p^{\prime},A_{h}}^{(i)}$.

  3. 3.

$\alpha^{(i)}=u_{p^{\prime},A_{h}}^{(i)}-\sum_{a\in
A_{h}}x_{ap^{\prime}}^{(i-1)}$, then $\sum_{a\in
A_{h}}x_{ap^{\prime}}^{(i)}=u_{p^{\prime},A_{h}}^{(i)}$.

Therefore, if $\alpha^{(i)}\neq\min_{e\in\vec{M}^{(i)}}x^{(i-1)}_{e}$, that is
if an edge is not removed, then either the left inequality or right inequality
of constraint 23 becomes tight in the $i^{th}$ round for some platform or
there is some platform, say $p^{\prime}\in P$, such that either left
inequality or right inequality of constraint 24 becomes tight in the $i^{th}$
round for some group, say $h\in[\chi]$. Since the total number of constraints
is $O(|V|)$, $|E|=O(|V|^{2})$, and the routine Find-Coefficient runs in
$O(|V|)$ time, we get $O(|V|^{3})$ iterations for the loop in Algorithm 2.
Since $GFLP$ can be solved in polynomial time, Algorithm Distribution-
Calculator is a polynomial-time algorithm. 5.1 can be solved in polynomial
time, therefore, Algorithm 4 also runs in polynomial time. ∎

######  Claim 5.8.

Let Algorithm 4 terminate in $k$ rounds and return a set of tuples,
$\mathcal{D}=\\{(\vec{M}^{(i)},\beta^{(i)})\\}_{i\in[k]}$, then, $\forall
i\in[k]$,

$x^{(i)}=\frac{x^{(0)}-\sum_{j=1}^{i}\beta^{(j)}\vec{M}^{(j)}}{\Gamma^{(i)}}$

###### Proof.

From steps 2 and 2 in Algorithm 4, we know that
$\beta^{(i)}=\Gamma^{(i-1)}\alpha^{(i)}$, and
$\Gamma^{(i)}=\Gamma^{(i-1)}(1-\alpha^{(i)})$ respectively, and
$\Gamma^{(0)}=1$. For the base case, $i=1$, we know from step 2 in Algorithm 2
that $x^{(1)}=\frac{x^{(0)}-\alpha^{(1)}\vec{M}^{(1)}}{1-\alpha^{(1)}}$. It is
easy to see that $\Gamma^{(1)}=(1-\alpha^{(1)})$ and
$\beta^{(1)}=\alpha^{(1)}$, therefore,

$x^{(1)}=\frac{x^{(0)}-\beta^{(1)}\vec{M}^{(1)}}{\Gamma^{(1)}}$

For the induction step, for some $i\in\mathbb{Z}\cap(1,k]$, let
$x^{(i-1)}=\frac{x^{(0)}-\sum_{j=1}^{i-1}\beta^{(j)}\vec{M}^{(j)}}{\Gamma^{(i-1)}}$.
We know that
$x^{(i)}=\frac{x^{(i-1)}-\alpha^{(i)}\vec{M}^{(i)}}{1-\alpha^{(i)}}$,
therefore, by induction hypothesis,

$x^{(i)}=\frac{\frac{x^{(0)}-\sum_{j=1}^{i-1}\beta^{(j)}\vec{M}^{(j)}}{\Gamma^{(i-1)}}-\alpha^{(i)}\vec{M}^{(i)}}{1-\alpha^{(i)}}=\frac{x^{(0)}-\sum_{j=1}^{i-1}\beta^{(j)}\vec{M}^{(j)}-\Gamma^{(i-1)}\alpha^{(i)}\vec{M}^{(i)}}{\Gamma^{(i-1)}(1-\alpha^{(i)})}$

hence,

$x^{(i)}=\frac{x^{(0)}-\sum_{j=1}^{i}\beta^{(j)}\vec{M}^{(j)}}{\Gamma^{(i)}}$

∎

######  Lemma 5.9.

Let Algorithm 4 terminate in $k$ rounds and return a set of tuples,
$\mathcal{D}=\\{(\vec{M}^{(i)},\beta^{(i)})\\}_{i\in[k]}$, then,
$x=\displaystyle\sum_{i=1}^{k}\beta^{(i)}\vec{M}^{(i)}$, where $x$ is computed
in step 4 of Algorithm 4 and $\displaystyle\sum_{i=1}^{k}\beta^{(i)}=1$.

###### Proof.

From 5.8, we know that $\forall i\in[k]$,

$x^{(k)}=\frac{x^{(0)}-\sum_{i=1}^{k}\beta^{(i)}\vec{M}^{(i)}}{\Gamma^{(k)}}.$

Since $x^{(k)}=\vec{0}$, we have
$x^{(0)}=x=\displaystyle\sum_{i=1}^{k}\beta^{(i)}\vec{M}^{(i)}$.

We will prove that $\displaystyle\sum_{i=1}^{k}\beta^{(i)}=1$, using induction
on $i$, backwards from $k$ to $0$. For the base case, $i=k$,
$x^{(k)}=\vec{0}$, therefore, for any real values of $\alpha$,
$x^{(k)}=(1-\alpha)\vec{M}+\alpha\vec{M}$, where $\vec{M}$ is an empty
matching. Note that if $u_{p},l_{p},u_{p,h},l_{p,h}$ are set to $0$, $\forall
p\in P,h\in[\chi]$, $GFLP$ would compute an empty matching. Therefore,
$x^{(k)}$ can be written as a convex combination of integer matchings computed
by $GFLP$. For the induction step, let us assume that
$x^{(i+1)}=\sum_{j}\gamma_{j}\vec{M}_{j}$, where $\vec{M}_{j}$ is an integer
matching computed by $GFLP$ for all values of $j$ and $\sum_{j}\gamma_{j}=1$,
for some $i\in[k-1]$. We know that
$x^{(i+1)}=\frac{x^{(i)}-\alpha^{(i)}\vec{M}^{(i)}}{1-\alpha^{(i)}}$.
Therefore,

$x^{(i)}=(1-\alpha^{(i)})x^{(i+1)}+\alpha^{(i)}\vec{M}^{(i)}=(1-\alpha^{(i)})\sum_{j}\gamma_{j}\vec{M}_{j}+\alpha^{(i)}\vec{M}^{(i)}$

Since $\sum_{j}\gamma_{j}=1$, by the induction hypothesis,
$(1-\alpha^{(i)})\sum_{j}\gamma_{j}+\alpha^{(i)}=1$, therefore, $x^{(i)}$ is
also a convex combination of integer matchings computed by $GFLP$.

From 5.8 we know that, $\forall i\in[k]$,
$x^{(i)}=\frac{x^{(0)}-\sum_{j=1}^{i}\beta^{(j)}\vec{M}^{(j)}}{\Gamma^{(i)}}$,
hence,

$x^{(0)}=\Gamma^{(i)}x^{(i)}+\sum_{j=1}^{i}\beta^{(j)}\vec{M}^{(j)}.$

Since, we have already shown that, $x^{(i)}$ is a convex combination of
integer matchings computed by $GFLP$ using induction, we just need to show
that $\Gamma^{(i)}+\sum_{j=1}^{i}\beta^{(j)}=1$. Expanding $\Gamma^{(i)}$ and
$\sum_{j=1}^{i}\beta^{(j)}$, we have

$\Gamma^{(i)}+\sum_{j=1}^{i}\beta^{(j)}=\Pi_{j=1}^{i}(1-\alpha^{(j)})+\sum_{j=1}^{i}\Pi_{l=1}^{j-1}(1-\alpha^{(l)})\alpha^{(j)}=1$

Therefore, $\displaystyle\sum_{i=1}^{k}\beta^{(i)}=1$. ∎

###### Proof of Theorem 3.7.

Let Algorithm 4 terminate in $k$ rounds and return a set of tuples,
$\mathcal{D}=\\{(\vec{M}^{(i)},\beta^{(i)})\\}_{i\in[k]}$. Therefore,
$x=\sum_{i=1}^{k}\beta^{(i)}\vec{M}^{(i)}$ and $\sum_{i=1}^{k}\beta^{(i)}=1$
by Lemma 5.9, where $x$ is an optimal solution of 5.1. We know that after
every iteration, we get another point inside the polytope of $GFLP$ by Lemma
5.5, therefore, in every iteration, the integer matching being computed in
step 2 of Algorithm 2 satisfies group fairness constraints. Therefore,
Algorithm 4 returns a distribution over group-fair integer matchings. By
substituting $\vec{\hat{x}}=x$, $\delta=0$, and $t=1$ in Lemma 4.12, we get
that the probability that an item $a\in A$ is matched to a platform $p\in S$,
where $S\subseteq N(a)$, in a matching sampled from $\mathcal{D}$ is
$L_{a,S}\leq\sum\limits_{p\in S}x_{ap}\leq U_{a,S}$, $\forall a\in
A,S\subseteq N(a)$. Hence, $\mathcal{D}$ is a probabilistic individually fair
distribution. The run time has been shown to be polynomial in Lemma 5.7. This
proves the theorem. ∎

##  6 $O(g)$ Bicriteria Approximation Algorithms

In this section, we work with an instance of a bipartite graph, $G(A,P,E)$,
where the items in the neighborhood of any platform $p$ belong to at most $g$
(Definition 6.3) distinct groups, and any item, $a\in A$, can belong to at
most $\Delta$ groups. We first reduce this instance to one where $\Delta=1$,
then use $GFLP$ with specific bounds in the form of 6.4, and Algorithm 2 to
compute a distribution over matchings in Algorithm 5. Since Section 5 also
addresses an instance where the groups are disjoint, we will use Lemmas from
Section 5 and an analysis technique similar to Section 5 to prove Theorem 3.5,
formally stated below.

######  Theorem 6.1 (Formal version of Theorem 3.5).

Given an instance of our problem where each item belongs to at most $\Delta$
groups, and $u_{p,h}\geq g$ $\forall p\in P,h\in[\chi]$, there is a
polynomial-time algorithm that computes a distribution $\mathcal{D}$ over a
set of group-fair matchings such that the expected size of a matching sampled
from $\mathcal{D}$ is at least $\frac{OPT}{2g}$. Given the individual fairness
parameters, $L_{a,k},U_{a,k}\in[0,1]$, for each item $a\in A$ and subset
$R_{a,k}$ $\forall$ $k\in[m]$,

$\displaystyle\frac{L_{a,k}}{2g}\leq\Pr_{M\sim\mathcal{D}}[\exists p\in
R_{a,k}\textrm{ s.t. }(a,p)\in M]\leq\frac{U_{a,k}}{2g}.$

Let us first define $g$ formally and then look at 6.4. To formally define $g$,
we first need the following definition:

######  Definition 6.2.

$\boldsymbol{C_{p}}=\\{C_{p,h}:C_{p,h}\neq\phi\\}_{h\in[\chi]}$ denotes a set
of groups for any platform $p$ such that $C_{p,h}=A_{h}\cap N(p)$, for some
$h\in[\chi]$. Here $N(p)$ denotes the set of neighbors of $p$ in $G$.

######  Definition 6.3.

$\boldsymbol{g}=\max_{p\in P}|C_{p}|$.

######  LP 6.4.

$\displaystyle\max\sum_{(a,p)\in E}x_{ap}$ (27) such that
$\displaystyle\sum_{a\in
A_{h}}x_{ap}\leq\left\lfloor\frac{u_{p,h}}{g}\right\rfloor\;,$
$\displaystyle\forall h\in[\chi],\;\forall p\in P$ (28) $\displaystyle 0\leq
x_{ap}\leq 1$ $\displaystyle\forall(a,p)\in E$ (29)

Input : $\mathcal{I}$

Output : Distribution over matchings satisfying the guarantees in Theorem 6.8.

1 Solve 4.2 on $G$ with the parameters in the input instance, $\mathcal{I}$,
and store the result in $x$

2 $g=\max_{p\in P}|C_{p}|$ (Definition 6.2 and 6.3)

3 For each item $a\in A$, we remove it from every group other than $C_{a}$
where $C_{a}=\operatorname*{arg\,min}_{C\in C_{p}:a\in C}u_{p,h}$. Let the
resulting graph be $G^{\prime}$.

4 $\mathcal{I}^{\prime}=(G^{\prime},A^{\prime}_{1}\cdots
A^{\prime}_{\chi},\vec{l},\vec{u},\vec{L},\vec{U})$

Return Distribution-
Calculator$(\mathcal{I}^{\prime},\frac{x}{2g},\lx@cref{creftypecap~refnum}{LP_group_approx})$

Algorithm 5 $2g$-BicriteriaApprox$(\mathcal{I}=(G,A_{1}\cdots
A_{\chi},\vec{l},\vec{u},\vec{L},\vec{U}))$

######  Observation 6.5.

Let $x$ be a feasible solution of 4.2, and $u_{p,h}\geq g$ $\forall p\in
P,h\in[\chi]$, then $\frac{x}{2g}$ lies inside the polytope of 6.4.

###### Proof.

Let $d$ be any positive real number, then we will consider the following two
cases:

  1. 1.

$d\geq 2$: It is trivial to see that $\frac{d}{2}\leq d-1\leq\lfloor d\rfloor$
in this case.

  2. 2.

$d\in[1,2)$: In this case, $d=1+\delta$ where $\delta\in[0,1)$. Therefore,
$\frac{\delta}{2}<\frac{1}{2}$, hence,

$\frac{d}{2}=\frac{1}{2}+\frac{\delta}{2}<1=\lfloor d\rfloor$

Therefore, for any positive real number $d\geq 1$,

$\frac{d}{2}\leq\lfloor d\rfloor$

Since $x$ is a feasible solution of 4.2, $\sum_{a\in A_{h}}x_{ap}\leq u_{p,h}$
$\forall p\in P,h\in[\chi]$ by constraint 6, therefore, $\forall p\in
P,h\in[\chi]$

$\frac{\sum_{a\in
A_{h}}x_{ap}}{2g}\leq\frac{u_{p,h}}{2g}\leq\left\lfloor\frac{u_{p,h}}{g}\right\rfloor$

The last inequality holds because of the assumption $u_{p,h}\geq g$ $\forall
p\in P,h\in[\chi]$, which implies $\frac{u_{p,h}}{g}\geq 1$ $\forall p\in
P,h\in[\chi]$. Therefore $\frac{x}{2g}$ satisfies constraint 28, constraint 29
is also satisfied because $\forall(a,p)\in E$, $0\leq x_{ap}\leq 1$,
therefore, $0\leq\frac{x_{ap}}{2g}\leq 1$. ∎

######  Lemma 6.6.

Let $x$ be any optimal solution of LP 6.4 on the graph resulting after step 5
in Algorithm 5, say $G^{\prime}$, then $x$ is an integer matching on
$G^{\prime}$ that satisfies the group fairness constraint 9.

###### Proof.

Any vertex solution of LP 6.4 on $G^{\prime}$ is integral if the groups are
disjoint, by Lemma 5.4, therefore, $x$ is an integer matching on $G^{\prime}$.
Let us fix an arbitrary platform, $p$, and let $T_{p}$ denote a set of groups
such that $A_{h}\cap N(p)\neq\phi$, $\forall h\in T_{p}$. Let us number all
the groups in $T_{p}$ in the ascending order of their upper bounds, breaking
ties arbitrarily, that is, for any two groups, say $h_{i},h_{j}\in T_{p}$,
$u_{p,h_{j}}>u_{p,h_{i}}$ iff $j>i$. Let us consider an arbitrary group,
$h_{q}\in T_{p}$, with upper bound $u_{p,h_{q}}$. Any item $a\in A$ that has
been removed from this group in step 5 of Algorithm 5 could only be in one of
the groups from $h_{1}$ to $h_{q-1}$. This is because an item stays in the
group with the lowest upper bound. Let $m_{i}=\displaystyle\sum_{a\in
A_{h_{i}}}x_{ap}$, then
$m_{i}\leq\left\lfloor\frac{u_{p,h_{i}}}{g}\right\rfloor$ due to constraint
28. Therefore,

$\displaystyle\sum_{i=1}^{q}m_{i}\leq\sum_{i=1}^{q}\left\lfloor\frac{u_{p,h_{i}}}{g}\right\rfloor\leq\sum_{i=1}^{q}\frac{u_{p,h_{i}}}{g}\leq\sum_{i=1}^{q}\frac{u_{p,h_{q}}}{g}\leq$
$\displaystyle g\cdot\frac{u_{p,h_{q}}}{g}=u_{p,h_{q}}$

Therefore, $\displaystyle\sum_{a\in A_{h}}x_{ap}\leq u_{p,h}$ $\forall h\in
T_{p}$ after all the items are returned to all the groups they belonged to in
the original graph. Therefore, $x$ satisfies constraint 9. ∎

######  Lemma 6.7.

Given a bipartite graph $G(A,P,E)$ with possibly non-disjoint groups and an
optimal solution of 4.2, Algorithm 5 returns a distribution over integer
matchings in polynomial time, such that each matching satisfies group fairness
constraints.

###### Proof.

We start with an optimal solution of 4.2, therefore, $\frac{x}{2g}$ is a
feasible solution of 6.4 by 6.5. Let $x^{(i)}$ be the state of the optimal
solution of 4.3, $x$, after the $i^{th}$ iteration of Algorithm 2. Note that
6.4 is $GFLP$(Definition 5.2) with specific upper and lower bounds, therefore,
$x^{(i)}$ always lies within the polytope of 6.4 by Lemma 5.5,$\forall
i\in[k-1]$, where $k$ is the number of iterations after which Algorithm 2
terminates. Therefore, if $x^{(i-1)}$ is non empty, a non empty integer
matching is computed in step 2 of Algorithm 2 for $k$ rounds and by Lemma 6.6
we know that each such matching satisfies group fairness constraints. From
Lemma 5.9, we know that $x$ can be written as a convex combination of integer
matchings computed by 6.4. Therefore, Algorithm 5 returns a distribution over
group-fair integer matchings. The run time of Algorithm 2 has been shown to be
polynomial in Lemma 5.7, since 4.2 can be solved in polynomial time, Algorithm
5 also runs in polynomial time. ∎

###### Proof of Theorem 6.1.

Let $x$ be any optimal solution of 4.2, then, Algorithm 5 can be used to
represent $\frac{x}{2g}$ as a distribution, say $\mathcal{D}$, of integer
group-fair matchings in polynomial time by Lemma 6.7. By setting $\hat{x}=x$,
$\delta=0$, and $t=2g$ in Lemma 4.12, we have for each item $a\in A$ and
subset $R_{a,k}$ $\forall$ $k\in[m]$,

$\displaystyle\frac{L_{a,k}}{2g}\leq\Pr_{M\sim\mathcal{D}}[\exists p\in
R_{a,k}\textrm{ s.t. }(a,p)\in M]\leq\frac{U_{a,k}}{2g}.$

This proves the theorem. ∎

###  6.1 Group Fairness Violation

In this section, we formally state and prove Theorem 3.6. We use 6.9 instead
of 6.4 to reduce the problem to something similar to the problem we saw in
Section 5, then use Algorithm 6, which is a slightly modified version of
Algorithm 5, and Lemmas from Section 5 to prove Theorem 3.6 which is formally
stated below.

######  Theorem 6.8 (Formal version of Theorem 3.6).

Given an instance of our problem with no lower bound constraints where each
item belongs to at most $\Delta$ groups, and $u_{p,h}\geq g$ $\forall p\in
P,h\in[\chi]$, we provide a polynomial-time algorithm that computes a
distribution ${\mathcal{D}}$ over a set of matching. The expected size of a
matching sampled from ${\mathcal{D}}$ is at least $\frac{OPT}{g}$, and each
matching in the distribution violates group fairness by an additive factor of
at most $\Delta$. Given the individual fairness parameters
$L_{\mathrm{a},S}\in[0,1]$ and $U_{\mathrm{a},S}\in[0,1]$ for each item
$\mathrm{a}\in A$ and each subset $S\subseteq N(\mathrm{a})$,

$\frac{L_{\mathrm{a},S}}{g}\leq\Pr_{M\sim\mathcal{D}}[M\text{ matches
}\mathrm{a}\text{ to a platform in }S]\leq\frac{U_{\mathrm{a},S}}{g}$

######  LP 6.9.

$\displaystyle\max\sum_{(a,p)\in E}x_{ap}$ (30) such that
$\displaystyle\sum_{a\in
C}x_{ap}\leq\left\lceil\frac{u_{p,h}}{g}\right\rceil\;,$ $\displaystyle\forall
h\in[\chi],\;\forall p\in P$ (31) $\displaystyle 0\leq x_{ap}\leq 1$
$\displaystyle\forall(a,p)\in E$ (32)

######  Observation 6.10.

Let $x$ be a feasible solution of 4.3, then $\frac{x}{g}$ lies inside the
polytope of 6.9.

Input : $\mathcal{I}$

Output : Distribution over matchings satisfying the guarantees in Theorem 6.8.

1 Solve 4.3 augmented with constraint 5 on $G$ and store the result in $x$

2 $g=\max_{p\in P}|C_{p}|$ (Definition 6.3)

3 For each item $a\in A$, we remove it from every group other than $C_{a}$
where $C_{a}=\operatorname*{arg\,min}_{C\in C_{p}:a\in C}u_{p,h}$. Let the
resulting graph be $G^{\prime}$.

4 $\mathcal{I}^{\prime}=(G^{\prime},A^{\prime}_{1}\cdots
A^{\prime}_{\chi},\vec{l},\vec{u},\vec{L},\vec{U})$

Return Distribution-
Calculator$(\mathcal{I}^{\prime},\frac{x}{g},\lx@cref{creftypecap~refnum}{LP_group_approx})$

Algorithm 6 $g$-BicriteriaApprox$(\mathcal{I}=(G,A_{1}\cdots
A_{\chi},\vec{l},\vec{u},\vec{L},\vec{U}))$

######  Lemma 6.11.

The solution computed by 6.9 in Algorithm 6 is an integer matching that
violates the group fairness constraint 9 by an additive factor of at most
$\Delta$.

###### Proof.

Any optimal solution of LP 6.9 on $G^{\prime}$ is integral if the groups are
disjoint, by Lemma 5.4, therefore, $x$ is an integer matching on $G^{\prime}$.
Let’s fix an arbitrary platform, $p$, and let $T_{p}$ denote a set of groups
such that $A_{h}\cap N(p)\neq\phi$, $\forall h\in T_{p}$. Let us number all
the groups in $T_{p}$ in the ascending order of their upper bounds, breaking
ties arbitrarily, that is, for any two groups say $h_{i},h_{j}\in T_{p}$,
$u_{p,h_{j}}>u_{p,h_{i}}$ iff $j>i$. Let us consider an arbitrary group,
$h_{q}\in[\chi]$, with upper bound $u_{p,h_{q}}$. Any item $a\in A$ that has
been removed from this group in step 6 of Algorithm 6 could only be in one of
the groups from $h_{1}$ to $h_{q-1}$. This is because an item stays in the
group with the lowest upper bound. Let $m_{i}=\displaystyle\sum_{a\in
h_{i}}x_{ap}$, then $m_{i}\leq\left\lceil\frac{u_{p,A_{h}}}{g}\right\rceil$
due to constraint 31. Therefore,

$\sum_{i=1}^{q}m_{i}\leq\sum_{i=1}^{q}\left\lceil\frac{u_{p,h_{i}}}{g}\right\rceil\leq\sum_{i=1}^{q}\left(\frac{u_{p,h_{i}}}{g}+1\right)\leq\sum_{i=1}^{q}\left(\frac{u_{p,h_{q}}}{g}+1\right)\leq\Delta\cdot\frac{u_{p,h_{q}}}{g}+\Delta\leq
u_{p,h_{q}}+\Delta$

The second last inequality holds because any item can belong to at most
$\Delta$ groups. Let $x_{ap}\in\\{0,1\\}$ be the value assigned to an edge
$(a,p)\in E$ in $M$ returned by LP 6.9, then $\displaystyle\sum_{a\in
A_{h}}x_{ap}\leq u_{p,h}+\Delta$ $\forall h\in[\chi]$ after all the items are
returned to all the groups they belonged to in the original graph. Therefore,
$M$ violates constraint 9 by an additive factor of at most $\Delta$. ∎

######  Lemma 6.12.

Given a bipartite graph $G(A,P,E)$ with possibly non-disjoint groups and an
optimal solution of 4.3, Algorithm 6 returns a distribution over integer
matchings such that each matching violates group fairness constraints by an
additive factor of at most $\Delta$, in polynomial time.

###### Proof.

The proof is similar to the proof of Lemma 6.7 with one key difference that in
each iteration, the matching being computed in step 2 of Algorithm 2 does not
satisfy group fairness constraints but violates group fairness constraints by
an additive factor of at most $\Delta$ by Lemma 6.11. ∎

###### Proof of Theorem 6.1.

Let $x$ be any optimal solution of 4.3 augmented with 5, then, Algorithm 6 can
be used to represent $\frac{x}{g}$ as a convex combination of integer
matchings that violate group fairness constraints by an additive factor of at
most $\Delta$, in polynomial time by Lemma 6.12. By setting $\hat{x}=x$,
$\delta=0$, and $t=g$ in Lemma 4.12, we have $\forall a\in A,S\subseteq N(a)$,

$\frac{L_{a,S}}{g}\leq\Pr_{M\sim\mathcal{D}}[M\text{ matches }a\text{ to some
platform in }S]\leq\frac{U_{a,S}}{g}$

The run time of Algorithm 2 has been shown to be polynomial in Lemma 5.7,
since 4.3 can be solved in polynomial time, Algorithm 6 also runs in
polynomial time. This proves the theorem. ∎

##  7 Experiments

In this section, we apply our main contribution, approximation algorithm 1
from Theorem 4.1, on two real-world datasets. The runtime bottleneck of our
primary solution (Algorithm 1) is the execution time of 4.3 (appendix). 4.3 is
a simplified version of 5.1 with polynomial number of variables and
constraints and Algorithm 1 solves 4.3 exactly once. Therefore, this solution
is scalable whenever a practical LP solver is used. In our experiments on
standard datasets, the algorithm performs much better than the
$2(\Delta+1)(\log(n/\epsilon)+1)$ approximation guarantee provided by Theorem
4.1. Here $n$ is the total number of items, $\Delta$ is the maximum number of
groups an item can belong to, and $\epsilon>0$ is a small value. There are no
comparison experiments since there are no benchmarks for solving this exact
problem. We use experiments to validate and demonstrate the practical
efficiency of Algorithm 1.

###  7.1 Datasets

##### Employee Access data

222https://www.kaggle.com/datasets/lucamassaron/amazon-employee-access-
challenge

: This data is from Amazon, collected from 2010-2011, and published on the
Kaggle platform. We use the testing set with 58921 samples for our
experiments. Each row in the dataset represents an access request made by an
employee for some resource within the company. In our model, the employees and
the resources correspond to items and platforms, respectively, and each
request represents an edge. We group the employees based on their role family.
An employee can make multiple requests, each under a different role family.
Therefore, each item can have edges to different platforms and belong to more
than one group. We run our experiments on datasets of sizes 1000, 2000, 3000,
and 5000 sampled from this dataset.

##### Grant Application Data

333https://www.kaggle.com/competitions/unimelb/data

: This data is from the University of Melbourne on grant applications
collected between 2004 and 2008 and published on the Kaggle platform. We use
the training set with 8,707 grant applications for our experiments. In our
model, the applicants and the grants correspond to items and platforms,
respectively, and each grant application represents an edge. We group the
applicants based on their research fields. The same applicant, de-identified
in the dataset, can apply to different grants under different research fields
represented as RFCD code in the dataset. Therefore, each item can have edges
to different platforms and belong to more than one group.

###  7.2 Experimental Setup and Results

We implement our algorithm in Python 3.7 using the libraries NumPy, scipy, and
Pandas. All the experiments we run using Google colab notebook on a virtual
machine with Intel(R) Xeon(R) CPU $@$ $2.20$GHz and $13$GB RAM. Both the
datasets on which we run our algorithm, are taken from Kaggle. We run our
experiments on one complete dataset and three different sample sizes on
another dataset. The sample size denotes the total number of rows present in
the unprocessed sample. The total number of edges can differ from the sample
size after data cleaning like removing null values and dropping duplicate
edges if any. For group fairness bounds, we set the same upper and lower
bounds for each platform group pair. If $n$ is the number of items, $m$ is the
number of platforms, and $g$ is the number of groups, the upper bound is
$\frac{kn}{mg}$, where $k=\lceil\frac{mg}{n}\rceil$. All the lower bounds are
set to $0$. For individual fairness constraints, we first choose a random
permutation of the platforms to create a ranking and then add constraints such
that an item should have $\frac{r}{2}\%$ chance of being matched to a platform
in the top $r\%$ in the ranking. For all the runs, $\epsilon=0.0001$.

We use the solution obtained by solving 5.1 as an upper bound on $OPT$. We
denote it by $UB$, and $SOL$ denotes the expected size of the solution given
by Algorithm 1 on different samples. Let $2(\Delta+1)(\log(n/\epsilon)+1)$ be
denoted by ‘approx’. In Table 2, we compare the actual approximation ratio,
$UB/SOL$, with the theoretical approximation ratio, ‘approx’. As can be seen
in Table 2, in our experiments on standard real datasets, the algorithm
performs much better than the worst-case theoretical guarantee provided by
Algorithm 1. We repeatedly apply our approximation algorithm from Theorem 4.1
on multiple datasets sampled from the Employee Access dataset under the same
experimental setup except for the $\epsilon$-value which is now set to
$0.001$. We see that the algorithm continues to perform much better than the
guarantee of $2(\Delta+1)(\log(n/\epsilon)+1)$ approximation provided in the
analysis of the algorithm in Section 4. The results can be seen in Table 3,
Table 4, Table 5, and Table 6.

Dataset | Sample Size | $\Delta$ | $\frac{UB}{SOL}$ | approx |  no. of match- ings |  run-time (seconds)
---|---|---|---|---|---|---
Employee Access data | 1000 | 3 | 5.43 | 191.2 | 892 | 11
Employee Access data | 2000 | 3 | 7.24 | 196.8 | 1871 | 60
Employee Access data | 3000 | 4 | 9.19 | 250 | 2786 | 180
Employee Access data | 5000 | 4 | 15.98 | 254 | 4651 | 900
Grant Application Data | 8707 | 12 | 7.92 | 652 | 3836 | 540
Table 2: Comparison of solution values on real-world datasets. $\Delta$ | $\frac{UB}{SOL}$ | approx |  no. of mat- chings |  run-time (seconds)
---|---|---|---|---
3 | 6.74 | 164.82 | 914 | 17.1
3 | 3.39 | 164.58 | 908 | 17.8
3 | 4.45 | 164.68 | 923 | 17.8
3 | 6.34 | 164.63 | 897 | 16.6
3 | 5.04 | 164.89 | 913 | 16.7
3 | 3.78 | 164.83 | 905 | 20.4
3 | 3.57 | 164.84 | 914 | 17.7
3 | 5.4 | 164.76 | 904 | 17
2 | 7.33 | 123.54 | 906 | 16.9
2 | 4.11 | 123.6 | 935 | 17.7
Table 3: Comparison of solution values with the theoretical bound for samples of size $1000$. $\Delta$ | $\frac{UB}{SOL}$ | approx |  no. of mat- chings |  run-time (seconds)
---|---|---|---|---
3 | 8.54 | 170.56 | 1852 | 105.5
3 | 9.97 | 170.6 | 1863 | 117
4 | 9.94 | 213.36 | 1850 | 105.1
3 | 8.52 | 170.53 | 1879 | 108.7
3 | 6.53 | 170.76 | 1864 | 109.1
4 | 10.54 | 213.48 | 1868 | 113.3
4 | 9.75 | 213.13 | 1867 | 108.1
4 | 9.55 | 213.17 | 1865 | 105.5
4 | 7.62 | 213.28 | 1848 | 107
3 | 9.60 | 170.79 | 1846 | 103.1
Table 4: Comparison of solution values with the theoretical bound for samples of size $2000$. $\Delta$ | $\frac{UB}{SOL}$ | approx |  no. of mat- chings |  run-time (seconds)
---|---|---|---|---
3 | 9.52 | 173.48 | 2828 | 328.7
4 | 11.86 | 216.69 | 2793 | 384.4
4 | 11.39 | 217.43 | 2816 | 318.7
4 | 14.28 | 217.22 | 2825 | 288.5
4 | 12.0 | 217.08 | 2798 | 317.4
4 | 11.46 | 217.01 | 2797 | 322.7
4 | 10.95 | 216.71 | 2787 | 313.5
4 | 13.54 | 217.05 | 2805 | 290.45
3 | 9.12 | 173.67 | 2791 | 374.6
3 | 8.51 | 173.66 | 2760 | 314.7
Table 5: Comparison of solution values with the theoretical bound for samples of size $3000$. $\Delta$ | $\frac{UB}{SOL}$ | approx |  no. of mat- chings |  run-time (seconds)
---|---|---|---|---
4 | 14.13 | 221.28 | 4671 | 1315.4
4 | 13.28 | 220.78 | 4666 | 1332.6
4 | 12.70 | 221.29 | 4670 | 1298.9
4 | 18.81 | 221.14 | 4661 | 1292.6
4 | 20.97 | 220.89 | 4617 | 1160.8
5 | 13.76 | 265.67 | 4626 | 1494.9
4 | 10.9 | 221.21 | 4646 | 1286.2
5 | 11.95 | 265.23 | 4648 | 1295.6
4 | 20.1 | 221.08 | 4609 | 1166.9
5 | 9.88 | 265.09 | 4658 | 1229.5
Table 6: Comparison of solution values with the theoretical bound for samples
of size $5000$.

##  8 Conclusion

Various notions of group fairness and individual fairness in matching have
been considered. However, to the best of our knowledge, this is the first work
addressing both the individual and group fairness constraints in the same
instance. Our work leads to several interesting open questions like improving
the $O(\Delta\log{n})$ approximation ratio in Theorem 4.1 and extending our
approximation results to the setting with lower bounds, and matching with two-
sided preferences.

##  9 Acknowledgements

We thank Shankar Ram for the initial discussions. AP was supported in part by
the Empower Programme of the Kotak IISc AI-ML Centre and the Walmart Center
for Tech Excellence at IISc (CSR Grant WMGT-23-0001). AL was supported in part
by SERB Award CRG/2023/002896, Pratiksha Trust Young Investigator Award and
the Walmart Center for Tech Excellence at IISc (CSR Grant WMGT-23-0001). PN
was supported by SERB Grant CRG/2019/004757.

## References

  * AAKZ [20] Georg Anegg, Haris Angelidakis, Adam Kurpisz, and Rico Zenklusen.  A technique for obtaining true approximations for k-center with covering constraints.  In Integer Programming and Combinatorial Optimization, 2020.
  * [2] Haris Aziz and Florian Brandl.  Efficient, fair, and incentive-compatible healthcare rationing.  In EC ’21: The 22nd ACM Conf. on Economics and Computation, 2021.
  * [3] Haris Aziz, Anton Baychkov, and Péter Biró.  Summer internship matching with funding constraints.  In Proc. of the 19th Int. Conf. on Autonomous Agents and Multiagent Systems, AAMAS ’20.
  * [4] Haris Aziz, Péter Biró, and Makoto Yokoo.  Matching market design with constraints.  In 36th AAAI Conf. on Artificial Intelligence, AAAI 2022.
  * [5] Haris Aziz, Aditya Ganguly, and Evi Micha.  Best of both worlds fairness under entitlements.  In Proc. of the 2023 Int. Conf. on Autonomous Agents and Multiagent Systems, AAMAS 2023.
  * AS [03] Atila Abdulkadiroglu and T. Sönmez.  School choice: A mechanism design approach.  The American Economic Review, 2003.
  * ASK [07] A. R. Abhyankar, S. A. Soman, and S. A. Khaparde.  Min-max fairness criteria for transmission fixed cost allocation.  IEEE Transactions on Power Systems, 22(4):2094–2104, 2007.
  * [8] Haris Aziz.  Simultaneously achieving ex-ante and ex-post fairness.  In Web and Internet Economics - 16th Int. Conf., WINE 2020, Proc.
  * [9] Suman Kalyan Bera, Deeparnab Chakrabarty, Nicolas Flores, and Maryam Negahbani.  Fair algorithms for clustering.  In Advances in Neural Information Processing Systems 32: Annual Conf. on Neural Information Processing Systems 2019, NeurIPS 2019.
  * [10] Tolga Bolukbasi, Kai-Wei Chang, James Y. Zou, Venkatesh Saligrama, and Adam Tauman Kalai.  Man is to computer programmer as woman is to homemaker? debiasing word embeddings.  In Annual Conf. on Neural Information Processing Systems 2016.
  * [11] Moshe Babaioff, Tomer Ezra, and Uriel Feige.  On best-of-both-worlds fair-share allocations.  In Web and Internet Economics - 18th Int. Conf., WINE 2022, Proc.
  * [12] Hedyeh Beyhaghi and Éva Tardos.  Randomness and Fairness in Two-Sided Matching with Limited Interviews.  In 12th Innovations in TCS Conf. (ITCS 2021).
  * BG [21] D. Bertsekas and R. Gallager.  Data Networks: Second Edition.  Athena Scientific, 2021.
  * Bir [46] Garrett Birkhoff.  Tres observaciones sobre el algebra lineal.  Univ. Nac. Tucuman, Ser. A, 5:147–154, 1946.
  * BLPW [20] Xiaohui Bei, Shengxin Liu, Chung Keung Poon, and Hongao Wang.  Candidate selections with proportional fairness constraints.  In Proc. of the 19th Int. Conf. on Autonomous Agents and Multiagent Systems, AAMAS, 2020.
  * CHRG [16] Matthew Costello, James Hawdon, Thomas Ratliff, and Tyler Grantham.  Who views online extremism? individual attributes leading to exposure.  Comput. Hum. Behav., 2016.
  * [17] L. Elisa Celis, Lingxiao Huang, and Nisheeth K. Vishnoi.  Multiwinner voting with fairness constraints.  In Proc. of the Twenty-Seventh Int. Joint Conf. on Artificial Intelligence, IJCAI 2018.
  * Cow [11] Cowen Institute.  Case studies of school choice and open enrollment in four cities.  Technical report, Cowen Institute, 2011.
  * [19] L. Elisa Celis, Damian Straszak, and Nisheeth K. Vishnoi.  Ranking with fairness constraints.  In 45th Int. Colloquium on Automata, Languages, and Programming, ICALP 2018.
  * CSV [17] L. Elisa Celis, Damian Straszak, and Nisheeth K. Vishnoi.  Ranking with fairness constraints.  In ICALP, 2017.
  * DJK [13] Nikhil R. Devanur, Kamal Jain, and Robert D. Kleinberg.  Randomized primal-dual analysis of ranking for online bipartite matching.  In SODA ’13, 2013.
  * [22] Michael Dinitz, Aravind Srinivasan, Leonidas Tsepenekas, and Anil Vullikanti.  Fair disaster containment via graph-cut problems.  In Int. Conf. on Artificial Intelligence and Statistics, AISTATS 2022.
  * [23] Seyed A. Esmaeili, Sharmila Duppala, Vedant Nanda, Aravind Srinivasan, and John P. Dickerson.  Rawlsian fairness in online bipartite matching: Two-sided, group, and individual.  In 21st Int. Conf. on Autonomous Agents and Multiagent Systems, AAMAS 2022.
  * [24] Michael Feldman, Sorelle A. Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubramanian.  Certifying and removing disparate impact.  In Proc. of the 21th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, 2015.
  * FK [16] Tamás Fleiner and Naoyuki Kamiyama.  A matroid approach to stable matchings with lower quotas.  Math. Oper. Res., 41(2):734–744, 2016.
  * FSABC [21] Golnoosh Farnadi, William St-Arnaud, Behrouz Babaki, and Margarida Carvalho.  Individual fairness in kidney exchange programs.  Proc. of the AAAI Conf. on Artificial Intelligence, 2021.
  * [27] Rupert Freeman, Nisarg Shah, and Rohit Vaish.  Best of both worlds: Ex-ante and ex-post fairness in resource allocation.  In EC ’20: The 21st ACM Conf. on Economics and Computation, 2020.
  * [28] David García-Soriano and Francesco Bonchi.  Maxmin-fair ranking: Individual fairness under group-fairness constraints.  In KDD ’21: The 27th ACM SIGKDD Conf. on Knowledge Discovery and Data Mining, 2021.
  * [29] L. Georgiadis, P. Georgatsos, K. Floros, and S. Sartzetakis.  Lexicographically optimal balanced networks.  In Proc. IEEE INFOCOM 2001.
  * [30] Aadityan Ganesh, Pratik Ghosal, Vishwa Prakash HV, and Prajakta Nimbhorkar.  Fair healthcare rationing to maximize dynamic utilities.  In 27th Pacific-Asia Conf. on Knowledge Discovery and Data Mining, PAKDD 2023.
  * [31] Sruthi Gorantla, Anay Mehrotra, Amit Deshpande, and Anand Louis.  Sampling individually-fair rankings that are always group fair.  In Proceedings of the 2023 AAAI/ACM Conf. on AI, Ethics, and Society, AIES 2023.
  * [32] Hiromichi Goko, Kazuhisa Makino, Shuichi Miyazaki, and Yu Yokoi.  Maximally satisfying lower quotas in the hospitals/residents problem with ties.  In 39th Int. Symposium on Theoretical Aspects of Computer Science, STACS 2022.
  * [33] Yannai A. Gonczarowski, Noam Nisan, Lior Kovalio, and Assaf Romm.  Matching for the israeli: Handling rich diversity requirements.  In Proc. of the 2019 ACM Conf. on Economics and Computation, EC 2019.
  * GSB [20] D. García-Soriano and F. Bonchi.  Fair-by-design matching.  In Data Min Knowl Disc 34, page 1291–1335, 2020.
  * Hah [91] E.L. Hahne.  Round-robin scheduling for max-min fairness in data networks.  IEEE Journal on Selected Areas in Comm., 9(7):1024–1039, 1991.
  * HKMM [16] Chien-Chung Huang, Telikepalli Kavitha, Kurt Mehlhorn, and Dimitrios Michail.  Fair matchings and related problems.  Algorithmica, 74(3):1184–1203, 2016.
  * HLL [12] Hassan Halabian, Ioannis Lambadaris, and Chung-Horng Lung.  Optimal server assignment in multi-server parallel queueing systems with random connectivities and random service failures.  In IEEE Int. Conf. on Comm. (ICC), 2012.
  * HPST [19] David G. Harris, Thomas Pensyl, Aravind Srinivasan, and Khoa Trinh.  A lottery model for center-type problems with outliers.  ACM Trans. Algorithms, 15(3), 2019.
  * [39] Martin Hoefer, Marco Schmalhofer, and Giovanna Varricchio.  Best of both worlds: Agents with entitlements.  In Proc. of the 2023 Int. Conf. on Autonomous Agents and Multiagent Systems, AAMAS 2023.
  * [40] Chien-Chung Huang.  Classified stable matching.  In Proc. of 21st ACM-SIAM Symp. on Discrete Algo., SODA 2010.
  * JMM+ [03] Kamal Jain, Mohammad Mahdian, Evangelos Markakis, Amin Saberi, and Vijay V. Vazirani.  Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP.  J. ACM, 50(6):795–824, 2003.
  * KHIY [17] Ryoji Kurata, Naoto Hamada, Atsushi Iwasaki, and Makoto Yokoo.  Controlled school choice with soft bounds and overlapping types.  J. Artif. Int. Res., 58(1):153–184, 2017.
  * KMM [15] Matthew Kay, Cynthia Matuszek, and Sean A. Munson.  Unequal representation and gender stereotypes in image search results for occupations.  In Proc. of the 33rd ACM Conf. on Human Factors in Computing Systems (CHI), 2015.
  * KRL [22] Till Kletti, Jean-Michel Renders, and Patrick Loiseau.  Introducing the expohedron for efficient pareto-optimal fairness-utility amortizations in repeated rankings.  In Proc. of the 15th ACM Int. Conf. on Web Search and Data Mining, 2022.
  * LNNS [23] Anand Louis, Meghana Nasre, Prajakta Nimbhorkar, and Govind S. Sankar.  Online algorithms for matchings with proportional fairness constraints and diversity constraints.  In ECAI - 26th European Conference on Artificial Intelligence, 2023.
  * Lus [99] Hanan Luss.  On equitable resource allocation problems: A lexicographic minimax approach.  Operations Research, 1999.
  * Man [13] David F Manlove.  Algorithmics of Matching Under Preferences.  WORLD SCIENTIFIC, 2013.
  * MAW [96] Nick McKeown, Venkat Anantharam, and Jean Walrand.  Achieving 100% throughput in an input-queued switch.  In INFOCOM’96, 1996.
  * Meh [13] Aranyak Mehta.  Online matching and ad allocation.  Foundations and Trends® in Theoretical Computer Science, 2013.
  * MSVV [07] Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani.  Adwords and generalized online matching.  J. ACM, 2007.
  * NNP [19] Meghana Nasre, Prajakta Nimbhorkar, and Nada Pulath.  Classified rank-maximal matchings and popular matchings – algorithms and hardness.  In Graph-Theoretic Concepts in Computer Science, pages 244–257, 2019.
  * [52] Gourab K. Patro, Abhijnan Chakraborty, Niloy Ganguly, and Krishna P. Gummadi.  Fair updates in two-sided market platforms: On incrementally updating recommendations.  In AAAI 2020, IAAI 2020,EAAI 2020.
  * Räc [08] Harald Räcke.  Optimal hierarchical decompositions for congestion minimization in networks.  In Proc. of the 40th Annual ACM Symposium on Theory of Computing STOC, pages 255–264. ACM, 2008.
  * RLB [07] Bozidar Radunovic and Jean-Yves Le Boudec.  A unified framework for max-min and min-max fairness with applications.  IEEE/ACM Trans. on Networking, 15(5):1073–1083, 2007.
  * [55] Tom Sühr, Asia J. Biega, Meike Zehlike, Krishna P. Gummadi, and Abhijnan Chakraborty.  Two-sided fairness for repeated matchings in two-sided markets: A case study of a ride-hailing platform.  In Proc. of the 25th ACM SIGKDD Int. Conf. on Knowledge Discovery & Data Mining, KDD ’19.
  * SHS [19] Erel Segal-Halevi and Warut Suksompong.  Democratic fair allocation of indivisible goods.  Artificial Intelligence, 2019.
  * [57] Ashudeep Singh, David Kempe, and Thorsten Joachims.  Fairness in ranking under uncertainty.  In Annual Conf. on Neural Information Processing Systems 2021, NeurIPS 2021.
  * [58] Govind S. Sankar, Anand Louis, Meghana Nasre, and Prajakta Nimbhorkar.  Matchings with group fairness constraints: Online and offline algorithms.  In Proc. of the 30th Int. Joint Conf. on Artificial Intelligence, IJCAI 2021.
  * SY [22] Tayfun Sönmez and M. Bumin Yenmez.  Affirmative action in india via vertical, horizontal, and overlapping reservations.  Econometrica, 90(3):1143–1176, 2022.
  * Vaz [13] V.V. Vazirani.  Approximation Algorithms.  Springer Berlin Heidelberg, 2013.
  * VN [23] Vishwa Prakash H. V. and Prajakta Nimbhorkar.  Weighted proportional allocations of indivisible goods and chores: Insights via matchings, 2023.
  * WS [11] David P. Williamson and David B. Shmoys.  The Design of Approximation Algorithms.  Cambridge University Press, 2011.

##  Appendix A Appendix

###  A.1 Dealing with infeasibility

The introduction of individual fairness constraints introduces the challenge
of having inconsistent constraints that could result in the LPs 4.2 and 5.1
becoming infeasible. To address this, one solution is to introduce a variable
to calculate the smallest multiplicative relaxation of the individual fairness
constraints, ensuring the feasibility of both LPs. Let $t\in[0,1]$ be the
additional variable. Given an instance of our problem, $\mathcal{I}$, with $n$
items and $m$ platforms, we can formulate another LP where the lower bounds on
all the individual fairness constraints are scaled by $t$, and the objective
of this new LP is to maximize $t$.

######  LP A.1.

$\displaystyle\max\quad t$ (33) such that $\displaystyle t\cdot
L_{a,k}\leq\sum_{p\in R_{a,k}}x_{ap}\leq U_{a,k},$ $\displaystyle\forall a\in
A,\forall k\in[m]$ (34) $\displaystyle l_{p}\leq\sum_{a\in N(p)}x_{ap}\leq
u_{p},$ $\displaystyle\forall p\in P$ (35) $\displaystyle
l_{p,h}\leq\sum_{a\in A_{h}}x_{ap}\leq u_{p,h},$ $\displaystyle\forall p\in
P,\forall h\in[\chi]$ (36) $\displaystyle 0\leq t\leq 1$ (37) $\displaystyle
0\leq x_{ap}\leq 1$ $\displaystyle\forall a\in A,\;\forall p\in P$ (38)

Since we address strong group fairness (Definition 3.2) only for disjoint
groups (Section 5), if A.1 is infeasible, then there is no group-fair matching
that satisfies the platform bounds (Equation 36). In this case, we just say
that there is no group-fair matching. If A.1 is feasible, let $t^{*}$ be its
optimal solution, then scaling the lower bounds of all the individual fairness
constraints of 5.1 by $t^{*}$ ensures feasibility. We do not scale down the
upper bounds because that would make the constraint tighter.

It is easy to see how this method can be replicated to 4.2 to ensure
feasibility. Since the group fairness constraints only have upper bounds in
4.2, a group-fair matching will always exist. Therefore, we can always compute
a distribution over group-fair matchings such that the relaxed individual
fairness constraints are satisfied with the approximation factor mentioned in
our result Theorem 4.1. Formally speaking, Algorithm 1 computes a distribution
$\mathcal{D}$ over a set of group-fair matchings such that given the
individual fairness parameters, $L_{a,k},U_{a,k}\in[0,1]$, for each item $a\in
A$ and subset $R_{a,k}$ $\forall$ $k\in[m]$,

$\displaystyle\frac{1}{f_{\epsilon}}\left(t^{*}\cdot
L_{a,k}-\epsilon\right)\leq\Pr_{M\sim\mathcal{D}}[\exists p\in R_{a,k}\textrm{
s.t. }(a,p)\in M]$
$\displaystyle\leq\frac{1}{f_{\epsilon}}\left(U_{a,k}+\epsilon\right).$

Here $f_{\epsilon}=\mathcal{O}(\Delta\log(n/\epsilon))$, $n$ is the total
number of items and each team can belong to at most $\Delta$ groups.

###  A.2 Proof of Lemma 5.4

The integrality of the polytope of $GFLP$ is implicit in [51] where they
construct a flow-network for the Classified Rank-Maximal Matching problem when
the classes of each vertex form a laminar family. We provide an explicit proof
of Lemma 5.4 using the following Claim.

######  Claim A.2.

In any basic feasible solution of $GFLP$, $\displaystyle\sum_{a\in
N(p)}x_{ap}$ is an integer, $\forall p\in P$ if the $l_{p}$, $u_{p}$,
$l_{p,h}$ and $u_{p,h}$ values are integers, $\forall p\in P$, $\forall
h\in[\chi]$.

###### Proof.

Let $x$ be a basic feasible solution of $GFLP$. For an arbitrary platform,
$p^{\prime}\in P$, let there be $r$ groups in $C_{p^{\prime}}$, say
$h_{1},h_{2}\dots h_{r}$. Suppose $\displaystyle\sum_{a\in
N(p^{\prime})}x_{a,p^{\prime}}=\sum_{i=1}^{r}\sum_{a\in h_{i}}x_{ap^{\prime}}$
is not an integer. This implies that there exists at least one group, say
$h_{q}\in C_{p^{\prime}}$, such that $\displaystyle\sum_{a\in
h_{q}}x_{a,p^{\prime}}$ is fractional, which in turn implies that there is at
least one item, say $b\in h_{q}$, such that $x_{bp^{\prime}}$ is fractional.
Let

$\displaystyle\begin{split}&w=\min\Big{(}x_{bp^{\prime}},\lceil
x_{bp^{\prime}}\rceil-x_{bp^{\prime}},\big{\lceil}\sum_{a\in
h_{q}}x_{a,p^{\prime}}\big{\rceil}-\sum_{a\in h_{q}}x_{a,p^{\prime}},\\\
&\big{\lceil}\sum_{a\in N(p^{\prime})}x_{a,p^{\prime}}\big{\rceil}-\sum_{a\in
N(p^{\prime})}x_{a,p^{\prime}},\sum_{a\in
h_{q}}x_{a,p^{\prime}}-\big{\lfloor}\sum_{a\in
h_{q}}x_{a,p^{\prime}}\big{\rfloor}\\\ &,\sum_{a\in
N(p^{\prime})}x_{a,p^{\prime}}-\big{\lfloor}\sum_{a\in
N(p^{\prime})}x_{a,p^{\prime}}\big{\rfloor}\Big{)}.\end{split}$

Since $x_{a,p^{\prime}}$, $\sum_{a\in h_{q}}x_{a,p^{\prime}}$, and $\sum_{a\in
N(p^{\prime})}x_{a,p^{\prime}}$ are not integers by our assumption,
$w\in(0,1)$. Let us modify $x$ by replacing $x_{bp^{\prime}}$ with
$x_{bp^{\prime}}+w$, and let the resulting ordered set be $y$. By the
definition of $w$ and the assumption that $\forall p\in P$, $\forall
h\in[\chi]$, the $u_{p}$ and $u_{p,h}$ values are integers, $y$ doesn’t
violate the constraints 23 to 25. Similarly, since $\forall p\in P$, $\forall
h\in[\chi]$, the $l_{p}$ and $l_{p,h}$ values are assumed to be integers, if
we modify $x$ by replacing $x_{bp^{\prime}}$ with $x_{bp^{\prime}}-w$, the
resulting ordered set, say $z$, will also not violate the constraints 23 to
25. Hence $y$ and $z$ are feasible solutions of $GFLP$. Clearly,

$x=\frac{1}{2}y+\frac{1}{2}z,$

which is a contradiction since a basic feasible solution of any LP cannot be
written as a convex combination of two other points in the polytope of the
same LP. ∎

###### Proof of Lemma 5.4.

Let $x$ be a basic feasible solution of $GFLP$. Let us suppose that $x$ is
fractional. From A.2, we know that $\displaystyle\sum_{a\in N(p)}x_{ap}$ is an
integer, $\forall p\in P$, in any vertex solution of $GFLP$. Therefore, for
some arbitrary platform, say $p^{\prime}\in P$, if there is an edge, say
$(b,p^{\prime})$ where $b\in A$, such that $x_{bp^{\prime}}$ is fractional,
then there must be at least one other edge $(b^{\prime},p^{\prime})$ where
$b^{\prime}\in A$, such that $x_{b^{\prime}p^{\prime}}$ is also fractional.
Let $b\in h_{1}$ and $b^{\prime}\in h_{2}$ where $h_{1},h_{2}\in
C_{p^{\prime}}$ and let $x_{bp^{\prime}}>x_{b^{\prime}p^{\prime}}$ without
loss of generality.

$\displaystyle\begin{split}&w=\min\Big{(}1-x_{bp^{\prime}},x_{b^{\prime}p^{\prime}},\sum_{a\in
h_{1}}x_{ap^{\prime}}-\Big{\lfloor}\sum_{a\in
h_{1}}x_{ap^{\prime}}\Big{\rfloor},\\\ &\sum_{a\in
h_{2}}x_{ap^{\prime}}-\Big{\lfloor}\sum_{a\in
h_{2}}x_{ap^{\prime}}\Big{\rfloor},\Big{\lceil}\sum_{a\in
h_{1}}x_{ap^{\prime}}\Big{\rceil}-\sum_{a\in h_{1}}x_{ap^{\prime}},\\\
&\Big{\lceil}\sum_{a\in h_{2}}x_{ap^{\prime}}\Big{\rceil}-\sum_{a\in
h_{2}}x_{ap^{\prime}}\Big{)}\end{split}$

Let us modify $x$ by replacing $x_{bp^{\prime}}$ and
$x_{b^{\prime}p^{\prime}}$ with $x_{bp^{\prime}}+w$ and
$x_{b^{\prime}p^{\prime}}-w$, respectively, and let the resulting ordered set
be $y$. By the definition of $w$ and the assumption that $\forall p\in P$,
$\forall h\in[\chi]$, the $u_{p,h}$ values are integers, $y$ doesn’t violate
the constraints 24 to 25. Similarly, if we modify $x$ by replacing
$x_{bp^{\prime}}$ and $x_{b^{\prime}p^{\prime}}$ with $x_{bp^{\prime}}-w$ and
$x_{b^{\prime}p^{\prime}}+w$, respectively, the resulting ordered set, say
$z$, will also not violate the constraints 24 to 25. It is easy to see that

$\displaystyle\sum_{a\in N(p^{\prime})}y_{ap^{\prime}}=\sum_{a\in
N(p^{\prime})}z_{ap^{\prime}}=\sum_{a\in N(p^{\prime})}x_{ap^{\prime}}$

Hence $y$ and $z$ also satisfy constraint 23 and hence are feasible solutions
of $GFLP$. Clearly,

$x=\frac{1}{2}y+\frac{1}{2}z,$

which is a contradiction since a basic feasible solution of any LP cannot be
written as a convex combination of two other points in the polytope of the
same LP. ∎

##  Appendix B Extension to other notions of fairness

Before delving into how to extend our results to the fairness notions in
Section 3.2, let us look at a more generic definition of individual fairness
that provides a framework to accommodate various individual fairness settings,
including the one in our problem (Definition 3.3).

######  Definition B.1 (Generic Probabilistic Individual Fairness).

Given individual fairness parameters $L_{a,S}\in[0,1]$ and $U_{a,S}\in[0,1]$
for each item $a$ and each subset $S$ of $N(a)$, where $N(a)$ denotes the
neighborhood of item $a$ in $G$. A distribution $\mathcal{D}$ on matchings in
$G$ is probabilistic individually fair if and only if $\forall a\in A,\forall
S\subseteq N(a)$,

$\displaystyle L_{a,S}\leq\Pr_{M\sim\mathcal{D}}[\exists p\in S\textrm{ s.t.
}(a,p)\in M]\leq U_{a,S}\text{ }$ (39)

It is easy to see how Equation 39 can not only capture the probabilistic
individual fairness constraints in our problem (Definition 3.3) but also
capture the requirement that items are matched to a low-ranking platform in
their preference list with low probability. This model allows users to set
Individual Fairness constraints based on their requirements. All our results
in Theorems 4.1, 6.1, 6.8 and 3.7 can be extended to this notion of fairness
by simply replacing the probabilistic individual fairness constraints in 4.2
and 5.1 with Equation 39. Our results provide the same approximation guarantee
for the Generic Probabilistic Individual Fairness as the Probabilistic
Individual Fairness. The only difference is that the algorithms may not stay
polynomial in the number of nodes and edges of the input graph $G$ due to the
potentially exponential number of constraints in the LPs. However, the runtime
will stay polynomial in the number of subsets with non-trivial bounds in the
input instance.

Next, we will look at extending our results to the fairness notions in Section
3.2. Let the input instance also provide the lower bound on the size of the
resulting matching, say $\zeta$.

1 Input : $LP,z,\zeta$

2 Output : Modified $LP$

31: Update the objective of $LP$ to  $\max z$

42: Add the following constraint to $LP$ $\sum_{(a,p)\in E}x_{ap}\geq\zeta$

3: Return $LP$

Algorithm 7 Update-LP$(LP,z,\zeta)$

###  B.1 Maxmin group fairness

In order to express Maxmin group fairness into 5.1, we first execute Update-
LP(5.1, $\mu,\zeta$). Let us call the resulting LP, $MAXLP$. Now we update
constraint 24 in $MAXLP$ to

$\sum_{(a,p)\in E}x_{ap}-\mu\geq 0,\forall p\in P,\forall h\in[\chi]$ (40)

Equation 40 ensures that even the group with the minimum representation in any
platform has a representation at least $\mu$ and with an objective of
maximizing the value of $\mu$, $MAXLP$, returns a $\mu$ value that maximizes
the representation of the least represented group subject to other
constraints. Let $x^{*},\mu^{*}$ denote an optimal solution of $MAXLP$, then
$x^{*}$ is a feasible solution of 5.1 if we set $l_{p,h}=\mu$, $\forall
h\in[\chi],\forall p\in P$. By replacing Step 1 in Algorithm 4 with ‘Solve
$MAXLP$ on $G$ and store the result in $x,\mu$’ we can obtain the results from
Theorem 3.7 in this setting but the distribution is over a set of maxmin group
fair matching. This proves part of $(1)$ in Theorem 3.11.

###  B.2 Maxmin individual fairness

Let Equation 5 be changed to

$\sum_{p\in P}x_{ap}\geq\mu,\forall a\in A$

Therefore, Maxmin individual fairness constraint can now be expressed into 5.1
and 4.3 by executing $MMLP=$ Update-LP(5.1, $\mu,\zeta$) and $MMLP^{\prime}=$
Update-LP(4.3, $\mu,\zeta$), respectively. Under this setting, where Equation
5 has been updated, if $x^{*},\mu^{*}$ denote an optimal solution of $MMLP$,
then $x^{*}$ is a feasible solution of 5.1. By replacing Step 1 in Algorithm 4
with ‘Solve $MMLP$ on $G$ and store the result in $x,\mu$’ we can obtain the
results from Theorem 3.7 in this setting. This proves $(2)$ of Theorem 3.11.

Similarly if $y^{*},z^{*}$ denote an optimal solution of $MMLP^{\prime}$, then
$y^{*}$ is a feasible solution of 4.3. By replacing Step 1 in Algorithm 1, and
Algorithm 5 with ‘Solve $MMLP^{\prime}$ on $G$ and store the result in
$x,\mu$’ we can obtain the results from Theorem 4.1, and Theorem 6.1 in this
setting where any violation of individual fairness would be a violation of
Maxmin individual fairness. This proves part of $(1)$ and $(2)$ in Theorem
3.12

###  B.3 Mindom group fairness

Mindom group fairness can be expressed into 5.1 and 4.3 by first executing
$MINLP=$ Update-LP(5.1, $-\mu,\zeta$) and $MINLP^{\prime}=$ Update-LP(4.3,
$-\mu,\zeta$), respectively and then by updating constraint 24 and 29 in
$MINLP$ and $MINLP^{\prime}$ respectively to

$\sum_{(a,p)\in E}x_{ap}-\mu\leq 0,\forall p\in P,\forall h\in[\chi]$ (41)

Let $x^{*},\mu^{*}$ denote an optimal solution of $MINLP$, then $x^{*}$ is a
feasible solution of 5.1 if we set $u_{p,h}=\mu$, $\forall h\in[\chi],\forall
p\in P$. Therefore, by replacing Step 1 in Algorithm 4 with ‘Solve $MINLP$ on
$G$ and store the result in $x,\mu$’ we can obtain the results from Theorem
3.7 in this setting but the distribution is over a set of mindom group fair
matching. This proves the remaining parts of $(1)$ in Theorem 3.11.

Similarly, if $y^{*},z^{*}$ denote an optimal solution of $MINLP^{\prime}$,
then $y^{*}$ is a feasible solution of 4.3 if we set $u_{p,h}=\mu$, $\forall
h\in[\chi],\forall p\in P$. Therefore, by replacing Step 1 in Algorithm 1, and
Algorithm 5 with ‘Solve $MINLP^{\prime}$ on $G$ and store the result in
$x,\mu$’ we can obtain the results from Theorem 4.1, and Theorem 6.1 in this
setting but the distribution is over a set of mindom group fair matching for
Theorem 4.1 and any matching in the distribution violates the mindom group
fairness condition by an additive factor of at most $(2-\lambda)\Delta$ for
Theorem 6.1. This proves the remaining parts of $(1)$ and $(2)$ in Theorem
3.12.