A few weeks ago I wrote here that the Israeli chapter of the game theory society decided to award an annual prize, the Michael B. Maschler prize, to an outstanding research student in game theory in Israel. Yesterday the judge panel has reached its decision, to award this year’s prize to John Levy, a Ph.D. student of Professor Abraham Neyman at the Hebrew University of Jerusalem (Center for Rationality).
John’s main contribution so far is a counterexample: he provided an example of a discounted stochastic game with contiuum of states without a stationary equilibrium. This result is striking because quite a few people worked hard on proving that a discounted stationary equilibrium does exist, and one paper proving it has been published…
A stochastic game is a sequential game that is given by a collection of matrix games. Each entry in each matrix contains a vector of payoffs, one for each player, and, in addition, a probability distribution over the set of matrices (also called transition function). At every stage of the game the players play one of the matrices; each player chooses an action, thereby an entry in the matrix is chosen. Each player receives the payoff prescribed for him by the chosen entry, and the matrix that the players will play in the following stage is chosen by the probability distribution over matrices indicated by the chosen entry. Thus, in a stochastic game the players play a sequence of matrix games, and their actions at every stage determine both their stage payoff, and influence the matrix games they will play in the future.
In a stochastic game each player receives a stream of payoffs, one per stage. It is assumed that each player tries to maximize the discounted sum of his stage payoffs.
Each matrix game is called a state. When the number of states is finite (or countable), the existence of a stationary equilibrium follows from a standard fixed-point argument. When the number of states is countable, the existence of an equilibrium is a difficult problem. Mertens and Parthasarathy proved the existence of a (not necessarily stationary) equilibrium under continuity assumptions on payoffs and transitions (see also this paper).
Yehuda Levy has constructed an example of a game that does not possess a measurable stationary discounted equilibrium. This is a remarkable achievement that puts an end to the chase for a proof of existence. Levy’s example is robust: any stochastic game which is “close” in a suitable manner to his example does not possess a measurable stationary equilibrium either. In a subsequent work, Levy proves that a stochastic game with a continuum of states that obeys an absolute continuity property (that is, all transition probabilities are absolutely continuous w.r.t. a fixed measure) need not have a stationary equilibrium. This result contrasts with a result of Nowak that proves the existence of stationary epsilon-equilibria under the absolute continuity assumption.
Yehuda brought new ideas to the area of stochastic games, an area that I feared exhausted itself in the last years. I am happy that he won the Maschler prize.