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

    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. Arie Tamir, 1993. "On the Core of Cost Allocation Games Defined on Location Problems," Transportation Science, INFORMS, vol. 27(1), pages 81-86, February.
    4. Andelman, Nir & Feldman, Michal & Mansour, Yishay, 2009. "Strong price of anarchy," Games and Economic Behavior, Elsevier, vol. 65(2), pages 289-317, March.
    5. Daniel Granot & Michael Maschler, 1998. "Spanning network games," International Journal of Game Theory, Springer;Game Theory Society, vol. 27(4), pages 467-500.
    6. 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.
    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. Moulin, Hervé, 2014. "Pricing traffic in a spanning network," Games and Economic Behavior, Elsevier, vol. 86(C), pages 475-490.
    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. 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. 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. 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.
    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. Moulin, Hervé, 2014. "Pricing traffic in a spanning network," Games and Economic Behavior, Elsevier, vol. 86(C), pages 475-490.
    5. 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.
    6. 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.
    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. "Pareto optimal equilibria for selfish bin packing with uniform cost sharing," Journal of Combinatorial Optimization, Springer, vol. 37(3), pages 827-847, April.
    9. Krzysztof R. Apt & Bart Keijzer & Mona Rahn & Guido Schäfer & Sunil Simon, 2017. "Coordination games on graphs," International Journal of Game Theory, Springer;Game Theory Society, vol. 46(3), pages 851-877, August.
    10. Marco Faravelli & Randall Walsh, 2011. "Smooth Politicians And Paternalistic Voters: A Theory Of Large Elections," Levine's Working Paper Archive 786969000000000250, David K. Levine.
    11. Argenton, Cédric & Willems, Bert, 2015. "Exclusion through speculation," International Journal of Industrial Organization, Elsevier, vol. 39(C), pages 1-9.
    12. 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.
    13. Steven J. Brams & Michael A. Jones & D. Marc Kilgour, 2002. "Single-Peakedness and Disconnected Coalitions," Journal of Theoretical Politics, , vol. 14(3), pages 359-383, July.
    14. Carlos Alós-Ferrer & Jaume García-Segarra & Miguel Ginés-Vilar, 2018. "Anchoring on Utopia: a generalization of the Kalai–Smorodinsky solution," Economic Theory Bulletin, Springer;Society for the Advancement of Economic Theory (SAET), vol. 6(2), pages 141-155, October.
    15. Tatsuya Kitagawa & Yasushi Masuda & Masashi Umezawa, 2020. "Impact of technology development costs on licensing form in a differentiated Cournot duopoly," International Journal of Economic Theory, The International Society for Economic Theory, vol. 16(2), pages 153-166, June.
    16. Youngsub Chun, 2020. "Some Impossibility Results on the Converse Consistency Principle in Bargaining," Homo Oeconomicus: Journal of Behavioral and Institutional Economics, Springer, vol. 37(1), pages 59-65, November.
    17. Meniere, Yann & Parlane, Sarah, 2010. "Decentralized licensing of complementary patents: Comparing the royalty, fixed-fee and two-part tariff regimes," Information Economics and Policy, Elsevier, vol. 22(2), pages 178-191, May.
    18. 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.
    19. Cordoba, Jose M. & Hammond, Peter J., 1998. "Asymptotically strategy-proof Walrasian exchange," Mathematical Social Sciences, Elsevier, vol. 36(3), pages 185-212, December.
    20. André Casajus & Harald Wiese, 2017. "Scarcity, competition, and value," International Journal of Game Theory, Springer;Game Theory Society, vol. 46(2), pages 295-310, May.

    More about this item

    Keywords

    ;
    ;
    ;
    ;

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