• 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.