PhD Defense: ALGORITHMIC FAIRNESS AND ONLINE DECISION MAKING IN COMBINATORIAL OPTIMIZATION AND UNSUPERVISED LEARNING

Classical combinatorial and unsupervised learning problems such as graph matching, set packing, and clustering are commonly used to model large-scale real-world applications. Examples of such applications include facility location problems to provide services in emergency, online advertising markets (matching ads to customers), organ exchanges which involves patient-donor pairs to exchange organs, recommending applicants to jobs, assigning jobs to servers, clustering of points, among others.The classical variants of these problems are extensively studied and are reasonably well-understood. Recently, there has been a growing emphasis on integrating fairness considerations into these classical problems spurred due to the bias in existing algorithms. This has given rise to a growing field known as algorithmic fairness. The goal of this research is to introduce novel online and fair variants of these problems by generalizing the classical formulations into two not necessarily disjoint directions. First, we integrate meaningful and rigorous notions of fairness into classical problems to formulate fair variants of the problem. Second, we address input uncertainty by extending classical problems into online and robust formulations. Specifically, we model probabilistic and deterministic uncertainty in input to provide average-case performance and worst-case robustness guarantees, respectively. In this thesis we focus on designing algorithms with provable guarantees for fair, online and robust variants of the aforementioned problems.In the first part of the thesis we study fair variants of classical combinatorial optimization problems like graph matching, online bipartite matching and set packing. Particularly, we study these problems under well-studied notions of group fairness called proportionality fairness and Rawlsian (max-min) fairness. The primary challenge in designing fair algorithms for these problems is that checking feasibility (determining the existence of a solution that satisfies the fairness constraints) is often NP-hard. In this work, we introduce probabilistic relaxations for deterministic group-fairness constraints. Further, we provide randomized algorithms that offer approximate probabilistic fairness guarantees, while maintaining a good (constant factor) approximation on the objective. Following the fair variants, we introduce an interesting variant of online bipartite matching problem called online minimum bipartite matching problem (OMBM). We provide deterministic and randomized algorithms for the OMBM problem under uniform metric and random order arrival model. We especially show the average case analysis of the deterministic and randomized greedy algorithms where the both of them are optimal in their respective families of algorithms.In the second part, we study the problems related to fair clustering, a well-studied topic in the fairness of unsupervised learning. Particularly, we consider the practical downstream challenges of fair clustering. First, we study the setting where cluster centers are assigned qualitative labels based on their inherent features. Following this, we propose fair labeled clustering that ensures proportional demographic representation across labels rather than individual clusters. We show that unlike their NP-hard counterparts in traditional fair clustering, these problems admit computationally efficient solutions. We further study the generalized model where the decision-maker has the flexibility to assign labels to the centers. Next, we study the problem of noisy group memberships by proposing a robust fair clustering problem. Specifically, we introduce a noise model to capture the imperfect group information, requiring only a small number of noise parameters. We formally define the robust fair clustering problem for the $k$-center objective under proportional fairness constraints. We provide a deterministic algorithm with provable guarantees for both robustness and clustering quality.Finally, we conclude by discussing open problems and outlining future research directions.