Simple stochastic games and a new class of total functions

Speaker  Christos Papadimitriou

Host  Nikhil Devanur and Yuval Peres

Affiliation  UC Berkeley

Duration  01:00:47

Date recorded  6 July 2010

Nash equilibrium, integer factorization, and stable configuration of a Hopfield net are examples of total functions, problems in NP that are guaranteed to always have solutions. Each such problem is an implicit existence theorem; consequently, total functions are categorized by the elementary argument involved in the proof of the theorem: Pigeonhole principle, parity argument, conservation of degree, or potential function (no other kinds are known...). We will survey this area, and introduce a new class, lower than those studied in the past, containing several problems that had resisted classification: The Shapley-Condon simple stochastic games, fixpoints of contraction maps, finding Nash equilibria in network games, and finding KKT points of polynomials. Interestingly, this new class is best understood in terms of real-valued functions.

©2010 Microsoft Corporation. All rights reserved.
> Simple stochastic games and a new class of total functions