Strong equilibrium in cost sharing connection games

• 成果类型: Article; Proceedings Paper
• 署名作者: Epstein, Amir; Feldman, Michal; Mansour, Yishay
• 署名单位: Hebrew University of Jerusalem; Hebrew University of Jerusalem; Tel Aviv University
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2008.07.002
• 发表日期: 2009
• 页码: 51-68
• 关键词: Strong equilibrium; Price of anarchy; Strong price of anarchy; coalitions; cost sharing; Network design

摘要

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 it 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 an), GCG, any SE is optimal. (C) 2008 Elsevier Inc. All rights reserved.