On Randomized Fictitious Play for Approximating Saddle Points Over Convex Sets

Given two bounded convex sets (Formula Presented.) and (Formula Presented.), specified by membership oracles, and a continuous convex–concave function (Formula Presented.), we consider the problem of computing an ε-approximate saddle point, that is, a pair (Formula Presented.) such that (Formula Presented.). Grigoriadis and Khachiyan (Oper Res Lett 18(2):53–58, 1995) gave a simple randomized variant of fictitious play 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 (Formula Presented.) random samples from log-concave distributions over the convex sets X and Y. It is assumed that X and Y have inscribed balls of radius 1/R and circumscribing balls of radius R. 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 (Formula Presented.) 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.