Elath Hall, 2nd floor, Feldman Building, Edmond J. Safra Campus
We study the subgame perfect equilibria of two-player stochastic games with perfect monitoring for a fixed discount factor. We develop a novel algorithm that, starting from larger correspondences, spirals inwards towards the state-dependent equilibrium payoff correspondence. At each iteration, starting from a vector of pivot points that are on the boundaries of each state's candidate equilibrium payoff set, we shave off part of each state's set of payoffs in a carefully chosen direction. The pivots are then advanced in this direction. As the cuts progress in a clockwise fashion, the pivots spiral around the equilibrium correspondence, with the trajectories asymptotically tracing out the the equilibrium payoff orrespondence. An implementation of this algorithm is also provided. Preliminary simulations indicate this algorithm is more efficient than existing methods. The theoretical results that underlie the algorithm also yield a bound on the number of extreme payoffs for equilibria starting in a given state.