IDEAS home Printed from https://ideas.repec.org/p/hai/wpaper/201022.html
   My bibliography  Save this paper

Implementing Efficient Graphs in Connection Networks

Author

Listed:
  • 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.

Suggested Citation

  • Ruben Juarez & Rajnish Kumar, 2010. "Implementing Efficient Graphs in Connection Networks," Working Papers 201022, University of Hawaii at Manoa, Department of Economics.
    • Handle: RePEc:hai:wpaper:201022
    as

    Download full text from publisher

    File URL: http://www.economics.hawaii.edu/research/workingpapers/WP_10-22.pdf
    File Function: Second version, 2010
    Download Restriction: no
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. Kaminski, Marek M., 2006. "Parametric rationing methods," Games and Economic Behavior, Elsevier, vol. 54(1), pages 115-133, January.
    2. Oscar Volij & Nir Dagan, 1997. "Bilateral Comparisons and Consistent Fair Division Rules in the Context of Bankruptcy Problems," International Journal of Game Theory, Springer;Game Theory Society, vol. 26(1), pages 11-25.
    3. Kaminski, Marek M., 2000. "'Hydraulic' rationing," Mathematical Social Sciences, Elsevier, vol. 40(2), pages 131-155, September.
    4. Sandholm, William H., 2001. "Potential Games with Continuous Player Sets," Journal of Economic Theory, Elsevier, vol. 97(1), pages 81-108, March.
    5. Hervé Moulin & Scott Shenker, 2001. "Strategyproof sharing of submodular costs:budget balance versus efficiency," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 18(3), pages 511-533.
    6. H. Peyton Young, 1987. "On Dividing an Amount According to Individual Claims or Liabilities," Mathematics of Operations Research, INFORMS, vol. 12(3), pages 398-414, August.
    7. 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.
    8. Hervé Moulin, 2008. "The price of anarchy of serial, average and incremental cost sharing," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 36(3), pages 379-405, September.
    9. 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.
    10. Moulin, Herve, 2002. "Axiomatic cost and surplus sharing," Handbook of Social Choice and Welfare, in: K. J. Arrow & A. K. Sen & K. Suzumura (ed.), Handbook of Social Choice and Welfare, edition 1, volume 1, chapter 6, pages 289-357, Elsevier.
    11. William Thomson, 2007. "On the existence of consistent rules to adjudicate conflicting claims: a constructive geometric approach," Review of Economic Design, Springer;Society for Economic Design, vol. 11(3), pages 225-251, November.
    12. 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.
    13. , & , & ,, 2007. "Secure implementation," Theoretical Economics, Econometric Society, vol. 2(3), September.
    14. Young, H. P., 1988. "Distributive justice in taxation," Journal of Economic Theory, Elsevier, vol. 44(2), pages 321-335, April.
    15. Stefano Lovo, 2009. "Preopening and equilibrium selection," Post-Print hal-00495940, HAL.
    16. 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-519, March.
    17. Russell Cooper & Douglas V. DeJong & Robert Forsythe & Thomas W. Ross, 1992. "Communication in Coordination Games," The Quarterly Journal of Economics, President and Fellows of Harvard College, vol. 107(2), pages 739-771.
    18. Juarez, Ruben, 2013. "Group strategyproof cost sharing: The role of indifferences," Games and Economic Behavior, Elsevier, vol. 82(C), pages 218-239.
    19. Hervé Moulin, 2000. "Priority Rules and Other Asymmetric Rationing Methods," Econometrica, Econometric Society, vol. 68(3), pages 643-684, May.
    20. 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.
    21. Levent Ülkü, 2013. "Optimal combinatorial mechanism design," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 53(2), pages 473-498, June.
    22. Chambers, Christopher P., 2006. "Asymmetric rules for claims problems without homogeneity," Games and Economic Behavior, Elsevier, vol. 54(2), pages 241-260, February.
    23. K. J. Arrow & A. K. Sen & K. Suzumura (ed.), 2002. "Handbook of Social Choice and Welfare," Handbook of Social Choice and Welfare, Elsevier, edition 1, volume 1, number 1.
    24. Roger B. Myerson, 1981. "Optimal Auction Design," Mathematics of Operations Research, INFORMS, vol. 6(1), pages 58-73, February.
    25. HervÊ Moulin, 1999. "Incremental cost sharing: Characterization by coalition strategy-proofness," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 16(2), pages 279-320.
    26. Kim, Youngse, 1996. "Equilibrium Selection inn-Person Coordination Games," Games and Economic Behavior, Elsevier, vol. 15(2), pages 203-227, August.
    27. Ruben Juarez, 2008. "The worst absolute surplus loss in the problem of commons: random priority versus average cost," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 34(1), pages 69-84, January.
    28. Sharkey, W.W., 1991. "Network Models in Economics," Papers 69, Bell Communications - Economic Research Group.
    29. Andelman, Nir & Feldman, Michal & Mansour, Yishay, 2009. "Strong price of anarchy," Games and Economic Behavior, Elsevier, vol. 65(2), pages 289-317, March.
    30. 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.
    31. Monderer, Dov & Shapley, Lloyd S., 1996. "Potential Games," Games and Economic Behavior, Elsevier, vol. 14(1), pages 124-143, May.
    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


    Cited by:

    1. Ruben Juarez & Jung S. You, 2019. "Optimality of the uniform rule under single-peaked preferences," Economic Theory Bulletin, Springer;Society for the Advancement of Economic Theory (SAET), vol. 7(1), pages 27-36, May.
    2. Andreas Darmann & Christian Klamler & Ulrich Pferschy, 2015. "Sharing the Cost of a Path," Studies in Microeconomics, , vol. 3(1), pages 1-12, June.
    3. Hougaard, Jens Leth & Tvede, Mich, 2015. "Minimum cost connection networks: Truth-telling and implementation," Journal of Economic Theory, Elsevier, vol. 157(C), pages 76-99.
    4. 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.
    5. Kristal K. Trejo & Ruben Juarez & Julio B. Clempner & Alexander S. Poznyak, 2023. "Non-Cooperative Bargaining with Unsophisticated Agents," Computational Economics, Springer;Society for Computational Economics, vol. 61(3), pages 937-974, March.
    6. Hougaard, Jens Leth & Tvede, Mich, 2022. "Trouble comes in threes: Core stability in minimum cost connection networks," European Journal of Operational Research, Elsevier, vol. 297(1), pages 319-324.
    7. María Gómez-Rúa & Juan Vidal-Puga, 2017. "A monotonic and merge-proof rule in minimum cost spanning tree situations," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 63(3), pages 813-826, March.
    8. Sinan Ertemel & Rajnish Kumar, 2018. "Proportional rules for state contingent claims," International Journal of Game Theory, Springer;Game Theory Society, vol. 47(1), pages 229-246, March.
    9. Ruben Juarez & Michael Wu, 2019. "Routing-Proofness in Congestion-Prone Networks," Games, MDPI, vol. 10(2), pages 1-18, April.
    10. Juarez, Ruben & Ko, Chiu Yu & Xue, Jingyi, 2018. "Sharing sequential values in a network," Journal of Economic Theory, Elsevier, vol. 177(C), pages 734-779.
    11. Bhardwaj, Bhavook & Kumar, Rajnish & Ortega, Josué, 2020. "Fairness and efficiency in cake-cutting with single-peaked preferences," Economics Letters, Elsevier, vol. 190(C).
    12. 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.
    13. Ruben Juarez & Kohei Nitta, 2017. "Profit-Sharing and Implementation of Efficient Outcomes," Working Papers 201702, University of Hawaii at Manoa, Department of Economics.
    14. Ruben Juarez & Kohei Nitta & Miguel Vargas, 2020. "Profit-sharing and efficient time allocation," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 70(3), pages 817-846, October.
    15. Han, Lining & Juarez, Ruben, 2018. "Free intermediation in resource transmission," Games and Economic Behavior, Elsevier, vol. 111(C), pages 75-84.
    16. Jung S. You & Ruben Juarez, 2021. "Incentive-compatible simple mechanisms," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 71(4), pages 1569-1589, June.
    17. Julio R. Fernández & Inés Gallego & Andrés Jiménez-Losada & Manuel Ordóñez, 2022. "Cost-allocation problems for fuzzy agents in a fixed-tree network," Fuzzy Optimization and Decision Making, Springer, vol. 21(4), pages 531-551, December.
    18. Jens Leth Hougaard & Mich Tvede, 2020. "Implementation of Optimal Connection Networks," IFRO Working Paper 2020/06, University of Copenhagen, Department of Food and Resource Economics.
    19. Jens Leth Hougaard & Mich Tvede, 2020. "Trouble Comes in Threes: Core stability in Minimum Cost Connection Networks," IFRO Working Paper 2020/07, University of Copenhagen, Department of Food and Resource Economics.
    20. Juarez, Ruben & Nitta, Kohei & Vargas, Miguel, 2021. "Coalitional efficient profit-sharing," Economics Letters, Elsevier, vol. 204(C).

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Juarez, Ruben & Ko, Chiu Yu & Xue, Jingyi, 2018. "Sharing sequential values in a network," Journal of Economic Theory, Elsevier, vol. 177(C), pages 734-779.
    2. Flores-Szwagrzak, Karol, 2015. "Priority classes and weighted constrained equal awards rules for the claims problem," Journal of Economic Theory, Elsevier, vol. 160(C), pages 36-55.
    3. Thomson, William, 2015. "Axiomatic and game-theoretic analysis of bankruptcy and taxation problems: An update," Mathematical Social Sciences, Elsevier, vol. 74(C), pages 41-59.
    4. Long, Yan & Sethuraman, Jay & Xue, Jingyi, 2021. "Equal-quantile rules in resource allocation with uncertain needs," Journal of Economic Theory, Elsevier, vol. 197(C).
    5. Carmen Herrero & Juan Moreno-Ternero & Giovanni Ponti, 2010. "On the adjudication of conflicting claims: an experimental study," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 34(1), pages 145-179, January.
    6. 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.
    7. Moreno-Ternero, Juan D. & Villar, Antonio, 2004. "The Talmud rule and the securement of agents' awards," Mathematical Social Sciences, Elsevier, vol. 47(2), pages 245-257, March.
    8. Moulin, Herve, 2002. "Axiomatic cost and surplus sharing," Handbook of Social Choice and Welfare, in: K. J. Arrow & A. K. Sen & K. Suzumura (ed.), Handbook of Social Choice and Welfare, edition 1, volume 1, chapter 6, pages 289-357, Elsevier.
    9. Hokari, Toru & Thomson, William, 2008. "On properties of division rules lifted by bilateral consistency," Journal of Mathematical Economics, Elsevier, vol. 44(11), pages 1057-1071, December.
    10. Stovall, John E., 2014. "Collective rationality and monotone path division rules," Journal of Economic Theory, Elsevier, vol. 154(C), pages 1-24.
    11. Harless, Patrick, 2017. "Wary of the worst: Maximizing award guarantees when new claimants may arrive," Games and Economic Behavior, Elsevier, vol. 105(C), pages 316-328.
    12. José-Manuel Giménez-Gómez & M. Marco-Gil, 2014. "A new approach for bounding awards in bankruptcy problems," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 43(2), pages 447-469, August.
    13. Karol Flores-Szwagrzak & Jaume García-Segarra & Miguel Ginés-Vilar, 2020. "Priority and proportionality in bankruptcy," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 54(4), pages 559-579, April.
    14. Erik Ansink & Hans-Peter Weikard, 2012. "Sequential sharing rules for river sharing problems," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 38(2), pages 187-210, February.
    15. Jingyi Xue, 2018. "Fair division with uncertain needs," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 51(1), pages 105-136, June.
    16. Jens Hougaard & Juan Moreno-Ternero & Lars Østerdal, 2013. "Rationing in the presence of baselines," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 40(4), pages 1047-1066, April.
    17. Andrea Gallice, 2019. "Bankruptcy problems with reference-dependent preferences," International Journal of Game Theory, Springer;Game Theory Society, vol. 48(1), pages 311-336, March.
    18. Hougaard, Jens Leth & Moreno-Ternero, Juan D. & Østerdal, Lars Peter, 2012. "A unifying framework for the problem of adjudicating conflicting claims," Journal of Mathematical Economics, Elsevier, vol. 48(2), pages 107-114.
    19. Maurice Koster, 2012. "Consistent cost sharing," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 75(1), pages 1-28, February.
    20. Jaume García-Segarra & Miguel Ginés-Vilar, 2023. "Additive adjudication of conflicting claims," International Journal of Game Theory, Springer;Game Theory Society, vol. 52(1), pages 93-116, March.

    More about this item

    Keywords

    Cost-sharing; Implementation; Average Cost; Egalitarian Mechanism.;
    All these keywords.

    JEL classification:

    • C70 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - General
    • C72 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Noncooperative Games
    • D71 - Microeconomics - - Analysis of Collective Decision-Making - - - Social Choice; Clubs; Committees; Associations
    • D85 - Microeconomics - - Information, Knowledge, and Uncertainty - - - Network Formation

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:hai:wpaper:201022. See general information about how to correct material in RePEc.

    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 CitEc recognized a bibliographic reference but did not link an item in RePEc 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 RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Web Technician (email available below). General contact details of provider: https://edirc.repec.org/data/deuhius.html .

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

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.