Accession Number ADA584029
Title Network Formation: Neighborhood Structures, Establishment Costs, and Distributed Learning.
Publication Date Sep 2012
Media Count 22p
Personal Author G. C. Chasparis J. S. Shamma
Abstract 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, 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.
Keywords Ad hoc network technologies
Coordination games
Costs
Learning
Nash networks
Network formations
Networks
Nodes
Overlay routing
Physical properties


 
Source Agency Non Paid ADAS
NTIS Subject Category 96 - Business & Economics
92B - Psychology
57T - Psychiatry
99F - Physical & Theoretical Chemistry
49 - Electrotechnology
Corporate Author Georgia Inst. of Tech., Atlanta. School of Electrical and Computer Engineering.
Document Type Journal article
Title Note Journal article.
NTIS Issue Number 1402
Contract Number FA9550-09-1-0420 FA9550-10-1-0573

Science and Technology Highlights

See a sampling of the latest scientific, technical and engineering information from NTIS in the NTIS Technical Reports Newsletter

Acrobat Reader Mobile    Acrobat Reader