Adaptive constraint satisfaction for Markov decision process congestion games: application to transportation networks

DOI10.1016/J.AUTOMATICA.2023.110879MaRDI QIDQ6163985zbMATH OpenFDO

Authors Sarah H. Q. Li, Yue Yu, Nicolas I. Miguel, Dan Calderone, Lillian J. Ratliff, Behçet Açıkmeşe

Publication date 30 June 2023

Published in Automatica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1907.08912

zbMATH Keywords

congestion gamesincentive designMarkov decision processonline optimizationstochastic gamestransportation systems

Mathematics Subject Classification ID

Transportation, logistics and supply chain management (90B06) Markov and semi-Markov decision processes (90C40) Potential and congestion games (91A14) Stochastic games, stochastic differential games (91A15)

Abstract: Under the Markov decision process (MDP) congestion game framework, we study the problem of enforcing population distribution constraints on a population of players with stochastic dynamics and coupled congestion costs. Existing research demonstrates that the constraints on the players' population distribution can be satisfied by enforcing tolls. However, computing the minimum toll value for constraint satisfaction requires accurate modeling of the player's congestion costs. Motivated by settings where an accurate congestion cost model is unavailable (e.g. transportation networks), we consider an MDP congestion game with unknown congestion costs. We assume that a constraint-enforcing authority can repeatedly enforce tolls on a population of players who converges to an $epsilon$-optimal population distribution for any given toll. We then construct a myopic update algorithm to compute the minimum toll value while ensuring that the constraints are satisfied on average. We analyze how the players' sub-optimal responses to tolls impact the rates of convergence towards the minimum toll value and constraint satisfaction. Finally, we construct a congestion game model for Uber drivers in Manhattan, New York City (NYC) using data from the Taxi and Limousine Commission (TLC) to illustrate how to efficiently reduce congestion while minimizing the impact on driver earnings.

Recommendations

• An optimal control approach to day-to-day congestion pricing for stochastic transportation networks
• Traffic congestion pricing via network congestion game approach
• A reinforcement learning scheme for the equilibrium of the in-vehicle route choice problem based on congestion game
• A differential game model of Nash equilibrium on a congested traffic network
• Potential game of multi-class, multi-criteria traffic assignment and congestion pricing

Cites work

• A class of games possessing pure-strategy Nash equilibria
• A Continuous Model of Transportation
• A reinforcement learning scheme for the equilibrium of the in-vehicle route choice problem based on congestion game
• Convex optimization: algorithms and complexity
• Efficient search of first-order Nash equilibria in nonconvex-concave smooth min-max problems
• First-order methods of smooth convex optimization with inexact oracle
• scientific article; zbMATH DE number 1818892 (Why is no real title available?)
• scientific article; zbMATH DE number 5685899 (Why is no real title available?)
• Mean field games
• Online learning of Nash equilibria in congestion games
• Potential games
• Prediction-Correction Interior-Point Method for Time-Varying Convex Optimization
• Rate Analysis of Inexact Dual First-Order Methods Application to Dual Decomposition
• Smart routing of electric vehicles for load balancing in smart grids
• Stochastic Games
• The effectiveness of Stackelberg strategies and tolls for network congestion games
• Variable demand and multi-commodity flow in Markovian network equilibrium
• Watch and learn: optimizing from revealed preferences feedback

Cited in

(2)

• A reinforcement learning scheme for the equilibrium of the in-vehicle route choice problem based on congestion game
• Decision-making problem for two-player Markov game: perspective of feedback control

This page was built for publication: Adaptive constraint satisfaction for Markov decision process congestion games: application to transportation networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6163985)