论文标题
资源分配游戏中贪婪算法的最佳效用设计
Optimal Utility Design of Greedy Algorithms in Resource Allocation Games
论文作者
论文摘要
设计用于多代理问题的分布式算法对于许多新兴的应用程序域至关重要，并且游戏理论方法正在作为设计此类算法的有用范例。但是，游戏理论方法的大部分重点是研究平衡行为，而瞬时行为通常不那么探索。因此，在本文中，我们研究了资源分配游戏中最佳响应过程的瞬态效率保证，该过程用于建模各种工程应用程序。具体而言，本文的主要重点是设计代理的效用功能，以在最佳响应过程中诱导最佳的短期系统级行为。有趣的是，由此产生的瞬态性能保证相对接近最佳的渐近性能保证。此外，我们表征了一种通过各种实用性设计优化渐近效率和瞬态效率的权衡。
Designing distributed algorithms for multi-agent problems is vital for many emerging application domains, and game-theoretic approaches are emerging as a useful paradigm to design such algorithms. However, much of the emphasis of the game-theoretic approach is on the study of equilibrium behavior, whereas transient behavior is often less explored. Therefore, in this paper we study the transient efficiency guarantees of best response processes in the context of resource-allocation games, which are used to model a variety of engineering applications. Specifically, the main focus of the paper is on designing utility functions of agents to induce optimal short-term system-level behavior under a best-response process. Interestingly, the resulting transient performance guarantees are relatively close to the optimal asymptotic performance guarantees. Furthermore, we characterize a trade-off that results when optimizing for both asymptotic and transient efficiency through various utility designs.
