Network formation: Neighborhood structures, establishment costs, and distributed learning

Georgios C. Chasparis, Jeff S. Shamma

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


We consider the problem of network formation in a distributed fashion. Network formation is modeled as a strategic-form game, where agents represent nodes that form and sever unidirectional links with other nodes and derive utilities from these links. Furthermore, agents can form links only with a limited set of neighbors. Agents trade off the benefit from links, which is determined by a distance-dependent reward function, and the cost of maintaining links. When each agent acts independently, trying to maximize its own utility function, we can characterize 'stable' networks through the notion of Nash equilibrium. In fact, the introduced reward and cost functions lead to Nash equilibria (networks), which exhibit several desirable properties such as connectivity, bounded-hop diameter, and efficiency (i.e., minimum number of links). Since Nash networks may not necessarily be efficient, we also explore the possibility of 'shaping' the set of Nash networks through the introduction of state-based utility functions. Such utility functions may represent dynamic phenomena such as establishment costs (either positive or negative). Finally, we show how Nash networks can be the outcome of a distributed learning process. In particular, we extend previous learning processes to so-called 'state-based' weakly acyclic games, and we show that the proposed network formation games belong to this class of games.

Original languageEnglish (US)
Article number6425448
Pages (from-to)1950-1962
Number of pages13
JournalIEEE Transactions on Cybernetics
Issue number6
StatePublished - Dec 2013
Externally publishedYes


  • Ad hoc networks
  • Distributed algorithms
  • Distributed network formation
  • Game theory
  • Learning automata
  • Wireless networks

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Human-Computer Interaction
  • Electrical and Electronic Engineering
  • Control and Systems Engineering
  • Computer Science Applications


Dive into the research topics of 'Network formation: Neighborhood structures, establishment costs, and distributed learning'. Together they form a unique fingerprint.

Cite this