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

Lichun Li, Cedric Langbort

Research output: Contribution to journalArticlepeer-review


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
Issue number4
StatePublished - Dec 1 2019


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

ASJC Scopus subject areas

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


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