Thursday, May 27 2021
11:30 - 12:30

IMSc Webinar

A Bridge between polynomial optimization and games with imperfect recall

B Srivathsan


Webinar: join at 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.

Download as iCalendar