Lab Lunch: 27 October 2020 - Kousha Etessami

Title: Computing a fixed point of a monotone function, and some applications

Abstract:

The task of computing a fixed point of a monotone function arises in a variety of applications.

In this talk I will describe recent work in which we have studied the computational complexity of computing a (any) fixed point of a given monotone function that maps a finite d-dimensional grid lattice with sides of length N = 2^n to itself, where the monotone function is presented succinctly via a Boolean circuit with d · n input gates and d · n output gates.  The existence of such a fixed point is guaranteed by Tarski's theorem.

In turns out that computing such a Tarski fixed point subsumes a number of important computational problems, including solving stochastic games, as well as computing a pure Nash equilibrium for supermodular games.

We show that the Tarski fixed point problem is contained in both the total search complexity classes PLS and PPAD.  Many questions remain open. I will discuss some of them.

(This talk describes joint work with C. Papadimitriou, A. Rubinstein,  and M. Yannakakis, in a paper titled:

"Tarski's theorem, supermodular games, and the complexity of  equilibria", that appeared in ITCS’2020.).