IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v239y2014i1p187-198.html
   My bibliography  Save this article

Optimal cost sharing for capacitated facility location games

Author

Listed:
  • Harks, Tobias
  • von Falkenhausen, Philipp

Abstract

We consider cost sharing for a class of facility location games, where the strategy space of each player consists of the bases of a player-specific matroid defined on the set of resources. We assume that resources have nondecreasing load-dependent costs and player-specific delays. Our model includes the important special case of capacitated facility location problems, where players have to jointly pay for opened facilities. The goal is to design cost sharing protocols so as to minimize the resulting price of anarchy and price of stability. We investigate two classes of protocols: basic protocols guarantee the existence of at least one pure Nash equilibrium and separable protocols additionally require that the resulting cost shares only depend on the set of players on a resource. We find optimal basic and separable protocols that guarantee the price of stability/price of anarchy to grow logarithmically/linearly in the number of players. These results extend our previous results (cf. von Falkenhausen & Harks, 2013), where optimal basic and separable protocols were given for the case of symmetric matroid games without delays.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:239:y:2014:i:1:p:187-198
    DOI: 10.1016/j.ejor.2014.04.048
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221714003919
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2014.04.048?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. Milchtaich, Igal, 1996. "Congestion Games with Player-Specific Payoff Functions," Games and Economic Behavior, Elsevier, vol. 13(1), pages 111-124, March.
    8. Moulin, Hervé, 2010. "An efficient and almost budget balanced cost sharing method," Games and Economic Behavior, Elsevier, vol. 70(1), pages 107-131, September.
    9. Tobias Harks & Max Klimm, 2012. "On the Existence of Pure Nash Equilibria in Weighted Congestion Games," Mathematics of Operations Research, INFORMS, vol. 37(3), pages 419-436, August.
    10. Martin J. Osborne & Ariel Rubinstein, 1994. "A Course in Game Theory," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262650401, April.
    11. Anna Bogomolnaia & Ron Holzman & Hervé Moulin, 2010. "Sharing the Cost of a Capacity Network," Mathematics of Operations Research, INFORMS, vol. 35(1), pages 173-192, February.
    12. Archer, Aaron & Feigenbaum, Joan & Krishnamurthy, Arvind & Sami, Rahul & Shenker, Scott, 2004. "Approximation and collusion in multicast cost sharing," Games and Economic Behavior, Elsevier, vol. 47(1), pages 36-71, April.
    13. 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.
    14. 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. Tobias Harks & Martin Hoefer & Anja Schedel & Manuel Surek, 2021. "Efficient Black-Box Reductions for Separable Cost Sharing," Mathematics of Operations Research, INFORMS, vol. 46(1), pages 134-158, February.

    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. 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.
    2. 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.
    3. 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.
    4. Ruben Juarez & Rajnish Kumar, 2013. "Implementing efficient graphs in connection networks," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 54(2), pages 359-403, October.
    5. 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.
    6. Ragavendran Gopalakrishnan & Jason R. Marden & Adam Wierman, 2014. "Potential Games Are Necessary to Ensure Pure Nash Equilibria in Cost Sharing Games," Mathematics of Operations Research, INFORMS, vol. 39(4), pages 1252-1296, November.
    7. Hervé Moulin & Yves Sprumont, 2007. "Fair allocation of production externalities : recent results," Revue d'économie politique, Dalloz, vol. 117(1), pages 7-36.
    8. Gaëtan Fournier & Marco Scarsini, 2014. "Hotelling Games on Networks: Efficiency of Equilibria," Documents de travail du Centre d'Economie de la Sorbonne 14033, Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne.
    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. Tobias Harks & Martin Hoefer & Anja Schedel & Manuel Surek, 2021. "Efficient Black-Box Reductions for Separable Cost Sharing," Mathematics of Operations Research, INFORMS, vol. 46(1), pages 134-158, February.
    11. Moulin, Hervé, 2014. "Pricing traffic in a spanning network," Games and Economic Behavior, Elsevier, vol. 86(C), pages 475-490.
    12. 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.
    13. Xiang-Yang Li & Zheng Sun & Weizhao Wang & Wei Lou, 2010. "Cost sharing and strategyproof mechanisms for set cover games," Journal of Combinatorial Optimization, Springer, vol. 20(3), pages 259-284, October.
    14. Tobias Harks & Max Klimm & Rolf Möhring, 2013. "Strong equilibria in games with the lexicographical improvement property," International Journal of Game Theory, Springer;Game Theory Society, vol. 42(2), pages 461-482, May.
    15. 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.
    16. Ibrahim Abada, Andreas Ehrenmann, and Xavier Lambin, 2020. "On the Viability of Energy Communities," The Energy Journal, International Association for Energy Economics, vol. 0(Number 1).
    17. 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.
    18. Corine M. Laan & Judith Timmer & Richard J. Boucherie, 2021. "Non-cooperative queueing games on a network of single server queues," Queueing Systems: Theory and Applications, Springer, vol. 97(3), pages 279-301, April.
    19. Le Breton, Michel & Shapoval, Alexander & Weber, Shlomo, 2021. "A game-theoretical model of the landscape theory," Journal of Mathematical Economics, Elsevier, vol. 92(C), pages 41-46.
    20. Jens Leth Hougaard & Hervé Moulin, 2018. "Sharing the cost of risky projects," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 65(3), pages 663-679, May.

    More about this item

    Keywords

    Game theory; Complexity theory;

    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:eee:ejores:v:239:y:2014:i:1:p:187-198. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.