Faites connaître cette offre !
Reference : UMR6074-OCASAN-001
Workplace : RENNES
Date of publication : Friday, July 9, 2021
Type of Contract : FTC Scientist
Contract Period : 12 months
Expected date of employment : 1 October 2021
Proportion of work : Full time
Remuneration : 2900-3000€ monthly gross salary
Desired level of education : PhD
Experience required : Indifferent
Congestion games model selfish resource sharing among several players. A special case is the one of network congestion games, in which players aim at routing traffic through a congested network. Their popularity is certainly due to the fact that they have important practical applications in transportation networks, or in large communication networks. In network congestion games, each player chooses a set of transitions, forming a simple path from a source state to a target state, and the cost of a transition increases with its load, that is, with the number of players using it.
Several works have focused on comparing the social cost of Nash equilibria in this setting compared to an optimal solution implemented by a central authority. The ratio between the two is called the price of anarchy, and several authors have given bounds on this ratio which are valid for all games in a given class. In this project, we will extend these results to the continuous-time setting in which traversing an edge takes a given amount of time, and the cost of a path depends on the time spent with other players while traversing edges. We will explore dynamic strategies in this setting, characterize Nash equilibria, sub-game perfect equilibria and other solution concepts relevant in this setting, develop algorithms to compute these as well as the price of anarchy. In addition, we will explore efficient techniques to handle large numbers of players.
PhD in computer science
Required for all applicants:
- Excellent skills and experience in game theory
- Excellent skills on subgame perfect equilibrium algorithms
- Excellent list of publications in top conferences and journals
The candidate will be part of the SUMO team.
Constraints and risks
We talk about it on Twitter!