A Nash bargaining solution for Cooperative Network Formation Games

Résumé : Le problème de formation des réseaux a reçu une attention croissante ces dernières années. Les travaux précédents ont abordé ce problème supposant que les réseaux soient créés par des utilisateurs égoïstes ; toutefois, ces réseaux peuvent être systématiquement sous-optimaux. Cet article aborde le problème de formation des réseaux en utilisant la théorie des jeux coopératifs, qui permet d'étudier les moyens pour faire respecter et soutenir la coopération entre des agents. La solution de ``Nash bargaining'' et la valeur de Shapley sont des concepts largement applicables pour résoudre ces jeux. Cependant, nous montrons que la valeur de Shapley présente trois inconvénients majeurs dans ce contexte : (1) il n'est pas évident de définir des fonctions caractéristiques significatives pour le jeu que nous étudions, (2) il peut déterminer pour certains utilisateurs des allocations de coût plus élevées que celles à l'équilibre de Nash (et donc, si les joueurs refusent de coopérer), et (3) le temps de computation est très long. Pour cette raison, nous résolvons le jeu coopératif de formation de réseau en utilisant le concept de ``Nash bargaining solution'' (NBS). Plus spécifiquement, nous étendons cette dernière approche au cas de plusieurs joueurs, et nous donnons une expression explicite pour l'allocation des coûts aux utilisateurs. En outre, nous comparons la NBS à la valeur de Shapley et à l'équilibre de Nash, montrant ses avantages et ses propriétés attrayantes en termes d'allocation des coûts aux utilisateurs et de temps de computation pour obtenir la solution. Les résultats numériques montrent que l'approche proposée permet d'allouer aux utilisateurs des coûts de manière équitable avec un temps de computation raisonnable, représentant un ``framework'' très effectif pour la conception de réseaux efficaces et stables.
Type de document :
Rapport
[Research Report] RR-7480, INRIA. 2010
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00544527
Contributeur : Konstantin Avrachenkov <>
Soumis le : vendredi 7 janvier 2011 - 14:57:14
Dernière modification le : dimanche 25 février 2018 - 14:48:02
Document(s) archivé(s) le : vendredi 8 avril 2011 - 03:20:33

Fichier

RR-7480.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00544527, version 3

Collections

Citation

Konstantin Avrachenkov, Jocelyne Elias, Fabio Martignon, Giovanni Neglia, Leon Petrosyan. A Nash bargaining solution for Cooperative Network Formation Games. [Research Report] RR-7480, INRIA. 2010. 〈inria-00544527v3〉

Partager

Métriques

Consultations de la notice

522

Téléchargements de fichiers

916