Group Fairness in Set Packing Problems

1 Introduction

Fielded kidney exchange programs (KEPs) often employ a utilitarian objective, where the overall utility of successful transplants is maximized. This approach, however, can penalize certain classes of hard-to-match patients (e.g., highly-sensitized, older, O-type blood, and others), as highlighted by many studies from the AI/ML [Dickerson et al., 2014; Li et al., 2014; Farnadi et al., 2021; Sun et al., 2021], economics [Roth et al., 2005; Ashlagi et al., 2019], and medical communities [Ashlagi et al., 2011]. Subsequent research by [McElfresh and Dickerson, 2018] explored two group-fairness criteria-lexicographical fairness and weighted fairness-under random-graph models, and determined that the tradeoff between efficiency and fairness, known as the "price of fairness," is relatively small. However, it should be noted that these guarantees apply only under the assumption of stochastic models in kidney exchange and there is currently a lack of fair algorithms with provable guarantees for the general problem-directed cycle packing-as originally defined [Abraham et al., 2007; Biro et al., 2009]. Several works studied approximation algorithms for KEPs under this model [Biro et al., 2009; Lin et al., 2019; Xiao and Wang, 2018] but none of those algorithms consider fairness; therefore the problem of group fairness in kidney exchange on arbitrary patient-donor graphs presents a unique and intriguing challenge, which can be approached from both theoretical computer science and economics perspectives.

KEPs are often formulated as cycle-packing problems with bounded length cycles, say cycle length at most k. This, in turn, can be reduced to k-set packing 1 by naively enumerating the cycles in O(nk ) worst-case time [Blum et al., 2015]; each cycle, which has l (less than or equal to k) vertices, represents a subset of l elements in the k-set packing formulation.

For the rest of the paper, we lean into kidney exchange to illustrate the need for fairness in the well-known k-set packing problem, though other suitable applications exist such as crew scheduling and barter exchanges. We conduct experiments over a realistic kidney-exchange dataset.

We study here the notion of group-fairness in k-set packing problems. In our model, each of the n elements in the universe U is assigned a color (category), and our goal is to compute a valid packing such that (i) each group is fairly represented satisfying exogenous proportionality constraints and (ii), subject to (i), the overall weight of the packing is maximized. On the flip side, our work is not solely meant to correct so-called unfair algorithms. Rather, the tools we develop also serve as a basis to understand and audit the group-level behavior of algorithms. That is to say, the lack of studies of group-level fairness in k-set packing is representative of missing, but necessary, work towards understanding group outcomes in kidney exchange, equitable crew scheduling, and k-set packing's other applications. Thus, we view our work as an important step towards understanding group-level fairness in kidney exchange.

Let [t] denote the set {1, 2, . . . , t}. In fair k-set packing, denoted FAIRSP, we are given a set of elements U = [n] and a collection S = {S1, . . . , Sm} of subsets of U where

1 The k-set packing problem is set packing over a universe U and collection of subsets S of U restricted to each S ∈ S having at most k elements. For k ≥ 3, it is NP-hard [Karp, 1972].

|Si| ≤ k for each Si. Each subset Si ∈ S has weight wi ≥ 0. Moreover, each u ∈ U is assigned one of c colors by C : U → [c]; i.e., each u belongs to one of c groups. We are also given a proportionality vector ⃗ p ∈ [0, 1]c such that ∑ℓ∈[c] pℓ = 1. The objective of FAIRSP is to select a packing 2 of maximum weight subject to a pℓ fraction of the packing consisting of elements with color ℓ: i.e., letting yi = 1 if Si is selected and yi = 0 otherwise, we aim to maximize ∑i∈[m] wiyi subject to the proportionality constraint.

However, many instances become immediately infeasible under these additional constraints. For example, let us consider an instance with U = {r, b1, b2, g1, g2}, S1 = {r, b1, b2}, S2 = {r, g1, g2}, and ⃗ p = [1/3, 1/3, 1/3]; here r, bi's, and gi's are colored red, blue, and green, respectively. Clearly, there does not exist a feasible (non-empty) fair packing. Instead, the fairness constraints can be satisfied in expectation by switching our target to a distribution over packings (say, pick each set with probability 1/2).

Observation 1. The integrality gap of the LP corresponding to FAIRSP is unbounded.

Therefore, we shift our attention to randomized notions of fairness. Such probabilistic fairness guarantees have been previously studied by [Asudeh et al., 2022; Bastani et al., 2019]. This motivates our work's exploration of randomized algorithms and probabilistic fairness.

Any randomized packing algorithm ALG is captured by a distribution D over the set of all packings; i.e., running ALG is akin to sampling from the distribution D. Let Zi = 1, i ∈ [m], indicate that Si is selected in the packing returned by ALG (Zi = 0 otherwise). Letting viℓ be the number of elements of color ℓ in Si, we have Nℓ := ∑i∈[m] viℓZi and N := ∑ℓ∈[c] Nℓ. We focus our study on FAIRSP, defined as follows: Given U, S, wi ≥ 0, C : U → [c] (as defined in FAIRSP), FAIRSP seeks a distribution D such that EZ∼D[∑i∈[m] wiZi] is maximized while satisfying the proportional constraints in expectation i.e., for any color ℓ, E[Nℓ] = pℓE[N] holds. We require E[N] > 0 to rule out the distribution with support only over the empty set.

In this paper, we study randomized algorithms for FAIRSP, with a focus on two specific randomized fairness notions outlined in Section 3. We drop the word probabilistic while referring to the proportionality constraints of FAIRSP for brevity.

2 RelatedWork

k-set packing is a well-studied problem in combinatorial optimization. For k = 2 the problem is maximum-weight matching, which can be solved in polynomial time, and for k = 3 the problem becomes APX-hard [Hazan et al., 2006]. To the best of our knowledge, the problem closest to our formulation is k-set packing. In the past, the best algorithms for both the weighted and unweighted variants depend on localsearch techniques with an approximation ratio of ( k+1 2 + ϵ) [Berman, 2000] and ( k+1 3 + ϵ) [F¨urer and Yu, 2014] respectively. However, recently, [Neuwohner, 2021] improved upon the weighted variant, achieving an approximation ratio of k+ϵk 2 3 . KEPs were formulated as instances of k-set packing in [Biro et al., 2009] for the study of approximation algorithms. Specifically, [Biro et al., 2009] developed a k -1+ ϵ approximation algorithm based on the local search technique utilizing augmenting paths.

2 A packing is a collection of pairwise disjoint subsets of S.

It is known that the natural LP-relaxation for k-set packing has an integrality gap at least k -1+ 1k [F¨uredi et al., 1993]. [Brubach et al., 2019] gives a k + ϵk-approximate algorithm based on LP rounding that almost matches this lower bound. [Anegg et al., 2021] simplified the analysis of [Brubach et al., 2019] and improved the approximation factor to k - ϵk. The problem is Ω( k log k )-hard to approximate [Hazan et al., 2006] (i.e., even an efficient O( k log k )-approximation seems unlikely).

To our knowledge, fair k-set packing has not been studied before for a general k, although the special case of k = 2 (i.e., maximum-weight matching) has been explored extensively under both group-[Sankar et al., 2021; Ma et al., 2022; Nanda et al., 2020] and individual- [Garc´ıa-Soriano and Bonchi, 2020] fairness. Fair Matching has been studied under various group-fairness notions such as lexicographical fairness [Garc´ıa-Soriano and Bonchi, 2020] and Rawlsian (maxmin) group fairness [Ma et al., 2022; Esmaeili et al., 2023]; both have been studied in online and offline settings.

A great deal of work in fair algorithm design uses the framework of modeling the problem as an optimization problem with precisely defined fairness constraints and vice-versa [Sankar et al., 2021]. Group-level fairness has been studied in various settings [Diana et al., 2021; Tsang et al., 2019; Ma et al., 2022]. [Asudeh et al., 2022] considered group-level proportionality fairness (both deterministic and randomized) for the fair maximum coverage problem which is closely related to the set packing problem.

3 Preliminaries andMain Contributions

Throughout this paper, we denote [n] = {1, . . . , n} for any positive integer n; we use OPT to denote both an optimal algorithm and its objective value; and analogously ALG for both a generic algorithm and its objective value. We use ϵn to denote a vanishing term i.e., limn→0 ϵn = 0. We use either {Yi} or {Yi}i∈[m] to refer to the set of variables {Y1, Y2, . . . , Ym} interchangeably.

Approximation Factor. For NP-hard combinatorial optimization problems, we utilize the powerful framework of approximation algorithms, where the aim is to design efficient algorithms (polynomial running time) with provably nearoptimal objectives values.

We say ALG achieves an approximation factor of α ≥ 1 if αE[ALG] ≥ OPT across all feasible FAIRSP instances.

Parameters. The complexity of FAIRSP can depend on the following parameters; number of colors c; maximum element frequency f ∈ [m], where the frequency of an element is the number of sets it belongs to; and k ∈ [n]. The k-restrained variant is necessary in applications such as crew scheduling and kidney exchange, as motivated by prior work [Bir´o et al., 2019]. Moreover, the natural LP for k-set packing (LP (3) without the constraints (3c)) has integrality gap of at least k - 1 + 1k and there exists a (k - ϵk)-approximate algorithm by [Anegg et al., 2021]. Note our algorithmic results are parameterized on k, c and f .

3 We use ϵn to denote a vanishing term i.e., limn→0 ϵn = 0.

We study algorithms with approximation guarantees on the packing objective and fairness of FAIRSP. We make this precise via two related fairness guarantees for randomized algorithms of FAIRSP.

Randomized approximate Fairness (RF). For any two colors ℓ, q ∈ [c],

The guarantee above is fair only in expectation. It is possible for a single realized packing to be very unfair itself. We address this next via a stronger notion of randomized proportional fairness.

Strongly Randomized approximate Fairness (SRF).

If a randomized algorithm ALG, satisfies the inequalities (1) and (2), then it is said to have a fairness factor γ with respect to RF and SRF respectively. RF and SRF, respectively, are ex-ante and ex-post fairness guarantees for FAIRSP algorithms with respect to the proportionality vector and underlying groups (colors). In Section 4 we give algorithms for FAIRSP with varied approximation guarantees on the packing objective and RF or SRF guarantees with fairness factor γ.

Connections to existing works. For k ≥ 3, the problem of k-set packing is well-studied, and several previous works (such as [Bansal et al., 2010; Brubach et al., 2019; Anegg et al., 2021]) have focused on developing algorithms based on the natural LP relaxation of k-set packing. The primary motivation for using LP rounding techniques is the ease of incorporating proportionality constraints as additional constraints in the LP, as demonstrated in LP (3). Our main technical challenge is to adapt these rounding algorithms in such a way that they produce packings with a small approximation factor and fairness ratio γ simultaneously.

Choosing a proportionality vector. Previous studies such as [Chierichetti et al., 2017; Bei et al., 2022] have examined a concept of proportional fairness that is broader than the one used in our work. They apply upper and lower bound constraints on the desired proportional representation of each group in the solution. In contrast, we use a special case where the upper and lower bounds coincide, meaning we insist on the final packing solution exactly preserving the proportional constraints.

Our algorithms take an input parameter ⃗ p and output a corresponding fair solution, assuming that the given instance is feasible. Determining an appropriate ⃗ p is intentionally deferred to stakeholders and policymakers. The question of how to fairly allocate resources to groups is an ongoing topic of debate which we make no attempt to conclude (e.g. see [Roth, 2015]). Nevertheless, we view our work as progress toward formalizing and facilitating discussion of group-level fairness in kidney exchange [McElfresh and Dickerson, 2018] and other k-set packing applications. For example, the ⃗ p corresponding to an optimal packing has optimal Price of Fairness (PoF); i.e., there is no cost to the objective. On the other hand, other choices of ⃗ p may come at a great PoF. For a policymaker to advocate for proportional group fairness, it is imperative they be able to articulate this trade-off. Our work is a step towards formalizing these necessary tools. Indeed, we explicitly view our work as descriptive, not prescriptive-we can map out a form of Pareto frontier (as in Figure 1) balancing the "tightness" imposed by the proportionality vector (x-axis) against the overall utility of the solution (y-axis). Then, a domain expert could use this for decision support when choosing the proper balance.

3.1 Main Contributions

We study the problem of FAIRSP, a probabilistic fair variant of the k-set packing problem. We motivate the probabilistic fairness notions (RF and SRF as defined in (1) and (2) resp.) by first showing that the deterministic fair variant FAIRSP has unbounded integrality gap for the natural LP relaxation of the problem.

We provide two algorithms FAIRSAMPLE and FAIRELIMINATE that respectively guarantee RF (with γ ≈ 1 w.h.p. and approximation factor α ≤ k + ϵn) and SRF (with γ = O(1) and α = O(ck2 ) where c is the number of colors). We say sufficiently large packing size to mean the fractional number of elements selected in the optimal LP (3) solution, i.e., ∑i∈[m] ∑ℓ∈[c] viℓy∗ i , is sufficiently large.

Theorem 1. For any instance of FAIRSP, FAIRSAMPLE is a randomized, polynomial-time algorithm with an approximation factor (k + ϵk) on the packing objective. Moreover, with probability 1 - ϵL, FAIRSAMPLE guarantees RF with γ = 1 + ϵL where L is a tunable parameter.

Theorem 2. For any instance of FAIRSP satisfying f = o(√n) and pℓ = Θ(1/c) for all ℓ ∈ [c], FAIRELIMINATE

is a randomized, polynomial-time algorithm with an approximation factor O(ck2 ) on the packing objective. Moreover, for instances with sufficiently large packing size, FAIRELIMINATE guarantees SRF with γ = O(1) .

Theorem 3. For any instance of FAIRSP satisfying f = o(n/k6 c4 ) and pℓ = Θ(1/c) for all ℓ ∈ [c], FAIRELIMINATE is a randomized, polynomial-time algorithm with an approximation factor of O(ck2 ) on the packing objective. Moreover, for instances with sufficiently large packing size, FAIRELIMINATE guarantees SRF with γ = O(1).

Remark 1. Theorem 3 is a stronger result than Theorem 1 since the former allows for instances with f (maximum frequency of any element) asymptotically larger than that of the latter.

Note that stronger fairness guarantees of FAIRELIMINATE holds for the family of FAIRSP instances satisfying: (i) the frequency of any element is bounded by n1-o(1) , e.g., f = o(n) for k = O(logn) and c = O(logn), (ii) the proportionality vector satisfies pℓ = Θ(1/c) for all ℓ, and (iii) the packing size is sufficiently large.

The input parameter a to FAIRELIMINATE is carefully chosen to balance both γ and α. For the family of instances with constant number of colors c, and sufficiently large packing size we prove that γ = O(1) and α = O(k2 ). For many practical real-world applications, like kidney-exchange markets, k is a very small number, say 2 or 3, thus resulting in a reasonable (constant) approximation factor for both FAIRSAMPLE and FAIRELIMINATE, along with the desired fairness guarantees.

Notice that k-set packing is a special case of FAIRSP with c = 1, hence the integrality gap of LP (3) is at least k-1+1/k [F¨uredi et al., 1993]. Therefore, our approximation factor for FAIRSAMPLE almost matches the lower bound and further guarantees RF with γ arbitrarily close to optimal i.e., 1.

Whereas, FAIRSAMPLE only guarantees fairness in expectation-with no promises on the ex-post fairness of the allocation-FAIRELIMINATE guarantees the stronger SRF with γ = O(1) and approximation factor α = O(ck2 ).

Finally, in Section 5, we support these theoretical results with experiments on synthetic datasets, including a realistic dataset drawn from a real-world kidney exchange.

4 Randomized Algorithms

In this section we focus on randomized algorithms for FAIRSP with RF and SRF guarantees. Our algorithms are based on rounding optimal Linear Program (LP) solutions. The LP formulation for FAIRSP, found in LP (3), is the standard LP formulation of set packing with added fairness constraints. Due to space constraints, we omit the proofs from this section.

Theorem 4. The optimal value of LP (3) is an upper bound on the objective of FAIRSP.

Proof. Consider an optimal randomized algorithm OPT 4 for FAIRSP. For each i ∈ [m], let yi be the probability that Si is packed by the randomized algorithm OPT. We can verify that the LP objective (3a) captures the exact value of OPT (i.e., the max expected weight of the packing). Therefore, to prove our claim it suffices to show that {yi}i∈[m] is a feasible point of LP (3). For each i ∈ [m], let Yi denote the indicator random variable that set Si is selected by OPT. OPT can be viewed as a distribution over all feasible deterministic algorithms, any realization {Yi} satifsies ∑j∈Si Yi ≤ 1 for each j ∈ [n]. Therefore, E[∑j∈Si Yi] ≤ 1 which satisfies (3b). Since OPT is optimal for FAIRSP, for each color ℓ ∈ [c], {Yi} must satisfy proportional constraints in expectation i.e., E[Nℓ] = pℓE[N], so (3c) is satisfied. Lastly, since {yi} are probabilities, (3d) is satisfied.

Lemma 1. An instance of FAIRSP is feasible if and only if its corresponding LP (3) has a non-zero feasible solution.

By Lemma 1 we can efficiently verify whether the underlying FAIRSP instance is feasible. Moreover, this implies our algorithms abort only when the underlying FAIRSP instance is infeasible.

Algorithmic challenges and techniques. As highlighted in the introduction, randomized algorithms can be substantially more powerful than deterministic ones on the objective studied here; however, the design and analysis of a randomized algorithm can be technically challenging mainly due to the craft involved in using randomness and analysis of such random variables. Several existing dependent rounding methods [Bansal et al., 2010; Brubach et al., 2019; Anegg et al., 2021] for k-set packing are based on randomized rounding (which samples subsets based on an LP solution) followed by suitable alterations (which drops some sets to ensure a packing is returned) that lead to a feasible packing with good approximation guarantees. However, the packing returned by these algorithms is far from satisfying any fairness constraints. Thus the main challenge we address is designing packing algorithms guaranteeing RF and SRF. Our primary contribution is the two algorithms, FAIRSAMPLE and FAIRELIMINATE, which are tailored to guarantee RF and SRF, respectively. Our algorithms utilize a randomized dependent rounding method, drawing inspiration from the works of [Bansal et al., 2010] and [Brubach et al., 2019], to optimize the packing objective function. Additionally, we modify existing algorithms to further provide probabilistic fairness guarantees (minimizing γ). In rest of the paper we use simulation to refer to Monte Carlo simulation.

1. We augment the rounding method of [Brubach et al., 2019] with a simulation based method to tightly bound the probability of selecting any subset Si, i ∈ [m]. Thus, guaranteeing RF with near-optimal γ (i.e., γ = 1+ϵL5 ). (See Theorem 1)

4 We use OPT for both the optimal algorithm and the optimal objective value interchangeably.

5L is the number of simulations in FAIRSAMPLE.

1. Although FAIRSAMPLE provides a better approximation on the packing objective than FAIRELIMINATE, it is hard to provide a useful lowertail bound of Nℓ since the random variables {Zi}i∈[m] are highly dependent. We use a much more intricate analysis on the simpler FAIRELIMINATE using concentration bounds from [Janson and Ruci ´nski, 2002] which guarantee SRF with γ = O(1) (a small constant), under reasonable assumptions on the input instances (See Theorems 2 and 3).

4.1 FAIRSAMPLE for RF Guarantees

We obtain FAIRSAMPLE, Algorithm 1, by augmenting the rounding algorithm from [Brubach et al., 2019] with an additional simulation step (step 13). The purpose behind the simulation-based sampling is to "tightly" bound E[Nℓ] for each color ℓ; the importance of this step is discussed in the "Intuition behind the analysis of FAIRSAMPLE". The probability of satisfying RF with γ = 1+ϵL depends on the number of simulations L. Nevertheless, L needs only be polynomial in the problem size for high-quality results. For more details on the simulation-based sampling method see the works of [Ma, 2014; Adamczyk et al., 2015].

Steps 1-4 FAIRSAMPLE solves the LP of the given FAIRSP instance or aborts if the LP is infeasible. Steps 7-10 Next, it runs randomized rounding on each variable using a carefully chosen function f(y∗ i ) on the optimal LP solution {y∗ i }. In the alteration step, the variables rounded to 1 are dropped based on a randomly ordered permutation generated in the previous step. These steps are repeated for L rounds. Steps 13- 15 Finally, with the previous L simulations, we have estimated q′i ≈ Pr(Si ∈ F2) for each i ∈ [m]. This ensures that Pr(Si ∈ F) ≈ y∗ i k+ k exp k , which is crucial to the analysis. Theorem 1 formalizes the approximation guarantees provided by FAIRSAMPLE for the objective and RF fairness ratio.

Intuition behind the analysis of FAIRSAMPLE. The first part of FAIRSAMPLE, steps 1-11, is similar to that of [Brubach et al., 2019], thus leading to k + ϵk approximation on packing objective. The remaining steps of FAIRSAMPLE ensure a tight upper bound on E[Nℓ] for each color ℓ. This is crucial to upper bounding E[Nℓ]/E[Nℓ′ ] for each pair of colors ℓ and ℓ′ , thus giving a suitable γ.

Theorem 1 demonstrates that FAIRSAMPLE has an approximation factor of (k + k exp(k) ) for the packing objective, and it guarantees RF with a γ = 1 + ϵL, which can be made arbitrarily close to optimal (γ = 1) with more simulations. However, it should be noted that the fairness guarantees of FAIRSAMPLE only hold with high probability, as they depend on the simulation step. Nevertheless, the experimental results in Section 5 show FAIRSAMPLE consistently achieves γ ≈ 1 even with only a few simulations.

Note that Theorem 1 only guarantees fairness in expectation-there are no guarantees on the ex-post fairness of the allocation. This shifts our attention to FAIRELIMINATE.

Algorithm 1 FAIRSAMPLE

Require: Number of Monte Carlo simulations L.

• 1: Solve LP (3) to get an optimal fractional solution {y∗ i }i∈[m].
• 2: if LP (3) is infeasible then
• 3: return "Infeasible"
• 4: end if
• 5: For all i ∈ [m], set Li = 0.
• 6: for j = 1, . . . ,L do
• 7: Construct F1 by sampling each set Si with probability f(y∗ i ) where f(x) = x(1 - x2 ).
• 8: For each Si ∈ F1, sample xi ∼ U(0, 1).
• 9: Build the valid packing F2 as follows. In increasing order of xi, pack Si if it does not intersect a previously selected set.
• 10: For each Si ∈ F2, increment Li by 1.
• 11: end for
• 12: Keep the packing F2 from the last run of the above loop.
• 13: Set q′i = Li/L for each i ∈ [m].
• 14: Shrink F2 into F as follows. For each Si ∈ F2, keep Si with probability y∗ i (q′i+ϵ)(k+ k ) .

exp (k)

• 15: return The packing F.

4.2 FAIRELIMINATE for SRF Guarantees

FAIRELIMINATE, Algorithm 2, incorporates randomized rounding followed by alterations, similar to [Bansal et al., 2010]. In the randomized rounding step, we select each Si independently based on a attenuation function ay∗ i k where a is a small constant. The main difference between FAIRELIMINATE and existing algorithms is allowing for an appropriate parameter a that results in a collection of sets with acceptable "expected packing weight" and "expected cardinality 6 ". The alteration step ensures a packing is returned by discarding intersecting sets while maintaining good expected weight and not losing too many elements of any color.

To guarantee SRF, we need concentration bounds on the upper and lower tails of Nℓ. Our randomized rounding procedure lets us upper bound Nℓ as a sum of independent random variables, making it easy to apply Hoeffding bounds on the upper tail. However, the critical part of the analysis is establishing a concentration on the lowerbound of Nℓ. We solve this problem by a clever application of the Deletion Method by [Janson and Ruci´nski, 2002].

Steps 1-4 are common between FAIRSAMPLE and FAIRELIMINATE. Steps 5-6 Each variable Yi is rounded w.r.t function ay∗ i k for a small constant a > 0; let F denote the set of all subsets that are sampled in this step. Steps 7-12 Then, in the alteration step, the algorithm removes any sets that intersect with other sets in F, and returns the remaining sets as the final packing. Theorems 2 and 3 state the approximation guarantees provided by FAIRELIMINATE on both the objective and SRF.

Intuition behind the analysis of FAIRELIMINATE. The key idea behind FAIRELIMINATE is to choose an appropriate value for a7 such that randomized rounding results in a set of variables {Yi} with an acceptable "expected weight".

6 Expected cardinality refers to the expected number of elements selected in this step i.e., E[∑i∈[m] |Si|Yi].

7 The value of a > 0 is selected via the analysis of the algorithm.

Algorithm 2 FAIRELIMINATE

• i k ) for a small constant

We then prove that the expected number of variables dropped in the alteration step is minimal, resulting in a high-quality approximation of the packing objective.

It's important to note the {Zi} are dependent random variables with both negative and positive correlations. As a result, we cannot directly use the Chernoff-Hoeffding bounds that are applied to sums of negatively correlated random variables, as outlined in [Panconesi and Srinivasan, 1997]. This creates a challenge in achieving concentration on the desired value of Nℓ. Instead we express Zi as a function of the independent {Yi}, allowing us to utilize various results on the polynomials of independent random variables such as [Kim and Vu, 2000; Janson and Ruci´nski, 2002; Schudy and Sviridenko, 2011]. We know that the random variable Zi takes the value either 1 or 0 based on two events: (i) the random variable Yi = 1 in the randomized rounding step, and (ii) none of its neighbors j ∈ N(i)8 have Yj = 1. Therefore, Zi = Yi(1 - maxj∈N(i) Yj), allowing us to express Nℓ as follows:

By applying the Hoeffding bound [Hoeffding, 1994], we can show that Aℓ = ∑i∈[m] viℓYi is concentrated around its mean with probability p. Additionally, we can use the Deletion method by [Janson and Ruci´nski, 2002] to prove that B is also concentrated around its mean with probability q. The crucial step in applying the Deletion Method is the construction of a hypergraph on the random variables {Yi}, which can be challenging. Finally, by a union bound and suitable p and q, we find concentration on the lower bound of Aℓ - 2kB.

Theorem 2 is a direct outcome of this approach. Theorem 3 is an enhancement of Theorem 2 resulting from a more refined analysis of the concentration of B in the Deletion Method. The complete justification for these theorems can be found in the full version of the paper.

8N(i) = {Sj : Si ∩Sj ̸= ∅}.

5 Experiments

Our experiments run on commodity hardware using Python 3.6 with NumPy [Harris et al., 2020] as well as IP and LP solvers in Gurobi 9.1.2. The empirical evaluation of our algorithms uses both purely synthetic and realistic kidney exchange FAIRSP instances. To benchmark our algorithms, we include i) ALG-BLIND, the LP-rounding (fairness agnostic) k-set packing randomized algorithm from [Brubach et al., 2019] as well as ii) IP-FSP and iii) IP-BLIND, which solve the integer restrictions of LP (3) with and without fairness constraints, respectively. The integer restrictions of IP-FSP and IP-BLIND make the fairness guarantee be satisfied deterministically as opposed to in expectation like RF.

Evaluation of randomized algorithms. FAIRSAMPLE and ALG-BLIND provide objective guarantees in expectation thus their reported objective values are the mean objectives of 300 independent LP solution roundings. FAIRSAMPLE uses L = 300 to estimate q′i values. Since FAIRELIMINATE provides ex-post fairness guarantees the reported objective values correspond to a single LP rounding per FAIRSP instance.

Kidney exchange datasets. We use realistic kidney exchange instances drawn from the US-based United Network for Organ Sharing (UNOS) fielded exchange program; our synthetic instances are generated from this data in the standard way [Dickerson et al., 2019]. In real programs, 9 both blood type and patient sensitization, a measure that is high when a patient's body has built up many antibodies to potential donor organs, are taken into account when deciding what type of participant to prioritize. Thus, in our experiments, we treat sensitization as a binary sensitive attribute (taking value 1 if the patient is sensitized and 0 otherwise), and separately treat patient blood type as a different binary sensitive attribute (taking value 1 if the patient is a hardto-match O-type blood, and 0 otherwise). These binary attributes give rise to two datasets, each with c = 2, which we call the blood group and sensitization datasets. We generate graphs of size 64, 128, 256, and 512 from that real data, noting that the largest exchanges in the world hover at or slightly below 256. 11 Recall as mentioned in the introduction, the FAIRSP instances have S consisting of all 2- and 3-cycles in said graphs. As a result, the largest FAIRSP instances have n = 512 and m ≈ 28000. We omit IP solutions for these largest instances as solving them takes too long and they only serve to motivate probabilistic fairness. Each graph size has 32 instances for which we create fair instances with proportionality vector ⃗ p ∈ {(0.25, 0.75), (0.5, 0.5), (0.75, 0.25)}. wi = |Si| for all Si ∈ S, and k = 3.

9 For example, the OPTN/UNOS 10 exchange transparently reports its prioritization points in Table 13-2; high values for the sensitization metric CPRA are prioritized extensively, and O-type candidates are prioritized as well. For summaries of countries' exchanges in the European Union and the United Kingdom, we refer the reader to [Bir´o et al., 2019].

10 https://optn.transplant.hrsa.gov/media/3390/ optn-policies-effective-as-of-dec-4-2019-board-adoptions.pdf

11 As examples, we direct the reader to [Bir´o et al., 2019], a recent survey of 17 European countries' national exchange programs, stating that the UK "has become the largest operating [kidney exchange program] in Europe, with 250 recipient-donor pairs registered per matching run," followed by the Netherlands and then Spain, with 110 recipient-donor pairs registered per run, and a long tail of countries afterward. In the US, programs tend to match at a faster cadence

Experiments on kidney exchange datasets. Altogether, the experiments solve a total of 864 IPs with fairness constraints, 960 LPs with fairness constraints, 96 IPs without fairness constraints and 128 LPs without fairness constraints. Both FAIRSAMPLE and FAIRELIMINATE produce solutions swiftly, taking up to 7 minutes for the largest instances. In both cases the bottleneck is solving the LP. Given there are multiple FAIRSP instances per graph size, the plots report the mean over all instances and the shaded regions capture 95% of the instances.

Figure 1 uses all 32 instances with n = 256 from the blood group dataset over each of 40 choices of ⃗ p; hence running FAIRSAMPLE 1280 times in 9 hours. Figure 2 shows FAIRSAMPLE achieves remarkably improved fairness at little cost to the objective compared to its fairness agnostic counterparts ALG-BLIND and IP-BLIND. IP-FSP also ran into several infeasible instances while this was never an issue for FAIRSAMPLE, further making the case for probabilistic fairness.

Experiments in Figure 3 use FAIRELIMINATE to round the 960 LPs with fairness constraints with 25 evenly spaced choices of the parameter a ∈ [0.1, 0.99]. Both the approximation and fairness factors improve as a increases. Although the worst-case guarantees in Theorem 3 are valid for a < (1-δ)p∗ /6k (for any δ > 0), in this real-world example the fairness guarantees continue to improve as a approaches 1. One explanation is that as a increases, the number of initially sampled sets increases but so does the number of sets dropped in the alterations step; however, since our instances are sparse the number of sets dropped is not too high. For comparison, we include the approximation and fairness factors from a single rounding of FAIRSAMPLE. Interestingly, here FAIRSAMPLE outperforms FAIRELIMINATE in ex-post fairness. One possible explanation is that the realistic instances are far fromworst-case.

which can keep pool sizes low; for example, arguably the most successful program in the US, which is run by the National Kidney Registry (NKR), had a pool size hovering around 150 recipient-donor pairs in Q1 2022 [National Kidney Registry, 2022].

DatasetMaxK. We generate 200 purely synthetic FAIRSP instances with n = 50, m = 1000, c ∈ {2, 3}, and ⃗ p generated uniformly at random. Each instance has a parameter max k ∈ {3, 8, 13, . . . , 49}. For each parameter configuration above, we independently generate 10 instances. Then this parameter max k is used to sample sets. For each i ∈ [m], Si ∈ S is a random subset of U with cardinality ki ∼ N(max k, 2) (while ensuring ki stays in between 2 and 50). For each Si ∈ S, wi is an integer drawn uniformly between 5 and 35. Element colors are chosen uniformly at random. As expected, the objectives decrease as k increases, thus the approximation factor of FAIRSAMPLE increases alongside k.

Acknowledgments

We thank the anonymous reviewers for their insightful comments that helped improve the paper. This research was supported in part by NSF CAREER Award IIS1846237, NSF Award CCF-1918749, NSF Award CCF1852352, NSF Award SMA-2039862, NIST MSE Award #20126334, DARPA GARD #HR00112020007, DARPA SI3-CMD #S4761, DoD WHS Award #HQ003420F0035, ARPA-E DIFFERENTIATE Award #1257037, ARL Award W911NF2120076, LTS MAGICAPPLE, and gifts by research awards from Amazon, and Google.