Computing solutions of the multiclass network equilibrium problem with affine cost functions

Frédéric Meunier () and Thomas Pradeau ()
Additional contact information
Frédéric Meunier: Université Paris Est, CERMICS
Thomas Pradeau: Université Paris Est, CERMICS

Annals of Operations Research, 2019, vol. 274, issue 1, No 21, 447-469

Abstract: Abstract We consider a non-atomic congestion game on a graph, with several classes of players. Each player wants to go from his origin vertex to his 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 such 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 two-terminal 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.

Keywords: Affine cost functions; Complexity results; Hyperplane arrangement; Lemke algorithm; Network congestion games; 90C33; 91A43; 90B06 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-018-2817-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:274:y:2019:i:1:d:10.1007_s10479-018-2817-z

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-018-2817-z

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().