Quantifying inefficiency in cost-sharing mechanisms

ABSTRACT

In a cost-sharing problem, several participants with unknown preferences vie to receive some good or service, and each possible outcome has a known cost. A cost-sharing mechanism is a protocol that decides which participants are allocated a good and at what prices. Three desirable properties of a cost-sharing mechanism are: incentive-compatibility, meaning that participants are motivated to bid their true private value for receiving the good; budget-balance, meaning that the mechanism recovers its incurred cost with the prices charged; and economic efficiency, meaning that the cost incurred and the value to the participants are traded off in an optimal way. These three goals have been known to be mutually incompatible for thirty years. Nearly all the work on cost-sharing mechanism design by the economics and computer science communities has focused on achieving two of these goals while completely ignoring the third.

We introduce novel measures for quantifying efficiency loss in cost-sharing mechanisms and prove simultaneous approximate budget-balance and approximate efficiency guarantees for mechanisms for a wide range of cost-sharing problems, including all submodular and Steiner tree problems. Our key technical tool is an exact characterization of worst-case efficiency loss in Moulin mechanisms, the dominant paradigm in cost-sharing mechanism design.

REFERENCES

• 1: Andelman, N., Feldman, M., and Mansour, Y. 2009. Strong price of anarchy. Games Econ. Behav. (http://pluto.huji.ac.il/~mfeldman/papers/coalition_full.pdf).
• 2: Archer, A., Feigenbaum, J., Krishnamurthy, A., Sami, R., and Shenker, S. 2004. Approximation and collusion in multi-cast cost sharing. Games Econ. Behav. 47, 1, 36--71.
• 3: Sanjeev Arora , Carsten Lund, Hardness of approximations, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 4: Yoram Bachrach , Evangelos Markakis , Ariel D. Procaccia , Jeffrey S. Rosenschein , Amin Saberi, Approximating power indices, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
• 5: Daniel Bienstock , Michel X. Goemans , David Simchi-Levi , David Williamson, A note on the prize collecting traveling salesman problem, Mathematical Programming: Series A and B, v.59 n.3, p.413-420, May 7, 1993 [doi>10.1007/BF01581256]
• 6: Bleischwitz, Y., and Monien, B. 2006. Fair cost-sharing methods for scheduling jobs on parallel machines. In Proceedings of the 6th Italian Conference on Algorithms and Complexity (CIAC). Lecture Notes in Computer Science, vol. 3998. Springer-Verlag, New York, 175--186.
• 7: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 8: Brenner, J., and Schäfer, G. 2007. Cost sharing methods for makespan and completion time scheduling. In Proceedings of the 24th International Symposium on Theoretical Aspects of Computer Science (STACS). Lecture Notes in Computer Science, vol. 4393. Springer-Verlag, Berlin, Germany, 670--681.
• 9: Chawla, S., Roughgarden, T., and Sundararajan, M. 2006. Optimal cost-sharing mechanisms for network design. In Proceedings of the 2nd Annual International Workshop on Internet and Network Economics (WINE). Lecture Notes in Computer Science, vol. 4286. Springer-Verlag, Berlin, Germany, 112--123.
• 10: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 11: Deb, R., and Razzolini, L. 1999. Auction-like mechanisms for pricing excludable public goods. J. Econ. Theory 88, 2, 340--368.
• 12: Nikhil R. Devanur , Milena Mihail , Vijay V. Vazirani, Strategyproof cost-sharing mechanisms for set cover and facility location games, Decision Support Systems, v.39 n.1, p.11-22, March 2005 [doi>10.1016/j.dss.2004.08.004]
• 13: Shahar Dobzinski , Aranyak Mehta , Tim Roughgarden , Mukund Sundararajan, Is Shapley Cost Sharing Optimal?, Proceedings of the 1st International Symposium on Algorithmic Game Theory, April 30-May 02, 2008, Paderborn, Germany [doi>10.1007/978-3-540-79309-0_29]
• 14: Edmonds, J. 1967. Optimum branchings. J. Res. NBS, Ser. B 71, 4, 233--240.
• 15: 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]
• 16: 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]
• 17: Joan Feigenbaum , Scott Shenker, Distributed algorithmic mechanism design: recent results and future directions, Proceedings of the 6th international workshop on Discrete algorithms and methods for mobile computing and communications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570810.570812]
• 18: Green, J., Kohlberg, E., and Laffont, J. J. 1976. Partial equilibrium approach to the free rider problem. J. Public Econ. 6, 4, 375--394.
• 19: A. Gupta , J. Könemann , S. Leonardi , R. Ravi , G. Schäfer, An efficient cost-sharing mechanism for the prize-collecting Steiner forest problem, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1153-1162, January 07-09, 2007, New Orleans, Louisiana
• 20: Anupam Gupta , Aravind Srinivasan , Éva Tardos, Cost-Sharing Mechanisms for Network Design, Algorithmica, v.50 n.1, p.98-119, December 2007 [doi>10.1007/s00453-007-9065-y]
• 21: Hart, S., and Mas-Colell, A. 1989. Potential, value, and consistency. Econometrica 57, 3, 589--614.
• 22: Jason Daniel Hartline , Anna R. Karlin, Optimization in the private value model: competitive analysis applied to auction design, University of Washington, 2003
• 23: Nicole Immorlica , Mohammad Mahdian , Vahab S. Mirrokni, Limitations of cross-monotonic cost-sharing schemes, ACM Transactions on Algorithms (TALG), v.4 n.2, p.1-25, May 2008 [doi>10.1145/1361192.1361201]
• 24: 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]
• 25: Kamal Jain , Vijay V. Vazirani, Equitable Cost Allocations via Primal-Dual-Type Algorithms, SIAM Journal on Computing, v.38 n.1, p.241-256, March 2008 [doi>10.1137/060658448]
• 26: Juarez, R. 2007. Group strategyproof cost sharing: the role of indifferences. http://www2.hawaii.edu/~ruben/gsp1.pdf.
• 27: Kent, K., and Skorin-Kapov, D. 1996. Population monotonic cost allocation on MST's. In Operational Research Proceedings KOI. 43--48.
• 28: Jon Kleinberg , Éva Tardos, Approximation algorithms for classification problems with pairwise relationships: metric labeling and Markov random fields, Journal of the ACM (JACM), v.49 n.5, p.616-639, September 2002 [doi>10.1145/585265.585268]
• 29: Jochen Könemann , Stefano Leonardi , Guido Schäfer , Stefan H. M. van Zwam, A Group-Strategyproof Cost Sharing Mechanism for the Steiner Forest Game, SIAM Journal on Computing, v.37 n.5, p.1319-1341, January 2008 [doi>10.1137/050646408]
• 30: Stefano Leonardi , Guido Schäfer, Cross-monotonic cost sharing methods for connected facility location games, Theoretical Computer Science, v.326 n.1-3, p.431-442, 20 October 2004 [doi>10.1016/j.tcs.2004.07.033]
• 31: Maniquet, F., and Sprumont, Y. 2004. Fair production and allocation of an excludable nonrival good. Econometrica 72, 2, 627--640.
• 32: Mas-Colell, A., Whinston, M. D., and Green, J. R. 1995. Microeconomic Theory. Oxford University Press.
• 33: Mehta, A., Roughgarden, T., and Sundararajan, M. 2009. Beyond Moulin mechanisms. Games Econ. Behav. (http://theory.stanford.edu/~tim/papers/bmm.pdf).
• 34: Monderer, D., and Shapley, L. S. 1996. Potential games. Games Econ. Behav. 14, 1, 124--143.
• 35: Moulin, H. 1999. Incremental cost sharing: Characterization by coalition strategy-proofness. Social Choice Welf. 16, 2, 279--320.
• 36: Moulin, H., and Shenker, S. 2001. Strategyproof sharing of submodular costs: Budget balance versus efficiency. Econ. Theory 18, 3, 511--533.
• 37: S. Muthukrishnan, Data streams: algorithms and applications, Foundations and Trends® in Theoretical Computer Science, v.1 n.2, p.117-236, August 2005 [doi>10.1561/0400000002]
• 38: Osborne, M. J., and Rubinstein, A. 1994. A Course in Game Theory. MIT Press, Cambridge.
• 39: 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
• 40: Roberts, K. 1979. The characterization of implementable choice rules. In Aggregation and Revelation of Preferences, J. J. Laffont, Ed. North-Holland, Amsterdam, The Netherlands.
• 41: Tim Roughgarden , Mukund Sundararajan, New trade-offs in cost-sharing mechanisms, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132528]
• 42: Tim Roughgarden , Mukund Sundararajan, Optimal Efficiency Guarantees for Network Design Mechanisms, Proceedings of the 12th international conference on Integer Programming and Combinatorial Optimization, June 25-27, 2007, Ithaca, NY, USA [doi>10.1007/978-3-540-72792-7_35]
• 43: Vickrey, W. 1961. Counterspeculation, auctions, and competitive sealed tenders. J. Finance 16, 1, 8--37.

INDEX TERMS

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

General Terms:
Algorithms, Economics, Theory

Keywords:
Mechanism design, Steiner tree, cost sharing, inefficiency, submodular functions