Incremental approximate saddle-point computation in zero-sum matrix games

Shaunak D. Bopardikar, Cedric Langbort

Research output: Contribution to journalConference article

Abstract

We consider the problem of approximately and efficiently computing saddle-point values for zero-sum matrix games. This problem arises in scenarios where the game's exact value is hard to compute, either because the columns of the matrix are revealed incrementally in time, or because the game's strategy space is too large for traditional methods (e.g., linear programming) to be effective in practice. We lever-age the established adaptive multiplicative weights algorithm but introduce a novel simple criterion to determine whether the minimizer's best strategy needs to be approximately re-computed as 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. Secondly, we argue that our approach can be computationally more efficient than simply re-computing the minimizer's best strategy upon addition of every new column of the matrix. Specifically, for the case when the columns of the matrix are generated independently and from the same distribution, we characterize the probability that the expected number of times the best response is re-computed exceeds a given fraction of the total number of columns in the matrix. Numerical simulations indicate even more significant computational improvement as compared to the analytic result.

Original languageEnglish (US)
Article number7039681
Pages (from-to)1936-1941
Number of pages6
JournalProceedings of the IEEE Conference on Decision and Control
Volume2015-February
Issue numberFebruary
DOIs
StatePublished - Jan 1 2014
Event2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014 - Los Angeles, United States
Duration: Dec 15 2014Dec 17 2014

Fingerprint

Matrix Game
Zero sum game
Saddlepoint
Minimizer
Multiplicative
Game
Computing
Linear programming
Exceed
Fold
Entire
Numerical Simulation
Scenarios
Computer simulation
Strategy

Keywords

  • Computational Methods
  • Game theory
  • Matrix Games
  • Probabilistic Methods

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Modeling and Simulation
  • Control and Optimization

Cite this

Incremental approximate saddle-point computation in zero-sum matrix games. / Bopardikar, Shaunak D.; Langbort, Cedric.

In: Proceedings of the IEEE Conference on Decision and Control, Vol. 2015-February, No. February, 7039681, 01.01.2014, p. 1936-1941.

Research output: Contribution to journalConference article

@article{4d6eef701f814902843a60c268e8ff76,
title = "Incremental approximate saddle-point computation in zero-sum matrix games",
abstract = "We consider the problem of approximately and efficiently computing saddle-point values for zero-sum matrix games. This problem arises in scenarios where the game's exact value is hard to compute, either because the columns of the matrix are revealed incrementally in time, or because the game's strategy space is too large for traditional methods (e.g., linear programming) to be effective in practice. We lever-age the established adaptive multiplicative weights algorithm but introduce a novel simple criterion to determine whether the minimizer's best strategy needs to be approximately re-computed as 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. Secondly, we argue that our approach can be computationally more efficient than simply re-computing the minimizer's best strategy upon addition of every new column of the matrix. Specifically, for the case when the columns of the matrix are generated independently and from the same distribution, we characterize the probability that the expected number of times the best response is re-computed exceeds a given fraction of the total number of columns in the matrix. Numerical simulations indicate even more significant computational improvement as compared to the analytic result.",
keywords = "Computational Methods, Game theory, Matrix Games, Probabilistic Methods",
author = "Bopardikar, {Shaunak D.} and Cedric Langbort",
year = "2014",
month = "1",
day = "1",
doi = "10.1109/CDC.2014.7039681",
language = "English (US)",
volume = "2015-February",
pages = "1936--1941",
journal = "Proceedings of the IEEE Conference on Decision and Control",
issn = "0191-2216",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "February",

}

TY - JOUR

T1 - Incremental approximate saddle-point computation in zero-sum matrix games

AU - Bopardikar, Shaunak D.

AU - Langbort, Cedric

PY - 2014/1/1

Y1 - 2014/1/1

N2 - We consider the problem of approximately and efficiently computing saddle-point values for zero-sum matrix games. This problem arises in scenarios where the game's exact value is hard to compute, either because the columns of the matrix are revealed incrementally in time, or because the game's strategy space is too large for traditional methods (e.g., linear programming) to be effective in practice. We lever-age the established adaptive multiplicative weights algorithm but introduce a novel simple criterion to determine whether the minimizer's best strategy needs to be approximately re-computed as 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. Secondly, we argue that our approach can be computationally more efficient than simply re-computing the minimizer's best strategy upon addition of every new column of the matrix. Specifically, for the case when the columns of the matrix are generated independently and from the same distribution, we characterize the probability that the expected number of times the best response is re-computed exceeds a given fraction of the total number of columns in the matrix. Numerical simulations indicate even more significant computational improvement as compared to the analytic result.

AB - We consider the problem of approximately and efficiently computing saddle-point values for zero-sum matrix games. This problem arises in scenarios where the game's exact value is hard to compute, either because the columns of the matrix are revealed incrementally in time, or because the game's strategy space is too large for traditional methods (e.g., linear programming) to be effective in practice. We lever-age the established adaptive multiplicative weights algorithm but introduce a novel simple criterion to determine whether the minimizer's best strategy needs to be approximately re-computed as 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. Secondly, we argue that our approach can be computationally more efficient than simply re-computing the minimizer's best strategy upon addition of every new column of the matrix. Specifically, for the case when the columns of the matrix are generated independently and from the same distribution, we characterize the probability that the expected number of times the best response is re-computed exceeds a given fraction of the total number of columns in the matrix. Numerical simulations indicate even more significant computational improvement as compared to the analytic result.

KW - Computational Methods

KW - Game theory

KW - Matrix Games

KW - Probabilistic Methods

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

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

U2 - 10.1109/CDC.2014.7039681

DO - 10.1109/CDC.2014.7039681

M3 - Conference article

AN - SCOPUS:84988221153

VL - 2015-February

SP - 1936

EP - 1941

JO - Proceedings of the IEEE Conference on Decision and Control

JF - Proceedings of the IEEE Conference on Decision and Control

SN - 0191-2216

IS - February

M1 - 7039681

ER -