A Lemke-like algorithm for the multiclass network equilibrium problem

Frédéric Meunier; Thomas Pradeau

doi:10.1007/978-3-642-45046-4_30

A Lemke-like algorithm for the multiclass network equilibrium problem

Frédéric Meunier
, Thomas Pradeau

École des ponts

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

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.

Original language	English
Title of host publication	Web and Internet Economics - 9th International Conference, WINE 2013, Proceedings
Pages	363-376
Number of pages	14
DOIs	https://doi.org/10.1007/978-3-642-45046-4_30
Publication status	Published - 1 Dec 2013
Event	9th International Conference on Web and Internet Economics, WINE 2013 - Cambridge, MA, United States Duration: 11 Dec 2013 → 14 Dec 2013

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8289 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	9th International Conference on Web and Internet Economics, WINE 2013
Country/Territory	United States
City	Cambridge, MA
Period	11/12/13 → 14/12/13

Keywords

Lemke algorithm
affine cost functions
congestion externalities
constructive proof
nonatomic games
transportation network

Access to Document

10.1007/978-3-642-45046-4_30

Cite this

Meunier, F., & Pradeau, T. (2013). A Lemke-like algorithm for the multiclass network equilibrium problem. In Web and Internet Economics - 9th International Conference, WINE 2013, Proceedings (pp. 363-376). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8289 LNCS). https://doi.org/10.1007/978-3-642-45046-4_30

@inproceedings{f1dc96f58ec840ebb908512272208d50,

title = "A Lemke-like algorithm for the multiclass network equilibrium problem",

abstract = "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.",

keywords = "Lemke algorithm, affine cost functions, congestion externalities, constructive proof, nonatomic games, transportation network",

author = "Fr{\'e}d{\'e}ric Meunier and Thomas Pradeau",

year = "2013",

month = dec,

day = "1",

doi = "10.1007/978-3-642-45046-4\_30",

language = "English",

isbn = "9783642450457",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "363--376",

booktitle = "Web and Internet Economics - 9th International Conference, WINE 2013, Proceedings",

note = "9th International Conference on Web and Internet Economics, WINE 2013 ; Conference date: 11-12-2013 Through 14-12-2013",

}

Meunier, F & Pradeau, T 2013, A Lemke-like algorithm for the multiclass network equilibrium problem. in Web and Internet Economics - 9th International Conference, WINE 2013, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8289 LNCS, pp. 363-376, 9th International Conference on Web and Internet Economics, WINE 2013, Cambridge, MA, United States, 11/12/13. https://doi.org/10.1007/978-3-642-45046-4_30

A Lemke-like algorithm for the multiclass network equilibrium problem. / Meunier, Frédéric; Pradeau, Thomas.
Web and Internet Economics - 9th International Conference, WINE 2013, Proceedings. 2013. p. 363-376 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8289 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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 -

A Lemke-like algorithm for the multiclass network equilibrium problem

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this