کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4662021 | 1633487 | 2012 | 11 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Alternating minima and maxima, Nash equilibria and Bounded Arithmetic Alternating minima and maxima, Nash equilibria and Bounded Arithmetic](/preview/png/4662021.png)
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.
Journal: Annals of Pure and Applied Logic - Volume 163, Issue 5, May 2012, Pages 604–614