Informational Braess' Paradox: The Effect of Information on Traffic Congestion
Daron Acemoglu, Ali Makhdoumi, Azarakhsh Malekian, Asuman Ozdaglar

Citation
Daron Acemoglu, Ali Makhdoumi, Azarakhsh Malekian, Asuman Ozdaglar. "Informational Braess' Paradox: The Effect of Information on Traffic Congestion". submitted for publication, 2016.

Abstract
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 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 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 network, 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 IBP will occur. In the process, we establish several properties of the SLI class of networks, which are comprised of linearly independent networks joined together. These properties include the characterization of the complement of the SLI class in terms of embedding a specific set of subgraphs, and also show that whether a graph is SLI can be determined in linear time. We further prove that the worst-case inefficiency performance of ICWE is no worse than the standard Wardrop Equilibrium with one type of users.

Electronic downloads

Internal. This publication has been marked by the author for FORCES-only distribution, so electronic downloads are not available without logging in.

Citation formats

• HTML

  Daron Acemoglu, Ali  Makhdoumi, Azarakhsh  Malekian, Asuman
  Ozdaglar. <a
  href="http://www.cps-forces.org/pubs/140.html"
  >Informational Braess' Paradox: The Effect of Information
  on Traffic Congestion</a>, <i>submitted for
  publication</i>,  2016.

• Plain text

  Daron Acemoglu, Ali  Makhdoumi, Azarakhsh  Malekian, Asuman
  Ozdaglar. "Informational Braess' Paradox: The Effect of
  Information on Traffic Congestion". <i>submitted
  for publication</i>,  2016.

• BibTeX

  @article{AcemogluMakhdoumiMalekianOzdaglar16_InformationalBraessParadoxEffectOfInformationOnTraffic,
      author = {Daron Acemoglu and Ali  Makhdoumi and Azarakhsh 
                Malekian and Asuman Ozdaglar},
      title = {Informational Braess' Paradox: The Effect of
                Information on Traffic Congestion},
      journal = {submitted for publication},
      year = {2016},
      abstract = {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 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 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 network, 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 IBP will
                occur. In the process, we establish several
                properties of the SLI class of networks, which are
                comprised of linearly independent networks joined
                together. These properties include the
                characterization of the complement of the SLI
                class in terms of embedding a specific set of
                subgraphs, and also show that whether a graph is
                SLI can be determined in linear time. We further
                prove that the worst-case inefficiency performance
                of ICWE is no worse than the standard Wardrop
                Equilibrium with one type of users. },
      URL = {http://cps-forces.org/pubs/140.html}
  }
  

Posted by Saurabh Amin on 16 Apr 2016.
Groups: forces
For additional information, see the Publications FAQ or contact webmaster at cps-forces org.