Paper Info
Title
A Necessary and Sufficient Condition for the Existence of Potential Functions for Heterogeneous Routing Games.
Abstract
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.
Year
Venue
Field
2013
CoRR
Mathematical economics,Mathematical optimization,Price of stability,Best response,Repeated game,Equilibrium selection,Price of anarchy,Normal-form game,Nash equilibrium,Example of a game without a value,Mathematics
DocType
Volume
Citations 
Journal
abs/1312.1075
0
PageRank 
References 
Authors
0.34
21
4
Name
Order
Citations
PageRank
Farhad Farokhi19522.77
Walid Krichene210814.02
Alexandre M. Bayen31250137.72
Karl Henrik Johansson43996322.75