  2-TBSG is a two-player game model which aims to find Nash equilibriums and is
widely utilized in reinforced learning and AI. Inspired by the fact that the
simplex method for solving the deterministic discounted Markov decision
processes (MDPs) is strongly polynomial independent of the discounted factor,
we are trying to answer an open problem whether there is a similar algorithm
for 2-TBSG. We develop a simplex strategy iteration where one player updates
its strategy with a simplex step while the other player finds an optimal
counterstrategy in turn, and a modified simplex strategy iteration. Both of
them belong to a class of geometrically converging algorithms. We establish the
strongly polynomial property of these algorithms by considering a strategy
combined from the current strategy and the equilibrium strategy. Moreover, we
present a method to transform general 2-TBSGs into special 2-TBSGs where each
state has exactly two actions.
