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 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. 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. 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.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:647971 |
| Date | January 2014 |
| Creators | Wang, Chenlan |
| Publisher | University of Warwick |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Source | http://wrap.warwick.ac.uk/67674/ |
Page generated in 0.0023 seconds