IDEAS home Printed from https://ideas.repec.org/a/spr/jogath/v42y2013i1p29-53.html
   My bibliography  Save this article

Strategic cooperation in cost sharing games

Author

Listed:
  • Martin Hoefer

Abstract

We examine strategic cost sharing games with so-called arbitrary sharing based on various combinatorial optimization problems. These games have recently been popular in computer science to study cost sharing in the context of the Internet. We concentrate on the existence and computational complexity of strong equilibria (SE), in which no coalition can improve the cost of each of its members. Our main result reveals a connection to the core in coalitional cost sharing games studied in operations research. For set cover and facility location games this results in a tight characterization of the existence of SE using the integrality gap of suitable linear programming formulations. Furthermore, it allows to derive all existing results for SE in network design cost sharing games with arbitrary sharing via a unified approach. In addition, we show that in general there is no efficiency loss, i.e., the strong price of anarchy is always 1. Finally, we indicate how the LP-approach is useful for the computation of near-optimal and near-stable approximate SE. Copyright Springer-Verlag 2013

Suggested Citation

  • Martin Hoefer, 2013. "Strategic cooperation in cost sharing games," International Journal of Game Theory, Springer;Game Theory Society, vol. 42(1), pages 29-53, February.
    • Handle: RePEc:spr:jogath:v:42:y:2013:i:1:p:29-53
    DOI: 10.1007/s00182-011-0312-8
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s00182-011-0312-8
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s00182-011-0312-8?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. 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.
    2. R.J. Aumann & S. Hart (ed.), 2002. "Handbook of Game Theory with Economic Applications," Handbook of Game Theory with Economic Applications, Elsevier, edition 1, volume 3, number 3.
    3. Daniel Granot & Michael Maschler, 1998. "Spanning network games," International Journal of Game Theory, Springer;Game Theory Society, vol. 27(4), pages 467-500.
    4. Xiaotie Deng & Toshihide Ibaraki & Hiroshi Nagamochi, 1999. "Algorithmic Aspects of the Core of Combinatorial Optimization Games," Mathematics of Operations Research, INFORMS, vol. 24(3), pages 751-766, August.
    5. Arie Tamir, 1993. "On the Core of Cost Allocation Games Defined on Location Problems," Transportation Science, INFORMS, vol. 27(1), pages 81-86, February.
    6. Andelman, Nir & Feldman, Michal & Mansour, Yishay, 2009. "Strong price of anarchy," Games and Economic Behavior, Elsevier, vol. 65(2), pages 289-317, March.
    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. 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.
    2. Vincent Mak & Darryl A. Seale & Eyran J. Gisches & Amnon Rapoport & Meng Cheng & Myounghee Moon & Rui Yang, 2018. "A network ridesharing experiment with sequential choice of transportation mode," Theory and Decision, Springer, vol. 85(3), pages 407-433, October.
    3. Moulin, Hervé, 2014. "Pricing traffic in a spanning network," Games and Economic Behavior, Elsevier, vol. 86(C), pages 475-490.

    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. 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.
    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. Moulin, Hervé, 2014. "Pricing traffic in a spanning network," Games and Economic Behavior, Elsevier, vol. 86(C), pages 475-490.
    4. 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.
    5. 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.
    6. György Dósa & Leah Epstein, 2019. "Pareto optimal equilibria for selfish bin packing with uniform cost sharing," Journal of Combinatorial Optimization, Springer, vol. 37(3), pages 827-847, April.
    7. Dutta, Bhaskar & Kar, Anirban, 2004. "Cost monotonicity, consistency and minimum cost spanning tree games," Games and Economic Behavior, Elsevier, vol. 48(2), pages 223-248, August.
    8. György Dósa & Leah Epstein, 2019. "Quality of strong equilibria for selfish bin packing with uniform cost sharing," Journal of Scheduling, Springer, vol. 22(4), pages 473-485, August.
    9. Marco Faravelli & Randall Walsh, 2011. "Smooth Politicians And Paternalistic Voters: A Theory Of Large Elections," Levine's Working Paper Archive 786969000000000250, David K. Levine.
    10. Ding, Zhanwen & Shi, Guiping, 2009. "Cooperation in a dynamical adjustment of duopoly game with incomplete information," Chaos, Solitons & Fractals, Elsevier, vol. 42(2), pages 989-993.
    11. Jhinyoung Shin & Rajdeep Singh, 2010. "Corporate Disclosures: Strategic Donation of Information," International Review of Finance, International Review of Finance Ltd., vol. 10(3), pages 313-337, September.
    12. Mario Guajardo & Kurt Jörnsten & Mikael Rönnqvist, 2016. "Constructive and blocking power in collaborative transportation," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 38(1), pages 25-50, January.
    13. Sylvie Thoron, 2016. "Morality Beyond Social Preferences: Smithian Sympathy, Social Neuroscience and the Nature of Social Consciousness [La moralité au delà des préférences sociales. La sympathie Smithienne, les neurosc," Post-Print hal-01645043, HAL.
    14. Nan Xia & S. Rajagopalan, 2009. "Standard vs. Custom Products: Variety, Lead Time, and Price Competition," Marketing Science, INFORMS, vol. 28(5), pages 887-900, 09-10.
    15. Gerard Llobet & Javier Suarez, 2010. "Entrepreneurial Innovation, Patent Protection and Industry Dynamics," Working Papers wp2010_1001, CEMFI.
    16. Platz, Trine Tornøe & Østerdal, Lars Peter, 2017. "The curse of the first-in–first-out queue discipline," Games and Economic Behavior, Elsevier, vol. 104(C), pages 165-176.
    17. Jihui Chen & Qiang Fu, 2017. "Do exclusivity arrangements harm consumers?," Journal of Regulatory Economics, Springer, vol. 51(3), pages 311-339, June.
    18. Dinah Rosenberg & Eilon Solan & Nicolas Vieille, 2009. "Protocols with No Acknowledgment," Operations Research, INFORMS, vol. 57(4), pages 905-915, August.
    19. Yusuke Kamishiro & Roberto Serrano & Myrna Wooders, 2021. "Monopolists of scarce information and small group effectiveness in large quasilinear economies," International Journal of Game Theory, Springer;Game Theory Society, vol. 50(4), pages 801-827, December.
    20. Di Feng & Bettina Klaus, 2022. "Preference revelation games and strict cores of multiple‐type housing market problems," International Journal of Economic Theory, The International Society for Economic Theory, vol. 18(1), pages 61-76, March.

    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:spr:jogath:v:42:y:2013:i:1:p:29-53. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.