Cooperative network design: A Nash bargaining solution approach

Abstract : The Network Design problem has received increasing attention in recent years. Previous works have addressed this problem considering almost exclusively networks designed by selfish users, which can be consistently suboptimal. This paper addresses the network design issue using cooperative game theory, which permits to study ways to enforce and sustain cooperation among users. Both the Nash bargaining solution and the Shapley value are widely applicable concepts for solving these games. However, the Shapley value presents several drawbacks in this context. For this reason, we solve the cooperative network design game using the Nash bargaining solution (NBS) concept. More specifically, we extend the NBS approach to the case of multiple players and give an explicit expression for users’ cost allocations. We further provide a distributed algorithm for computing the Nash bargaining solution. Then, we compare the NBS to the Shapley value and the Nash equilibrium solution in several network scenarios, including real ISP topologies, showing its advantages and appealing properties in terms of cost allocation to users and computation time to obtain the solution. Numerical results demonstrate that the proposed Nash bargaining solution approach permits to allocate costs fairly to users in a reasonable computation time, thus representing a very effective framework for the design of efficient and stable networks.
Type de document :
Article dans une revue
Computer Networks, Elsevier, 2015, 83, pp.265-279. 〈10.1016/j.comnet.2015.03.017〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01255728
Contributeur : Giovanni Neglia <>
Soumis le : mercredi 13 janvier 2016 - 19:33:31
Dernière modification le : jeudi 5 avril 2018 - 12:30:09

Lien texte intégral

Identifiants

Citation

Konstantin Avrachenkov, Jocelyne Elias, Fabio Martignon, Giovanni Neglia, Leon Petrosyan. Cooperative network design: A Nash bargaining solution approach. Computer Networks, Elsevier, 2015, 83, pp.265-279. 〈10.1016/j.comnet.2015.03.017〉. 〈hal-01255728〉

Partager

Métriques

Consultations de la notice

328