论文标题
加权拥塞游戏的统一近似潜力
A Unifying Approximate Potential for Weighted Congestion Games
论文作者
论文摘要
我们提供了一个统一的黑框工具，用于在加权拥堵游戏中建立近似平衡的存在，同时又限制了它们的稳定价格。我们的框架可以通过一般成本（包括减少的资源）来处理资源，并根据一组参数进行制定，这些参数是通过成本函数的基本分析属性确定的。 我们通过将其应用于恢复Caragiannis和Fanelli [iCalp'19]进行多项式拥堵游戏的最新结果来证明我们的工具的力量；改善Chen和Roughgarden的公平成本分享游戏的界限[理论计算。 Syst。，2009年]；并为无抵押成本提供新的界限。我们框架的一个有趣特征是，它可以很容易地应用于不同成本功能的不同家族的混合物。例如，我们为其资源是多项式和凹入成本的圆锥形组合的游戏提供界限。 在我们的分析的核心中，使用了统一的近似潜在功能，该功能足够简单，足以适用于任意拥堵游戏，但同时足够强大，可以在各种不同的成本功能上产生最新的界限。
We provide a unifying, black-box tool for establishing existence of approximate equilibria in weighted congestion games and, at the same time, bounding their Price of Stability. Our framework can handle resources with general costs--including, in particular, decreasing ones--and is formulated in terms of a set of parameters which are determined via elementary analytic properties of the cost functions. We demonstrate the power of our tool by applying it to recover the recent result of Caragiannis and Fanelli [ICALP'19] for polynomial congestion games; improve upon the bounds for fair cost sharing games by Chen and Roughgarden [Theory Comput. Syst., 2009]; and derive new bounds for nondecreasing concave costs. An interesting feature of our framework is that it can be readily applied to mixtures of different families of cost functions; for example, we provide bounds for games whose resources are conical combinations of polynomial and concave costs. In the core of our analysis lies the use of a unifying approximate potential function which is simple and general enough to be applicable to arbitrary congestion games, but at the same time powerful enough to produce state-of-the-art bounds across a range of different cost functions.
