On Randomized Fictitious Play for Approximating Saddle Points over Convex Sets

Abstract

Given two bounded convex sets X ⊆ ℝ^m and Y ⊆ ℝⁿ, specified by membership oracles, and a continuous convex-concave function F:X×Y → ℝ, we consider the problem of computing an ε-approximate saddle point, that is, a pair (x ^*,y ^*) ∈ X×Y such that $\sup_{y\in Y} F(x^*,y)\le \inf_{x\in X}F(x,y^*)+\varepsilon .$ Grigoriadis and Khachiyan (1995), based on a randomized variant of fictitious play, gave a simple algorithm for computing an ε-approximate saddle point for matrix games, that is, when F is bilinear and the sets X and Y are simplices. In this paper, we extend their method to the general case. In particular, we show that, for functions of constant “width”, an ε-approximate saddle point can be computed using O ^*(n + m) random samples from log-concave distributions over the convex sets X and Y. As a consequence, we obtain a simple randomized polynomial-time algorithm that computes such an approximation faster than known methods for problems with bounded width and when ε ∈ (0,1) is a fixed, but arbitrarily small constant. Our main tool for achieving this result is the combination of the randomized fictitious play with the recently developed results on sampling from convex sets. A full version of this paper can be found at http://arxiv.org/abs/1301.5290 .