One world mathematical game theory seminar abstracts

April 6, UNIFORMLY SUPPORTED APPROXIMATE EQUILIBRIA IN FAMILIES OF GAMES, JOHN LEVY

This paper considers uniformly bounded classes of non-zero-sum strategic-form games with compact continuous action spaces. The class of games is assumed to be defined via a semi-algebraic condition. We show that for each varepsilon>0, the support size required for varepsilon-equilibrium can be taken to be uniform over the entire class. As a corollary, the value in the zero-sum case, as a function of a single-variable, is well behaved in the limit. More generally, the result only requires that the collection of payoff functions considered, as a function of other players actions, have finite Vapnik–Chervonenkis dimension.

April 20, ALGORITHMS FOR RANK-1 BIMATRIX GAMES , BERNHARD VON STENGEL

The rank of a bimatrix game is the matrix rank of the sum of the two payoff matrices. For a game of rank r, the set of its Nash equilibria is the intersection of a one-dimensional set of equilibria of parameterized games of rank r-1 with a hyperplane. We comprehensively analyze games of rank one. They are economically more interesting than zero-sum games (which have rank zero), but are nearly as easy to solve. We show the following results: (1) One equilibrium of a rank-1 game can be found in polynomial time by binary search. (2) All equilibria of a rank-1 game can be found by a pivoting method that follows a piecewise linear path. In contrast, such a path-following method finds only one equilibrium of a general bimatrix game. (3) The number of equilibria of a rank-1 game may be exponential. (4) We present a new rank-preserving homeomorphism between bimatrix games and their equilibrium correspondence. It is a variation of the Kohlberg-Mertens homeomorphism used for the concept of strategic stability of an equilibrium component.

Joint work with Bharat Adsul, Jugal Garg, Ruta Mehta, and Milind Sohoni.

May 4, DOES MORAL PLAY EQUILIBRATES, JÖRGEN WEIBULL

Results in evolutionary game theory, as well as recent experimental results suggest that we should expect some Kantian moral motivation, alongside pure self-interest, in a range of strategic interactions. But does Nash equilibrium always exist if players are partly morally motivated? The answer is negative, and the reason is that morality may destroy linearity with respect to randomization, so the “right thing to do” may sometimes be not to randomize. This talk presents an analysis of the existence of (pure or mixed) symmetric Nash equilibria in finite and symmetric two-player games when played by partially morally motivated players. The analysis is carried out for complete information between equally moral players, and for incomplete information about one’s opponent’s degree of morality. Necessary and sufficient conditions for the existence of equilibrium are given, and the results are illustrated by examples and counter-examples.

Joint work with Immanuel Bomze and Werner Schachinger,

May 18, VIABLE NASH EQUILIBRIA: FORMATION AND DEFECTION, EHUD KALAI

To be credible, economic analysis should restrict itself to the use of only those Nash equilibria that are viable. To assess the viability of an equilibrium π, I study simple dual indices: a formation index, F(π), that species the number of loyalists that can form π; and a defection index, D(π), that species the number of defectors that π can sustain.

Surprisingly, these simple indices (1) predict the performance of Nash equilibria in social systems and lab experiments, i.e., they assess equilibrium viability; and (2) they also uncover new properties of Nash equilibria and stability issues that have so far eluded game theory refinements.

June 1, MONOLOGUES, DIALOGUES AND COMMON PRIORS, DOV SAMET

Our main purpose is to provide a simple test enabling to conclude that two agents do not share a common prior. The test is simple as it does not require information about agents’ knowledge and beliefs, but rather only the record of a dialogue between the agents. In each stage of a joint learning process the agents tell  each other the probability they ascribe to a fixed event and update their beliefs about the event. To characterize dialogues that are consistent with a common prior, we first characterize monologues, that is, sequences of probabilities assigned by a single agent to a given event in an exogenous learning process. We show that a sequence is a monologue if and only if it has a bounded relative variation.   A dialogue  is consistent with a common prior if and only if each mixture of the monologues comprising the dialogue is itself a monologue.

Joint work with Alfredo Di Tillio, Ehud Lehrer and  Herakles Polemarchakis.

June 15, TO INFINITY AND BEYOND: SCALING ECONOMIC THEORIES VIA LOGICAL COMPACTNESS, YANNAI A. GONCZAROWSKI 

Many economic-theoretic models incorporate finiteness assumptions that, while introduced for simplicity, play a real role in the analysis. Such assumptions introduce a conceptual problem, as results that rely on finiteness are often implicitly robust; for example, they may depend upon edge effects or artificial boundary conditions. Here, we present a unified method that enables us to remove finiteness assumptions, such are those on datasets, market sizes and time horizons. We the apply our approach to a variety of revealed preference, matching, and exchange economy settings.

The key  to our approach is Logical Compactness, a core result from Propositional Logic. Building on Logical Compactness, in a revealed-preference setting, we reprove Reny’s [2015] infinite-data version of Afriat’s [1967] theorem and (newly) prove an infinite-data version of McFadden and Richter’s 1971, 1990] characterization of rationalizable stochastic datasets. In a matching setting, we reprove large-market existence results implied by Fleiner’s [2003] analysis, and prove both the strategy-proofnessof the man-optimal stable mechanism in infinite markets, and an infinite-market version of Nguyen and Vohra’s [2018] existence result for near-feasible stable matchings with couples. In a trading-network setting, we prove that the Hatfield et al. [2013] result on existence of Walrasian equilibria extends infinite markets. Finally, we prove that Pereyra’s [2013] existence result for dynamic two-sided matching markets extends to doubly-infinite time horizon.

Joint work with Scott Duke Kominers and Ran I. Shorrer.

June 29, LONG INFORMATION DESIGN, JÈROME RENAULT

We study zero-sum dynamic splitting games between two designers who want to influence the final action of a decision-maker. Each designer controls the public information on a private persistent state: in each period the designers can disclose information to the decision-maker about their own state. Extending tools from repeated games with incomplete information, we study the value and optimal strategies depending on the timing of game, the possible deadline and the possible restrictions on information revelation. Our analysis covers continuous unconstrained environments, the case where a subset of Blackwell experiments are is available to the designer, as well as environments in which designers can only induce finite sets of posterior beliefs. There may be no bound on the number of communication stages required at equilibrium.

Joint work with Frédéric Koessler, Marie Laclau and Tristan Tomala.

July 13, GAMES, DYNAMICS AND OPTIMIZATION, PANAYOTIS MERTIKOPOULOS

This talk aims to survey the triple-point interface between optimization, game theory and dynamical systems. In the first part of the talk, we will discuss how the ordinary differential equation (ODE) method of stochastic approximation can be used to analyze the trajectories of stochastic first-order algorithms in non-convex programs – both in terms of convergence to the problem’s critical set as well as the avoidance of non-minimizing critical manifolds. Subsequently, we will examine the behaviors of these algorithms in a game-theoretic context involving several optimizing agents, each with their individual objective. In this multi-agent setting, the situation is considerably more involved. On the one hand, if the game being played satisfies a monotonicity condition known as “diagonal strict convexity” (Rosen, Econometrica, 1965), the induced sequence of play converges to Nash equilibrium with probability 1. On the other hand, in non-monotone games, the sequence of play may converge with arbitrarily high probability to spurious attractors that are in no way unilaterally stable (or even stationary). “Traps” of this type can arise even in simple two-player zero-sum games with one-dimensional action sets and polynomial payoffs, a fact which highlights the fundamental gap between min-min and min-max problems. 

We will discuss both classical and recent results – but not the proofs thereof.

July 27, TOO MUCH OF A GOOD THING? THE DYNAMICS OF TRUST AND LOYALTY, JOHANNES HÖRNER

We consider a repeated game between a seller and a buyer, in which due to private information and lack of flexible transfers, cooperation cannot be sustained efficiently. At random times, the buyer has a need arising for a good. When it arises, the buyer buys either from the seller (at an exogenous price) or takes an outside option. The value of the outside option is i.i.d. over time. We consider three informational structures, depending on whether the opportunity to trade and value of the outside option are public or private information. When the buyer goes to the seller, the seller chooses how much effort to exert. In order to incentivize effort from the seller, the buyer needs to cooperate more than he would like to, regardless of the informational structure.

August 10, ON SUSTAINABLE EQUILIBRIA, RIDA LARAKI

Following the ideas laid out in Myerson (1996), Hofbauer (2000) defined an equilibrium of a game as sustainable if it can be made the unique equilibrium of a game obtained by deleting a subset of the strategies that are inferior replies to it, and then adding others. Hofbauer also formalized Myerson’s conjecture about the relationship between the sustainability of an equilibrium and its index: for a generic class of games, an equilibrium is sustainable iff its index is +1. Von Schemde and von Stengel (2008) proved this conjecture for bimatrix games. This paper shows that the conjecture is true for all finite games. More precisely, we prove that an isolated equilibrium of a given game has index +1 if and only if it can be made unique in a larger game obtained by adding finitely many strategies that are inferior replies to the equilibrium.

Joint work with Srihari Govindan and Lucas Pahl.

August 24, COALITION-PROOF RISK SHARING UNDER FRICTIONS, GEORGE J. MAILATH

We analyze efficient risk-sharing arrangements when coalitions may deviate. Coalitions form to insure against idiosyncratic income risk. Self-enforcing contracts for both the original coalition and any deviating coalition rely on a belief in future cooperation, and we treat the contracting conditions of original and deviating coalitions symmetrically. We show that better belief coordination (higher social capital) tightens incentive constraints since it facilitates both the formation of the original as well as a deviating coalition. As a consequence, the payoff of successfully formed coalitions might be declining in the degree of belief coordination and equilibrium allocations might feature resource burning or utility burning.

Joint work with Harold L. Cole, Dirk Krueger and Yena Park.

September 7,  A SYNTHESIS OF BEHAVIOURAL AND MAINSTREAM ECONOMICS, ROBERT J. AUMANN

Mainstream economic theory is based on the rationality assumption: that people act as best they can to promote their interests. In contrast, behavioural economics holds that people act by behavioural rules of thumb, often with poor results. We propose a synthesis according to which people indeed act by rules, which usually work well, but may work poorly in exceptional or contrived scenarios. The reason is that like physical features, behavioural rules are the product of evolutionary processes; and evolution works on the usual, the common — not the exception, not the contrived scenario.

September 21,  MAKING DECISIONS UNDER MODEL MISSPECIFICATION, MASSIMO MARINACCI

We propose a decision criterion for decision problems under model misspecification.

Joint work with Simone Cerreia-Vioglio, Fabio Maccheroni and Lars Peter Hansen

October 5, CHOOSING A PROJECT UNDER PARTIAL TRUTH, ERAN SHMAYA

A principal has to choose an action from a set of available actions, which is known to an agent. The agent can propose a set of actions to the principal to choose from. The agent can only propose available actions, but he might hide some of them from the principal. The principal can pick one of the actions, or reject all of them. We solve for the mechanism that minimizes the principal’s worst-case regret. 

October 19,  ABSORING GAMES WITH INCOMPLETE INFORMATION ON BOTH SIDES AND THE MERTENS CONJECTURES, BRUNO ZILIOTTO

We consider zero-sum absorbing games where the payoff depends on two fixed parameters drawn randomly at the outset of the game, one that is announced to Player 1 only, the other one that is announced to Player 2 only. We solve two long-standing open problems, that correspond to the Mertens conjectures (1986) for this model, that is:

  • the limit value exists,
  • when Player 1 knows both parameters, (incomplete information on one side), the uniform maxmin is equal to the limit value.

The proof builds on a new approximation technique for belief dynamics, that is of self-interest and extends beyond the zero-sum case.

The first half of the talk caters to a general audience, while the second half is more specialized. 

November 2,  IMPLEMENTATION VIA INFORMATION DESIGN IN BINARY-ACTION SUPERMODULAR GAMES, STEPHEN MORRIS

What outcomes can be implemented by the choice of an information structure in binary-action supermodular games? An outcome is partially implementable if it satisfies obedience (Bergemann and Morris (2016)). We characterize when an outcome is smallest equilibrium implementable (induced by the smallest equilibrium) and fully implementable (induced by all equilibria). Smallest equilibrium implementation requires a stronger sequential obedience condition: there is a stochastic ordering of players under which players are prepared to switch to the high action even if they think only those before them will switch. Full implementation requires sequential obedience in both directions. Our characterization of smallest equilibrium implementation can be used to solve the information design problem with adversarial equilibrium selection.

Joint work with Daisuke Oyama and Satoru Takahashi

November 9,  EQUILIBRIUM COMPUTATION AND THE FOUNDATION OF DEEP LEARNING, COSTIS DASKALAKIS

Deep Learning has recently yielded important advances in single-agent learning challenges, much of that progress being fueled by the empirical success of gradient descent and its variants in computing local optima of non-convex optimization problems. In multi-agent learning applications, the role of single-objective optimization is played by equilibrium computation, yet our understanding of its complexity in settings that are relevant for Deep Learning remains sparse. In this talk we focus on min-max optimization of nonconvex-nonconcave objectives, which has found applications in GANs, and other adversarial learning problems. Here, not only are there no known gradient-descent based methods converging to even local and approximate min-max equilibria, but the computational complexity of identifying them remains poorly understood. We show that finding approximate local min-max equilibria of Lipschitz and smooth objectives requires a number of queries to the function and its gradient that is exponential in the relevant parameters, in sharp contrast to the polynomial number of queries required to find approximate local minima of non-convex objectives. Our oracle lower bound is a byproduct of a complexity-theoretic result showing that finding approximate local min-max equilibria is computationally equivalent to finding Brouwer fixed points, and Nash equilibria in non zero-sum games, and thus PPAD-complete. Minimal complexity theory knowledge will be assumed in the talk.

 Joint work with Stratis Skoulakis and Manolis Zampetakis

November 2,  IMPLEMENTATION VIA INFORMATION DESIGN IN BINARY-ACTION SUPERMODULAR GAMES, STEPHEN MORRIS

What outcomes can be implemented by the choice of an information structure in binary-action supermodular games? An outcome is partially implementable if it satisfies obedience (Bergemann and Morris (2016)). We characterize when an outcome is smallest equilibrium implementable (induced by the smallest equilibrium) and fully implementable (induced by all equilibria). Smallest equilibrium implementation requires a stronger sequential obedience condition: there is a stochastic ordering of players under which players are prepared to switch to the high action even if they think only those before them will switch. Full implementation requires sequential obedience in both directions. Our characterization of smallest equilibrium implementation can be used to solve the information design problem with adversarial equilibrium selection.

Joint work with Daisuke Oyama and Satoru Takahashi

November 16,  CHARGES AND BETS: A GENERAL CHARACTERIZATION OF COMMON PRIORS, MIKLOS PINTER

The seminal no betting theorem on the equivalence of common priors and absence of agreeable bets obtains only over compact state spaces. We show here that this equivalence can be generalised to any infinite space if we expand the set of priors to include probability charges as priors. Going beyond the strict prior/no common prior dichotomy, we further uncover a fine-grained decomposition of the space of type spaces into continuum many subclasses in each of which an epistemic condition approximating common priors is equivalent to a behavioural condition limiting acceptable bets. Several additional concepts relating to approximations of common priors and type spaces admitting common priors are studied, elucidating more aspects of the structure of the class of type spaces.

 Joint work with Ziv Hellman

 

 

November 30, Junior talk: GLOBAL GAMES ON SOCIAL NETWORKS OF INFORMATION EXCHANGE, PRZEMYSLAW SIEMASZKO 

In this paper we propose a model of a global game on a social network of information exchange. The aim is to examine how information structure and the network topology influence the decision of players who can choose to participate in a collective action. We prove that the game has a unique equilibrium and show the conditions for uniqueness in a static network setting. We provide comparative statics to analyse the effect of changes in parameters of the model. We find how trust in a player’s prior compared to information received from others influences the equilibrium, and show mechanisms for players’ willingness to share their personal views. Later on, we extend the model by introducing a network formation game and analyse it’s equilibria. Finally, we provide a simulation to illustrate the evolution of social networks under proposed conditions and decisions taken by players.

November 30,  REPUTATION BUILDING UNDER OBSERVATIONAL LEARNING, HARRY PEI

I study a social learning model where a sequence of myopic players observe their predecessors’ actions as well as some private signals, and then forecast the behavior of a strategic long-run player. A sequence of buyers interact with a patient seller, who is either a strategic type or a commitment type that plays the optimal commitment action in every period. When each buyer observes all previous buyers’ actions and a bounded subset of the seller’s past actions, there exist equilibria in which the patient seller receives his minmax payoff since the speed of learning goes to zero as the seller becomes patient. When each buyer observes all previous buyers’ actions and an unboundedly informative private signal about the seller’s current-period action, the speed of learning is bounded away from zero and a patient seller receives at least his optimal commitment payoff in all equilibria.