Simple stochastic games and a new class of total functions

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.

Speaker Details

Christos H. Papadimitriou is C. Lester Hogan Professor of Computer Science at UC Berkeley. Before joining Berkeley in 1996 he taught at Harvard, MIT, Athens Polytechnic, Stanford, and UCSD. He has written five textbooks and many articles on algorithms and complexity, and their applications to optimization, databases, AI, and, more recently, game theory and the Internet. He holds a PhD from Princeton, and honorary doctorates from ETH (Zurich), the University of Macedonia (Thessaloniki), the University of Athens, and the University of Cyprus.
He is a member of the American Academy of Arts and Sciences, the National Academy of Sciences, and of the National Academy of Engineering, and a fellow of the ACM. His novel “Turing (a novel about computation),” was published by MIT Press in 2003, and his graphic novel “Logicomix” (Bloomsbury) appeared in October 2009.

Date:
Speakers:
Christos Papadimitriou
Affiliation:
UC Berkeley
    • Portrait of Jeff Running

      Jeff Running