IMSc Webinar

A Bridge between polynomial optimization and games with imperfect recall

B Srivathsan

CMI

Webinar: join at https://zoom.us/j/98144583184?pwd=SU81bkNUSGJNaUhwOEs4NndiZDhRQT09 We will give a gentle introduction to extensive form games with imperfect recall, and describe some new complexity results. Using a one-to-one correspondence between these games on one side and multivariate polynomials on the other side, we show that in general, solving games with imperfect recall is as hard as solving certain problems of the first order theory of reals. We establish square-root-sum hardness for a specific class called A-loss games. On the positive side, we find restrictions on games and strategies motivated by Bridge bidding that give polynomial-time complexity. Joint work with Hugo Gimbert and Soumyajit Paul.