Friday, October 30th will bring two distinguished researchers within computational game theory to Aarhus: Uri Zwick, Tel Aviv and Kousha Etessami, Edinburgh. They will present their work in two lectures in "IT-huset, Lokale 129", Uri Zwick from 10.01 am to 11am and Kousha Etessami from 11.01 am to 12am. Please note that the talks are scheduled to start at 1 minute past the hour, not 15 minutes.....
Also, at 1.15pm, Daniel Andersson will defend his Phd thesis
entitled "Perfect-Information Games with Cycles" in "IT-huset,
Lokale 121".
Title of Uri Zwick's lecture (Oct 30, 10.01am-11am, IT-huset, Lokale 129):
Local improvement algorithms and Policy iteration algorithms
Abstract:
The policy iteration algorithms is a simple family of algorithms that
can be applied in many different settings, ranging from the
relatively simple problem of finding a minimum mean weight
cycle in a graph, the more challenging solution of Markov Decision
Processes (MDPs), to the solution of 2-player full information
stochastic games, also known as Simple Stochastic Games (SSGs).
It was recently shown by Fridmann that the worst case running time
of a natural deterministic version of the policy iteration algorithm,
when applied to Parity Games (PGs), is exponential. It is still open,
however, whether deterministic policy iteration algorithm can solve
Markov Decision Processes in polynomial time, and whether randomized
policy iteration algorithms can solve Simple Stochastic Games in
polynomial time.
The talk will survey what is known regarding policy iteration
algorithms and mention many intriguing open problems.
Title of Kousha Etessami's lecture (Oct 30, 11.01am-12am, IT-huset, Lokale 129):
The complexity of Nash equilibria and other fixed points
Abstract: We reexamine what it means to compute Nash equilibria and, more generally, what it means to compute a fixed point of a given Brouwer function, and we investigate the complexity of the associated problems. Specifically, we study the complexity of the following problem: given a finite game with 3 or more players, and given epsilon > 0, approximate some actual Nash Equilibrium to within distance epsilon. We show that for games with 3 (or more) players approximating an actual NE within any non-trivial distance is at least as hard as long standing open problems in numerical computation (the square-root-sum problem and arithmetic circuit decision problems), which are not known to be in NP nor in the polynomial time hierarchy. Thus, approximating an actual NE for 3-player games is much harder, in our present state of knowledge, than the PPAD-complete problems of computing an epsilon-NE for 3-player games, and of computing an actual NE for 2-player game. We define a new complexity class, FIXP, which captures search problems that can be cast as fixed point computation problems for functions represented by algebraic circuits (straight line programs) over basis {+,*,max} with rational coefficients. We show that the computation (approximate or otherwise) of actual Nash equilibria for 3 or more players is FIXP-complete. We show that PPAD is precisely equal to the piecewise-linear fragment of FIXP where the basis is restricted to the operators {+,max}. Many other important problems in game theory, economics, and probability theory, can be formulated as fixed point problems for such algebraic functions. We discuss several such problems: computing economic market equilibria, computing the value of Shapley˘s stochastic games and Condon's simpler games, and computing extincition probabilities of branching processes. We show that for approximation, or even exact computation, some of these problems can be placed in PPAD, while others are at least as hard as the square-root sum and arithmetic circuit decision problems, and some are FIXP-complete.
Host: Peter Bro Miltersen