AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI   Info

AG Audience

English

30 Minutes

Saarbrücken

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), based on a randomized variant of fictitious play, gave a simple algorithm 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^*(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 $\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.

Ali Pourmiri

--email hidden

passcode not visible

logged in users only