Journal
IEEE TRANSACTIONS ON CYBERNETICS
Volume 43, Issue 6, Pages 1950-1962Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TSMCB.2012.2236553
Keywords
Ad hoc networks; distributed algorithms; distributed network formation; game theory; learning automata; wireless networks
Categories
Funding
- Air Force Office of Scientific Research [FA9550-09-1-0420, FA9550-10-1-0573]
- Swedish Research Council through the Linnaeus Center
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available