TY - JOUR

T1 - On Randomized Fictitious Play for Approximating Saddle Points Over Convex Sets

AU - Elbassioni, Khaled

AU - Makino, Kazuhisa

AU - Mehlhorn, Kurt

AU - Ramezani, Fahimeh

N1 - Publisher Copyright:
© 2014, Springer Science+Business Media New York.

PY - 2015/10/5

Y1 - 2015/10/5

N2 - Given two bounded convex sets (Formula Presented.) and (Formula Presented.), specified by membership oracles, and a continuous convex–concave function (Formula Presented.), we consider the problem of computing an ε-approximate saddle point, that is, a pair (Formula Presented.) such that (Formula Presented.). Grigoriadis and Khachiyan (Oper Res Lett 18(2):53–58, 1995) gave a simple randomized variant of fictitious play 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 (Formula Presented.) 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 (Formula Presented.) 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.

AB - Given two bounded convex sets (Formula Presented.) and (Formula Presented.), specified by membership oracles, and a continuous convex–concave function (Formula Presented.), we consider the problem of computing an ε-approximate saddle point, that is, a pair (Formula Presented.) such that (Formula Presented.). Grigoriadis and Khachiyan (Oper Res Lett 18(2):53–58, 1995) gave a simple randomized variant of fictitious play 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 (Formula Presented.) 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 (Formula Presented.) 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.

KW - Convex optimization

KW - Multiplicative weights update method

KW - Saddle point

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

U2 - 10.1007/s00453-014-9902-8

DO - 10.1007/s00453-014-9902-8

M3 - Article

AN - SCOPUS:84940955361

SN - 0178-4617

VL - 73

SP - 441

EP - 459

JO - Algorithmica (New York)

JF - Algorithmica (New York)

IS - 2

ER -