Game theory and the Reverse mathematics theme

Question

After having studied carefully Simpson's book SOSOA (Subsystems of second order arithmetic) I've naturally arrived at the question about the connection of Game theory with Reverse mathematics. Is there such a thing? Results such as this is of interest for me: any finite normal form game has a Nash Equilibrium iff $\textsf{WKL}_0$ holds over $\textsf{RCA}_0$. It is just an example, I do not claim it is true.

Answer 1

There is an extensive body of research on games (specifically determinacy principles) and reverse mathematics. Just to mention a few results:

• WKL$_0$ is equivalent to clopen determinacy for games on $\{0,1\}$ (= "Finite-length, finite-option games have winning strategies").

• ATR$_0$ is equivalent to both clopen determinacy on $\omega$ and to open determinacy on $\omega$ - this is due to Steel.

  • Incidentally, clopen and open determinacy for games on $\mathbb{R}$ are not equivalent in higher reverse mathematics; this was initially proved by me via forcing, then shortly after given a much better proof by Hachtman via fine structure theory, and apparently there's another proof by Sato (although it hasn't appeared yet) via proof theory.

(From now on, games are on $\omega$.)

• $\Pi^1_1$-CA$_0$ is equivalent to $\Sigma^0_1\wedge\Pi^0_1$-determinacy.

• A very fine-grained analysis has been conducted by Nemoto, e.g. here.

• At the higher determinacy levels, there is a tight analysis by Montalban/Shore (see e.g. this paper); it's a bit technical, however, due to their proof that no true $\Sigma^1_4$ sentence can imply $\Delta^1_2$-CA$_0$ (in particular, full $\Sigma^1_1$ determinacy doesn't imply $\Delta^1_2$-CA$_0$), which renders straightforward reversals impossible.

  • In particular, they show that $(i)$ for each $n$, Z$_2$ proves $n$-$\Pi^0_3$ determinacy, but $(ii)$ $\Delta^0_4$-determinacy isn't provable in Z$_2$ (this refuted an earlier claim by Martin).

• An astronomically less important, but still in my mind neat, example (and plugging my own work): determinacy for Banach-Mazur games for Borel subspaces of Baire space is equivalent to ATR$_0$ and to Banach-Mazur determinacy for analytic subspaces (I got the lower bounds, the upper bounds being essentially due to Steel); meanwhile, determinacy for $\Sigma^1_2$-Banach-Mazur games is independent of ZFC, so there could be some really cool stuff here (but I haven't been able to tease it out).

---

Moving from determinacy to equilibria, I'm less familiar with this but Yamazaki/Peng/Peng showed that Glicksberg's theorem ("every continuous game has a mixed Nash equilibrium") is equivalent to ACA$_0$. See also Weiguang Peng's thesis.

In general, equilibria seem to have not been studied as much as determinacy principles in reverse math; I suspect this is because of the hugely important role determinacy principles play in set theory.

Possibly also of interest, but not strictly reverse math:

• The complexity-theoretic difficulty of finding Nash equilibria has been studied by several people, e.g. Daskalakis/Goldberg/Papadimitriou.

• Equilibria have been studied from the perspective of Weirauch reducibility by Pauly.

• Tanaka looked at equilibria in a constructive context.