Talks

PhD Proposal: Algorithmic Fairness Issues in Machine Learning and Operations Research

Seyed Esmaeili

4107 Brendan Iribe Center for Computer Science and Engineering (IRB)

Wednesday, April 6, 2022, 10:00 am-12:00 pm

You are subscribed to this talk through .
You are watching this talk through .
You are subscribed to this talk. (unsubscribe, watch)
You are watching this talk. (unwatch, subscribe)
You are not subscribed to this talk. (watch, subscribe)

Abstract

Much of decision making is now rendered at least partly through algorithms which were originally designed to optimize an objective such as accuracy or revenue while mostly ignoring the possible un- fairness or harm that could be caused. As a result several case studies have demonstrated empirically that deployed algorithmic decision making systems do in fact violate standard notions of fairness. This has made the issue of fairness an important consideration in algorithm design. In this thesis we will consider fair variants of fundamental and important problems in machine learning and operations research.

We start by considering clustering where we focus on a common group (demographic) fairness notion and address important variants of it: (I) we start with the frequent case where group memberships are imperfectly known. Based on stochastic optimization we propose probabilistic fair clustering which is a generalization of fair clustering that handles the case of unknown group memberships. We derive approximation algorithms for this setting and empirically test their performance. (II) As largely known in fair algorithms achieving fairness mostly comes at the expense of degrading the value of the optimization objective. In fact, in the case of fair clustering the degradation (price of fairness) can be unbounded. To handle this, we propose fair clustering under a bounded cost where we define a measure of unfairness and minimize this measure subject to a pre-set upper bound on the clustering objective. We derive lower bounds on the approximation ratio and give approximation algorithms as well. (III) we consider the downstream effects of clustering where the center (prototype) of each cluster is examined and each cluster is assigned a label of a specific quality based on its prototype. These labels are shared over a collection of clusters and as a result traditional fair clustering is too restrictive. We therefore propose fair labelled clustering where proportional demographic representation is to be preserved over the labels instead of the clusters and derive algorithms for it.

We then move to another problem, namely online bipartite matching which in its most common form involves three interacting entities: two sides (buyers and sellers) to be matched and the platform operator. Unlike the existing literature we derive online algorithms with competitive ratio guarantees for the operator’s revenue as well as fairness guarantees for the two sides to be matched, thus providing utility guarantees for all sides of the market.

We then consider redistricting which is a much different problem from clustering and matching since we are not given a clear measure to optimize but are rather given a collection of rules that a valid redistricting map has to satisfy. The ambiguity of these rules leads to a large set of valid redistricting maps and hence pose the issue of map selection. Inspired by the Kemeny rule for rank aggregation, we propose to aggregate the redistricting maps by choosing the medoid map. Using a method for sampling redistricting maps, we derive linear time algorithms and sample complexity results for this problem. As a by product, our method has the potential to detect gerrymandered maps based on their distance from the central map. Finally, we discuss ongoing research that centers around fairness and strategic manipulation in interactive learning settings. For example, we consider learning in multi-armed bandits for fair hiring or under the strategic manipulation of a coalition.

Examining Committee:

Chair:
Department Representative:

Dr. John Dickerson
Dr. Ian Miers
Dr. Aravind Srinivasan
Dr. Alex Slivkins

Bio

Seyed Esmaeili is a PhD student at the University of Maryland, College Park. His research interests are in machine learning, algorithms, and fairness. More specifically, his work focuses on producing algorithms with theoretical guarantees that address fairness issues in various topics such as clustering, matching, and redistricting.

This talk is organized by Tom Hurst