Name
Title | ||
|---|---|---|
Distributed optimization by myopic strategic interactions and the price of heterogeneity |
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1109/CDC.2013.6760041 | Decision and Control |
Keywords | Field | DocType |
game theory,graph theory,network theory (graphs),quadratic programming,stability,Nash equilibria,agent interconnection,asymmetric interaction,best-response dynamical systems,complex characteristics,consensus,constrained myopic strategic games,constrained quadratic optimization problem,distributed optimization,heterogeneity price,local information,low-cost heterogenous design,myopic strategic interaction,social dominance,social equivalence,stability properties,star graphs | Graph theory,Graph,Mathematical optimization,Mathematical economics,Computer science,Dynamical systems theory,Equivalence (measure theory),Game theory,Quadratic programming,Nash equilibrium | Conference |
ISSN | ISBN | Citations |
0743-1546 | 978-1-4673-5714-2 | 2 |
PageRank | References | Authors |
0.48 | 4 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bahman Gharesifard | 1 | 340 | 26.54 |
| Behrouz Touri | 2 | 176 | 21.12 |
| Tamer Basar | 3 | 3497 | 402.11 |
| Cedric Langbort | 4 | 95 | 15.18 |