Advanced Search
MyIDEAS: Login

Implementing Efficient Graphs in Connection Networks

Contents:

Author Info

  • Ruben Juarez

    ()
    (University of Hawaii at Manoa, Economics Department)

  • Rajnish Kumar

    ()
    (LSU, Department of Economics)

Abstract

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 property, Pareto Nash Implementation (PNI), requires that the efficient outcome 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 asymmetric 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 asymmetric 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.

Download Info

If you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
File URL: http://www.economics.hawaii.edu/research/workingpapers/WP_10-22.pdf
File Function: Second version, 2010
Download Restriction: no

Bibliographic Info

Paper provided by University of Hawaii at Manoa, Department of Economics in its series Working Papers with number 201022.

as in new window
Length: 39 pages
Date of creation: 19 Nov 2010
Date of revision:
Handle: RePEc:hai:wpaper:201022

Contact details of provider:
Postal: 2424 Maile Way, Honolulu, HI 96822
Phone: (808)956-8730
Fax: (808)956-4347
Email:
Web page: http://www.economics.hawaii.edu/
More information through EDIRC

Order Information:
Email:
Web: http://www.economics.hawaii.edu/research/working.html

Related research

Keywords: Cost-sharing; Implementation; Average Cost; Egalitarian Mechanism.;

Other versions of this item:

Find related papers by JEL classification:

References

References listed on IDEAS
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.:
as in new window
  1. Sjostrom, Tomas & Yamato, Takehiko & Saijo, Tatsuyoshi, 2007. "Secure implementation," Theoretical Economics, Econometric Society, vol. 2(3), September.
  2. 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.
  3. 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.
  4. Kaminski, Marek M., 2006. "Parametric rationing methods," Games and Economic Behavior, Elsevier, vol. 54(1), pages 115-133, January.
  5. 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.
  6. 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.
  7. Andelman, Nir & Feldman, Michal & Mansour, Yishay, 2009. "Strong price of anarchy," Games and Economic Behavior, Elsevier, vol. 65(2), pages 289-317, March.
  8. 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.
  9. 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.
  10. Hervé Moulin, 2008. "The price of anarchy of serial, average and incremental cost sharing," Economic Theory, Springer, vol. 36(3), pages 379-405, September.
  11. Hervé Moulin, 2000. "Priority Rules and Other Asymmetric Rationing Methods," Econometrica, Econometric Society, vol. 68(3), pages 643-684, May.
  12. Juarez, Ruben, 2013. "Group strategyproof cost sharing: The role of indifferences," Games and Economic Behavior, Elsevier, vol. 82(C), pages 218-239.
  13. Monderer, Dov & Shapley, Lloyd S., 1996. "Potential Games," Games and Economic Behavior, Elsevier, vol. 14(1), pages 124-143, May.
  14. Young, H. P., 1988. "Distributive justice in taxation," Journal of Economic Theory, Elsevier, vol. 44(2), pages 321-335, April.
  15. 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.
  16. Sandholm, William H., 2001. "Potential Games with Continuous Player Sets," Journal of Economic Theory, Elsevier, vol. 97(1), pages 81-108, March.
  17. Hervé Moulin & Scott Shenker, 2001. "Strategyproof sharing of submodular costs:budget balance versus efficiency," Economic Theory, Springer, vol. 18(3), pages 511-533.
  18. 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.
  19. Chambers, Christopher P., 2006. "Asymmetric rules for claims problems without homogeneity," Games and Economic Behavior, Elsevier, vol. 54(2), pages 241-260, February.
  20. Kim, Youngse, 1996. "Equilibrium Selection inn-Person Coordination Games," Games and Economic Behavior, Elsevier, vol. 15(2), pages 203-227, August.
  21. 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.
  22. Kaminski, Marek M., 2000. "'Hydraulic' rationing," Mathematical Social Sciences, Elsevier, vol. 40(2), pages 131-155, September.
Full references (including those not matched with items on IDEAS)

Citations

Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
as in new window

Cited by:
  1. Jens Leth Hougaard & Mich Tvede, 2013. "Minimum Cost Connection Networks: Truth-telling and Implementation," MSAP Working Paper Series 03_2013, University of Copenhagen, Department of Food and Resource Economics.
  2. 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.
  3. Jens Leth Hougaard & Mich Tvede, 2010. "Strategyproof Nash Equilibria in Minimum Cost Spanning Tree Models," MSAP Working Paper Series 01_2010, University of Copenhagen, Department of Food and Resource Economics.

Lists

This item is not listed on Wikipedia, on a reading list or among the top items on IDEAS.

Statistics

Access and download statistics

Corrections

When requesting a correction, please mention this item's handle: RePEc:hai:wpaper:201022. 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: (Web Technician).

If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

If references are entirely missing, you can add them using this form.

If the full references list an item that is present in RePEc, but the system did not link to it, you can help with this form.

If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your profile, as there may be some citations waiting for confirmation.

Please note that corrections may take a couple of weeks to filter through the various RePEc services.