Network Formation: Neighborhood Structures, Establishment Costs, and Distributed Learning
(2013) In IEEE Transactions on Cybernetics 43(6). p.1950-1962- 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... (More)
- 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. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/4272429
- author
- Chasparis, Georgios LU and Shamma, Jeff S.
- organization
- publishing date
- 2013
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- Ad hoc networks, distributed algorithms, distributed network formation, game theory, learning automata, wireless networks
- in
- IEEE Transactions on Cybernetics
- volume
- 43
- issue
- 6
- pages
- 1950 - 1962
- publisher
- IEEE - Institute of Electrical and Electronics Engineers Inc.
- external identifiers
-
- wos:000327647500036
- scopus:84890019847
- pmid:23757585
- ISSN
- 2168-2267
- DOI
- 10.1109/TSMCB.2012.2236553
- language
- English
- LU publication?
- yes
- id
- cc6d5e0d-d9fa-4bf1-9e2a-121a62834f24 (old id 4272429)
- date added to LUP
- 2016-04-01 14:55:31
- date last changed
- 2022-03-29 23:31:29
@article{cc6d5e0d-d9fa-4bf1-9e2a-121a62834f24,
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.}},
author = {{Chasparis, Georgios and Shamma, Jeff S.}},
issn = {{2168-2267}},
keywords = {{Ad hoc networks; distributed algorithms; distributed network formation; game theory; learning automata; wireless networks}},
language = {{eng}},
number = {{6}},
pages = {{1950--1962}},
publisher = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}},
series = {{IEEE Transactions on Cybernetics}},
title = {{Network Formation: Neighborhood Structures, Establishment Costs, and Distributed Learning}},
url = {{http://dx.doi.org/10.1109/TSMCB.2012.2236553}},
doi = {{10.1109/TSMCB.2012.2236553}},
volume = {{43}},
year = {{2013}},
}