Soumyajit Paul 's thesis defence (M2F department, DART team)

In this thesis we study the complexity of computing optimal strategies in two player zero-sum games with imperfect information. In games with Imperfect information players only have partial knowledge about their position in the game. This makes the task of computing optimal strategies hard especially when players forget previously gained information. To further substantiate this hardness we consider two player zero-sum games with imperfect information modeled in the extensive form and provide several new complexity results on computing maxmin value for various classes of imperfect information. For lower bound results we consider problems such as the Square-root sum problem and also complexity classes which involve computation over reals, more precisely Existential Theory of Reals (ETR) and other fragments of the First Order Theory of Reals (FOT(R)).
On a positive note we identify a new class of imperfect recall games for which the optimal strategies can be computed efficiently.
Towards the goal of studying Bridge Bidding theoretically we also provide a new model for studying Bridge Bidding. We make some initial observations for the class of 2 player Bridge games with single suit on this model and lay down the path for future investigations.

Amphi LaBRI