When Do Potential Functions Exist in Heterogeneous Routing Games?
2014 (English)Report (Other academic)
We study a heterogeneous routing game in which vehicles might belong to more than one type. The type determines the cost of traveling along an edge as a function of the flow of various types of vehicles over that edge. We relax the assumptions needed for the existence of a Nash equilibrium in this heterogeneous routing game. We extend the available results to present necessary and sufficient conditions for the existence of a potential function. We characterize a set of tolls that guarantee the existence of a potential function when only two types of users are participating in the game. We present an upper bound for the price of anarchy (i.e., the worst-case ratio of the social cost calculated for a Nash equilibrium over the social cost for a socially optimal flow) for the case in which only two types of players are participating in a game with affine edge cost functions. A heterogeneous routing game with vehicle platooning incentives is used as an example throughout the article to clarify the concepts and to validate the results.
Place, publisher, year, edition, pages
TRITA-EE, ISSN 1653-5146 ; 2014:009
Heterogeneous Routing Game, Nash Equilibrium, Potential Functions, Optimization
Control Engineering Transport Systems and Logistics
IdentifiersURN: urn:nbn:se:kth:diva-141199OAI: oai:DiVA.org:kth-141199DiVA: diva2:695605
QC 201402132014-02-112014-02-112014-02-21Bibliographically approved