Before revision:  The existence follows from an algorithm that converges from any starting point to such a point in a number of evaluations to f, \nabla_{y f(x,y), and  \nabla^2_y f(x,y), that is polynomial in 1/\varepsilon, the dimension d,  and the bounds on f and its Lipschitz constant . In addition to existence, our model retains many desirable properties of the min-max model. For instance, it empowers the min-player to make updates that take into account the max-player's response, and in the case of strong convexity/concavity it corresponds to a global min-max solution with duality gap O(\epsilon^2) .
After revision:  The existence follows from an algorithm that converges from any starting point to such a point in a number of evaluations to f, \nabla_{y f(x,y), and \nabla^2_y f(x,y), that is polynomial in 1/\varepsilon, the dimension d, and the bounds on f and its Lipschitz constant .