check
Game Theory & Math Economics: Ben Brooks (University of Chicago) - "An algorithm for two-player stochastic games with perfect monitoring" | Einstein Institute of Mathematics

Game Theory & Math Economics: Ben Brooks (University of Chicago) - "An algorithm for two-player stochastic games with perfect monitoring"

Date: 
Sun, 31/05/201516:00-17:00
Location: 
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.