Description:

Abstract

Fair allocation of indivisible goods is an exciting topic since it presents challenging theoretical problems and finds applications in several real-world scenarios. A substantial body of work has focused on the unconstrained version of the fair allocation problem leaving many open questions in the constrained setting. In this talk, I’ll focus on a part of my doctoral dissertation that investigates fair allocation under matroid constraints. First, I’ll deep dive into a simple set system, called partition matroid. In this setting, the set of goods are grouped into disjoint categories and a limit (cardinality constraint) is specified on the number of goods that can be allocated from each category to any agent. The objective is to find a fair allocation in which the bundle allocated to any agent satisfies the given cardinality constraints. This problem is a generalization of the well-studied (unconstrained) fair allocation problem. The two central notions of fairness, in the context of allocation of indivisible goods, are envy freeness up to one good (EF1) and the maximin share guarantee (MMS). I’ll talk about the existence and algorithmic guarantees for these solution concepts under cardinality constraints. In particular, I’ll show that EF1 and 1/3-MMS allocations exist and can be computed in polynomial time. Furthermore, I’ll talk about the existence of fair solutions under a more general class of matroid constraints. I’ll then describe how these concepts can be extended to scenarios where there are two groups of agents with each group having cardinal preferences over the agents of the other group and the goal is to satisfy fairness guarantees for both groups. For the two-sided fairness problem, I’ll discuss efficient algorithms for specific instances of the problem and investigate computational issues in obtaining fairness guarantees for all agents across both groups. Finally, I will talk about our collaboration with non-profits where we use these solution concepts to provide decision support for various public healthcare programs.

Biography
Arpita Biswas is a CRCS Postdoctoral Fellow at Harvard University. She earned her Ph.D. degree from the Department of Computer Science and Automation (CSA), Indian Institute of Science (IISc). She has been awarded the Best Thesis Prize by the Indian Academy of Engineering (INAE) 2021, Best Thesis Award by the Department of CSA, IISc (2020-2021), a Google Ph.D. Fellowship (2016-2020), and a GHCI scholarship (2018). She has been recognized as a Rising Star in STOC 2021 and in the Trustworthy ML Seminar Series for her contribution to algorithms for fair decision-making. Her broad areas of interest include Algorithmic Game Theory, Optimization, and Machine Learning. She has worked on a wide range of problems, including fair resource allocation, health intervention planning, multi-armed bandits, online crowdsourcing, dynamic pricing in transportation, and ride-sharing. More details about her can be obtained at https://sites.google.com/view/arpitabiswas/.