Iterative computation of security strategies in matrix games with growing action set

摘要

This paper considers a multi-stage matrix game in which one player (minimizer) generates a new action at every stage. Our objective is to find a computationally efficient way to compute the responding strategy of the other player (maximizer) to achieve the maxmin value of the matrix game at the current stage. Since the maxmin problem can be transformed to an LP problem, shadow vertex simplex method is considered. Noticing that our LP model violates the non-degeneracy assumption in shadow vertex method, we make a relaxed non-degeneracy assumption, prove that the necessary and sufficient condition of a shadow vertex still holds with the relaxed non-degeneracy assumption, and hence assure that shadow vertex method is still an efficient method in our case. Based on these result, the iterative shadow vertex method is presented. Instead of starting the search from the original shadow vertex, the iterative shadow vertex method starts the search from the previously visited feasible shadow vertex with the largest objective value. Our simulation results demonstrate the iterative shadow vertex method has much fewer average pivot steps compared with the regular shadow vertex method.