Strong equilibrium in cost sharing connection games

Amir Epstein, Michal Feldman and Yishay Mansour

Games and Economic Behavior, 2009, vol. 67, issue 1, 51-68

Abstract: We study network games in which each player wishes to connect his source and sink, and the cost of each edge is shared among its users either equally (in Fair Connection Games--FCG's) or arbitrarily (in General Connection Games--GCG's). We study the existence and quality of strong equilibria (SE)--strategy profiles from which no coalition can improve the cost of each of its members--in these settings. We show that SE always exist in the following games: (1) Single source and sink FCG's and GCG's. (2) Single source multiple sinks FCG's and GCG's on series parallel graphs. (3) Multi source and sink FCG's on extension parallel graphs. As for the quality of the SE, in any FCG with n players, the cost of any SE is bounded by H(n) (i.e., the harmonic sum), contrasted with the [Theta](n) price of anarchy. For any GCG, any SE is optimal.

Keywords: Strong; equilibrium; Price; of; anarchy; Strong; price; of; anarchy; Coalitions; Cost; sharing; Network; design (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (23)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0899-8256(08)00138-3
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:gamebe:v:67:y:2009:i:1:p:51-68

Access Statistics for this article

Games and Economic Behavior is currently edited by E. Kalai

More articles in Games and Economic Behavior from Elsevier
Bibliographic data for series maintained by Catherine Liu ().