Equitable cost allocations via primal-dual-type algorithms

ABSTRACT

Perhaps the strongest notion of truth-revealing in a cost sharing method is group strategyproofness. However, matters are not so clear-cut on fairness, and many different, sometimes even conflicting, notions of fairness have been proposed which have relevance in different situations. We present a large class of group strategyproof cost sharing methods, for submodular cost functions, satisfying a wide range of fairness criteria, thereby allowing the service provider to choose a method that best satisfies the notion of fairness that is most relevant to her application. Our class includes the Dutta-Ray egalitarian method as a special case. It also includes a new cost sharing method, which we call the opportunity egalitarian method.

REFERENCES

• 1: Yehuda Afek , Yishay Mansour , Zvi Ostfeld, Convergence complexity of optimistic rate based flow control algorithms (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.89-98, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237837]
• 2: J. Arin, J. Kupers, and D. Vermeulen. An axiomatic approach to egalitarianism in TU games. Dept. of (MATH)ematics, Maastricht University, 2000.
• 3: J. Arin, J. Kupers, and D. Vermeulen. Some characterization of egalitarian solutions on classes of TU games. Mimeo, 2000.
• 4: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 5: B. Dutta, The egalitarian solution and reduced game properties in convex games, International Journal of Game Theory, v.19 n.2, p.153-169, 1990 [doi>10.1007/BF01761074]
• 6: B. Dutta and D. Ray. A concept of egalitarianism under participation constraints. Econometrica, 57:615--635.
• 7: B. Dutta and D. Ray. Constrained egalitarian allocations. Games and Economic Behavior, 4, 1992.
• 8: Satoru Iwata , Lisa Fleischer , Satoru Fujishige, A combinatorial strongly polynomial algorithm for minimizing submodular functions, Journal of the ACM (JACM), v.48 n.4, p.761-777, July 2001 [doi>10.1145/502090.502096]
• 9: D. Fudenberg and J. Tirole. Game Theory. The MIT Press, Cambridge, 1991.
• 10: Ashish Goel , Adam Meyerson , Serge Plotkin, Approximate majorization and fair online load balancing, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.384-390, January 07-09, 2001, Washington, D.C., United States
• 11: G. Hardy, H. Littlewood, and G. Polya. Inequalities. Cambridge University Press, Cambridge, 1934.
• 12: T. Hokari. Monotone-path Dutta-Ray solutions on convex games. To appear, Social Choice and Welfare.
• 13: T. Hokari. Weighted Dutta-Ray solutions on convex games. Mimeo, University of Rochester, 1998.
• 14: J. L. Hougard, B. Peleg, and L. P. Osterdal. The Dutta-Ray solution on the class of convex games: a generalisation and its monotonicity properties. Mimeo, University of Copenhagen, 2000.
• 15: J. Jaffe. Bottleneck flow control. IEEE Trans. Communication, 29:954--962, 1981.
• 16: J.Y. Jaffray and P. Mongin. Constrained egalitarianism in a simple redistribution model. THEMA, Universite Cergy-Pontoise, 1998.
• 17: Kamal Jain , Vijay Vazirani, Applications of approximation algorithms to cooperative games, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.364-372, July 2001, Hersonissos, Greece [doi>10.1145/380752.380825]
• 18: Kamal Jain , Vijay V. Vazirani, Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation, Journal of the ACM (JACM), v.48 n.2, p.274-296, March 2001 [doi>10.1145/375827.375845]
• 19: Jon Kleinberg , Eva Tardos , Yuval Rabani, Fairness in Routing and Load Balancing, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.568, October 17-18, 1999
• 20: F. Klijn, M. Slikker, S. Tijs, and J. Zarzuelo. Characterizations of the egalitarian solutions for convex games. Mimeo,CentER, Tilburg, 2000.
• 21: N. Megiddo. Optimal flows in networks with source and sinks. (MATH). Programming, 7, 1974.
• 22: H. Moulin. Incremental cost sharing: characterization by coalition strategy-proofness. Social Choice and Welfare, 16:279--320, 1999.
• 23: S. Mutuswami. Strategyproof mechanism for cost sharing. Working paper, Indian Statistical Institute.
• 24: Alexander Schrijver, A combinatorial algorithm minimizing submodular functions in strongly polynomial time, Journal of Combinatorial Theory Series B, v.80 n.2, p.346-355, Nov. 2000 [doi>10.1006/jctb.2000.1989]
• 25: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.1 Applications and Expert Systems
          Subjects: Games

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms, Experimentation, Performance, Theory