TY - JOUR

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

AU - Bopardikar, Shaunak D.

AU - Langbort, Cédric

N1 - Publisher Copyright:
© 2016 Elsevier Ltd. All rights reserved.

PY - 2016/7/1

Y1 - 2016/7/1

N2 - 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.

AB - 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.

KW - Computational methods

KW - Scenario approach

KW - Zero-sum matrix games

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

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

U2 - 10.1016/j.automatica.2016.02.018

DO - 10.1016/j.automatica.2016.02.018

M3 - Article

AN - SCOPUS:84961798916

SN - 0005-1098

VL - 69

SP - 150

EP - 156

JO - Automatica

JF - Automatica

ER -