PhD Proposal: Probabilistic notions of Fairness for problems in Combinatorial Optimization

Classical Combinatorial Optimization problems such as graph matching, set covering, set packing, and clustering have been extensively studied for over half a century and are relatively well-understood. Recently, there has been growing emphasis on integrating fairness considerations into these classical problems, spurred by several recent studies on discrimination by existing unfair algorithms. This has given rise to a new field known as algorithmic fairness, wherein various fundamental problems are studied under varying notions of fairness.My proposed research focuses on incorporating a probabilistic notion of fairness into these NP-Hard problems. We will begin the talk by motivating our probabilistic notion of fairness. Subsequently, we will introduce proportional fairness, a widely studied notion of group fairness. Then we discuss incorporating this notion into problems such as Graph Matching and Set Packing, and present our algorithms with provable guarantees. Following this, we will introduce fair variants of a set cover problem aiming to capture both group and individual fairness simultaneously. We will then present our algorithms for multiple variants of this problem. Finally, we will talk about open problems and future research directions within the general area of algorithmic fairness.