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.

(2015). Cooperative network design: A Nash bargaining solution approach [journal article - articolo]. In COMPUTER NETWORKS. Retrieved from http://hdl.handle.net/10446/106041

Cooperative network design: A Nash bargaining solution approach

ELIAS, Jocelyne;MARTIGNON, Fabio;
2015-01-01

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.
articolo
2015
Avrachenkov, Konstantin; Elias, Jocelyne; Martignon, Fabio; Neglia, Giovanni; Petrosyan, Leon
(2015). Cooperative network design: A Nash bargaining solution approach [journal article - articolo]. In COMPUTER NETWORKS. Retrieved from http://hdl.handle.net/10446/106041
File allegato/i alla scheda:
File Dimensione del file Formato  
COMNET_2015.pdf

Solo gestori di archivio

Versione: Documento in Pre-print
Licenza: Licenza default Aisberg
Dimensione del file 384.68 kB
Formato Adobe PDF
384.68 kB Adobe PDF   Visualizza/Apri
1-s2.0-S1389128615001127-main.pdf

Solo gestori di archivio

Versione: publisher's version - versione editoriale
Licenza: Licenza default Aisberg
Dimensione del file 750.75 kB
Formato Adobe PDF
750.75 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

Aisberg ©2008 Servizi bibliotecari, Università degli studi di Bergamo | Terms of use/Condizioni di utilizzo

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10446/106041
Citazioni
  • Scopus 18
  • ???jsp.display-item.citation.isi??? 18
social impact