TY - GEN

T1 - On randomized fictitious play for approximating saddle points over convex sets

AU - Elbassioni, Khaled

AU - Makino, Kazuhisa

AU - Mehlhorn, Kurt

AU - Ramezani, Fahimeh

PY - 2013

Y1 - 2013

N2 - Given two bounded convex sets X âŠ† â m and Y âŠ† â n, specified by membership oracles, and a continuous convex-concave function F:X×Y → â, we consider the problem of computing an ε-approximate saddle point, that is, a pair (x,y) â̂̂ X×Y such that Grigoriadis and Khachiyan (1995), based on a randomized variant of fictitious play, gave a simple algorithm 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 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 ε â̂̂ (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. A full version of this paper can be found at http://arxiv.org/abs/1301.5290.

AB - Given two bounded convex sets X âŠ† â m and Y âŠ† â n, specified by membership oracles, and a continuous convex-concave function F:X×Y → â, we consider the problem of computing an ε-approximate saddle point, that is, a pair (x,y) â̂̂ X×Y such that Grigoriadis and Khachiyan (1995), based on a randomized variant of fictitious play, gave a simple algorithm 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 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 ε â̂̂ (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. A full version of this paper can be found at http://arxiv.org/abs/1301.5290.

UR - http://www.scopus.com/inward/record.url?scp=84884965591&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-38768-5_8

DO - 10.1007/978-3-642-38768-5_8

M3 - Conference contribution

AN - SCOPUS:84884965591

SN - 9783642387678

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 65

EP - 76

BT - Computing and Combinatorics - 19th International Conference, COCOON 2013, Proceedings

T2 - 19th International Computing and Combinatorics Conference, COCOON 2013

Y2 - 21 June 2013 through 21 June 2013

ER -