## 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, 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 language | English (US) |
---|---|

Article number | 6425448 |

Pages (from-to) | 1950-1962 |

Number of pages | 13 |

Journal | IEEE Transactions on Cybernetics |

Volume | 43 |

Issue number | 6 |

DOIs | |

State | Published - Dec 2013 |

Externally published | Yes |

## Keywords

- 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