TY - GEN
T1 - A Lemke-like algorithm for the multiclass network equilibrium problem
AU - Meunier, Frédéric
AU - Pradeau, Thomas
PY - 2013/12/1
Y1 - 2013/12/1
N2 - We consider a nonatomic congestion game on a connected graph, with several classes of players. Each player wants to go from its origin vertex to its destination vertex at the minimum cost and all players of a given class share the same characteristics: cost functions on each arc, and origin-destination pair. Under some mild conditions, it is known that a Nash equilibrium exists, but the computation of an equilibrium in the multiclass case is an open problem for general functions. We consider the specific case where the cost functions are affine and propose an extension of Lemke's algorithm able to solve this problem. At the same time, it provides a constructive proof of the existence of an equilibrium in this case.
AB - We consider a nonatomic congestion game on a connected graph, with several classes of players. Each player wants to go from its origin vertex to its destination vertex at the minimum cost and all players of a given class share the same characteristics: cost functions on each arc, and origin-destination pair. Under some mild conditions, it is known that a Nash equilibrium exists, but the computation of an equilibrium in the multiclass case is an open problem for general functions. We consider the specific case where the cost functions are affine and propose an extension of Lemke's algorithm able to solve this problem. At the same time, it provides a constructive proof of the existence of an equilibrium in this case.
KW - Lemke algorithm
KW - affine cost functions
KW - congestion externalities
KW - constructive proof
KW - nonatomic games
KW - transportation network
UR - https://www.scopus.com/pages/publications/84893039267
U2 - 10.1007/978-3-642-45046-4_30
DO - 10.1007/978-3-642-45046-4_30
M3 - Conference contribution
AN - SCOPUS:84893039267
SN - 9783642450457
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 363
EP - 376
BT - Web and Internet Economics - 9th International Conference, WINE 2013, Proceedings
T2 - 9th International Conference on Web and Internet Economics, WINE 2013
Y2 - 11 December 2013 through 14 December 2013
ER -