On randomized fictitious play for approximating saddle points over convex sets

Khaled Elbassioni, Kazuhisa Makino, Kurt Mehlhorn, Fahimeh Ramezani

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations


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.

Original languageBritish English
Title of host publicationComputing and Combinatorics - 19th International Conference, COCOON 2013, Proceedings
Number of pages12
StatePublished - 2013
Event19th International Computing and Combinatorics Conference, COCOON 2013 - Hangzhou, China
Duration: 21 Jun 201321 Jun 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7936 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference19th International Computing and Combinatorics Conference, COCOON 2013


Dive into the research topics of 'On randomized fictitious play for approximating saddle points over convex sets'. Together they form a unique fingerprint.

Cite this