Given two bounded convex sets $$X\subseteq \mathbb R^m$$X⊆Rm and $$Y\subseteq \mathbb R^n,$$Y⊆Rn, specified by membership oracles, and a continuous convex---concave function $$F:X\times Y\rightarrow \mathbb R$$F:X×Y?R, we consider the problem of computing an $$\varepsilon $$?-approximate saddle point, that is, a pair $$(x^*,y^*)\in X\times Y$$(x?,y?)?X×Y such that $$\sup _{y\in Y} F(x^*,y)\le \inf _{x\in X}F(x,y^*)+\varepsilon .$$supy?YF(x?,y)≤infx?XF(x,y?)+?. Grigoriadis and Khachiyan (Oper Res Lett 18(2):53---58, 1995) gave a simple randomized variant of fictitious play for computing an $$\varepsilon $$?-approximate saddle point for matrix games, that is, when $$F$$F is bilinear and the sets $$X$$X and $$Y$$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 $$\varepsilon $$?-approximate saddle point can be computed using $$O^* \big (\frac{(n+m)}{\varepsilon ^2}\ln R \big )$$O?((n+m)?2lnR) random samples from log-concave distributions over the convex sets $$X$$X and $$Y$$Y. It is assumed that $$X$$X and $$Y$$Y have inscribed balls of radius $$1/R$$1/R and circumscribing balls of radius $$R$$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 $$\varepsilon \in (0,1)$$??(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.
['Khaled M. Elbassioni', 'Kazuhisa Makino', 'Kurt Mehlhorn', 'Fahimeh Ramezani']
On Randomized Fictitious Play for Approximating Saddle Points Over Convex Sets