A Lemke-like algorithm for the Multiclass Network Equilibrium Problem - ParisTech Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2013

A Lemke-like algorithm for the Multiclass Network Equilibrium Problem

Résumé

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.
Fichier principal
Vignette du fichier
Lemke_like_hal.pdf (347.92 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00857611 , version 1 (03-09-2013)

Identifiants

  • HAL Id : hal-00857611 , version 1

Citer

Frédéric Meunier, Thomas Pradeau. A Lemke-like algorithm for the Multiclass Network Equilibrium Problem. 2013. ⟨hal-00857611⟩
137 Consultations
307 Téléchargements

Partager

Gmail Facebook X LinkedIn More