Alternating minima and maxima, Nash equilibria and Bounded Arithmetic

AbstractWe show that the least number principle for Σˆkb (strict Σkb) 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 ∀Σˆ1b formulas that characterize ∀Σˆ1b theorems of the levels T2k 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