World Congresses of The Game Theory Society

The Prize in Game Theory and Computer Science of the Game Theory Society in Honour of Ehud Kalai was established in 2008 by a donation from Yoav Shoham in recognition of Ehud Kalai’s role in promoting the connection of the two research areas. Eligibility Rules for Awards until 2016 The Prize is awarded to the person (or persons) who have published the best paper at the interface of game theory and computer science in the last decade. Preference will be given to candidates of age 45 or less at the time of the award, but this is not an absolute constraint. The amount of the Prize is USD 2,500 plus travel expenses of up to USD 2,500 to attend the Congress. Amended Eligibility Rules for Awards after 2016 The GTS officers approved in January 2016 new eligibility rules. As recommended by the 2016 Prize Committee (Preston McAfee, David Parkes, Eva Tardos, and Bernhard von Stengel), they follow the eligibility rules of the Gödel Prize (change highlighted in italics): The Prize will be awarded to the person (or persons) who have published the best paper at the interface of game theory and computer science. Any research paper is eligible that was published in a recognized refereed journal before nomination, but the main results were not published (either in preliminary form in conference proceedings or on a preprint server, or in final form) 14 or more years before the year of the award. This extended period is in recognition of the fact that the value of fundamental work cannot always be immediately assessed. Preference will be given to candidates of age 45 or less at the time of the award, but this is not an absolute constraint. The amount of the Prize will be USD 2,500 plus travel expenses of up to USD 2,500 to attend the Congress.

Oskar Morgenstern’s vision of the need for a new economic science that deals with strategies and coalitions gave birth to game theory. The Oskar Morgenstern Lecture, given at each World Congress of the Game Theory Society, honors an individual who has made important contributions in game theory with significant economic content.

 

Lloyd Shapley pioneered many topics in game theory and their application to economics and political science. The Lloyd Shapley Lecture is given at each World Congress of the Game Theory Society by a distinguished game theorist aged 40 or under at the time of the Lecture.

 

John von Neumann was a co-founder of game theory and one of the pre-eminent mathematicians of the 20th century. The John von Neumann Lecture, given at each World Congress of the Game Theory Society, honors an individual who has made important developments in game theory that are of significant mathematical interest.

Harsanyi Lecture: Oliver Hart

Oliver Hart is a British-born American economist, currently the Andrew E. Furer Professor of Economics at Harvard University. Together with Bengt R. Holmström, he received the Nobel Memorial Prize in Economic Sciences in 2016.
Oliver Hart is an expert on contract theory, theory of the firm, corporate finance, and law and economics. His research centers on the roles that ownership structure and contractual arrangements play in the governance and boundaries of corporations. He has used his theoretical work on firms in two legal cases as a government expert (Black and Decker v. U.S.A. and WFC Holdings Corp. (Wells Fargo) v. U.S.A.) where companies claimed tax related benefits as a result from selling some of their business. The government used Hart’s research to claim that because the companies retained control of the sold assets, they could not lay claim to the tax benefits.

Morgenstern Lecture: Douglas Bernheim

B. Douglas Bernheim is an American professor of Economics, currently the Edward Ames Edmunds Professor of Economics at Stanford University; his previous academic appointments have included an endowed chair in Economics and Business Policy at Princeton University and an endowed chair in Insurance and Risk Management at Northwestern University’s J.L. Kellogg Graduate School of Management, Department of Finance. He has published many articles in academic journals, and has received a number of awards recognizing his contributions to the field of economics.

Title and Abstract of the Prize Lecture, given on July 20^th, 2021:

Positive Welfare Economics

Welfare Economics, the study of economic well-being, consists of two separate branches, one concerning individual well-being, the other concerning social aggregation. The first branch includes the standard revealed preference paradigm as well as tools from Behavioral Welfare Economics. The second branch subsumes work on social choice and welfare.

Vast literatures study these issues from a normative perspective. They ask, how should we evaluate individual well-being? How should we determine overall social welfare? The normative principles that have emerged from these inquiries have proven useful in innumerable applications.

The objective of this research agenda is to study these issues from a positive perspective. We ask, how do people actually evaluate what is good and bad for other individuals? How do they actually aggregate to reach conclusions about social welfare?

Research in positive welfare economics is valuable because it helps us understand why societies adopt particular policies. With respect to aggregation, it helps us understand how people think their societies ought to balance majority preference against the protection of minorities, judgments which (arguably) their elected representatives ought to respect. It also helps us understand how behavioral considerations, such as cognitive biases, can influence policy formation.

This work departs from most (but not all) of the literature on social preferences by focusing on outcomes for others without implicating selfish concerns.

von Neumann Lecture: Josef Hofbauer

Joseph Hofbauer is an Austrian mathematician, currently the Professor of Biomathematics at the University of Vienna. He graduated from the same university and then spent time at Northwestern, the University of Alberta at Edmonton and the Collegium Budapest. He specializes in dynamical systems and their applications in the field of biomathematics as well as evolutionary game theory where he worked with Karl Sigmund.

Title and Abstract of the Prize Lecture, given on July 19^th, 2021:

(Dynamic) Stability of Nash Equilibria

(open) problem: which Nash equilibria of a bimatrix game are stable under the replicator dynamics.

Shapley Lecture: Aislinn Bohren

Aislinn Bohren studies various topics in microeconomics with a focus on models of information and how individuals interact in dynamic settings. Her research explores questions related to learning under model misspecification, discrimination, information aggregation, moral hazard and the econometrics of randomized experiments. Her work on discrimination has both theoretical and empirical components, and builds on my research on learning under model misspecification. Her work in the other four areas is theoretical, and includes applications to designing rating systems, information campaigns and committees, and providing incentives in online labor markets.

Title and Abstract of the Prize Lecture, given on July 20^th, 2021:

Learning with Heuristics and Misspecified Models

Game Theory and Computer Science (Kalai) Prize: Yakov Babichenko and Aviad Rubinstein

Yakov Babichenko received his Ph.D. from Hebrew University in 2012 and is now Associate Professor in the Faculty of Industrial Engineering and Management at the Technion. His research interest is in game theory. He is interested in adaptive learning in games and the rate of convergence of these adaptive processes, as well as in the complexity of equilibria in games in several models such as computational complexity, communication complexity, and query complexity.

Aviad Rubinstein is an assistant professor at Stanford. He was previously a Rabin postdoc at Harvard and completed his PhD at UC Berkeley. His research explores the frontier between what can and cannot be computed efficiently.  

Title and Abstract of the Prize Lecture, given on July 19^th, 2021:

Communication Complexity of Approximate Nash Equilibria

For a constant ε, we prove a P(N) lower bound on the (randomized) communication complexity of ε-Nash equilibrium in two-player N by N games. For n-player binary-action games we prove an exp(n) lower bound for the (randomized) communication complexity of ε-Nash equilibrium. The implications of these results on the rate of convergence of dynamics to Nash equilibria are discussed.

• Morgenstern Lecture:

Thomas Palfrey, Flintridge Professor of Economics and Political Science at the California Institute of Technology, has been selected to present the Morgenstern Lecture at the 2016 World Congress of the Game Theory Society. Thomas Palfrey graduated from the University of Michigan in 1975 and received his PhD in 1981 from Caltech. He is best known for his contributions to Game Theory (both theoretical and experimental) and pioneered its use in the study of Politics.

Title and Abstract of the Prize Lecture, given on 27 July 2016:
Trading Votes for Votes – A Decentralized Matching Algorithm

Vote-trading is common practice in committees and group decision-making. Yet we know very little about its properties. Inspired by the similarity between the logic of sequential rounds of pairwise vote-trading and matching algorithms, we explore three central questions that have parallels in the matching literature: (1) Does a stable allocation of votes always exists? (2) Is it reachable through a decentralized algorithm? (3) What welfare properties does it possess? We prove that a stable allocation exists and is always reached in a finite number of trades, for any number of voters and issues, for any separable preferences, and for any rule on how trades are prioritized. Its welfare properties, however, are guaranteed to be desirable only under specific conditions. A laboratory experiment confirms that stability has predictive power on the vote allocation achieved via sequential pairwise trades, but lends only weak support to the dynamic algorithm itself. Joint work with Alessandra Casella.

• von Neumann Lecture:

Sylvain Sorin, Professor at the University of Paris VI (Pierre and Marie Curie), has been selected to present the von Neumann Lecture at the 2016 World Congress of the Game Theory Society. Sylvain Sorin graduated in 1976 from the Ecole Normale Superieure de Saint Cloud and received his Doctorat d’Etat in 1981 from Paris VI. Since then he has made fundamental contributions to a variety of areas in the Theory of Games: repeated games, stochastic games, merging and reputation, and approachability. Beyond the force of his ideas, he has played a significant role in the cultivation and subsequent flourishing of what might arguably be called a “French School” of Game Theory.

Title and Abstract of the Prize Lecture, given on 26 July 2016:
Asymptotic Value of Dynamic Games

Long term strategic interactions in a stationary environment have usually been modeled as repeated games. At each stage of the process, the moves of the players determine the joint law of the new state and signals to the players and a stage-specific payoff. An evaluation that assigns a (for example, discounted) weight to each stage induces a total weighted payoff, hence a game, with a value that depends on the evaluation.
Longer games, when the duration associated to the evaluation increases, correspond to vanishing stage weight, and the associated limit of the game values is the asymptotic value. We will describe recent advances involving new approaches and results (including cases of existence and non-existence of the limit).
Another alternative approach for studying multistage interactions considers a continuous time process that the players observe and control at discrete times, corresponding to a partition. The asymptotic approach is the analysis of the game as the mesh of the partition decreases, thus with vanishing stage duration. We will present new developments in this direction and discuss the relation with differential games or more generally games in continuous time.
In both frameworks the main tool is the recursive structure and the associate operator that extend the initial Shapley formula for finite discounted stochastic games.

• Shapley Lecture:

Bruno Ziliotto graduated in Mathematics under the supervision of Jerome Renault at the Toulouse School of Economics in 2015, and is currently holding a post-doctoral fellowship from the Fondation des Sciences Mathematiques de Paris. Ziliotto contributed deeply and widely to the general theory of repeated games. He has refuted two long-standing conjectures, which were highlighted by Mertens in a published talk at the International Congress of Mathematicians (Berkeley, 1986), by proving that the value of the n-stage stochastic game with finitely many states and actions, unobservable states, and symmetric information, need not converge. His work and results are already reshaping the research agenda in mathematical game theory.

Title and Abstract of the Prize Lecture, given on 28 July 2016:
Limit Value in Stochastic Games

In a zero-sum stochastic game, two players interact repeatedly, and receive a stream of payoffs that depends on their actions and on a variable called state of nature. The state of nature may change along the game, according to players’ actions. The first model of this kind was introduced by Shapley (1953). A widely studied question is to determine whether the value of the n-stage game and the value of the lambda-discounted game converge as n goes to infinity and the discount factor lambda goes to 0. This question was studied in an extremely large variety of models, according to the information and the state dynamics structure, both in discrete time and continuous time. This talk starts with an overview of the topic, illustrating its theoretical significance and its connections with other problems in economics, computer science and pure mathematics. One model that has received particular interest is the model of discrete-time zero-sum stochastic games with signals. Mertens (1986) conjectured that the limit value should always exist in this model. In the second part of the talk, we give a counterexample to this conjecture. Indeed, we consider the particular class of stochastic games with public signals on the state and perfect monitoring, and provide an example that does not have a limit value.

• Game Theory and Computer Science (Kalai) Prize:

Tim Roughgarden is an Associate Professor of Computer Science and (by courtesy) Management Science and Engineering at Stanford University. His paper “Intrinsic Robustness of the Price of Anarchy” (Journal of the ACM (JACM) 62:5, Article No. 32, 2015.Conference version: STOC ’09, Proc. 41st Annual ACM Symposium on Theory of Computing, pages 513-522, 2009) has been selected as the winner of the Game Theory and Computer Science (Kalai) Prize in 2016 (prize certificate).
Tim Roughgarden received a BS in Applied Mathematics from Stanford in 1997, and a PhD in Computer Science from Cornell in 2002.

An important direction of research in the computer science and game theory interface is aiming to quantify the inefficiency of equilibria in games, dubbed by Koutsoupias and Papadimitriou as the price of anarchy. This line of research aims to distinguish between games where equilibria can be arbitrarily far from a centrally designed optimum solution, and those where the loss of efficiency is more limited. A bound like this can help the analyst evaluate the need to change mechanisms to improve efficiency. The winning paper unifies this line of work, and, perhaps most importantly, offers an extension theorem. Classically, the price of anarchy aimed at bounding the efficiency loss at Nash equilibria. The fact that many games have multiple Nash equilibria, and the computational difficulty of finding Nash equilibria, cast shadow on the implicit assumption that players will be able to coordinate on a Nash equilibrium of the game. The paper extends the same bound to all (coarse) correlated equilibria. This extension is especially important as such equilibria arise whenever all players use a form of no-regret learning to choose their strategies, such as Hart and Mas-Colell’s regret matching.

Roughgarden’s paper has been highly influential since its publication. Its concept of “smoothness proof” quickly entered the lexicon of researchers working on the price of anarchy, and it has stimulated numerous refinements, extensions, and applications.

Title and Abstract of the Prize Lecture, given on 27 July 2016:
Intrinsic Robustness of the Price of Anarchy

The price of anarchy is a measure of the inefficiency of selfish behavior that has been successfully analyzed in many applications, including network routing, resource allocation, auctions, and even models of basketball. It is defined as the worst-case ratio between the welfare of a Nash equilibrium and that of an optimal (first-best) solution. Seemingly, a bound on the price of anarchy is meaningful only if players successfully reach some Nash equilibrium. The main result of this paper is that for many of the classes of games in which the price of anarchy has been studied, results are “intrinsically robust”: a bound on the worst-case price of anarchy for pure Nash equilibria necessarily implies the exact same worst-case bound for much larger sets of outcomes, including mixed Nash equilibria, correlated equilibria, and sequences of outcomes generated by natural experimentation strategies (such as successive best responses or simultaneous regret-minimization). We also discuss subsequent developments, such as generalizations to incomplete-information games with applications to mechanism design.

• Morgenstern Lecture: Paul Milgrom
• von Neumann Lecture: Jean-Francois Mertens (delivered by Abraham Neyman)
• Shapley Lecture: Parag Pathak
• Game Theory and Computer Science (Kalai) Prize (awarded 2013, Stony Brook, Workshop on Computational Game Theory):  Benjamin Edelman, Michael Ostrovsky, Michael Schwarz and Hal Varian for their fundamental analysis of Online Advertisement Auctions (prize certificate).

• Morgenstern Lecture: Jean Tirole
• von Neumann Lecture: Abraham Neyman
• Shapley Lecture: Tim Roughgarden
• Game Theory and Computer Science (Kalai) Prize:  Constantinos Daskalakis, Paul W. Goldberg and Christos H. Papadimitriou for their key conceptual and technical contributions on the complexity of computing Nash equilibrium (prize certificate).

• Morgenstern Lecture: Robert Wilson

• Morgenstern Lecture: Lloyd Shapley
• The Donald P. Jacobs Lecture on Management Applications: David Kreps