Pricing for Fairness: Distributed Resource Allocation for Multiple Objectives

摘要

In this paper, we present a simple distributed algorithm for resource allocation which simultaneously approximates the optimum value for a large class of objective functions. In particular, we consider the class of canonical utility functions U that are symmetric, non-decreasing, concave, and satisfy U(0) = 0. Our distributed algorithm is based on primal-dual updates. We prove that this algorithm is an O(log ρ)-approximation for all canonical utility functions simultaneously, i.e. without any knowledge of U. The algorithm needs at most O(log 2 ρ) iterations where ρ is the biggest one among the number of flows, the number of edges, and the ratio between the maximum capacity and the minimum capacity of the edges in the network. This result is refined for multi-path routing problem, and also extended to a natural pricing mechanism that results in a simple and practical protocol for bandwidth allocation in a network.