Variable demand and multi-commodity flow in Markovian network equilibrium. (June 2022)

• Record Type: Journal Article
• Authors: Yu, Yue; Calderone, Dan; Li, Sarah H.Q.; Ratliff, Lillian J.; Açıkmeşe, Behçet
• Is Part Of: Automatica. Volume 140(2022)
• Publication Date: 2022-06
• Subjects: Wardrop equilibrium -- Markov decision process -- Network optimization; Automatic control -- Periodicals; Automation -- Periodicals; 629.805
• DOI: 10.1016/j.automatica.2022.110224
• Languages: English
• ISSNs: 0005-1098

Abstract

Abstract: Markovian network equilibrium generalizes the classical Wardrop equilibrium in network games. At a Markovian network equilibrium, each player of the game solves a Markov decision process instead of a shortest path problem. We propose two novel extensions of Markovian network equilibrium by considering (1) variable demand, which offers the players a quitting option, and (2) multi-commodity flow, which allows players to have heterogeneous ending time. We further develop dynamic-programming-based iterative algorithms for the proposed equilibrium problems, together with their arithmetic complexity analysis. Finally, we illustrate our network equilibrium model via a multi-commodity ride-sharing example, and compare the computational efficiency of our algorithms against the state-of-the-art optimization software MOSEK over extensive numerical experiments.