  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 solve the new LP with a new constraint efficiently. Considering the
potentially huge number of constraints, which corresponds to the large size of
the other player's action set, we use 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 shadow vertex method with relaxed assumption to make sure such
method works well in our model, then analyze the probability that the old
optimum remains optimal in the new LP, and finally provides the iterative
shadow vertex method whose computational complexity is shown to be strictly
less than that of shadow vertex method. The simulation results demonstrates our
main results about the probability of re-computing the optimum and the
computational complexity of the iterative shadow vertex method.
