Braess' paradox: A cooperative game‐theoretic point of view. Issue 3 (25th January 2021)

• Record Type: Journal Article
• Authors: Passacantando, Mauro; Gnecco, Giorgio; Hadas, Yuval; Sanguineti, Marcello
• Is Part Of: Networks. Volume 78:Issue 3(2021)
• Page Start: 264
• Page End: 283
• Publication Date: 2021-01-25
• Subjects: Braess' paradox -- system optimum -- traffic assignment -- transportation networks -- TU games -- user equilibrium; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.22018
• Languages: English
• ISSNs: 0028-3045

Abstract

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.