6th International Conference on Performance Evaluation Methodologies and Tools

Research Article

Cost allocation protocols for network formation on connection situations

Download289 downloads
  • @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
Bruno Escoffier1,*, Laurent Gourvès2, Jérôme Monnot2, Stefano Moretti2
  • 1: Université Paris Dauphine and CNRS UMR
  • 2: CNRS
*Contact email: escoffier@lamsade.dauphine.fr

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.