PhD Defense: Social Aspects of Algorithms: Fairness, Diversity, and Resilience to Strategic Behavior

With algorithms becoming ubiquitous in our society, it is important to ensure that they are compatible with our social values. In this thesis, we study some of the social aspects of algorithms including diversity, resilience to the strategic behavior of individuals, and fairness.Lack of diversity has a potential impact on discrimination against marginalized groups. When a homogenous team produces a technology, their outcome best serves a specific population. One way of mitigating inherent biases is to form a diverse team working on designing a technology. In the first part of this thesis, we study a problem called diverse b-matchings, where the goal is to form a diverse set of teams. In this problem, we ask the question of how to create a set of teams from a set of workers where each worker has multiple features (e.g., gender, race, etc.), in order to maximize diversity with respect to all the features. We show when the number of features is given as part of the input, this problem is NP-hard, and design a pseudo-polynomial time to solve this problem.Next, we take into consideration the vulnerability of algorithms to manipulation and gaming. We study the problem of how to learn a linear classifier in presence of strategic agents that desire to be classified as positive and that are able to modify their position by a limited amount, making the classifier not be able to observe the true position of agents but rather a position where the agent pretends to be. We focus on designing algorithms with bounded number of mistakes for a few different variations of this problem.Many automated algorithms were shown to have implicit biases against certain demographics. Due to their growing impact on different aspects of everyday life, it is crucial to focus on designing algorithms that are inclusive, unbiased, and helpful to the entire population. Many of the typical application scenarios where fairness has been identified to be crucial (e.g. lending, marketing, job selection etc.) require clustering large datasets with sensitive features. We study two different notions of fairness, in a clustering problem called correlation clustering. In this problem, given a graph where each edge is labeled positive or negative, the goal is to obtain a clustering of the vertices that minimizes disagreements, i.e. the number of negative edges trapped inside a cluster plus positive edges between different clusters. In the first fairness notion, which respects group fairness, our aim is to generate clusters with a minimum number of disagreements, where the distribution of a feature (e.g. gender) in each cluster is the same as the global distribution. The second notion of fairness that we study is a cluster-wise objective function that asks to minimize the maximum number of disagreements of each cluster. We focus on designing approximation algorithms for both of these notions.
Examining Committee:

Chair: Dr. Samir Khuller Dean's rep: Dr. Louiqa Raschid Members: Dr. Avrim Blum
Dr. John P. Dickerson Dr. David Mount