Alternating minima and maxima, Nash equilibria and Bounded Arithmetic

We show that the least number principle for (Sigma) over cap (b)(k)(strict Sigma(b)(k)) formulas can be characterized by the existence of alternating minima and maxima of length k. We show simple prenex forms of these formulas whose herbrandizations (by polynomial time functions) are for all(Sigma) over cap (b)(l) formulas that characterize for all(Sigma) over cap (b)(l) theorems of the levels T-2(k) of the Bounded Arithmetic Hierarchy, and we derive from this another characterization, in terms of a search problem about finding pure Nash equilibria in k-turn games. (C) 2011 Elsevier B.V. All rights reserved.