Traffic Networks provide a model for studying selfish routing: non-cooperative agents travel from sources to destinations experiencing a latency that depends on the network congestion and, hence, on routes chosen by other agents. Traffic stabilizes to a game-theoretic equilibrium in which all agents experience the same latency. A multi-commodity (that is, a graph with many source-target pairs) is vulnerable if there exists an assignment of latency functions to edges such that the resulting traffic network suffers from the counterintuitive phenomenon, called Braess paradox, for which a network increases its efficiency by removing edges. Building on an existing characterization of vulnerable multi-commodities and a polynomial algorithm to check vulnerability for single commodities, in this paper we present a polynomial-time algorithm that checks whether a directed multi-commodity is vulnerable or not. This definitely closes a question opened by Roughgarden about 20 years ago.
Polynomial recognition of vulnerable multi-commodities / Fiorenza, Dario; Gorla, Daniele; Salvo, Ivano. - In: INFORMATION PROCESSING LETTERS. - ISSN 0020-0190. - 179(2022). [10.1016/j.ipl.2022.106282]
Polynomial recognition of vulnerable multi-commodities
Daniele Gorla
;Ivano Salvo
2022
Abstract
Traffic Networks provide a model for studying selfish routing: non-cooperative agents travel from sources to destinations experiencing a latency that depends on the network congestion and, hence, on routes chosen by other agents. Traffic stabilizes to a game-theoretic equilibrium in which all agents experience the same latency. A multi-commodity (that is, a graph with many source-target pairs) is vulnerable if there exists an assignment of latency functions to edges such that the resulting traffic network suffers from the counterintuitive phenomenon, called Braess paradox, for which a network increases its efficiency by removing edges. Building on an existing characterization of vulnerable multi-commodities and a polynomial algorithm to check vulnerability for single commodities, in this paper we present a polynomial-time algorithm that checks whether a directed multi-commodity is vulnerable or not. This definitely closes a question opened by Roughgarden about 20 years ago.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.