Learning an Unknown Network State in Routing Games
We study learning dynamics induced by myopic travelers who repeatedly play a routing game on a transportation network with an unknown state. The state impacts cost functions of one or more edges of the network. In each stage, travelers choose their routes according to Wardrop equilibrium based on pu...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Elsevier BV
2020
|
| Online Access: | https://hdl.handle.net/1721.1/125223 |
| _version_ | 1826203817714122752 |
|---|---|
| author | Wu, Manxi Amin, Saurabh |
| author2 | Massachusetts Institute of Technology. Institute for Data, Systems, and Society |
| author_facet | Massachusetts Institute of Technology. Institute for Data, Systems, and Society Wu, Manxi Amin, Saurabh |
| author_sort | Wu, Manxi |
| collection | MIT |
| description | We study learning dynamics induced by myopic travelers who repeatedly play a routing game on a transportation network with an unknown state. The state impacts cost functions of one or more edges of the network. In each stage, travelers choose their routes according to Wardrop equilibrium based on public belief of the state. This belief is broadcasted by an information system that observes the edge loads and realized costs on the used edges, and performs a Bayesian update to the prior stage's belief. We show that the sequence of public beliefs and edge load vectors generated by the repeated play converge almost surely. In any rest point, travelers have no incentive to deviate from the chosen routes and accurately learn the true costs on the used edges. However, the costs on edges that are not used may not be accurately learned. Thus, learning can be incomplete in that the edge load vector at rest point and complete information equilibrium can be different. We present some conditions for complete learning and illustrate situations when such an outcome is not guaranteed. |
| first_indexed | 2024-09-23T12:43:34Z |
| format | Article |
| id | mit-1721.1/125223 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T12:43:34Z |
| publishDate | 2020 |
| publisher | Elsevier BV |
| record_format | dspace |
| spelling | mit-1721.1/1252232022-10-01T10:45:49Z Learning an Unknown Network State in Routing Games Wu, Manxi Amin, Saurabh Massachusetts Institute of Technology. Institute for Data, Systems, and Society Massachusetts Institute of Technology. Department of Civil and Environmental Engineering We study learning dynamics induced by myopic travelers who repeatedly play a routing game on a transportation network with an unknown state. The state impacts cost functions of one or more edges of the network. In each stage, travelers choose their routes according to Wardrop equilibrium based on public belief of the state. This belief is broadcasted by an information system that observes the edge loads and realized costs on the used edges, and performs a Bayesian update to the prior stage's belief. We show that the sequence of public beliefs and edge load vectors generated by the repeated play converge almost surely. In any rest point, travelers have no incentive to deviate from the chosen routes and accurately learn the true costs on the used edges. However, the costs on edges that are not used may not be accurately learned. Thus, learning can be incomplete in that the edge load vector at rest point and complete information equilibrium can be different. We present some conditions for complete learning and illustrate situations when such an outcome is not guaranteed. 2020-05-13T19:47:13Z 2020-05-13T19:47:13Z 2019-12 2020-05-13T17:18:19Z Article http://purl.org/eprint/type/ConferencePaper 2405-8963 https://hdl.handle.net/1721.1/125223 Wu, Manxi, and Saurabh Amin. "Learning an Unknown Network State in Routing Games." IFAC-PapersOnLine, 52, 20 (2019): 345-350. © 2019 IFAC-PapersOnLine. All rights reserved. en http://dx.doi.org/10.1016/j.ifacol.2019.12.179 IFAC-PapersOnLine Creative Commons Attribution-NonCommercial-NoDerivs License http://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf Elsevier BV IFAC-PapersOnLine |
| spellingShingle | Wu, Manxi Amin, Saurabh Learning an Unknown Network State in Routing Games |
| title | Learning an Unknown Network State in Routing Games |
| title_full | Learning an Unknown Network State in Routing Games |
| title_fullStr | Learning an Unknown Network State in Routing Games |
| title_full_unstemmed | Learning an Unknown Network State in Routing Games |
| title_short | Learning an Unknown Network State in Routing Games |
| title_sort | learning an unknown network state in routing games |
| url | https://hdl.handle.net/1721.1/125223 |
| work_keys_str_mv | AT wumanxi learninganunknownnetworkstateinroutinggames AT aminsaurabh learninganunknownnetworkstateinroutinggames |