New trade-offs in cost-sharing mechanisms

ABSTRACT

A cost-sharing mechanism is a protocol that collects bids from a set of players, selects a subset of the players to receive a service (incurring a subset-dependent cost), and determines a price to charge each of these players. Three standard requirements for cost-sharing mechanisms are incentive compatibility, which states that players are motivated to bid their true valuation for the service; budget-balance, meaning that the prices charged should recover the cost incurred; and efficiency, which states that the cost incurred and the valuations of the players served should be traded off in an optimal way. These three goals have been known to be mutually incompatible for thirty years. As a result, nearly all work on cost-sharing mechanisms in the economics and theoretical computer science literatures has focused on achieving two of these goals while completely ignoring the third.We show that incentive-compatibility, budget-balance, and approximate efficiency are simultaneously achievable for a wide range of cost functions, where efficiency is measured using the social cost---the sum of the incurred service cost and the excluded valuations. In particular, we prove such guarantees for well-known mechanisms for all submodular cost functions and for the Steiner tree cost function. We also prove a generic, quantifiable trade-off between the objectives of efficiency and budget-balance in groupstrategyproof cost-sharing mechanisms.

REFERENCES

• 1: Elliot Anshelevich , Anirban Dasgupta , Jon Kleinberg , Eva Tardos , Tom Wexler , Tim Roughgarden, The Price of Stability for Network Design with Fair Cost Allocation, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.295-304, October 17-19, 2004 [doi>10.1109/FOCS.2004.68]
• 2: A. Archer, J. Feigenbaum, A. Krishnamurthy, R. Sami, and S. Shenker. Approximation and collusion in multicast cost sharing. Games and Economic Behavior, 47(1):36--71, 2004.
• 3: Nikhil R. Devanur , Milena Mihail , Vijay V. Vazirani, Strategyproof cost-sharing mechanisms for set cover and facility location games, Proceedings of the 4th ACM conference on Electronic commerce, p.108-114, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779942]
• 4: Joan Feigenbaum , Arvind Krishnamurthy , Rahul Sami , Scott Shenker, Hardness results for multicast cost sharing, Theoretical Computer Science, v.304 n.1-3, p.215-236, 28 July 2003 [doi>10.1016/S0304-3975(03)00085-9]
• 5: Joan Feigenbaum , Christos H. Papadimitriou , Scott Shenker, Sharing the cost of multicast transmissions, Journal of Computer and System Sciences, v.63 n.1, p.21-41, August 2001 [doi>10.1006/jcss.2001.1754]
• 6: J. Green, E. Kohlberg, and J. J. Laffont. Partial equilibrium approach to the free rider problem. Journal of Public Economics, 6:375--394, 1976.
• 7: A. Gupta, A. Srinivasan, and É. Tardos. Cost-sharing mechanisms for network design. In APPROX '04, pages 139--150.
• 8: S. Hart and A. Mas-Colell. Potential, value, and consistency. Econometrica, 57(3):589--614, 1989.
• 9: Nicole Immorlica , Mohammad Mahdian , Vahab S. Mirrokni, Limitations of cross-monotonic cost sharing schemes, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 10: 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]
• 11: Kamal Jain , Vijay V. Vazirani, Equitable cost allocations via primal-dual-type algorithms, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509956]
• 12: K. Kent and D. Skorin-Kapov. Population monotonic cost allocation on mst's. In Operational Research Proceedings KOI, pages 43--48, 1996.
• 13: J. Könemann, S. Leonardi, and G. Schäfer. A group-strategyproof mechanism for Steiner forests. In SODA '05, pages 612--619.
• 14: J. Könemann, S. Leonardi, G. Schäfer, and S. van Zwam. From primal-dual to cost shares and back: A stronger LP relaxation for the steiner forest problem. In ICALP '05, pages 1051--1063.
• 15: Stefano Leonardi , Guido Schaefer, Cross-monotonic cost-sharing methods for connected facility location games, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA [doi>10.1145/988772.988814]
• 16: H. Moulin. Incremental cost sharing: Characterization by coalition strategy-proofness. Social Choice and Welfare, 16:279--320, 1999.
• 17: H. Moulin. Axiomatic cost and surplus sharing. In K. J. Arrow, A. K. Sen, and K. Suzumura, editors, Handbook of Social Choice and Welfare, volume 1, chapter 6, pages 289--357. North-Holland, 2002.
• 18: H. Moulin and S. Shenker. Strategyproof sharing of submodular costs: Budget balance versus efficiency. Economic Theory, 18:511--533, 2001.
• 19: Martin Pál , Éva Tardo, Group Strategyproof Mechanisms via Primal-Dual Algorithms, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.584, October 11-14, 2003
• 20: K. Roberts. The characterization of implementable choice rules. In J. J. Laffont, editor, Aggregation and Revelation of Preferences. North-Holland, 1979.
• 21: T. Roughgarden. Potential functions and the inefficiency of equilibria. In ICM '06. To appear.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.0 GENERAL

General Terms:
Algorithms, Economics, Theory

Keywords:
Braess's Paradox, random graphs, selfish routing