On incremental approximate saddle-point computation in zero-sum matrix games

Shaunak D. Bopardikar, Cedric Langbort

Research output: Contribution to journalArticle

Abstract

We consider the problem of approximately computing saddle-point of a zero-sum matrix game when either the columns of the matrix are revealed incrementally in time or the matrix is too large to apply traditional methods. We leverage the established adaptive multiplicative weights algorithm but introduce a novel simple criterion to determine whether the approximately computed minimizer's best strategy needs to be re-computed when a new column of the matrix is introduced. Our main results are two-fold. First, we show that our proposed incremental approach achieves the same accuracy as applying the adaptive multiplicative weights algorithm on the entire matrix, if known a priori. Second, when the columns of the matrix are generated independently and from the same distribution, we show that the expected number of times the approximate strategy is re-computed grows at most logarithmically with the number of columns of the matrix, thereby being computationally efficient.

Original languageEnglish (US)
Pages (from-to)150-156
Number of pages7
JournalAutomatica
Volume69
DOIs
StatePublished - Jul 1 2016

Keywords

  • Computational methods
  • Scenario approach
  • Zero-sum matrix games

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Electrical and Electronic Engineering

Cite this