• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Algorithmic Game Theory >On the Approximability of Combinatorial Exchange Problems
【24h】

On the Approximability of Combinatorial Exchange Problems

机译：关于组合交换问题的逼近性

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

摘要

In a combinatorial exchange the goal is to find a feasible trade between potential buyers and sellers requesting and offering bundles of indivisible goods. We investigate the approximability of several optimization objectives in this setting and show that the problems of surplus and trade volume maximization are inapproximable even with free disposal and even if each agent's bundle is of size at most 3. In light of the negative results for surplus maximization we consider the complementary goal of social cost minimization and present tight approximation results for this scenario. Considering the more general supply chain problem, in which each agent can be a seller and buyer simultaneously, we prove that social cost minimization remains inapproximable even with bundles of size 3, yet becomes polynomial time solvable for agents trading bundles of size 1 or 2. This yields a complete characterization of the approximability of supply chain and combinatorial exchange problems based on the size of traded bundles. We finally briefly address the problem of exchanges in strategic settings.
机译：在组合交易中，目标是在潜在的买家和卖家之间寻找并提供捆绑的不可分割商品的可行交易。我们研究了在这种情况下几个优化目标的逼近度，并表明即使有免费处置，即使每个代理的捆束最大为3，盈余和交易量最大化的问题也是不可接近的。鉴于盈余最大化的负面结果我们考虑了社会成本最小化的补充目标，并针对这种情况提出了严格的近似结果。考虑到更普遍的供应链问题，即每个代理商可以同时成为卖方和买方，我们证明即使成本为3的捆绑包，社会成本最小化仍然是不可近似的，但是对于交易规模为1或2的代理商，多项式时间可以解决。这样就可以根据交易束的大小完整地描述供应链的可近似性和组合交换问题。我们最后简要地解决了战略环境中的交流问题。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号