首页> 外文会议>Algorithmic game theory >Price of Stability in Survivable Network Design
【24h】

Price of Stability in Survivable Network Design

机译:生存网络设计中的稳定性代价

获取原文
获取原文并翻译 | 示例

摘要

We study the survivable version of the game theoretic network formation model known as the Connection Game, originally introduced in [4]. In this model, players attempt to connect to a common source node in a network by purchasing edges, and sharing their costs with other players. We introduce the survivable version of this game, where each player desires 2 edge-disjoint connections between her pair of nodes instead of just a single connecting path, and analyze the quality of exact and approximate Nash equilibria. For the special case where each node represents a player, we show that Nash equilibria are guaranteed to exist and price of stability is 1. For the general version of the Survivable Connection Game, we show that there always exists a 2-approximate Nash equilibrium that is as cheap as the socially optimal solution.
机译:我们研究了被称为连接游戏的博弈论网络形成模型的可生存版本,该模型最初在[4]中引入。在此模型中,玩家尝试通过购买边缘并与其他玩家分担费用来连接到网络中的公共源节点。我们介绍了该游戏的可生存版本,其中,每个玩家都希望在其成对的节点之间有2条边缘不相连的连接,而不仅仅是一条连接路径,并分析精确和近似Nash均衡的质量。对于每个节点代表一个玩家的特殊情况,我们证明了纳什均衡存在,并且稳定价格为1。对于一般版本的《生存连接博弈》,我们表明始终存在一个2近似的纳什均衡,即与社会最优解决方案一样便宜。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号