19 June 2020 in IEEE Control Systems Letters
Verifying set invariance has classical solutions stemming from the seminal work by Nagumo, and defining sets via a smooth barrier function constraint inequality results in computable flow conditions for guaranteeing set invariance. While a majority of these historic results on set invariance consider flow conditions on the boundary, this letter fully characterizes set invariance through minimal barrier functions by directly appealing to a comparison result to define a flow condition over the entire domain of the system. A considerable benefit of this approach is the removal of regularity assumptions of the barrier function. This letter also outlines necessary and sufficient conditions for a valid differential inequality condition, giving the minimum conditions for this type of approach. We also show when minimal barrier functions are necessary and sufficient for set invariance.
8 March 2024 in IEEE Transactions on Automatic Control
Designing fast, distributed algorithms for multi-agent problems is vital for many novel application domains. Greedy algorithms have been shown in many multi-agent 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 paper is the characterization of the performance guarantees through a linear program construction.
25 July 2025 in IEEE Transactions on Automatic Control
Deriving competitive, distributed solutions to multi-agent problems is cruncial 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.