Convex-Concave Min-Max Stackelberg Games

Min-max optimization problems (i.e., min-max games) have been attracting a great deal of attention because of their applicability to a wide range of machine learning problems. Although significant progress has been made recently, the literature to date has focused on games with independent action sets; little is known about solving games with dependent action sets, which can be interpreted as min-max Stackelberg games, i.e., sequential two-player zero-sum games. The canonical solution concept for min-max Stackelberg games is the Stackelberg equilibrium, whose existence we establish when the objective function is continuous and the constraints satisfy appropriate convexity conditions. We then introduce two first-order methods that compute Stackelberg equilibria in a large class of convex-concave min-max Stackelberg games, and show that our methods converge in polynomial time. Min-max Stackelberg games were first studied by Wald, under the posthumous name of Wald's maximin model, a variant of which is the main paradigm used in robust optimization, which means that our methods can likewise be used to solve many robust convex optimization problems. We observe that the computation of competitive equilibria in homothetic Fisher markets also comprises a min-max Stackelberg game. Further, we demonstrate the efficacy and efficiency of our algorithms in practice by computing competitive equilibria in homothetic Fisher markets with varying utility structures. Our experiments suggest potential ways to extend our theoretical results, by demonstrating how different smoothness properties can affect the convergence rate of our algorithms.