Informational Braess’ Paradox: The Effect of Information on Traffic Congestion
To systematically study the implications of additional information about routes provided to certain users (e.g., via GPS-based route guidance systems), we introduce a new class of congestion games in which users have differing information sets about the available edges and can only use routes consis...
Main Authors: | , , , |
---|---|
Other Authors: | |
Format: | Article |
Language: | English |
Published: |
Institute for Operations Research and the Management Sciences (INFORMS)
2019
|
Online Access: | https://hdl.handle.net/1721.1/121504 |
_version_ | 1811088253303914496 |
---|---|
author | Acemoglu, Daron Makhdoumi Kakhaki, Ali Malekian, Azarakhsh Ozdaglar, Asu |
author2 | Massachusetts Institute of Technology. Department of Economics |
author_facet | Massachusetts Institute of Technology. Department of Economics Acemoglu, Daron Makhdoumi Kakhaki, Ali Malekian, Azarakhsh Ozdaglar, Asu |
author_sort | Acemoglu, Daron |
collection | MIT |
description | To systematically study the implications of additional information about routes provided to certain users (e.g., via GPS-based route guidance systems), we introduce a new class of congestion games in which users have differing information sets about the available edges and can only use routes consisting of edges in their information set. After defining the notion of an information-constrained wardrop equilibrium (ICWE) for this class of congestion games and studying its basic properties, we turn to our main focus: whether additional information can be harmful (in the sense of generating greater equilibrium costs/delays). We formulate this question in the form of an informational Braess' paradox (IBP), which extends the classic Braess' paradox in traffic equilibria and asks whether users receiving additional information can become worse off. We provide a comprehensive answer to this question showing that in any network in the series of linearly independent(SLI) class, which is a strict subset of series-parallel networks, the IBP cannot occur, and in any network that is not in the SLI class, there exists a configuration of edge-specific cost functions for which the IBP will occur. In the process, we establish several properties of the SLI class of networks, which include the characterization of the complement of the SLI class in terms of embedding a specific set of networks, and also an algorithm that determines whether a graph is SLI in linear time. We further prove that the worst-case inefficiency performance of ICWE is no worse than the standard Wardrop equilibrium. |
first_indexed | 2024-09-23T13:59:11Z |
format | Article |
id | mit-1721.1/121504 |
institution | Massachusetts Institute of Technology |
language | English |
last_indexed | 2024-09-23T13:59:11Z |
publishDate | 2019 |
publisher | Institute for Operations Research and the Management Sciences (INFORMS) |
record_format | dspace |
spelling | mit-1721.1/1215042020-03-31T14:57:38Z Informational Braess’ Paradox: The Effect of Information on Traffic Congestion Acemoglu, Daron Makhdoumi Kakhaki, Ali Malekian, Azarakhsh Ozdaglar, Asu Massachusetts Institute of Technology. Department of Economics Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems To systematically study the implications of additional information about routes provided to certain users (e.g., via GPS-based route guidance systems), we introduce a new class of congestion games in which users have differing information sets about the available edges and can only use routes consisting of edges in their information set. After defining the notion of an information-constrained wardrop equilibrium (ICWE) for this class of congestion games and studying its basic properties, we turn to our main focus: whether additional information can be harmful (in the sense of generating greater equilibrium costs/delays). We formulate this question in the form of an informational Braess' paradox (IBP), which extends the classic Braess' paradox in traffic equilibria and asks whether users receiving additional information can become worse off. We provide a comprehensive answer to this question showing that in any network in the series of linearly independent(SLI) class, which is a strict subset of series-parallel networks, the IBP cannot occur, and in any network that is not in the SLI class, there exists a configuration of edge-specific cost functions for which the IBP will occur. In the process, we establish several properties of the SLI class of networks, which include the characterization of the complement of the SLI class in terms of embedding a specific set of networks, and also an algorithm that determines whether a graph is SLI in linear time. We further prove that the worst-case inefficiency performance of ICWE is no worse than the standard Wardrop equilibrium. 2019-07-08T12:34:20Z 2019-07-08T12:34:20Z 2018-08 2017-11 2019-06-28T16:39:27Z Article http://purl.org/eprint/type/JournalArticle 0030-364X 1526-5463 https://hdl.handle.net/1721.1/121504 Acemoglu, Daron, Ali Makhdoumi, Azarakhsh Malekian and Asu Ozdaglar. "Informational Braess’ Paradox: The Effect of Information on Traffic Congestion." Operations research 66, no. 4 (August 2018): 893-917. en 10.1287/OPRE.2017.1712 Operations research Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/octet-stream Institute for Operations Research and the Management Sciences (INFORMS) MIT web domain |
spellingShingle | Acemoglu, Daron Makhdoumi Kakhaki, Ali Malekian, Azarakhsh Ozdaglar, Asu Informational Braess’ Paradox: The Effect of Information on Traffic Congestion |
title | Informational Braess’ Paradox: The Effect of Information on Traffic Congestion |
title_full | Informational Braess’ Paradox: The Effect of Information on Traffic Congestion |
title_fullStr | Informational Braess’ Paradox: The Effect of Information on Traffic Congestion |
title_full_unstemmed | Informational Braess’ Paradox: The Effect of Information on Traffic Congestion |
title_short | Informational Braess’ Paradox: The Effect of Information on Traffic Congestion |
title_sort | informational braess paradox the effect of information on traffic congestion |
url | https://hdl.handle.net/1721.1/121504 |
work_keys_str_mv | AT acemogludaron informationalbraessparadoxtheeffectofinformationontrafficcongestion AT makhdoumikakhakiali informationalbraessparadoxtheeffectofinformationontrafficcongestion AT malekianazarakhsh informationalbraessparadoxtheeffectofinformationontrafficcongestion AT ozdaglarasu informationalbraessparadoxtheeffectofinformationontrafficcongestion |