2014/12/19 by Frédéric Meunier, Meunier, Frédéric, Thomas Pradeau +1 · 1 citation
Computer Science · Decision Sciences · Economics, Econometrics and Finance · Mathematics · #Computer Science and Game Theory (cs.GT) #Economic theories and models #FOS: Computer and information sciences #FOS: Mathematics #Game Theory and Applications #Game Theory and Voting Systems #Optimization and Control (math.OC) #cs.GT #math.OC
paper · pdf · doi:10.48550/arxiv.1412.6496
arxiv created 2014/12/19 · openalex publication_date 2014/12/19 · arxiv updated 2014/12/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider a nonatomic congestion game on a 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. We show that this problem is polynomially solvable when the number of vertices and the number of classes are fixed. In particular, it shows that the parallel-link case with a fixed number of classes is polynomially solvable. On a more practical side, we propose an extension of Lemke's algorithm able to solve this problem.