Utility Design for Distributed Resource Allocation-Par II: Applications to Submodular, Covering, and Supermodular Problems

• 成果类型: Article
• 署名作者: Paccagnan, Dario; Marden, Jason R.
• 署名单位: Imperial College London; University of California System; University of California Santa Barbara; University of California System; University of California Santa Barbara
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2021.3052497
• 发表日期: 2022
• 页码: 618-632
• 关键词: Distributed and combinatorial optimization; game theory; price of anarchy (PoA); resource allocation

摘要

A fundamental component of the game-theoretic approach to distributed control is the design of local utility functions. Relative to resource allocation problems that are additive over the resources, Part I showed how to design local utilities so as to maximize the associated performance guarantees (Paccagnan, et al., 2020), which we measure by the price of anarchy. The purpose of this article is to specialize these results to the case of submodular, covering, and supermodular problems. In all these cases, we obtain tight expressions for the price of anarchy that often match or improve the guarantees associated with state-of-the-art approximation algorithms. Two applications and corresponding numerics are presented: the vehicle-target assignment problem and a coverage problem arising in wireless data caching.