2024/05/30 by Rohit Konda, Konda, Rohit, Rahul Chandan +5
Economics, Econometrics and Finance · #FOS: Electrical engineering #Game Theory and Voting Systems #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2406.17791
openalex publication_date 2024/05/30 · openalex created_date 2024/06/28 · openalex updated_date 2026/07/28
Deriving competitive, distributed solutions to multi-agent problems is crucial for many developing application domains; Game theory has emerged as a useful framework to design such algorithms. However, much of the attention within this framework is on the study of equilibrium behavior, whereas transient behavior is often ignored. Therefore, in this paper we study the transient efficiency guarantees of best response processes in the context of submodular resource allocation games, which find application in various engineering contexts. Specifically the main focus of this paper is on characterizing the optimal short-term system-level behavior under the best-response process. Interestingly, the resulting transient performance guarantees are relatively close to the optimal asymptotic performance guarantees. Furthermore, we characterize the trade-offs that result when optimizing for both asymptotic and transient efficiency through various utility designs.