• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Artificial intelligence >BOB: Improved winner determination in combinatorial auctions and generalizations
【24h】

BOB: Improved winner determination in combinatorial auctions and generalizations

机译：BOB：改进了组合拍卖和概括中的获胜者确定度

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

摘要

Combinatorial auctions can be used to reach efficient resource and task allocations in multiagent systems where the items are complementary or substitutable. Determining the winners is NP-complete and inapproximable, but it was recently shown that optimal search algorithms do very well on average. This paper presents a more sophisticated search algorithm for optimal (and anytime) winner determination, including structural improvements that reduce search tree size, faster data structures, and optimizations at search nodes based on driving toward, identifying and solving tractable special cases. We also uncover a more general tractable special case, and design algorithms for solving it as well as for solving known tractable special cases substantially faster. We generalize combinatorial auctions to multiple units of each item, to reserve prices on singletons as well as combinations, and to combinatorial exchanges. All of these generalizations support both complementarity and substitutability of the items. Finally, we present algorithms for determining the winners in these generalizations.
机译：组合拍卖可用于在物品互补或可替换的多主体系统中达成有效的资源和任务分配。确定优胜者是NP完全的，而且是不可估计的，但是最近发现，最佳搜索算法的平均效果很好。本文提出了一种用于优化（任何时间）获胜者确定的更复杂的搜索算法，包括在减少，缩小数据树结构，加快数据结构以及基于趋向，识别和解决易处理的特殊情况的搜索节点上进行优化的结构改进。我们还发现了一个更一般的易处理特例，并设计了用于解决该问题的算法以及用于以更快的速度解决已知的易处理特例的算法。我们将组合拍卖概括为每个项目的多个单位，以单件和组合的价格保留价格，并组合交易。所有这些概括都支持项目的互补性和可替代性。最后，我们提出了在这些概括中确定赢家的算法。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号