Skip to main content
SpringerLink
Log in

Strategic cooperation in cost sharing games

  • Published:
International Journal of Game Theory Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Albers S (2009) On the value of coordination in network design. SIAM J Comput 38(6): 2273–2302

    Article  Google Scholar 

  • Andelman N, Feldman M, Mansour Y (2009) Strong price of anarchy. Games Econ Behav 65(2): 289–317

    Article  Google Scholar 

  • Anshelevich E, Caskurlu B (2011a) Price of stability in survivable network design. Theory Comput Syst 49(1): 98–138

    Article  Google Scholar 

  • Anshelevich E, Caskurlu B (2011b) Exact and approximate equilibria for optimal group network formation. Theor Comput Sci 412(39): 5298–5314

    Article  Google Scholar 

  • Anshelevich E, Karagiozova A (2011) Terminal backup, 3D matching, and covering cubic graphs. SIAM J Comput 40(3): 678–708

    Article  Google Scholar 

  • Anshelevich E, Dasgupta A, Kleinberg J, Roughgarden T, Tardos É, Wexler T (2008a) The price of stability for network design with fair cost allocation. SIAM J Comput 38(4): 1602–1623

    Article  Google Scholar 

  • Anshelevich E, Dasgupta A, Tardos É, Wexler T (2008b) Near-optimal network design with selfish agents. Theory Comput 4: 77–109

    Article  Google Scholar 

  • Anshelevich E, Caskurlu B, Hate A (2010) Strategic multiway cut and multicut games. In: Proc. 8th intl. workshop approximation and online algorithms (WAOA), pp 1–12

  • Aumann R (1959) Acceptable points in general cooperative n-person games. In: Contributions to the theory of games IV, vol 40 of annals of mathematics study. Princeton University Press, Princeton, pp 287–324

    Google Scholar 

  • Bird C (1976) On cost allocation for a spanning tree: a game theoretic approach. Networks 6: 335–350

    Article  Google Scholar 

  • Calinescu G, Karloff H, Rabani Y (2000) An improved approximation algorithm for multiway cut. J Comput Syst Sci 60(3): 564–574

    Article  Google Scholar 

  • Cardinal J, Hoefer M (2010) Non-cooperative facility location and covering games. Theor Comput Sci 411(16–18): 1855–1876

    Article  Google Scholar 

  • Chen H-L, Roughgarden T, Valiant G (2010) Designing network protocols for good equilibria. SIAM J Comput 39(5): 1799–1832

    Article  Google Scholar 

  • Deng X, Ibaraki T, Nagamochi H (1999) Algorithmic aspects of the core of combinatorial optimization games. Math Oper Res 24(3): 751–766

    Article  Google Scholar 

  • Epstein A, Feldman M, Mansour Y (2009) Strong equilibrium in cost sharing connection games. Games Econ Behav 67(1): 51–68

    Article  Google Scholar 

  • Faigle U, Fekete S, Hochstättler W, Kern W (1998) On approximately fair cost allocation in Euclidean TSP games. OR Spektrum 20(1): 29–37

    Article  Google Scholar 

  • Goemans M, Skutella M (2004) Cooperative facility location games. J Algorithms 50(2): 194–214

    Article  Google Scholar 

  • Goemans M, Williamson D (1995) A general approximation technique for constrained forest problems. SIAM J Comput 24(2): 296–317

    Article  Google Scholar 

  • Granot D (1986) A generalized linear production model: a unifying model. Math Prog 34: 212–222

    Article  Google Scholar 

  • Granot D, Huberman G (1981) On minimum cost spanning tree games. Math Prog 21: 1–18

    Article  Google Scholar 

  • Granot D, Maschler M (1998) Spanning network games. Int J Game Theory 27: 467–500

    Article  Google Scholar 

  • Hoefer M (2009) Non-cooperative tree creation. Algorithmica 53(1): 104–131

    Article  Google Scholar 

  • Hoefer M (2010) Strategic cooperation in cost sharing games. In: Proc. 6th intl workshop Internet and network economics (WINE), pp 258–269

  • Hoefer M (2011) Competitive cost sharing with economies of scale. Algorithmica 60(4): 743–765

    Article  Google Scholar 

  • Hoefer M, Krysta P (2005) Geometric network design with selfish agents. In: Proc. 11th conf. computing and combinatorics (COCOON), pp 167–178

  • Immorlica N, Mahdian M, Mirrokni V (2008) Limitations of cross-monotonic cost sharing schemes. ACM Trans Algorithms 4(2). doi:10.1145/1361192.1361201

  • Jain K, Mahdian M (2007) Cost sharing. In: Nisan N, Tardos É, Roughgarden T, Vazirani V (eds) Algorithmic game theory, chapter 15. Cambridge University Press, Cambridge

    Google Scholar 

  • Jain K, Vazirani V (2001) Applications of approximation algorithms to cooperative games. In: Proc. 33rd symp. theory of computing (STOC), pp 364–372

  • Könemann J, Leonardi S, Schäfer G, van Zwam S (2008) A group-strategyproof cost sharing mechanism for the Steiner forest game. SIAM J Comput 37(5): 1319–1341

    Article  Google Scholar 

  • Leonardi S, Sankowski P (2007) Network formation games with local coalitions. In Proc. 26th symp. principles of distributed computing (PODC), pp 299–305

  • Megiddo N (1978) Cost allocation for Steiner trees. Networks 8(1): 1–6

    Article  Google Scholar 

  • Owen G (1975) On the core of linear production games. Math Prog 9: 358–370

    Article  Google Scholar 

  • Pál M, Tardos É (2003) Group strategyproof mechanisms via primal-dual algorithms. In: Proc. 44th symp. foundations of computer science (FOCS), pp 584–593

  • Prodon A, Libeling TM, Gröflin H (1985) Steiner’s problem on two-trees. Technical report, Départment de Mathemátiques, EPF Lausanne. Working paper RO 850315

  • Skorin-Karpov D (1995) On the core of the minimum cost Steiner tree game in networks. Ann Oper Res 57: 233–249

    Article  Google Scholar 

  • Tamir A (1991) On the core of network synthesis games. Math Prog 50: 123–135

    Article  Google Scholar 

  • Tamir A (1993) On the core of cost allocation games defined on location problems. Transp Sci 27: 81–86

    Article  Google Scholar 

  • Wong R (1984) A dual ascent approach for Steiner tree problems on a directed graph. Math Prog 28(3): 271–287

    Article  Google Scholar 

  • Young HP (1994) Cost allocation. In: Aumann R, Hart S (eds) Handbook of game theory with economic applications vol 2, Chap 34. North-Holland Science Publishers, Amsterdam, pp 1194–1235

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. RWTH Aachen University, Lehrstuhl Informatik I, 52074, Aachen, Germany

    Martin Hoefer

Authors
  1. Martin Hoefer
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Martin Hoefer.

Additional information

An extended abstract of this work appeared in the Proceedings of the 6th Workshop on Internet and Network Economics (Hoefer 2010).

Rights and permissions

Reprints and permissions

About this article

Cite this article

Hoefer, M. Strategic cooperation in cost sharing games. Int J Game Theory 42, 29–53 (2013). https://doi.org/10.1007/s00182-011-0312-8

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00182-011-0312-8

Keywords

Search

Navigation