Lloyd Shapley Lecture

In a zero-sum stochastic game, two players interact repeatedly, and receive a stream of payoffs that depends on their actions and on a variable called state of nature. The state of nature may change along the game, according to players’ actions. The first model of this kind was introduced by Shapley (1953). A widely studied question is to determine whether the value of the n-stage game and the value of the lambda-discounted game converge as n goes to infinity and the discount factor lambda goes to 0. This question was studied in an extremely large variety of models, according to the information and the state dynamics structure, both in discrete time and continuous time. This talk starts with an overview of the topic, illustrating its theoretical significance and its connections with other problems in economics, computer science and pure mathematics. One model that has received particular interest is the model of discrete-time zero-sum stochastic games with signals. Mertens (1986) conjectured that the limit value should always exist in this model. In the second part of the talk, we give a counterexample to this conjecture. Indeed, we consider the particular class of stochastic games with public signals on the state and perfect monitoring, and provide an example that does not have a limit value.

The lecture connects potential functions to approximation guarantees in congestion and cost-sharing games. It uses Shapley-value cost shares to explain the existence and convergence of pure equilibria, examines inefficiency through the price of anarchy, and characterizes cost-allocation rules that guarantee a pure equilibrium.