Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Wang, Chenlan
Languages: English
Types: Doctoral thesis
Subjects: HE

Classified by OpenAIRE into

ACM Ref: TheoryofComputation_GENERAL
arxiv: Computer Science::Computer Science and Game Theory
The price of anarchy is a game-theoretical concept and it measures system degradation caused by players' selfish behaviours. This thesis extends models of congestion games to take stochastic demands into account and studies the price of anarchy on the basis of generalised models developed in this research. In the presence of stochastic demands, the models developed in this study better re\ud flect the reality of a transportation network. The study would help provide a theoretical foundation and insights into mechanism design of transportation games and traffic control in practice.\ud \ud This thesis is concerned with both non-atomic and atomic congestion games, which involve an infinite and finite number of travellers respectively. We introduce the notions of user equilibrium and system optimum under stochastic demands and investigate the behaviours of travellers and central coordinators in a stochastic environment. At a user equilibrium, travellers choose routes independently and aim to minimise their own expected travel costs, while at a system optimum, traffic is fully coordinated to minimise the expected total cost over the whole network.\ud \ud We extend two existing methods of bounding the price of anarchy and compute the quality upper bounds for polynomial cost functions and very general settings of demand distributions. More specifically, we consider positive-valued distributions and normal distributions for non-atomic congestion games, and positive-valued discrete distributions for atomic congestion games. Our results show that the price of anarchy depends on the class of cost functions, demand distributions and, to some extent, network topologies. All the upper bounds are tight in some special cases, including the case of deterministic demands. The two bounding methods are also compared.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • Agachai Sumalee and Wei Xu. First-best marginal cost toll for a tra c network with stochastic demand. Transportation Research Part B: Methodological, 45(1):41{59, 2011.
    • Chenlan Wang, Xuan Vinh Doan, and Bo Chen. Price of anarchy for nonatomic congestion games with stochastic demands. Transportation Research Part B: Methodological, 70:90{111, 2014a.
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article