Visible to the public Distributed Optimization by Myopic Strategic Interactions and the Price of HeterogeneityConflict Detection Enabled

TitleDistributed Optimization by Myopic Strategic Interactions and the Price of Heterogeneity
Publication TypeConference Paper
Year of Publication2013
AuthorsBahman Gharesifard, Behrouz Touri, Tamer Başar, University of Illinois at Urbana-Champaign, Cedric Langbort, University of Illinois at Urbana-Champaign
Conference Name52nd Conference on Decision and Control
Date Published12/2013
Conference LocationFlorence, Italy
KeywordsNSA SoS Lablets Materials, science of security, Toward a Theory of Resilience in Systems: A Game-Theoretic Approach, UIUC

This paper is concerned with the tradeoffs between low-cost heterogenous designs and optimality. We study a class of constrained myopic strategic games on networks which approximate the solutions to a constrained quadratic optimization problem; the Nash equilibria of these games can be found using best-response dynamical systems, which only use local information. The notion of price of heterogeneity captures the quality of our approximations. This notion relies on the structure and the strength of the interconnections between agents. We study the stability properties of these dynamical systems and demonstrate their complex characteristics, including abundance of equilibria on graphs with high sparsity and heterogeneity. We also introduce the novel notions of social equivalence and social dominance, and show some of their interesting implications, including their correspondence to consensus. Finally, using a classical result of Hirsch [1], we fully characterize the stability of these dynamical systems for the case of star graphs with asymmetric interactions. Various examples illustrate our results.

Citation Keynode-31858

Other available formats:

Distributed Optimization by Myopic Strategic Interactions and the Price of Heterogeneity.pdf