On October 11, Jakub Szymanik will give a LIRa talk. Everyone is cordially invited! (Note: this talk was earlier announced to take place in September. It has been postponed due to a scheduling conflict.)
Speaker: Jakub Szymanik (University of Groningen)
Title: Complexity of Backward Induction Games
Room: Science Park, B0.203
Time: Thursday, 11. October, 15:30-17:30
Abstract: Inspired by the logical analysis of backward induction and
the cognitive science experiments, we investigate the computational
complexity of the reasoning in extensive form dynamic games. We
formalize the computational complexity of a general decision problem
the players face, i.e., is pay-off n reachable by player i in the
game, assuming common knowledge of rationality. We show that such
defined problem is PTIME-complete. Moreover, we provide a more
refined analysis of the complexity of particular game trials which
takes into account alternation type of the game and pay-offs
distribution.