CLIMB talk with Christos Papadimitriou

Title: Convergence of game dynamics and the meaning of a game

Speaker: Christos Papadimitriou, Professor, Columbia Engineering

Abstract:
In 1950 John F. Nash proved that every game has a Nash equilibrium, and this marked the beginning not just of game theory but also of modern economic thought. During the 1990s, as games came under computational scrutiny, flaws of the Nash equilibrium were noted: It is not unique, and this leads to the quagmire of equilibrium selection, and it is intractable to compute anyway. I propose to reframe a game as a mapping from a prior distribution over the strategy space to the limit distribution of repeated play via gradient descent -- called replicator dynamics in the case of games. Three theorems serendipitously proved over the past year together imply that this new conception of a game is well motivated, well defined, and can be computed very efficiently.

Bio:
Papadimitriou considers himself fundamentally a teacher, having taught at UC Berkeley for 22 years before coming to Columbia in 2017, and before that at Harvard, MIT, the National Technical University of Athens, Stanford, and UC San Diego. He authored the textbooks Computational Complexity, Combinatorial Optimization, Algorithms, and Elements of the Theory of Computation. He has also written novels, sometimes with an educational aspiration, including the NYT best-seller Logicomix and his latest, Independence.

Papadimitriou is a member of the National Academy of Sciences and the National Academy of Engineering, a fellow of the American Association of Arts and Sciences, and the recipient of the Knuth Prize, the Gödel prize, the EATCS award, IEEE’s John von Neumann Medal, the IEEE Computer Society Charles Babbage Award, Technion's 2019 Harvey Prize, ACM EC's inaugural career award, IEEE's Women of the Edvac Computer Pioneer Award, and ACM EC's inaugural career award. In 2015, the president of the Hellenic Republic named him a commander of the Order of the Phoenix.

He received his BS in Electrical Engineering from Athens Polytechnic in 1972, and his PhD from Princeton in 1976. He has also received nine honorary doctorates, including from ETH (Zurich), EPFL (Lausanne), and the Universities of Paris (Dauphine), Cyprus, and Athens.

CLIMB
The Center for the Theoretical Foundations of Learning, Inference, Information, Intelligence, Mathematics and Microeconomics at Berkeley (CLIMB) was established to address new conceptual and mathematical challenges arising at the interface between technology, science, and society. CLIMB recognizes the emergence of a new generation of technology that focuses on data, inferences, and decisions, a development that is leading to a deeper engagement between technology and real-world phenomena that involve human decisions, values, discoveries, and culture.