Pricing for fairness: distributed resource allocation for multiple objectives

ABSTRACT

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² ρ) iterations. Here n is the number of flows, m is the number of edges, R is the ratio between the maximum capacity and the minimum capacity of the edges in the network, and ρ is max (n, m, R).We extend this result to multi-path routing, and also to a natural pricing mechanism that results in a simple and practical protocol for bandwidth allocation in a network. When the protocol reaches equilibrium, the allocated bandwidths are the same as when the distributed algorithm converges; hence the protocol is also an O(log ρ) approximation for all canonical utility functions.

REFERENCES

• 1: Yehuda Afek , Yishay Mansour , Zvi Ostfeld, Convergence complexity of optimistic rate-based flow-control algorithms, Journal of Algorithms, v.30 n.1, p.106-143, Jan. 1999 [doi>10.1006/jagm.1998.0970]
• 2: A. Awerbuch and Y. Azar. Local optimization of global objectives: competitive distributed deadlock resolution and resource allocation. Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pages 240--49, 1994.
• 3: B. Awerbuch and Y. Shavitt. Converging to approximated max-min flow fairness in logarithmic time. Proceedings of the 17th IEEE Infocom conference, pages 1350--57, 1998.
• 4: Yair Bartal , John W. Byers , Danny Raz, Global Optimization Using Local Information with Applications to Flow Control, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.303, October 19-22, 1997
• 5: Yair Bartal , Martin Farach-Colton , Shibu Yooseph , Lisa Zhang, Fast, fair, and frugal bandwidth allocation in ATM networks, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.92-101, January 17-19, 1999, Baltimore, Maryland, United States
• 6: Rishi Bhargava , Ashish Goel , Adam Meyerson, Using approximate majorization to characterize protocol fairness, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.330-331, June 2001, Cambridge, Massachusetts, United States
• 7: S. Cho and A. Goel. Bandwidth allocation in networks: a single dual-update subroutine for multiple objectives. Lecture Notes in Computer Science (proceedings of the first Workshop on Combinatorial and Algorithmic Aspects of Networks (CAAN), Aug 2004), 3405:28--41.
• 8: Bruno Codenotti , Amin Saberi , Kasturi Varadarajan , Yinyu Ye, Leontief economies encode nonzero sum two-player games, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.659-667, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109629]
• 9: Lisa K. Fleischer, Approximating Fractional Multicommodity Flow Independent of the Number of Commodities, SIAM Journal on Discrete Mathematics, v.13 n.4, p.505-520, Oct. 2000 to Nov. 2000 [doi>10.1137/S0895480199355754]
• 10: Naveen Garg , Jochen Koenemann, Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems., Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.300, November 08-11, 1998
• 11: Naveen Garg , Neal E. Young, On-Line End-to-End Congestion Control, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.303-312, November 16-19, 2002
• 12: A. Goel and A. Meyerson. Simultaneous optimization via approximate majorization for concave profits or convex costs. Algorithmica, 44(4):301--323, May 2006.
• 13: Ashish Goel , Adam Meyerson , Serge Plotkin, Combining fairness with throughout: online routing with multiple objectives, Journal of Computer and System Sciences, v.63 n.1, p.62-79, August 2001 [doi>10.1006/jcss.2001.1755]
• 14: Ashish Goel , Adam Meyerson , Serge Plotkin, Approximate majorization and fair online load balancing, ACM Transactions on Algorithms (TALG), v.1 n.2, p.338-349, October 2005 [doi>10.1145/1103963.1103970]
• 15: G.H. Hardy, J.E. Littlewood, and G. Polya. Some simple inequalities satisfied by convex functions. Messenger Math., 58:145--152, 1929.
• 16: G.H. Hardy, J.E. Littlewood, and G. Polya. Inequalities. 1st ed., 2nd ed. Cambridge University Press, London and New York., 1934, 1952.
• 17: F.P. Kelly, A.K. Maulloo, and D.K.H. Tan. Rate control in communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research Society, 49:237--252, 1998.
• 18: Jon Kleinberg , Yuval Rabani , Éva Tardos, Fairness in routing and load balancing, Journal of Computer and System Sciences, v.63 n.1, p.2-20, August 2001 [doi>10.1006/jcss.2001.1752]
• 19: A. Kumar , J. Kleinberg, Fairness measures for resource allocation, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.75, November 12-14, 2000
• 20: Steven H. Low , Larry Peterson , Limin Wang, Understanding TCP vegas: a duality model, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.226-235, June 2001, Cambridge, Massachusetts, United States
• 21: Michael Luby , Noam Nisan, A parallel approximation algorithm for positive linear programming, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.448-457, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167211]
• 22: A.W. Marshall and I. Olkin. Inequalities: theory of majorization and its applications. Academic Press (Volume 143 of Mathematics in Science and Engineering), 1979.
• 23: Serge A. Plotkin , David B. Shmoys , Éva Tardos, Fast approximation algorithms for fractional packing and covering problems, Mathematics of Operations Research, v.20 n.2, p.257-301, May 1995 [doi>10.1287/moor.20.2.257]
• 24: Arie Tamir, Least majorized elements and generalized polymatroids, Mathematics of Operations Research, v.20 n.3, p.583-589, Aug. 1995 [doi>10.1287/moor.20.3.583]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

Additional Classification:
  G. Mathematics of Computing
  G.0 GENERAL

General Terms:
Algorithms, Theory

Keywords:
fairness, pricing, primal-dual