Research Article
Cost allocation protocols for network formation on connection situations
@INPROCEEDINGS{10.4108/valuetools.2012.250360, author={Bruno Escoffier and Laurent Gourv\'{e}s and J\^{e}r\~{o}me Monnot and Stefano Moretti}, title={Cost allocation protocols for network formation on connection situations}, proceedings={6th International Conference on Performance Evaluation Methodologies and Tools}, publisher={IEEE}, proceedings_a={VALUETOOLS}, year={2012}, month={11}, keywords={spanning tree cost allocation protocol}, doi={10.4108/valuetools.2012.250360} }- Bruno Escoffier
Laurent Gourvès
Jérôme Monnot
Stefano Moretti
Year: 2012
Cost allocation protocols for network formation on connection situations
VALUETOOLS
ICST
DOI: 10.4108/valuetools.2012.250360
Abstract
The issue of embedding cost-awareness in the design of communication network devices and protocols has been growing at a fast rate in last years. Under certain connection situations, however, network design is not enforced by a central authority. This is the case, for instance, of power control for wireless networks, where the cost of a link is a function of the power needed to send a message to a remote node, which increases with the distance. Here each player wishes to consume as few power as possible to send its request and the main question is how to avoid that players deviate from a socially optimal network.
In this paper, we study strategic games based on connection situations with the objective to coordinate self-interested agents placed on the nodes of a graph to realize a more efficient communication network. We address the problem of the design of cost allocation protocols that may guarantee the convergence of the best response dynamic and we analyze the effects of cost monotonicity and other state-dependent properties on the optimality of a protocol.