The task of computing a fixed point of a monotone function arises in a large variety of applications. In this talk we shall study the computational complexity of computing a (any) fixed point of a given discrete function, f:[N]^d --> [N]^d, mapping the finite d-dimensional Euclidean grid lattice with sides of length N=2^n to itself, such that the function f is monotone with respect to the standard coordinate-wise
partial order on vectors in [N]^d. By Tarski's Theorem, such a monotone function always has a fixed point, and indeed has a non-empty lattice of fixed points.

In the "black box" model, the monotone function is assumed to be given by an oracle that we can query at any point in the domain [N]^d, and the aim is to find a (any) fixed point with a minimum number of queries. In the "white box" model, the function is given succinctly by a Boolean circuit with d*n input gates and d*n output gates, and we call the total search problem of either computing a (any) fixed point for such a succinctly presented function, or else computing a pair of points that witness its non-monotonicity, the TARSKI problem.

It turns out that the TARSKI problem subsumes a variety of important computational problems, including prominent equilibrium computation problems in game theory and economics whose complexity status is not yet fully understood. These include among them computing/approximating the
value of Condon's or Shapley's stochastic games, and computing a pure Nash equilibrium for (succinctly presented) super-modular games and games with strategic complementarities.

We show that TARSKI is contained in both the total search complexity classes PLS and PPAD. In the black box model, it was known that finding a
fixed can be done in (log N)^d queries, and we show that it requires at least (log N)^2 queries already on the 2-dimensional grid, even for randomized algorithms.

We conclude by discussing the current complexity status of the TARSKI problem, based on some more recent results, both in the white-box model
and black-box oracle model of computation.

(This talk describes joint work with C. Papadimitriou, A. Rubinstein, and
M. Yannakakis, that appeared in ITCS'2020.)

Multi-agent learning in games is a fundamentally challenging domain that is typically studied in a two step process. First, we prove convergence to a particular class of game theoretic equilibria such as Nash equilibria, correlated equilibria or variations thereof and then we use the properties of these equilibria to understand system performance. In this talk, we will be examining rich multi-agent learning scenarios where such approaches do not work and whose behavior is formally chaotic but nevertheless precise understanding of their behavior can be established.