Group Fairness in Set Packing Problems

Kidney exchange programs (KEPs) typically seek to match incompatible patient-donor pairs based on a utilitarian objective where the number or overall quality of transplants is maximized-implicitly penalizing certain classes of difficult to match (e.g., highly-sensitized) patients. Prioritizing the welfare of highly-sensitized (hard-to-match) patients has been studied as a natural fairness criterion. We formulate the KEP problem as k-set packing with a probabilistic group fairness notion of proportionality fairness-namely, fair k-set packing (FAIRSP). In this work we propose algorithms that take arbitrary proportionality vectors (i.e., policy-informed demands of how to prioritize different groups) and return a probabilistically fair solution with provable guarantees. Our main contributions are randomized algorithms as well as hardness results for FAIRSP variants. Additionally, the tools we introduce serve to audit the price of fairness involved in prioritizing different groups in realistic KEPs and other kset packing applications. We conclude with experiments on synthetic and realistic kidney exchange FAIRSP instances.