Wang, Chenlan (2014) Price of anarchy for congestion games with stochastic demands. PhD thesis, University of Warwick.

Preview

PDF WRAP_THESIS_Wang_2014.pdf - Submitted Version - Requires a PDF viewer. Download (672Kb) | Preview

Request Changes to record.

Abstract

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.

Item Type:	Thesis (PhD)
Subjects:	H Social Sciences > HE Transportation and Communications
Library of Congress Subject Headings (LCSH):	Traffic control -- Mathematical models, Traffic congestion -- Mathematical models, Stochastic analysis
Official Date:	September 2014
Dates:	Date Event September 2014 Submitted
Institution:	University of Warwick
Theses Department:	Warwick Business School
Thesis Type:	PhD
Publication Status:	Unpublished
Supervisor(s)/Advisor:	Chen, Bo, Dr. ; Doan, XXuan Vinh
Extent:	vi, 117 leaves : illustrations (black and white), charts
Language:	eng

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads