# Item

ITEM ACTIONSEXPORT

Released

Paper

#### On Randomized Fictitious Play for Approximating Saddle Points Over Convex Sets

##### MPS-Authors

##### External Ressource

No external resources are shared

##### Fulltext (public)

arXiv:1301.5290.pdf

(Preprint), 666KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Elbassioni, K., Makino, K., Mehlhorn, K., & Ramezani, F. (2014). On Randomized Fictitious Play for Approximating Saddle Points Over Convex Sets. Retrieved from http://arxiv.org/abs/1301.5290.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0024-5E4C-C

##### Abstract

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.