Socially-Aware Network Design Games

Abstract : In many scenarios network design is not enforced by a central authority, but arises from the interactions of several self-interested agents. This is the case of the Internet, where connectivity is due to Autonomous Systems' choices, but also of overlay networks, where each user client can decide the set of connections to establish. Recent works have used game theory, and in particular the concept of Nash Equilibrium, to characterize stable networks created by a set of selfish agents. The majority of these works assume that users are completely non-cooperative, leading, in most cases, to inefficient equilibria. To improve efficiency, in this paper we propose two novel socially-aware network design games. In the first game we incorporate a socially-aware component in the users' utility functions, while in the second game we use additionally a Stackelberg (leader-follower) approach, where a leader (e.g., the network administrator) architects the desired network buying an appropriate subset of network's links, driving in this way the users to overall efficient Nash equilibria. We provide bounds on the Price of Anarchy and other efficiency measures, and study the performance of the proposed schemes in several network scenarios, including realistic topologies where players build an overlay on top of real Internet Service Provider networks. Numerical results demonstrate that (1) introducing some incentives to make users more socially-aware is an effective solution to achieve stable and efficient networks in a distributed way, and (2) the proposed Stackelberg approach permits to achieve dramatic performance improvements, designing almost always the socially optimal network.
Type de document :
Rapport
[Research Report] RR-7141, INRIA. 2009, pp.21
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00439687
Contributeur : Konstantin Avrachenkov <>
Soumis le : mercredi 9 décembre 2009 - 15:41:57
Dernière modification le : jeudi 11 janvier 2018 - 16:57:57
Document(s) archivé(s) le : jeudi 17 juin 2010 - 23:27:05

Fichier

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

Identifiants

  • HAL Id : inria-00439687, version 1

Collections

Citation

Jocelyne Elias, Fabio Martignon, Konstantin Avrachenkov, Giovanni Neglia. Socially-Aware Network Design Games. [Research Report] RR-7141, INRIA. 2009, pp.21. 〈inria-00439687〉

Partager

Métriques

Consultations de la notice

552

Téléchargements de fichiers

121