Simple stochastic games and a new class of total functions

Опубликовано 17 августа 2016, 21:42

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.