A Nash Bargaining Solution for Cooperative Network Formation Games

Abstract : The Network Formation 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 formation issue using cooperative game theory, which permits to study ways to enforce and sustain cooperation among agents. Both the Nash bargaining solution and the Shapley value are widely applicable concepts for solving these games. However, we show that the Shapley value presents three main drawbacks in this context: (1) it is non-trivial to define meaningful characteristic functions for the cooperative network formation game, (2) it can determine for some players cost allocations that are even higher than those at the Nash Equilibrium (i.e., if players refuse to cooperate), and (3) it is computationally very cumbersome.For this reason, we solve the cooperative network formation 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. Furthermore, we compare the NBS to the Shapley value and the Nash equilibrium solution, showing its advantages and appealing properties in terms of cost allocation to users and computation time to get 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 :
Communication dans un congrès
Jordi Domingo-Pascual; Pietro Manzoni; Sergio Palazzo; Ana Pont; Caterina Scoglio. 10th IFIP Networking Conference (NETWORKING), May 2011, Valencia, Spain. Springer, Lecture Notes in Computer Science, LNCS-6640 (Part I), pp.307-318, 2011, NETWORKING 2011. 〈10.1007/978-3-642-20757-0_24〉
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00648190
Contributeur : Hal Ifip <>
Soumis le : jeudi 7 septembre 2017 - 11:57:56
Dernière modification le : jeudi 5 avril 2018 - 11:04:29

Fichier

978-3-642-20757-0_24_Chapter.p...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Konstantin Avrachenkov, Jocelyne Elias, Fabio Martignon, Giovanni Neglia, Leon Petrosyan. A Nash Bargaining Solution for Cooperative Network Formation Games. Jordi Domingo-Pascual; Pietro Manzoni; Sergio Palazzo; Ana Pont; Caterina Scoglio. 10th IFIP Networking Conference (NETWORKING), May 2011, Valencia, Spain. Springer, Lecture Notes in Computer Science, LNCS-6640 (Part I), pp.307-318, 2011, NETWORKING 2011. 〈10.1007/978-3-642-20757-0_24〉. 〈hal-00648190v2〉

Partager

Métriques

Consultations de la notice

117

Téléchargements de fichiers

72