...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >Quality of equilibria for selfish bin packing with cost sharing variants
【24h】

Quality of equilibria for selfish bin packing with cost sharing variants

机译：具有成本共享变体的自私箱包装均衡质量

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

摘要

Bin packing is the problem of splitting a set of items into a minimum number of subsets, called bins, of total sizes no larger than 1, where a solution is called a packing. We study bin packing games where an item also has a positive weight, and given a valid packing of the items, each item has a cost associated with it, such that the cost of an item is the ratio between its weight and the total weight of items packed in its bin. That is, the cost sharing is based linearly on the weights of items. We study several types of Nash equilibria: pure Nash equilibria, strong equilibria, strictly Pareto optimal equilibria, and weakly Pareto optimal equilibria, and show that any game of this class of bin packing games admits all these types of equilibria. We study the (asymptotic) prices of anarchy and stability (PoA and PoS) of these games with respect to the four types of equilibria. We find that the problem is strongly related to the well-known FIRST FIT algorithm, and all the four PoA values are equal to 1.7. The PoS values are shown to be equal to 1, except for strong equilibria, for which the PoS value is 1.7. Additionally, we study the sub-class of bin packing games with equal weights, where the cost sharing of each bin is uniform in the sense that the cost of a bin is shared equally between its items. We analyze the price of anarchy, and find that this value is strictly smaller than 1.7 and in particular, it is not larger than 1.699396 and it is at least 1.69664. (C) 2019 Elsevier B.V. All rights reserved.
机译：装箱问题是将一组物品拆分为最小数量的子集，称为箱子，总尺寸不大于1，其中解决方案称为装箱。我们研究了装箱博弈，其中一个物品也有一个正的重量，并且给定一个物品的有效包装，每个物品都有一个与之相关的成本，这样一个物品的成本就是它的重量和包装在它的箱子里的物品的总重量之间的比率。也就是说，成本分摊基于项目的权重。我们研究了几种类型的纳什均衡：纯纳什均衡、强均衡、严格帕累托最优均衡和弱帕累托最优均衡，并证明这类装箱博弈的任何博弈都允许所有这些类型的均衡。我们研究了关于这四类均衡的无政府状态和稳定性（PoA和PoS）的（渐近）价格。我们发现该问题与著名的第一拟合算法密切相关，并且所有四个PoA值都等于1.7。PoS值显示为等于1，但强平衡除外，其PoS值为1.7。此外，我们还研究了等权装箱博弈的子类，其中每个箱子的成本分担是一致的，因为箱子的成本在其物品之间是平均分担的。我们分析了无政府状态的代价，发现这个值严格小于1.7，尤其是不大于1.699396，至少为1.69664。（C） 2019爱思唯尔B.V.版权所有。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号