Group Fairness in Network Design and Combinatorial Optimization
Abstract
Consider the following classical network design model. There are n clients in a multi-graph with a single sink node. Each edge has a cost to buy and a length if bought; typically, costlier edges have smaller lengths. There is a budget B on the total cost of edges bought. Given a set of bought edges, the distance of a client to the sink is the shortest path according to the edge lengths. Such a model captures buy-at-bulk network design and facility location as special cases. Rather than pose this as a standard optimization problem, we ask a different question: Suppose a provider is allocating budget B to build this network, how should it do so in a manner that is fair to the clients? We consider a classical model of group fairness termed the core in cooperative game theory: If each client contributes its share B/n amount of budget as tax money, no subset of clients should be able to pool their tax money to deviate and build a different network that simultaneously improves all their distances to the sink. The question is: Does such a solution always exist, or approximately exist? We consider an abstract "committee selection" model from social choice literature that captures not only the above problem but also other combinatorial optimization problems where we need to provision public resources subject to combinatorial constraints in order to provide utility to clients. For this general model, we show that an approximately fair solution always exists, where the approximation scales down the tax money each client can use for deviation by only a constant factor. Our existence result relies on rounding an interesting fractional relaxation to this problem. In certain cases such as the facility location problem, it also implies a polynomial time algorithm. We also show that similar results when the approximation is on the utility that clients derive by deviating.
Bio
Kamesh Munagala is a Professor of Computer Science at Duke University. He obtained his Ph.D. (2003) and M.S. (2002) in Computer Science from Stanford University and B.Tech. (1998) in Computer Science and Engineering from IIT Bombay. He is broadly interested in algorithm design and discrete optimization. His work is both methodological, encompassing approximation and online algorithms, algorithmic fairness, and algorithmic game theory, as well as applied to domains such as e-commerce and data analysis. He is an ACM Distinguished Scientist (2019); a recipient of the NSF CAREER Award (2008) and the Alfred P. Sloan Research Fellowship (2009); and co-author on the best papers at the WINE 2018 and WWW 2009 conferences. He currently serves as the Associate Chair of the CS Department at Duke.
