Algorithmic Fairness and Online Decision Making in Combinatorial Optimization and Unsupervised Learning

Abstract

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. 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 \emph{algorithmic fairness}. In this thesis we focus on designing algorithms with provable guarantees for fair and/or online 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 fairness. The primary challenge in designing fair algorithms for these problems is that checking the feasibility\footnote{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. We begin with the fair online bipartite matching problem. While existing works primarily focus on one-sided fairness, we generalize the framework to provide simultaneous guarantees for both sides of the market. We incorporate both group and individual Rawlsian fairness criteria which seeks to maximize the utility of the worst case groups and individuals. To address this, we present randomized algorithms that satisfy these constraints in expectation. Furthermore, our algorithms also allow for tunable parameters designed to handle the trade-offs between the utilities of the two sides of market and the platform operator (e.g., in ride-sharing, the two sides are the drivers and riders, where the platform (Uber/Lyft) refers to theoperator). Next we present set packing and bipartite matching problems under proportional fairness constraints. Proportional fairness is a well-studied notion of group fairness where the desired lower bound and upper bound proportions set by stakeholder for each group must be satisfied. A notable special case is when when these bounds are equal for all groups. In this thesis we begin by introducing strong probabilistic relaxations of group-fairness notions and we refer to the solutions that satisfy such definitions as \emph{probably almost fair} and \emph{probably approximately fair}. The high-level idea is that we show strong guarantees like tail bounds for the probability that the solution returned by our randomized algorithm is almost-fair and approximately-fair respectively. We conclude the first part by introducing a variant of online minimum bipartite matching problem under uniform metric and provide algorithms along with matching lower bounds. The second part of this thesis study the problems related to \emph{fair clustering}, a well-studied topic in the fairness of unsupervised learning. Particularly, we consider the practical downstream challenges of fair clustering. In the first problem, we study the setting where cluster centers are assigned \emph{qualitative} labels based on their inherent features. Because these labels are often shared across multiple clusters, traditional fair clustering constraints no longer capture this settings. Therefore, we propose \emph{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 framework. Specifically, we formulate 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 algorithm with provable guarantees for both robustness and clustering quality. We further characterize the inherent trade-off between these two metrics.Finally, empirical evaluations on real-world datasets validate the effectiveness and practical utility of our proposed methods. ˘Finally, we conclude by discussing open problems and outlining future research directions.