Alternating minima and maxima, Nash equilibria and Bounded Arithmetic

We show that the least number principle for Σˆkb (strict Σkb) formulas can be characterized by the existence of alternating minima and maxima of length kk. 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 kk-turn games.

► The least number principle for Σˆkb is characterized by alternating minima and maxima of length kk. ► Simple characterization of ∀Σˆ1b theorems of levels T2k of Bounded Arithmetic. ► A characterization in terms of a search problem about finding pure equilibria in kk-turn games.