Home > Research > Publications & Outputs > Price of Anarchy in queueing systems
View graph of relations

Price of Anarchy in queueing systems

Research output: Contribution to conference - Without ISBN/ISSN Abstract

Published
Publication date2012
<mark>Original language</mark>English
EventOR54 - The Annual Conference of the Operational Research Society - The University of Edinburgh, Edinburgh, United Kingdom
Duration: 4/09/20126/09/2012

Conference

ConferenceOR54 - The Annual Conference of the Operational Research Society
CountryUnited Kingdom
CityThe University of Edinburgh, Edinburgh
Period4/09/126/09/12

Abstract

A queueing system can be represented as a stochastic process, in which events (e.g. arrivals, service completions) occur at random points in time. Problems related to the optimal control of queueing systems are usually concerned with the optimisation of an overall summary measure of the system’s performance, such as the long-run average cost incurred per unit time. These types of problem can be modelled using Markov Decision Processes (MDPs), in which we seek to determine an optimal "policy" which specifies the most advantageous decisions to be taken by the system controller. Decisions may involve the admission (or denial) of service to individual customers, the routing of customers between different service facilities and the scheduling of service priorities.

In this talk we briefly discuss methods of finding optimal policies for queueing systems, and some of the structural properties of these optimal solutions. We also discuss the general principle that the performance of a queueing system as a whole is not optimised if customers are allowed to make "selfish" decisions which maximise their own expected net gain. A measure of the sub-optimality of selfish (myopic) policies is given by the 'Price of Anarchy' (PoA), which is simply a ratio of the long-run average cost under a 'selfish' policy to the average cost under an optimal policy. The concept of PoA has been studied in various game theoretical settings, and in this talk we aim to discuss its applicability to queueing systems and MDPs in general.