Congestion games with player-specific cost functions

Abstract : We consider congestion games on graphs. In nonatomic games, we are given a set of infinitesimal players. Each player wants to go from one vertex to another by taking a route of minimal cost, the cost of a route depending on the number of players using it. In atomic splittable games, we are given a set of players with a non-negligible demand. Each player wants to ship his demand from one vertex to another by dividing it among different routes. In these games, we reach a Nash equilibrium when every player has chosen a minimal-cost strategy. The existence of a Nash equilibrium is ensured under mild conditions. The main issues are the uniqueness, the computation, the efficiency and the sensitivity of the Nash equilibrium. Many results are known in the specific case where all players are impacted in the same way by the congestion. The goal of this thesis is to generalize these results in the case where we allow player-specific cost functions. We obtain results on uniqueness of the equilibrium in nonatomic games. We give two algorithms able to compute a Nash equilibrium in nonatomic games when the cost functions are affine. We find a bound on the price of anarchy for some atomic splittable games, and prove that it is unbounded in general, even when the cost functions are affine. Finally we find results on the sensitivity of the equilibrium to the demand in atomic splittable games
Document type :
Theses
Complete list of metadatas

Cited literature [113 references]  Display  Hide  Download

https://pastel.archives-ouvertes.fr/tel-01130025
Contributor : Abes Star <>
Submitted on : Wednesday, March 11, 2015 - 9:43:07 AM
Last modification on : Friday, May 17, 2019 - 7:15:44 AM
Long-term archiving on : Friday, June 12, 2015 - 10:21:03 AM

File

2014PEST1096.pdf
Version validated by the jury (STAR)

Identifiers

  • HAL Id : tel-01130025, version 1

Collections

Citation

Thomas Pradeau. Congestion games with player-specific cost functions. General Mathematics [math.GM]. Université Paris-Est, 2014. English. ⟨NNT : 2014PEST1096⟩. ⟨tel-01130025⟩

Share

Metrics

Record views

421

Files downloads

292