Braess' paradox is a classical result in the theory of congestion games. It motivates theoretically why adding a resource (e.g., an arc) to a network may sometimes worsen, rather than improve, the overall network performance. Differently from previous literature, which studies Braess' paradox in a non-cooperative game-theoretic setting, in this work, a framework is proposed to investigate its occurrence by exploiting cooperative games with transferable utility (TU games) on networks. In this way, instead of focusing on the marginal contribution to the network utility provided by the insertion of an arc when a single initial scenario is considered, the arc average marginal utility with respect to various initial scenarios, that is, its Shapley value in a suitably-defined TU game, is evaluated. It is shown that, for choices of the utility function of the TU game modeling congestion, there are cases for which the Shapley value associated with an arc is negative, meaning that its average marginal contribution to the network utility is negative.

Passacantando, M., Gnecco, G., Hadas, Y., Sanguineti, M. (2021). Braess’ paradox: a cooperative game-theoretic point of view. NETWORKS, 78(3), 264-283 [10.1002/net.22018].

Braess’ paradox: a cooperative game-theoretic point of view

Passacantando, M
;
2021

Abstract

Braess' paradox is a classical result in the theory of congestion games. It motivates theoretically why adding a resource (e.g., an arc) to a network may sometimes worsen, rather than improve, the overall network performance. Differently from previous literature, which studies Braess' paradox in a non-cooperative game-theoretic setting, in this work, a framework is proposed to investigate its occurrence by exploiting cooperative games with transferable utility (TU games) on networks. In this way, instead of focusing on the marginal contribution to the network utility provided by the insertion of an arc when a single initial scenario is considered, the arc average marginal utility with respect to various initial scenarios, that is, its Shapley value in a suitably-defined TU game, is evaluated. It is shown that, for choices of the utility function of the TU game modeling congestion, there are cases for which the Shapley value associated with an arc is negative, meaning that its average marginal contribution to the network utility is negative.
Si
Articolo in rivista - Articolo scientifico
Scientifica
Braess' paradox; system optimum; traffic assignment; transportation networks; TU games; user equilibrium;
English
264
283
20
Passacantando, M., Gnecco, G., Hadas, Y., Sanguineti, M. (2021). Braess’ paradox: a cooperative game-theoretic point of view. NETWORKS, 78(3), 264-283 [10.1002/net.22018].
Passacantando, M; Gnecco, G; Hadas, Y; Sanguineti, M
File in questo prodotto:
File Dimensione Formato  
net.22018_issue.pdf

Solo gestori archivio

Descrizione: Special Issue Article
Tipologia di allegato: Publisher’s Version (Version of Record, VoR)
Dimensione 1.55 MB
Formato Adobe PDF
1.55 MB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/10281/391585
Citazioni
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
Social impact