Iterative Computation of Security Strategies of Matrix Games with Growing Action Set

Lichun Li, Cedric Langbort

Research output: Contribution to journalArticlepeer-review

Abstract

This paper studies how to efficiently update the saddle-point strategy, or security strategy of one player in a matrix game when the other player develops new actions in the game. It is well known that the saddle-point strategy of one player can be computed by solving a linear program. Developing a new action will add a new constraint to the existing LP. Therefore, our problem becomes how to efficiently solve the new LP with a new constraint. Considering the potentially huge number of constraints, which corresponds to the large size of the other player’s action set, we use the shadow vertex simplex method, whose computational complexity is lower than linear with respect to the size of the constraints, as the basis of our iterative algorithm. We first rebuild the main theorems in the shadow vertex method with a relaxed non-degeneracy assumption to make sure such a method works well in our model, then analyze the probability that the old optimum remains optimal in the new LP, and finally provide the iterative shadow vertex method whose average computational complexity is shown to be strictly less than that of the shadow vertex method. The simulation results demonstrate our main results about the probability of re-computing the optimum and the computational complexity of the iterative shadow vertex method.

Original languageEnglish (US)
Pages (from-to)942-964
Number of pages23
JournalDynamic Games and Applications
Volume9
Issue number4
DOIs
StatePublished - Dec 1 2019

Keywords

  • Game theory
  • Growing action set
  • Iterative computation
  • Shadow vertex method

ASJC Scopus subject areas

  • Statistics and Probability
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Computational Theory and Mathematics
  • Computational Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Iterative Computation of Security Strategies of Matrix Games with Growing Action Set'. Together they form a unique fingerprint.

Cite this