b'@online{DBLP:journals/corr/abs-1301-5290,'b'\nTITLE = {On Randomized Fictitious Play for Approximating Saddle Points Over Convex Sets},\nAUTHOR = {Elbassioni, Khaled and Makino, Kazuhisa and Mehlhorn, Kurt and Ramezani, Fahimeh},\nLANGUAGE = {eng},\nURL = {http://arxiv.org/abs/1301.5290},\nEPRINT = {1301.5290},\nEPRINTTYPE = {arXiv},\nYEAR = {2014},\nABSTRACT = {Given two bounded convex sets $X\\subseteq\\RR^m$ and $Y\\subseteq\\RR^n,$ specified by membership oracles, and a continuous convex-concave function $F:X\\times Y\\to\\RR$, we consider the problem of computing an $\\eps$-approximate saddle point, that is, a pair $(x^*,y^*)\\in X\\times Y$ such that $\\sup_{y\\in Y} F(x^*,y)\\le \\inf_{x\\in X}F(x,y^*)+\\eps.$ Grigoriadis and Khachiyan (1995) gave a simple randomized variant of fictitious play for computing an $\\eps$-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 $\\eps$-approximate saddle point can be computed using $O^*(\\frac{(n+m)}{\\eps^2}\\ln R)$ 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 $\\eps \\in (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.},\n}\n'