TY - CONF

T1 - Price of Anarchy in queueing systems

AU - Shone, Robert

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

M3 - Abstract

T2 - OR54 - The Annual Conference of the Operational Research Society

Y2 - 4 September 2012 through 6 September 2012

ER -