Game Theoretic Decidability and Undecidability
Tai‐Wei Hu, Mamoru Kaneko · 2014
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 EIR 2 (a fixed-point extension) of the epistemic logic KD 2 to capture individual decision making from the viewpoint of logical inference. In the logic EIR 2 prediction/decision making is described by the belief set ∆(g) for player where g specifies a game. Our results on prediction/decision making differ between solvable and unsolvable games. For the former, we show that player 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 (EIR 2 ;∆(g)) is incomplete in the sense of Godel’s incompleteness theorem for an unsolvable game g .T his result is related to “self-referential”, but its main source is a discord generated by interdependence of payoffs and independent prediction/decision making.