Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

1997 | Book

Introduction Read chapter Read first chapter

Competitive Markov Decision Processes

Authors: Jerzy Filar, Koos Vrieze

Publisher: Springer New York

Included in: Professional Book Archive

Login to get access
insite
SEARCH

About this book

This book is intended as a text covering the central concepts and techniques of Competitive Markov Decision Processes. It is an attempt to present a rig­ orous treatment that combines two significant research topics: Stochastic Games and Markov Decision Processes, which have been studied exten­ sively, and at times quite independently, by mathematicians, operations researchers, engineers, and economists. Since Markov decision processes can be viewed as a special noncompeti­ tive case of stochastic games, we introduce the new terminology Competi­ tive Markov Decision Processes that emphasizes the importance of the link between these two topics and of the properties of the underlying Markov processes. The book is designed to be used either in a classroom or for self-study by a mathematically mature reader. In the Introduction (Chapter 1) we outline a number of advanced undergraduate and graduate courses for which this book could usefully serve as a text. A characteristic feature of competitive Markov decision processes - and one that inspired our long-standing interest - is that they can serve as an "orchestra" containing the "instruments" of much of modern applied (and at times even pure) mathematics. They constitute a topic where the instruments of linear algebra, applied probability, mathematical program­ ming, analysis, and even algebraic geometry can be "played" sometimes solo and sometimes in harmony to produce either beautifully simple or equally beautiful, but baroque, melodies, that is, theorems.

Table of Contents

Frontmatter

Introduction

1. Introduction
Abstract
Since the 1950s two of the classes of dynamic, stochastic, decision models that have been studied extensively by applied mathematicians, operations researchers, electrical engineers, and mathematical economists are Stochastic Games and Markov Decision Processes, respectively. The name Stochastic Games stems from the seminal paper by Shapley (1953) even though some authors use the name Markov Games, which probably dates back to Zachrisson (1964). Markov decision processes are also called Controlled Markov Chains by the engineers, and it appears that their evolution was stimulated by the books of Bellman (1957) and Howard (1960).
Jerzy Filar, Koos Vrieze

Mathematical Programming Perspective

Frontmatter
2. Markov Decision Processes: The Noncompetitive Case
Abstract
This chapter is devoted to the presentation of the basic theory of finite state/finite action Markov decision processes. Of course, in the context of this book, the entire subject of Markov decision processes forms only a special case of the competitive Markov decision processes, that is, Stochastic Games. Namely, this is the case where there is only one controller, and hence the underlying mathematical problem is “merely” an optimization problem.
Jerzy Filar, Koos Vrieze
3. Stochastic Games via Mathematical Programming
Abstract
This chapter is devoted to the introduction of the theory of finite state/action Stochastic Games. These games can be regarded as competitive Markov decision processes where there are two or more controllers, usually called players, whose fortunes are coupled either because the probability transitions are coupled or because their rewards are coupled, or both. It is assumed that the players have complete knowledge of these coupling functions but that they behave “noncooperatively,” that is, they choose their controls without any collusion and with the single-minded purpose of each maximizing her/his own payoff criterion.
Jerzy Filar, Koos Vrieze

Existence, Structure and Applications

Frontmatter
4. Summable Stochastic Games
Abstract
For many decision problems evolving in discrete time, it is natural to sum the payoffs earned at the different time points. For instance, in Chapter 2 the discounted Markov decision problem was shown to be equivalent to a stopping problem of a certain type, guaranteeing that the sum of the payoffs remains finite. The same holds for discounted stochastic games. So, quite naturally one can ask for conditions guaranteeing a model that possesses nontrivial solutions with respect to the sum of the immediate payoffs as the criterion. Classes of games for which such a criterion is well defined will be called summable stochastic games. We will study three classes of summable stochastic games.
Jerzy Filar, Koos Vrieze
5. Average Reward Stochastic Games
Abstract
In this chapter limiting average reward stochastic games are treated. Most of the chapter is devoted to the zero-sum case. In Section 5.4, nonzero-sum games are studied.
Jerzy Filar, Koos Vrieze
6. Applications and Special Classes of Stochastic Games
Abstract
This chapter is devoted to applications of stochastic games to motivating situations. It quite often appears that a representation of such a realistic situation as a stochastic game leads to a game where the data have certain structural characteristics. For example, a characteristic property could be that the data of the game are such that the transition probabilities are influenced only by the action variable of one player, thus leading to the concept of a single-controller stochastic game. In this way. structural properties of the data of a stochastic game give rise to special classes of games. We have chosen to order this chapter according to these special classes. For each of them we will give the main theoretical results that can be derived with the aid of the theorems of the previous chapters. Next, for each of the special classes, we give one or more applications that will illustrate the special features of the various classes. The emphasis in these applications will be placed on the representation as a stochastic game and on general properties of such games, rather than on the computation of solutions of special examples.
Jerzy Filar, Koos Vrieze
Backmatter
Metadata
Title
Competitive Markov Decision Processes
Authors
Jerzy Filar
Koos Vrieze
Copyright Year
1997
Publisher
Springer New York
Electronic ISBN
978-1-4612-4054-9
Print ISBN
978-1-4612-8481-9
DOI
https://doi.org/10.1007/978-1-4612-4054-9