Implementing Efficient Graphs in Connection Networks
We consider the problem of sharing the cost of a network that meets the connection demands of a set of agents. The agents simultaneously choose paths in the network connecting their demand nodes. A mechanism splits the total cost of the network formed among the participants. We introduce two new properties of implementation. The first prop- erty, Pareto Nash Implementation (PNI), requires that the efficient out- come is always implemented in a Nash equilibrium, and that the efficient outcome Pareto dominates any other Nash equilibrium. The average cost mechanism (AC) and other assymetric variations, are the only rules that meet PNI. These mechanisms are also characterized under Strong Nash Implementation. The second property, Weakly Pareto Nash Implementation (WPNI), requires that the least inefficient equilibrium Pareto dominate any other equilibrium. The egalitarian mechanism (EG), a variation of AC that meets individual rationality, and other assymetric mechanisms are the only rules that meet WPNI and Individual Rationality. PNI and WPNI provide the first economic justification of the Price of Stability (PoS), a seemingly natural measure in the computer science literature but not easily embraced in economics. EG minimizes the PoS across all individually rational mechanisms.ntable SCFs in our environment if we add a few desirable axioms.
|Date of creation:|
|Date of revision:|
|Contact details of provider:|| Postal: |
Web page: http://www.business.lsu.edu/economics
More information through EDIRC
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- William Thomson, 2006.
"On the Existence of Consistent Rules to Adjudicate Conflicting Claims: A Constructive Geometric Approach,"
RCER Working Papers
528, University of Rochester - Center for Economic Research (RCER).
- William Thomson, 2007. "On the existence of consistent rules to adjudicate conflicting claims: a constructive geometric approach," Review of Economic Design, Springer, vol. 11(3), pages 225-251, November.
- Young, H. P., 1988. "Distributive justice in taxation," Journal of Economic Theory, Elsevier, vol. 44(2), pages 321-335, April.
- Ruben Juarez, 2008. "The worst absolute surplus loss in the problem of commons: random priority versus average cost," Economic Theory, Springer, vol. 34(1), pages 69-84, January.
- Juarez, Ruben, 2013. "Group strategyproof cost sharing: The role of indifferences," Games and Economic Behavior, Elsevier, vol. 82(C), pages 218-239.
- Kaminski, Marek M., 2006. "Parametric rationing methods," Games and Economic Behavior, Elsevier, vol. 54(1), pages 115-133, January.
- Sprumont, Yves, 1991. "The Division Problem with Single-Peaked Preferences: A Characterization of the Uniform Allocation Rule," Econometrica, Econometric Society, vol. 59(2), pages 509-19, March.
- Oscar Volij & Nir Dagan, 1997.
"Bilateral Comparisons and Consistent Fair Division Rules in the Context of Bankruptcy Problems,"
International Journal of Game Theory,
Springer, vol. 26(1), pages 11-25.
- Nir Dagan & Oscar Volij, 1997. "Bilateral Comparisons and Consistent Fair Division Rules in the Context of Bankruptcy Problems," Economic theory and game theory 004, Nir Dagan.
- Volij, Oscar & Dagan, Nir, 1997. "Bilateral Comparisons and Consistent Fair Division Rules in the Context of Bankruptcy Problems," Staff General Research Papers 5141, Iowa State University, Department of Economics.
- Kaminski, Marek M., 2000. "'Hydraulic' rationing," Mathematical Social Sciences, Elsevier, vol. 40(2), pages 131-155, September.
- HervÊ Moulin, 1999. "Incremental cost sharing: Characterization by coalition strategy-proofness," Social Choice and Welfare, Springer, vol. 16(2), pages 279-320.
- Andelman, Nir & Feldman, Michal & Mansour, Yishay, 2009. "Strong price of anarchy," Games and Economic Behavior, Elsevier, vol. 65(2), pages 289-317, March.
- Hervé Moulin, 2008. "The price of anarchy of serial, average and incremental cost sharing," Economic Theory, Springer, vol. 36(3), pages 379-405, September.
- Levent Ulku, 2009.
"Optimal Combinatorial Mechanism Design,"
0903, Centro de Investigacion Economica, ITAM.
- Aumann, Robert J. & Maschler, Michael, 1985. "Game theoretic analysis of a bankruptcy problem from the Talmud," Journal of Economic Theory, Elsevier, vol. 36(2), pages 195-213, August.
- Hervé Moulin & Scott Shenker, 2001. "Strategyproof sharing of submodular costs:budget balance versus efficiency," Economic Theory, Springer, vol. 18(3), pages 511-533.
- Monderer, Dov & Shapley, Lloyd S., 1996. "Potential Games," Games and Economic Behavior, Elsevier, vol. 14(1), pages 124-143, May.
- Epstein, Amir & Feldman, Michal & Mansour, Yishay, 2009. "Strong equilibrium in cost sharing connection games," Games and Economic Behavior, Elsevier, vol. 67(1), pages 51-68, September.
- Tatsuyoshi Saijo & Tomas Sjostrom & Takehiko Yamato, 2005.
Economics Working Papers
0056, Institute for Advanced Study, School of Social Science.
- Sandholm, William H., 2001. "Potential Games with Continuous Player Sets," Journal of Economic Theory, Elsevier, vol. 97(1), pages 81-108, March.
- Hougaard, Jens Leth & Tvede, Mich, 2012. "Truth-telling and Nash equilibria in minimum cost spanning tree models," European Journal of Operational Research, Elsevier, vol. 222(3), pages 566-570.
- Thomson, William, 2003. "Axiomatic and game-theoretic analysis of bankruptcy and taxation problems: a survey," Mathematical Social Sciences, Elsevier, vol. 45(3), pages 249-297, July.
- Hervé Moulin, 2000. "Priority Rules and Other Asymmetric Rationing Methods," Econometrica, Econometric Society, vol. 68(3), pages 643-684, May.
- Sharkey, W.W., 1991. "Network Models in Economics," Papers 69, Bell Communications - Economic Research Group.
- Monderer, Dov & Shapley, Lloyd S., 1996. "Fictitious Play Property for Games with Identical Interests," Journal of Economic Theory, Elsevier, vol. 68(1), pages 258-265, January.
- Kim, Youngse, 1996. "Equilibrium Selection inn-Person Coordination Games," Games and Economic Behavior, Elsevier, vol. 15(2), pages 203-227, August.
- Chambers, Christopher P., 2006. "Asymmetric rules for claims problems without homogeneity," Games and Economic Behavior, Elsevier, vol. 54(2), pages 241-260, February.
When requesting a correction, please mention this item's handle: RePEc:lsu:lsuwpp:2011-03. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: ()
If references are entirely missing, you can add them using this form.