The Price of Connectivity in Fair Division
Abstract:
We study the allocation of indivisible goods that form an undirected graph and quantify the loss of fairness when we impose a constraint that each agent must receive a connected subgraph. Our focus is on well-studied fairness notions including envy-freeness and maximin share fairness. We introduce the price of connectivity to capture the largest gap between the graph-specific and the unconstrained maximin share, and derive bounds on this quantity which are tight for large classes of graphs in the case of two agents and for paths and stars in the general case. In addition, we determine the optimal relaxation of envy-freeness that can be obtained with each graph for two agents, and characterize the set of trees and complete bipartite graphs that always admit an allocation satisfying envy-freeness up to one good (EF1) for three agents. Our work demonstrates several applications of graph-theoretic tools and concepts to fair division problems.
Joint work with Xiaohui Bei, Ayumi Igarashi, and Xinhang Lu. Appeared at AAAI 2021.
Biodata:
I am an assistant professor in the School of Computing at the National University of Singapore. Previously, I was a postdoctoral researcher in computer science at the University of Oxford, hosted by Edith Elkind. I completed my PhD at Stanford University, where my advisor was Tim Roughgarden, and received my bachelor's and master's degrees from Massachusetts Institute of Technology. My research interests include algorithmic game theory, mechanism design, social choice theory, and other problems at the interface between computer science and economics.