ZERO-SUM MARKOV GAMES AND WORST-CASE OPTIMAL-CONTROL OF QUEUING-SYSTEMS

Zero-sum stochastic games model situations where two persons, called p layers, 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 wi th a single controller who has only partial information on the system: the dynamic of the system may depend on some parameter that is unknow n to the controller, and may vary in time in an unpredictable way. A w orst-case criterion may be considered, where the unknown parameter is assumed to be chosen by ''nature'' (called player 1), and the objectiv e of the controller (player 2) is then to design a policy that guarant ees the best performance under worst-case behaviour of nature. The pur pose of this paper is to present a survey of stochastic games in queue s, where both tools and applications are considered. The first part is devoted to the tools. We present some existing tools for solving fini te horizon and infinite horizon discounted Markov games with unbounded cost, and develop new ones that are typically applicable in queueing problems. We then present some new tools and theory of expected averag e cost stochastic games with unbounded cost. In the second part of the paper we present a survey on existing results on worst-case control o f queues, and illustrate the structural properties of best policies of the controller, worst-case policies of nature, and of the value funct ion. Using the theory developed in the first part of the paper, we ext end some of the above results, which were known to hold for finite hor izon costs or for the discounted cost, to the expected average cost.