- Christos Papadimitriou, University of California, Berkeley, USA.
- Rakesh Vohra, University of Pennsylvania, USA.
- Kevin Leyton-Brown, University of British Columbia, Canada.
Keynote Talk by Christos Papadimitriou
Christos Papadimitriou, University of California, Berkeley, USA.
Title: Dynamics, Games, and Solution Concepts
Short Bio:Christos H. Papadimitriou is the C. Lester Hogan Professor of Computer Science at UC Berkeley. Before joining Berkeley in 1996, he taught at Harvard, MIT, NTU Athens, Stanford, and UCSD. He has written many books and articles on algorithms and complexity, and their applications to optimization, databases, control, AI, robotics, economics and game theory, the Internet, evolution, and the brain. He holds a PhD from Princeton, and nine honorary doctorates. He is a member of the National Academy of Sciences of the US, the American Academy of Arts and Sciences, and the National Academy of Engineering, and is a recipient of the Knuth prize, the Go"del prize, the Kalai prize for CS in Game Theory, the EATCS award, and the von Neumann medal. He has also written three novels: "Turing," "Logicomix" (with Apostolos Doxiadis) and "Independence" (in Greek).
Keynote Talk by Rakesh Vohra
Rakesh Vohra, University of Pennsylvania, USA.
Abstract:Each year the National Resident Matching Program matches about 20,000 would be residents to hospitals. To encourage participation in the centralized clearinghouse, the matching is supposed to be stable. This means that no subset of doctors and hospitals should be able to improve upon their match by contracting outside the clearinghouse. The problem of finding such a stable matching was conceived by David Gale and Lloyd Shapley. Not only did they show the existence of stable matchings (in certain circumstances) they did so via a simple and elegant algorithm called the deferred acceptance algorithm (DA). It and its variants have become the algorithm of choice for determining stable matchings in a variety of settings. Each setting has imposed new demands on the algorithm. Among them are to how to handle complementarities and distributional constraints. The simplicity of the DA makes it difficult to accommodate these new considerations except in special cases. In this talk I will outline an alternative approach based on Scarf’s lemma for tackling such problems. The lemma arose in the context of co-operative Game Theory, is closely related to Sperner’s lemma and has subsequently found applications in combinatorics. This is based on joint work with Thanh Nguyen.
Short Bio:Rakesh Vohra is the George A. Weiss and Lydia Bravo Weiss University Professor, Professor of Economics, Professor of Electrical and Systems Engineering and Co-Director of the Warren Center for Network & Data Sciences. His research interests are in mechanism design and game theory and their application.
Keynote Talk by Kevin Leyton-Brown
Kevin Leyton-Brown, University of British Columbia, Canada.
Abstract:It is common to assume that players in a game will adopt Nash equilibrium strategies. However, experimental studies have demonstrated that Nash equilibrium is often a poor description of human players' behavior, even in unrepeated normal-form games. Nevertheless, human behavior in such settings is far from random. Drawing on data from real human play, the field of behavioral game theory has developed a variety of models that aim to capture these patterns. The current state of the art in that literature is a model called quantal cognitive hierarchy. It predicts that agents approximately best respond and explicitly model others' beliefs to a finite depth, grounded in a uniform model of nonstrategic play. We have shown that even stronger models can be built by drawing on ideas from cognitive psychology to better describe nonstrategic behavior. However, this whole approach requires extensive expert knowledge and careful choice of functional form. Deep learning presents an alternative, offering the promise of automatic cognitive modeling. We introduce a novel architecture that allows a single network to generalize across different input and output dimensions by using matrix units rather than scalar units, and show that its performance significantly outperforms that of the previous state of the art.
Short Bio:Kevin Leyton-Brown is a professor of Computer Science at the University of British Columbia and an associate member of the Vancouver School of Economics. He holds a PhD and M.Sc. from Stanford University (2003; 2001) and a B.Sc. from McMaster University (1998). He studies the intersection of computer science and microeconomics, addressing computational problems in economic contexts and incentive issues in multiagent systems. He also applies machine learning to the automated design and analysis of algorithms for solving hard computational problems.