Optimal Utility Design of Greedy Algorithms in Resource Allocation Games

• 成果类型: Article
• 署名作者: Konda, Rohit; Chandan, Rahul; Grimsman, David; Marden, Jason R.
• 署名单位: University of California System; University of California Santa Barbara; Brigham Young University
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2024.3375252
• 发表日期: 2024
• 页码: 6592-6604
• 关键词: Greedy algorithms; games; resource management; STANDARDS; Distributed algorithms; Wireless communication; Task analysis; Algorithm design; distributed systems; game theory; optimization; resource allocation

摘要

Designing fast, distributed algorithms for multiagent problems is vital for many novel application domains. Greedy algorithms have been shown in many multiagent contexts to be an efficient approach to arrive at good solutions quickly. In this work, we ask the following: Is there any way to improve the performance of greedy algorithms without sacrificing the linear run-time guarantees? For this, we take inspiration from incentive design in the game-theoretic literature. In this work, we consider a modified version of the greedy algorithm where agents do not optimize against the global objective. Instead, each agent is prescribed an auxiliary utility function (which may differ from the original objective function) in which it optimizes under. By designing the utility functions properly, we show in this work that the resulting performance guarantees of the greedy algorithm can increase significantly. We study this approach in the context of resource-allocation games, which are used to model a rich variety of engineering applications. Interestingly, the performance guarantees from the modified greedy algorithm can be significantly close to the best centralized performance guarantees. The main technical contribution of the article is the characterization of the performance guarantees through a linear program construction.