PhD Proposal: On Designing Fair Algorithms
The growing use of algorithms in different aspects of today's life raises the question of whether they are fair or they are discriminating against certain groups. Defining the concept of fairness is a challenging task. Many optimization problems can be re-defined to integrate the notion of fairness into their objective functions. In this proposal, we consider research challenges for designing fair objectives and algorithms for two optimization problems.The first problem we consider is integrating a notion of fairness with the classical problem of correlation clustering. Correlation clustering is a fundamental combinatorial optimization problem arising in many contexts and applications that have been the subject of dozens of papers in the literature. In this problem, we are given a general weighted graph where each edge is labeled positive or negative. The goal is to obtain a partitioning (clustering) of the vertices that minimizes disagreements – weight of negative edges trapped inside a cluster plus positive edges between different clusters. Much of the research in this area mainly focus on minimizing total disagreement, a global objective for this problem. We study a cluster-wise objective function that asks to minimize the maximum number of disagreements of each cluster, which we call min-max correlation clustering. The min-max objective is a natural objective that respects the quality of every cluster and tries to be fair to each cluster.The second problem is called diverse b-matching. Bipartite b-matching, where agents on one side of a market are matched to one or more agents or items on the other, is a classical model that is used in myriad application areas such as healthcare, advertising, education, and general resource allocation. Traditionally, the primary goal of such models is to maximize a linear function of the constituent matches (e.g., linear social welfare maximization) subject to some constraints. Recent work has studied a new goal of balancing whole-match diversity and economic efficiency, where the objective is instead a monotone submodular function over the matching. These more general models are largely NP-hard. In this work, we identify theoretically-tractable segments of the diverse b-matching problem space and propose new algorithms that construct provably-optimal diverse b-matchings in polynomial time.
Chair: Dr. Samir Khuller Dept rep: Dr. John Dickerson Members: Dr. David Mount Dr. Barna Saha