5th World Congress · 2016

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.

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.

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.

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.