Skip to Main content Skip to Navigation

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 :
Complete list of metadata

Cited literature [113 references]  Display  Hide  Download
Contributor : ABES STAR :  Contact
Submitted on : Wednesday, March 11, 2015 - 9:43:07 AM
Last modification on : Thursday, June 3, 2021 - 3:15:53 AM
Long-term archiving on: : Friday, June 12, 2015 - 10:21:03 AM


Version validated by the jury (STAR)


  • HAL Id : tel-01130025, version 1



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



Record views


Files downloads