Differentiable Path-Following Methods to Compute Stationary Equilibria, Perfect Stationary Equilibria and Proper Stationary Equilibria in Robust Stochastic Games

Description

As an effective paradigm for modeling and analysis of the interactions among competitive players over time, stochastic games have been successfully applied in various fields. In these applications, the computation of stationary equilibrium plays an important role. The integration of robust optimization into stochastic games results in robust stochastic games and provides an effective alternative to deal with uncertainty in both payoffs and state transition probabilities that frequently occurs in the applications. When robust stochastic games are finite (a finite number of players and a finite number of pure strategies for each player in each state), one can naturally extend to them the concepts of perfect equilibrium and proper equilibrium in strategic games and create two strict refinements of stationary equilibrium: perfect stationary equilibrium and proper stationary equilibrium. This project aims at developing effective and efficient differentiable path-following methods to compute a stationary equilibrium, a perfect stationary equilibrium and a proper stationary equilibrium in robust stochastic games when uncertainty in payoffs and state transition probabilities can be presented asbounded polyhedrons. We will exploit in the developments a differentiable increasing function of an extra variable, which takes values between zero and one and vanishes before the extra variable descends to zero. Utilizing the function and logarithmic-barrierterms, we will constitute a logarithmic-barrier robust stochastic game and establish the existence of a smooth path to a stationary equilibrium. We will formulate a perturbed robust stochastic game depending on the extra variable such that a stationaryequilibrium of this perturbed game is an epsilon-perfect stationary equilibrium for a positive value of the extra variable. Applying this perturbed game, we will make up a logarithmic-barrier robust stochastic game and reap a smooth path to a perfect stationary equilibrium. Moreover, we will set up a perturbed robust stochastic game satisfying that a stationary equilibrium of this perturbed game is an epsilon-proper stationary equilibrium provided that the extra variable is positive. Making use of this perturbed game, we will devise a logarithmic-barrier robust stochastic game and acquire a smooth path to a proper stationary equilibrium. We will also explore convexquadratic-penalty robust stochastic games to arrive at the existence of smooth paths that meet the requirements. By fully capitalizing on special structures and scaling techniques, efficient procedures will be attained to numerically trace the smooth pathsand a software package of the methods will be made available for solving robust stochastic games from applications.