Game Theoretic Decidability and Undecidability

We study the possibility of prediction/decision making in a finite 2—person game with pure strategies, following the Nash-Johansen noncooperative solution theory. We adopt the infinite-regress logic EIR2 (a fixed-point extension) of the epistemic logic KD2 to capture individual decision making from the viewpoint of logical inference. In the logic EIR2, prediction/decision making is described by the belief set ∆i(g) for player i, where g specifies a game. Our results on prediction/decision making differ between solvable and unsolvable games. For the former, we show that player i can decide whether each of his strategies is a final decision or not. For the latter, we obtain undecidability, i.e., he can neither decide some strategy to be a possible decision nor disprove it. Thus, the theory (EIR2; ∆i(g)) is incomplete in the sense of Gödel’s incompleteness theorem for an unsolvable game g. This result is related to “self-referential”, but its main source is a discord generated by interdependence of payoffs and independent prediction/decision making.