The price of anarchy, a concept introduced by Koutsoupias and Papadimitriou [9], is the main topic of this thesis. It is a measure of the loss of efficiency that occurs when there is no central control over a system consisting of many "selfish" agents. We will be particularly interested in this in the context of network games, which can be used to model congestion in traffic and communication networks. / After an introduction of the relevant concepts and review of related work, we proceed with the new results of this thesis. We provide a new upper bound for the price of anarchy in the case of atomic unsplittable agents with polynomial cost functions, and demonstrate that it is tight by an explicit construction. We then introduce a new model for network routing that introduces priorities; users with a higher priority on a link will be able to traverse the link more quickly. Our model is fairly general, and allows various different priority schemes for modelling different situations. One particularly interesting version, which we have dubbed the timestamp game, assigns priorities according to the order of arrival at the start of the link. / We derive tight upper bounds for the price of anarchy in our model in the case of polynomial cost functions and nonatomic agents. We also obtain tight results in the unsplittable case with linear cost functions, and an upper bound with polynomial cost functions. / While we concentrate on network games, most of the results carry through to the more general class of congestion games, which we also discuss.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.101156 |
| Date | January 2006 |
| Creators | Olver, Neil. |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Master of Science (Department of Mathematics and Statistics.) |
| Rights | © Neil Olver, 2006 |
| Relation | alephsysno: 002599958, proquestno: AAIMR32765, Theses scanned by UMI/ProQuest. |
Page generated in 0.0013 seconds