Variable demand and multi-commodity flow in Markovian network equilibrium

DOI10.1016/J.AUTOMATICA.2022.110224MaRDI QIDQ2125514zbMATH OpenOpenAlexFDO

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

Publication date 14 April 2022

Published in Automatica (Search for Journal in Brave)

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

zbMATH Keywords

Markov decision processnetwork optimizationWardrop equilibrium

Mathematics Subject Classification ID

Stochastic network models in operations research (90B15) Markov and semi-Markov decision processes (90C40) Games involving graphs (91A43)

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 state-of-the-art optimization software Mosek over extensive numerical experiments.

Recommendations

• Markovian traffic equilibrium
• On a network equilibrium problem with mixed demand
• A Markov chain model for traffic equilibrium problems
• The network equilibrium problem with mixed demand
• scientific article; zbMATH DE number 2202895

Cites work

• An algorithm for the equilibrium assignment problem with random link times
• Convex optimization: algorithms and complexity
• Discrete time, finite state space mean field games
• Duality and network theory in passivity-based cooperative control
• Existence and uniqueness result for mean field games with congestion effect on graphs
• scientific article; zbMATH DE number 3961334 (Why is no real title available?)
• scientific article; zbMATH DE number 1239298 (Why is no real title available?)
• scientific article; zbMATH DE number 1321699 (Why is no real title available?)
• scientific article; zbMATH DE number 700091 (Why is no real title available?)
• scientific article; zbMATH DE number 3365044 (Why is no real title available?)
• Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
• Markovian traffic equilibrium
• Method of successive weighted averages (MSWA) and self-regulated averaging schemes for solving stochastic user equilibrium problem
• On the convergence of descent methods for monotone variational inequalities
• Robust Control of Markov Decision Processes with Uncertain Transition Matrices

Cited in

(5)

• Simple undirected two-commodity integral flow with a unitary demand
• Markovian traffic equilibrium
• scientific article; zbMATH DE number 2096642 (Why is no real title available?)
• Equilibrium Supply-Demand Allocation in a Single-Commodity Network
• Adaptive constraint satisfaction for Markov decision process congestion games: application to transportation networks

Describes a project that uses

Uses Software

• Mosek
• Matlab

This page was built for publication: Variable demand and multi-commodity flow in Markovian network equilibrium

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