Equitable cost allocations via primal-dual-type algorithms
Authors:
Open Access
- 19 May 2002
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 313-321
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.Keywords
This publication has 9 references indexed in Scilit:
- Applications of approximation algorithms to cooperative games2001
- A combinatorial strongly polynomial algorithm for minimizing submodular functionsJournal of the ACM, 2001
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxationJournal of the ACM, 2001
- A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial TimeJournal of Combinatorial Theory, Series B, 2000
- Incremental cost sharing: Characterization by coalition strategy-proofnessSocial Choice and Welfare, 1999
- Convergence complexity of optimistic rate based flow control algorithms (extended abstract)1996
- The egalitarian solution and reduced game properties in convex gamesInternational Journal of Game Theory, 1990
- A Concept of Egalitarianism Under Participation ConstraintsEconometrica, 1989
- Bottleneck Flow ControlIEEE Transactions on Communications, 1981