TY - GEN
T1 - Distributed optimization by myopic strategic interactions and the price of heterogeneity
AU - Gharesifard, Bahman
AU - Touri, Behrouz
AU - Başar, Tamer
AU - Langbort, Cedric
PY - 2013
Y1 - 2013
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84902338538&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84902338538&partnerID=8YFLogxK
U2 - 10.1109/CDC.2013.6760041
DO - 10.1109/CDC.2013.6760041
M3 - Conference contribution
AN - SCOPUS:84902338538
SN - 9781467357173
T3 - Proceedings of the IEEE Conference on Decision and Control
SP - 1174
EP - 1179
BT - 2013 IEEE 52nd Annual Conference on Decision and Control, CDC 2013
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 52nd IEEE Conference on Decision and Control, CDC 2013
Y2 - 10 December 2013 through 13 December 2013
ER -