Zero-Sum Discrete-Time Markov Games with Unknown Disturbance Distribution

Stochastic games were introduced by Shapley in 1953. Quoting from Shapley himself, “In a stochastic game the play proceeds by steps from position to position, according to transition probabilities controlled jointly by the two players.” At each stage, each player chooses an action, and the first player receives a payoff from the second player, depending on the stage and on the actions chosen. The ‘unknown disturbance distribution’ refers to the fact that not all components of the game are known by the players. This reflects a realistic scenario of a complex environment, like in many economic applications. This disturbance is modeled as a sequence of independent and identically distributed random variables with unknown distribution. At each stage, before choosing their action, the players implement some kind of estimation procedure in order to gain some insight into the disturbance, and so on the evolution of the game. Two estimation procedures are detailed in the book: density estimation and empirical approximation, which is applicable even when the distribution does not have a density. The existence of a value of the game is established under the two frameworks of discounted payoff and average payoff.

 

Chapter 5 introduces examples to show the relevance of the estimation and control procedures analyzed throughout the book. Two concrete examples are presented: a game model for reservoir operations (i.e. allocation of water to irrigation, domestic use, industry, etc., where the different demands are seen as conflicting and the inflow is modeled as a random variable) and a game model for storage (for example, for secured cloud storage). Some details on the numerical implementation of the methods are presented as well.

 

This is a Springer Brief, so one should not expect a textbook or an introduction to the topic; it is a concise presentation of current research, building on the author’s work published throughout the years.

 

From the introduction: “this book is the first part of a project whose objective is to make a systematic analysis on recent developments in this kind of games (…). The second part of the project will deal with another class of game models”. I think this 2-part project will be a valuable reference for researchers in the field.

---

 

Fabio Mainardi (fabio.mainardi@rd.nestle.com) is a mathematician working as a senior data scientist at Nestlé Research. His mathematical interests are number theory, functional analysis, discrete mathematics and probability.