• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Symposium on Mathematical Foundations of Computer Science >Multicast Transmissions in Non-cooperative Networks with a Limited Number of Selfish Moves
【24h】

Multicast Transmissions in Non-cooperative Networks with a Limited Number of Selfish Moves

机译：非协作网络中的多播传输，具有有限数量的自私动作

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We study a multicast game in communication networks in which a source sends the same message or service to a set of destinations and the cost of the used links is divided among the receivers according to given cost sharing methods. Assuming a selfish and rational behavior, each receiving user is willing to select a strategy yielding the minimum shared cost. A Nash equilibrium is a solution in which no user can decrease its payment by adopting a different strategy, and the price of anarchy is defined as the worst case ratio between the overall communication cost yielded by an equilibrium and the minimum possible one. Nash equilibria requiring an excessive number of steps to be reached or being hard to compute or not existing at all, we are interested in the determination of the price of anarchy reached in a limited number of rounds, each of which containing at least one move per receiving user. We consider different reasonable cost sharing methods, including the well-known Shapley and egalitarian ones, and investigate their performances versus two possible global criteria: the overall cost of the used links and the maximum shared cost of users. We show that, even in case of two receivers making the best possible move at each step, the number of steps needed to reach a Nash equilibrium can be arbitrarily large. Moreover, we determine the cost sharing methods for which a single round is already sufficient to get a price of anarchy comparable to the one at equilibria, and the ones not satisfying such a property. Finally, we show that finding the sequence of moves leading to the best possible global performance after one-round is already an intractable problem, i.e., NP-hard.
机译：我们在通信网络中研究多播游戏，其中源将相同的消息或服务发送到一组目的地，并且根据给定的成本共享方法在接收器中划分使用的链路的成本。假设自私和合理的行为，每个接收用户愿意选择产生最小共享成本的策略。纳什均衡是一种解决方案，其中通过采用不同的策略，没有用户可以减少其支付，并且无政府状态的价格被定义为总线纤维的整体通信成本与最小可能的策略之间的最坏情况比。纳什均衡需要达到过多的步骤或根本难以计算或不努力计算或不存在，我们有兴趣确定在有限数量数量的无政府状态价格确定，每个人都包含至少一个移动接收用户。我们考虑了不同合理的成本共享方法，包括众所周知的福利人和平等主义者，并调查他们的表现与两个可能的全局标准：使用的链路的总成本和用户的最大共享成本。我们展示了，即使在两个接收器的情况下，也可以在每个步骤中做出最好的移动，所需的步骤数量可以是任意大的。此外，我们确定一个轮的成本共享方法已经足以获得与均衡处相当的无政府状态价格，以及不满足这种财产的无政府关系。最后，我们表明，在一轮后，找到导致最佳可能的全局性能的动作序列已经是一个难以处理的问题，即，NP-HARD。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号