期刊
IEEE TRANSACTIONS ON AUTOMATIC CONTROL
卷 67, 期 2, 页码 618-632出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TAC.2021.3052497
关键词
Distributed and combinatorial optimization; game theory; price of anarchy (PoA); resource allocation
资金
- Swiss National Science Foundation [P2EZP2-181618]
- Office of Naval Research [N00014-15-1-2762]
- National Science Foundation [ECCS-1351866]
- Swiss National Science Foundation (SNF) [P2EZP2_181618] Funding Source: Swiss National Science Foundation (SNF)
This article focuses on the design of local utility functions in distributed control using game-theoretic approach. It specializes the results for submodular, covering, and supermodular problems, providing tight expressions for the price of anarchy that often surpass the guarantees of state-of-the-art approximation algorithms. Two applications, specifically the vehicle-target assignment problem and a coverage problem in wireless data caching, are presented with corresponding numerical results.
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据