Width-Independence Beyond Linear Objectives: Distributed Fair Packing and Covering Algorithms.
Jelena Diakonikolas, Maryam Fazel, Lorenzo Orecchia · arXiv (Cornell University) · 2018
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 inequality aversion parameter $\alpha \in [0, \infty]$. 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 \rightarrow \infty$). In this work, we consider general $\alpha$-fair resource allocation problems, defined as the maximization of $\alpha$-fair utility functions under packing constraints. We give improved distributed algorithms for constructing $\epsilon$-approximate solutions to such problems. Our algorithms are width-independent, that is, their running times depend only poly-logarithmically on the largest entry of the constraint matrix, and closely match the state-of-the-art guarantees for distributed algorithms for packing linear programs -- the case $\alpha = 0.$ Previously known width-independent algorithms for $\alpha$-fair resource allocation have convergence times with much worse dependence on $\epsilon$ and $\alpha$. Our analysis leverages the Approximate Duality Gap framework of Diakonikolas and Orecchia to obtain better algorithms with a more streamlined analysis. Finally, we introduce a natural counterpart of $\alpha$-fairness for minimization problems and motivate its usage in the context of fair task allocation. This generalization yields $\alpha$-fair covering problems, for which we provide the first width-independent nearly-linear-time approximate solvers by reducing their analysis to the $\alpha < 1$ case of the $\alpha$-fair packing problem.