• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Algorithmic Game Theory >Singleton Acyclic Mechanisms and Their Applications to Scheduling Problems
【24h】

Singleton Acyclic Mechanisms and Their Applications to Scheduling Problems

机译：单子非循环机制及其在调度问题中的应用

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Mehta, Roughgarden, and Sundararajan recently introduced a new class of cost sharing mechanisms called acyclic mechanisms. These mechanisms achieve a slightly weaker notion of truthfulness than the well-known Moulin mechanisms, but provide additional freedom to improve budget balance and social cost approximation guarantees. In this paper, we investigate the potential of acyclic mechanisms for combinatorial optimization problems. In particular, we study a subclass of acyclic mechanisms which we term singleton acyclic mechanisms. We show that every ρ-approximate algorithm that is partially increasing can be turned into a singleton acyclic mechanism that is weakly group-strategyproof and p-budget balanced. Based on this result, we develop singleton acyclic mechanisms for parallel machine scheduling problems with completion time objectives, which perform extremely well both with respect to budget balance and social cost.
机译：Mehta，Roughgarden和Sundararajan最近引入了一种称为非循环机制的新型成本分担机制。与众所周知的穆兰机制相比，这些机制的真实性略弱一些，但提供了更多的自由来改善预算平衡和社会成本的近似保证。在本文中，我们研究了非循环机制用于组合优化问题的潜力。特别地，我们研究非循环机制的子类，我们称其为单例非循环机制。我们表明，每个部分增加的ρ近似算法都可以转变为单子非循环机制，这种机制对组策略的抵抗力很弱，而且p预算平衡。基于此结果，我们针对具有完成时间目标的并行机器调度问题开发了单例非循环机制，该机制在预算平衡和社会成本方面均表现出色。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号