Institute for Software Research Seminar
- Newell-Simon Hall
- KEVIN LEYTON-BROWN
- Professor of Computer Science
- University of British Columbia
- and Associate Member, Vancouver School of Economics
Modeling Nonstrategic Human Play in Games
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. Leveraging a novel architecture that allows a single network to generalize across different input and output dimensions by using matrix units rather than scalar units, we have shown that even better predictive performance can be achieved.
However, the success of such approaches raises a more fundamental question: at what point does such behavior get so complex that it ought to be considered strategic? The typical answer is that one should check to see whether the behavior involves modeling other agents: strategic agents do so, while nonstrategic agents do not. However, this is not a wholly satisfying answer, because we lack theoretical tools for arguing that a complicated, apparently nonstrategic behavior cannot be rephrased in strategic terms. We overcome this hurdle by introducing a new, formal characterization of nonstrategic behavior that satisfies two properties: (1) it is general enough to capture all purportedly "nonstrategic" decision rules of which we are aware; (2) we prove that behavior obeying our characterization is distinct from strategic behavior in a precise sense.
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 various problems in artificial intelligence, notably the automated design and analysis of algorithms for solving hard computational problems.
He has co-written two books, "Multiagent Systems" and "Essentials of Game Theory," and over 100 peer-refereed technical articles; his work has received over 11,000 citations and an h-index of 41. He is an Fellow of the Association for the Advancement of Artificial Intelligence (AAAI; elected 2018). He was a member of a team that won the 2018 INFORMS Franz Edelman Award for Achievement in Advanced Analytics, Operations Research and Management Science, described as "the leading O.R. and analytics award in the industry." This award recognizes a "completed, practical application that had significant, verifiable and quantifiable impact on the performance of [a] client organization," in his case the Federal Communications Commission. Leyton-Brown also received UBC's 2015 Charles A. McDowell Award for Excellence in Research, a 2014 NSERC E.W.R. Steacie Memorial Fellowship—previously given to a computer scientist only 10 times since its establishment in 1965—and a 2013Outstanding Young Computer Science Researcher Prize from the Canadian Association of Computer Science. He and his coauthors have received paper awards from JAIR, ACM-EC, AAMAS and LION, and numerous medals for the portfolio-based SAT solver SATzilla at international SAT solver competitions (2003–15).
He has co-taught two Coursera courses on "Game Theory" to over 700,000 students (and counting!), and has received awards for his teaching at UBC—notably, a 2013/14 Killam Teaching Prize. He is chair of the ACM Special Interest Group on Electronic Commerce, which runs the annual Economics & Computation conference. He has served as an associate editor for the Artificial Intelligence Journal (AIJ), the Journal of Artificial Intelligence Research (JAIR), ACM Transactions on Economics and Computation (ACM-TEAC), and AI Access; and was program chair for the ACM Conference on Electronic Commerce (ACM-EC) in 2012.
He has held a wide range of visiting professor/researcher positions, at: Technion Israel Institute of Technology(April 2018); Microsoft Research New York City (Jan–Feb 2018); Microsoft Research New England (Mar–Jun 2016); Harvard's EconCS group (Mar–Jun 2016); the Simons Institute for the Theory of Computing at UC Berkeley (Aug–Sep, Nov 2016; Sep-Dec 2015); the Institute for Advanced Studies at Hebrew University of Jerusalem, Israel (Mar–Jun 2011); Makerere University in Kampala, Uganda (Sep 2010–Jan 2011).
He currently advises Auctionomics, AI21, and Qudos. He is a co-founder of Kudu.ug and Meta-Algorithmic Technologies. He was scientific advisor to UBC spinoff Zite until it was acquired by CNN in 2011. His past consulting has included work for Zynga, Trading Dynamics, Ariba, and Cariocas.
Faculty Host: Fei Fang