Orateur
Description
An extension of robust optimization to extensive-form games with payoff uncertainty yields robust extensive-form games. To compute Nash equilibria in behavioral strategies for robust extensive-form games with perfect recall, we acquire from a characterization a polynomial system as a necessary and sufficient condition of Nash equilibrium in robust extensive-form games. As a result of this condition, this paper develops a differentiable path-following method to compute Nash equilibria. Incorporating a logarithmic-barrier term into each player's payoff function with an extra variable, we constitute a logarithmic-barrier robust extensive-form game in which each player solves at each information set a convex optimization problem. Applying the optimality conditions to the barrier game and the equilibrium condition yields a polynomial equilibrium system for the barrier game. As a result of this system, we establish the existence of a smooth path that starts from an arbitrary totally mixed behavioral strategy profile and ends at a Nash equilibrium as the extra variable vanishes. For numerical comparisons, we formulate, as an alternative scheme, a convex-quadratic-penalty robust extensive-form game and secure a globally convergent convex-quadratic-penalty differentiable path-following method for Nash equilibria in robust extensive-form games. Numerical comparisons show that the logarithmic-barrier path-following method significantly outperforms the convex-quadratic-penalty path-following method.
