IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v59y2011i6p1491-1503.html
   My bibliography  Save this article

The Worst-Case Efficiency of Cost Sharing Methods in Resource Allocation Games

Author

Listed:
  • Tobias Harks

    (Department of Quantitative Economics, Maastricht University, 6200 MD Maastricht, The Netherlands)

  • Konstantin Miller

    (Telecommunication Networks Group, Technische Universität Berlin, 10587 Berlin, Germany)

Abstract

Resource allocation problems play a key role in many applications, including traffic networks, telecommunication networks, and economics. In most applications, the allocation of resources is determined by a finite number of independent players, each optimizing an individual objective function. An important question in all these applications is the degree of suboptimality caused by selfish resource allocation. We consider the worst-case efficiency of cost sharing methods in resource allocation games in terms of the ratio of the minimum guaranteed surplus of a Nash equilibrium and the maximal surplus. Our main technical result is an upper bound on the efficiency loss that depends on the class of allowable cost functions and the class of allowable cost sharing methods. We demonstrate the power of this bound by evaluating the worst-case efficiency loss for three well-known cost sharing methods: incremental cost sharing, marginal cost pricing, and average cost sharing.

Suggested Citation

  • Tobias Harks & Konstantin Miller, 2011. "The Worst-Case Efficiency of Cost Sharing Methods in Resource Allocation Games," Operations Research, INFORMS, vol. 59(6), pages 1491-1503, December.
    • Handle: RePEc:inm:oropre:v:59:y:2011:i:6:p:1491-1503
    DOI: 10.1287/opre.1110.0979
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1110.0979
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1110.0979?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Patrick T. Harker, 1988. "Multiple Equilibrium Behaviors on Networks," Transportation Science, INFORMS, vol. 22(1), pages 39-46, February.
    2. 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.
    3. William Novshek, 1985. "On the Existence of Cournot Equilibrium," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 52(1), pages 85-98.
    4. Yang, Hai & Xu, Wei & Heydecker, Benjamin, 2010. "Bounding the efficiency of road pricing," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 46(1), pages 90-108, January.
    5. Roberto Cominetti & José R. Correa & Nicolás E. Stier-Moses, 2009. "The Impact of Oligopolistic Competition in Networks," Operations Research, INFORMS, vol. 57(6), pages 1421-1437, December.
    6. Samet, Dov & Tauman, Yair, 1982. "The Determination of Marginal Cost Prices under a Set of Axioms," Econometrica, Econometric Society, vol. 50(4), pages 895-909, July.
    7. Daron Acemoglu & Asuman Ozdaglar, 2007. "Competition and Efficiency in Congested Markets," Mathematics of Operations Research, INFORMS, vol. 32(1), pages 1-31, February.
    8. Smith, M. J., 1979. "The marginal cost taxation of a transportation network," Transportation Research Part B: Methodological, Elsevier, vol. 13(3), pages 237-242, September.
    9. Hai Yang & Deren Han & Hong Lo, 2008. "Efficiency of Atomic Splittable Selfish Routing with Polynomial Cost Functions," Networks and Spatial Economics, Springer, vol. 8(4), pages 443-451, December.
    10. F. H. Knight, 1924. "Some Fallacies in the Interpretation of Social Cost," The Quarterly Journal of Economics, President and Fellows of Harvard College, vol. 38(4), pages 582-606.
    11. José R. Correa & Andreas S. Schulz & Nicolás E. Stier-Moses, 2004. "Selfish Routing in Capacitated Networks," Mathematics of Operations Research, INFORMS, vol. 29(4), pages 961-976, November.
    12. Yang, Hai & Zhang, Xiaoning, 2008. "Existence of anonymous link tolls for system optimum on networks with mixed equilibrium behaviors," Transportation Research Part B: Methodological, Elsevier, vol. 42(2), pages 99-112, February.
    13. Yang, Hai & Huang, Hai-Jun, 2004. "The multi-class, multi-criteria traffic network equilibrium and systems optimum problem," Transportation Research Part B: Methodological, Elsevier, vol. 38(1), pages 1-15, January.
    14. Ramesh Johari & John N. Tsitsiklis, 2004. "Efficiency Loss in a Network Resource Allocation Game," Mathematics of Operations Research, INFORMS, vol. 29(3), pages 407-435, August.
    15. Ramesh Johari & John N. Tsitsiklis, 2009. "Efficiency of Scalar-Parameterized Mechanisms," Operations Research, INFORMS, vol. 57(4), pages 823-839, August.
    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. Fielbaum, Andres & Kucharski, Rafał & Cats, Oded & Alonso-Mora, Javier, 2022. "How to split the costs and charge the travellers sharing a ride? aligning system’s optimum with users’ equilibrium," European Journal of Operational Research, Elsevier, vol. 301(3), pages 956-973.
    2. Tami Tamir, 2023. "Cost-sharing games in real-time scheduling systems," International Journal of Game Theory, Springer;Game Theory Society, vol. 52(1), pages 273-301, March.
    3. Zhenliang Liao & Phillip Hannam, 2013. "The Mekong Game: Achieving an All-win Situation," Water Resources Management: An International Journal, Published for the European Water Resources Association (EWRA), Springer;European Water Resources Association (EWRA), vol. 27(7), pages 2611-2622, May.
    4. Philipp von Falkenhausen & Tobias Harks, 2013. "Optimal Cost Sharing for Resource Selection Games," Mathematics of Operations Research, INFORMS, vol. 38(1), pages 184-208, February.
    5. Vasilis Gkatzelis & Konstantinos Kollias & Tim Roughgarden, 2016. "Optimal Cost-Sharing in General Resource Selection Games," Operations Research, INFORMS, vol. 64(6), pages 1230-1238, December.
    6. Harks, Tobias & von Falkenhausen, Philipp, 2014. "Optimal cost sharing for capacitated facility location games," European Journal of Operational Research, Elsevier, vol. 239(1), pages 187-198.

    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. Roberto Cominetti & José R. Correa & Nicolás E. Stier-Moses, 2009. "The Impact of Oligopolistic Competition in Networks," Operations Research, INFORMS, vol. 57(6), pages 1421-1437, December.
    2. Feng, Zengzhe & Gao, Ziyou & Sun, Huijun, 2014. "Bounding the inefficiency of atomic splittable selfish traffic equilibria with elastic demands," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 63(C), pages 31-43.
    3. Harks, Tobias & Schröder, Marc & Vermeulen, Dries, 2019. "Toll caps in privatized road networks," European Journal of Operational Research, Elsevier, vol. 276(3), pages 947-956.
    4. Vincenzo Bonifaci & Tobias Harks & Guido Schäfer, 2010. "Stackelberg Routing in Arbitrary Networks," Mathematics of Operations Research, INFORMS, vol. 35(2), pages 330-346, May.
    5. Balmaceda, Felipe & Balseiro, Santiago R. & Correa, José R. & Stier-Moses, Nicolás E., 2016. "Bounds on the welfare loss from moral hazard with limited liability," Games and Economic Behavior, Elsevier, vol. 95(C), pages 137-155.
    6. (Walker) Wang, Wei & Wang, David Z.W. & Sun, Huijun & Feng, Zengzhe & Wu, Jianjun, 2016. "Braess Paradox of traffic networks with mixed equilibrium behaviors," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 93(C), pages 95-114.
    7. Wang, Hua & Meng, Qiang & Zhang, Xiaoning, 2020. "Multiple equilibrium behaviors of auto travellers and a freight carrier under the cordon-based large-truck restriction regulation," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 134(C).
    8. Hugo E. Silva & Robin Lindsey & André de Palma & Vincent A. C. van den Berg, 2017. "On the Existence and Uniqueness of Equilibrium in the Bottleneck Model with Atomic Users," Transportation Science, INFORMS, vol. 51(3), pages 863-881, August.
    9. Ramesh Johari & John N. Tsitsiklis, 2011. "Parameterized Supply Function Bidding: Equilibrium and Efficiency," Operations Research, INFORMS, vol. 59(5), pages 1079-1089, October.
    10. Roughgarden, Tim & Schoppmann, Florian, 2015. "Local smoothness and the price of anarchy in splittable congestion games," Journal of Economic Theory, Elsevier, vol. 156(C), pages 317-342.
    11. Cheng Wan, 2016. "Strategic decentralization in binary choice composite congestion games," Post-Print hal-02885837, HAL.
    12. Yang, Hai & Zhang, Xiaoning, 2008. "Existence of anonymous link tolls for system optimum on networks with mixed equilibrium behaviors," Transportation Research Part B: Methodological, Elsevier, vol. 42(2), pages 99-112, February.
    13. Huibing Yin & Prashant Mehta & Sean Meyn & Uday Shanbhag, 2014. "On the Efficiency of Equilibria in Mean-Field Oscillator Games," Dynamic Games and Applications, Springer, vol. 4(2), pages 177-207, June.
    14. Wan, Cheng, 2016. "Strategic decentralization in binary choice composite congestion games," European Journal of Operational Research, Elsevier, vol. 250(2), pages 531-542.
    15. Liu, Tian-Liang & Chen, Jian & Huang, Hai-Jun, 2011. "Existence and efficiency of oligopoly equilibrium under toll and capacity competition," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 47(6), pages 908-919.
    16. Haoning Xi & Liu He & Yi Zhang & Zhen Wang, 2020. "Bounding the efficiency gain of differentiable road pricing for EVs and GVs to manage congestion and emissions," PLOS ONE, Public Library of Science, vol. 15(7), pages 1-36, July.
    17. Harks, Tobias & von Falkenhausen, Philipp, 2014. "Optimal cost sharing for capacitated facility location games," European Journal of Operational Research, Elsevier, vol. 239(1), pages 187-198.
    18. Patrick Maillé & Nicolás E. Stier-Moses, 2009. "Eliciting Coordination with Rebates," Transportation Science, INFORMS, vol. 43(4), pages 473-492, November.
    19. Philipp von Falkenhausen & Tobias Harks, 2013. "Optimal Cost Sharing for Resource Selection Games," Mathematics of Operations Research, INFORMS, vol. 38(1), pages 184-208, February.
    20. Sylvain Sorin & Cheng Wan, 2016. "Finite composite games: Equilibria and dynamics," Post-Print hal-02885860, HAL.

    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:inm:oropre:v:59:y:2011:i:6:p:1491-1503. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.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.