论文标题
网络成本分布游戏的资源感知协议
Resource-Aware Protocols for Network Cost-Sharing Games
论文作者
论文摘要
我们研究了通过$ n $ n $代理的网络成本共享游戏中的无政府状态（POA）界限的分散成本共享协议的程度。我们专注于资源感知协议的模型，在该模型中，设计师可以先访问网络结构，还可以提高优势的总成本（过度充电），并且我们研究具有凹面或凸成本功能的游戏类。我们首先考虑凹入的成本功能，我们的主要结果是针对对称游戏的成本分配协议，用于指示的无环图上的对称性游戏，可实现$ 2+\ varepsilon $的POA，用于某些任意的小型$ \ varepsilon $，该$ \ varepsilon $提高到至少两个玩家的游戏$ 1+\ varepsilon $。对于串联并行图，我们还获得了1个POA，并表明任何协议都无法获得超过$ω（\ sqrt {n}）$的POA，用于多播游戏。然后，我们还考虑了凸成本函数，并证明了串联 - 平行网络和多播游戏的类似结果，以及在无需过度充电的情况下，在有名acyclic图上POA的$ω（n）$的下限。
We study the extent to which decentralized cost-sharing protocols can achieve good price of anarchy (PoA) bounds in network cost-sharing games with $n$ agents. We focus on the model of resource-aware protocols, where the designer has prior access to the network structure and can also increase the total cost of an edge(overcharging), and we study classes of games with concave or convex cost functions. We first consider concave cost functions and our main result is a cost-sharing protocol for symmetric games on directed acyclic graphs that achieves a PoA of $2+\varepsilon$ for some arbitrary small positive $\varepsilon$, which improves to $1+\varepsilon$ for games with at least two players. We also achieve a PoA of 1 for series-parallel graphs and show that no protocol can achieve a PoA better than $Ω(\sqrt{n})$ for multicast games. We then also consider convex cost functions and prove analogous results for series-parallel networks and multicast games, as well as a lower bound of $Ω(n)$ for the PoA on directed acyclic graphs without the use of overcharging.
