Inefficiency on networks
An economy in which individual agents each choose their optimum strategy does not necessarily optimise the average pay-off per individual. One measure of the global inefficiency of such an economy is known as the Price of Anarchy (PoA). Many studies have considered the PoA in the context of traffic...
| Main Author: | |
|---|---|
| Format: | Thesis (University of Nottingham only) |
| Language: | English |
| Published: |
2018
|
| Online Access: | https://eprints.nottingham.ac.uk/51892/ |
| _version_ | 1848798598054019072 |
|---|---|
| author | Rose, Alex |
| author_facet | Rose, Alex |
| author_sort | Rose, Alex |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | An economy in which individual agents each choose their optimum strategy does not necessarily optimise the average pay-off per individual. One measure of the global inefficiency of such an economy is known as the Price of Anarchy (PoA). Many studies have considered the PoA in the context of traffic networks, in which traffic is routed along paths between origin-destination nodes and a cost or ``latency'' is incurred for traversing the edges of the network. Costs associated to edges are increasing functions of the traffic routed to the edge, creating the effect of congestion.
The majority of these studies have focussed on deriving upper bounds on the PoA under various conditions, such as polynomial edge cost functions. While these studies are useful for identifying the maximum potential inefficiency, they neglect to consider the global causes for inefficiency or how inefficiency can be reduced. Moreover, they do not consider the PoA outside of the context of traffic networks.
This thesis considers the variation of the PoA with the total traffic volume and the potential for congestion, with the results displaying new and non-trivial scaling effects. An investigative study determines the causes of the scaling effects and identifies conditions for which high levels of inefficiency occur. A method for reducing the PoA by restricting the amount of traffic on certain links is presented and analysed.
A novel context for the PoA involving the spatial, pairwise matching of agents is also considered. Motivated by the recent emergence of ride-sharing companies, this model considers the inefficiency when agents seek to pair with their nearest neighbour, compared to the optimum matching which minimises the distance between paired agents. The PoA is again analysed as a function of various system parameters. When agents enter the system at different times, it is shown that it may be more efficient to delay a matching until multiple pairs of agents have entered, and the ``Price of Impatience'' is introduced to measure the inefficiency of matching agents at their entry times. |
| first_indexed | 2025-11-14T20:22:19Z |
| format | Thesis (University of Nottingham only) |
| id | nottingham-51892 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-14T20:22:19Z |
| publishDate | 2018 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-518922025-02-28T14:07:24Z https://eprints.nottingham.ac.uk/51892/ Inefficiency on networks Rose, Alex An economy in which individual agents each choose their optimum strategy does not necessarily optimise the average pay-off per individual. One measure of the global inefficiency of such an economy is known as the Price of Anarchy (PoA). Many studies have considered the PoA in the context of traffic networks, in which traffic is routed along paths between origin-destination nodes and a cost or ``latency'' is incurred for traversing the edges of the network. Costs associated to edges are increasing functions of the traffic routed to the edge, creating the effect of congestion.
The majority of these studies have focussed on deriving upper bounds on the PoA under various conditions, such as polynomial edge cost functions. While these studies are useful for identifying the maximum potential inefficiency, they neglect to consider the global causes for inefficiency or how inefficiency can be reduced. Moreover, they do not consider the PoA outside of the context of traffic networks.
This thesis considers the variation of the PoA with the total traffic volume and the potential for congestion, with the results displaying new and non-trivial scaling effects. An investigative study determines the causes of the scaling effects and identifies conditions for which high levels of inefficiency occur. A method for reducing the PoA by restricting the amount of traffic on certain links is presented and analysed.
A novel context for the PoA involving the spatial, pairwise matching of agents is also considered. Motivated by the recent emergence of ride-sharing companies, this model considers the inefficiency when agents seek to pair with their nearest neighbour, compared to the optimum matching which minimises the distance between paired agents. The PoA is again analysed as a function of various system parameters. When agents enter the system at different times, it is shown that it may be more efficient to delay a matching until multiple pairs of agents have entered, and the ``Price of Impatience'' is introduced to measure the inefficiency of matching agents at their entry times. 2018-07-19 Thesis (University of Nottingham only) NonPeerReviewed application/pdf en arr https://eprints.nottingham.ac.uk/51892/1/thesis_with_pdfcode.pdf Rose, Alex (2018) Inefficiency on networks. PhD thesis, University of Nottingham. |
| spellingShingle | Rose, Alex Inefficiency on networks |
| title | Inefficiency on networks |
| title_full | Inefficiency on networks |
| title_fullStr | Inefficiency on networks |
| title_full_unstemmed | Inefficiency on networks |
| title_short | Inefficiency on networks |
| title_sort | inefficiency on networks |
| url | https://eprints.nottingham.ac.uk/51892/ |