首页> 外文会议>Algorithms and complexity >Online Cooperative Cost Sharing
【24h】

Online Cooperative Cost Sharing

机译:在线合作成本分摊

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

摘要

The problem of sharing the cost of a common infrastructure among a set of strategic and cooperating players has been the subject of intensive research in recent years. However, most of these studies consider cooperative cost sharing games in an offline setting, i.e., the mechanism knows all players and their respective input data in advance. In this paper, we consider cooperative cost sharing games in an online setting: Upon the arrival of a new player, the mechanism has to take instantaneous and irreversible decisions without any knowledge about players that arrive in the future. We propose an online model for general demand cost sharing games and give a complete characterization of both weakly group-strategyproof and group-strategyproof online cost sharing mechanisms for this model. Moreover, we present a simple method to derive incremental online cost sharing mechanisms from online algorithms such that the competitive ratio is preserved. Based on our general results, we develop online cost sharing mechanisms for several binary demand and general demand cost sharing games.
机译:近年来,在一组战略合作伙伴之间分担共同基础设施成本的问题一直是深入研究的主题。然而,这些研究中的大多数都考虑了离线环境下的合作成本分摊游戏,即该机制提前知道了所有参与者及其各自的输入数据。在本文中,我们考虑了在线环境下的合作成本共享游戏:新玩家到来后,该机制必须做出即时且不可逆转的决策,而无需任何有关未来玩家的知识。我们为一般需求成本分摊游戏提出了一个在线模型,并给出了该模型的弱群体策略和群体策略在线成本分担机制的完整描述。此外,我们提出了一种简单的方法,可以从在线算法中获取增量在线成本分担机制,从而保持竞争比。根据我们的总体结果,我们为几种二进制需求和一般需求成本共享游戏开发了在线成本共享机制。

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号