Zero-sum Markov games and worst-case optimal control of queueing systems

Zero-sum stochastic games model situations where two persons, called players, control some dynamic system, and both have opposite objectives. One player wishes typically to minimize a cost which has to be paid to the other player. Such a game may also be used to model problems with a single controller who has only partial information on the system: the dynamic of the system may depend on some parameter that is unknown to the controller, and may vary in time in an unpredictable way. A worst-case criterion may be considered, where the unknown parameter is assumed to be chosen by ‘nature’ (called player 1), and the objective of the controller (player 2) is then to design a policy that guarantees the best performance under worst-case behaviour of nature. The purpose of this paper is to present a survey of stochastic games in queues, where both tools and applications are considered. The first part is devoted to the tools. The paper presents some existing tools for solving finite horizon and infinite horizon discounted Markov games with unbounded cost, and develops new ones that are typically applicable in queueing problems. It then presents some new tools and theory of expected average cost stochastic games with unbounded cost. In the second part of the paper it presents a survey on existing results on worst-case control of queues, and illustrates the structural properties of best policies of the controller, worst-case policies of nature, and of the value function. Using the theory developed in the first part of the paper, it extends some of the above results, which were known to hold for finite horizon costs or for the discounted cost, to the expected average cost.