Abstract
Fair allocation of resources has deep roots in early philosophy, and has been broadly studied in political science, economic theory, operations research, and networking. Over the past decades, an axiomatic approach to fair resource allocation has led to the general acceptance of a class of alpha-fair utility functions parametrized by a single non-negative inequality aversion parameter alpha. In theoretical computer science, the most well-studied examples are linear utilities (alpha = 0), proportionally fair or Nash utilities (alpha = 1), and max-min fair utilities (alpha = infinity). Maximization of alpha-fair utility functions over convex sets leads to alpha-fair allocation vectors, whose fairness properties are well-studied and axiomatically justified. For most applications, a natural feasible set is a packing polytope, and we refer to the corresponding problem as the alpha-fair packing. The special case of alpha = 0 is known as the packing linear program, which has been widely studied in theoretical computer science due to the phenomenon of width-independence. Namely, for packing linear programs it is possible to obtain first-order methods whose running times scale poly-logarithmically with the constraint matrix width -- the maximum ratio of its non-zero elements. By contrast, this is not possible for general linear programming. In this talk, I will present distributed and width-independent first-order methods for solving general alpha-fair packing problems and their minimization counterparts -- alpha-fair covering problems. The convergence times (number of distributed iterations) of these algorithms scale as Õ(1/eps^2) and Õ(1/eps), which greatly improves upon Õ(1/eps^5) and Õ(1/eps^4) previously known only for the alpha-fair packing problems. I will further discuss how special, local, structure of these problems relates to the phenomenon of width-independence, and conclude with a few open problems. Joint work with Maryam Fazel and Lorenzo Orecchia.