论文标题
自私垃圾箱的最佳成本共享规则设计
Best Cost-Sharing Rule Design for Selfish Bin Packing
论文作者
论文摘要
在自私的垃圾箱中，每个项目都被视为一个自私的玩家，他们的目标是通过选择可以适合的垃圾箱来最大程度地降低成本份额。要使用最少使用的垃圾箱，成本共享规则起着重要作用。目前最著名的成本分享规则具有大于1.45的\ emph {$ poa $），而一般的下限4/3 $ poa $适用于任何成本共享规则，没有任何物品可以单方面移动到空箱中。在本文中，我们提出了一个小说和简单的规则，其中$ poa $匹配$ 4/3 $的下限，从而完全解决了这款游戏。新规则始终承认NASH平衡，其\ emph {of稳定性}（$ pos $）是一个。此外，众所周知的bin包装算法$ bfd $（最适合降低）被证明可以达到强大的平衡，这意味着在多项式时间内可以产生渐近近似值的稳定包装。作为设计框架的扩展，我们进一步研究了自私计划游戏的变体，并设计了达到$ pos = 1 $和$ poa = 4/3 $的最佳协调机制。
In selfish bin packing, each item is regarded as a selfish player, who aims to minimize the cost-share by choosing a bin it can fit in. To have a least number of bins used, cost-sharing rules play an important role. The currently best known cost sharing rule has a \emph{price of anarchy} ($PoA$) larger than 1.45, while a general lower bound 4/3 on $PoA$ applies to any cost-sharing rule under which no items have the incentive to move unilaterally to an empty bin. In this paper, we propose a novel and simple rule with a $PoA$ matching the lower bound of $4/3$, thus completely resolving this game. The new rule always admits a Nash equilibrium and its \emph{price of stability} ($PoS$) is one. Furthermore, the well-known bin packing algorithm $BFD$ (Best-Fit Decreasing) is shown to achieve a strong equilibrium, implying that a stable packing with an asymptotic approximation ratio of $11/9$ can be produced in polynomial time. As an extension of the designing framework, we further study a variant of the selfish scheduling game, and design a best coordination mechanism achieving $PoS=1$ and $PoA=4/3$ as well.
