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 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.
December 14, SUNSPOT EQUILIBRIUM IN ABSORBING GAMES, ORIN MUNK
Quitting games are stochastic games in which every player has two actions, Continue and Quit. The game terminates as soon as at least one player quits, and the terminal payoff depends on the set of players who quit at the termination stage. If no player ever quits, the payoff is 0 to all players. General quitting games are quitting games in which the players have more than a single continue action, and the terminal payoff depends both on the set of players who quit at the terminal stage, as well as on the continue actions chosen by the other players.
Solan and Solan (2020) proved that every quitting game admits a sunspot uniform epsilon-equilibrium, and Solan and Solan (2019) proved the same result for general quitting games in which the terminal payoff is always positive. We extend the result of Solan and Solan (2019) to the so called L-shaped games. These are quitting games in which two players have two continue actions, all other players have a single continue action, and among the four action profiles in which all players choose continue actions, one is terminating. The proof requires a new technique, that involves the definition of a continuous function whose range is the set of games that approximate the original game.
December 14, ANALOGY-BASED EXPECTATION EQUILIBRIUM AND RELATED CONCEPTS: THEORY, APPLICATIONS, AND BEYOND , PHILIPPE JEHIEL
In this survey, I provide a unified definition of analogy-based expectation equilibrium (ABEE) for strategic environments involving multiple stages and private information. I discuss various alternative interpretations of the concept as well as how to use ABEE in practice. I review a variety of applications including two new ones related to speculative trading and personnel economics. I then discuss a number of alternative equilibrium concepts emphasizing the links and differences with ABEE. Finally, I discuss possible next steps in particular related to the endogenization of analogy partitions.
December 28, OPTIMAL PERSUASION VIA BI-POOLING, YAKOV BABICHENKO
The canonical Bayesian persuasion setting studies a model where an informed agent, the Sender, can partially share his information with an uninformed agent, the Receiver. The Receiver’s utility is a function of the state of nature and the Receiver’s action while the Sender’s is only a function of the Receiver’s action. The classical results characterize the Sender’s optimal information disclosure policy whenever the state space is finite. In this paper we study the same setting where the state space is an interval on the real line. We introduce the class of bi-pooling policies and the induced distribution over posteriors which we refer to as bi-pooling distributions. We show that this class of distributions characterizes the set of optimal distributions in the aforementioned setting. Every persuasion problem admits an optimal bi-pooling distribution as a solution. Conversely, for every bi-pooling distribution there exists a persuasion problem in which the given distribution is the unique optimal one. We leverage this result to study the structure of the price function in this setting and to identify optimal information disclosure policies.
Joint work with Itai Arieli, Rann Smorodinski and Takuro Yamashita.
January 11, PURE NASH EQUILIBRIA AND BEST-REPONSE DYNAMICS IN RANDOM GAMES, MARCO SCARSINI
In finite games mixed Nash equilibria always exist, but pure equilibria may fail to exist. To assess the relevance of this nonexistence, we consider games where the payoffs are drawn at random. In particular, we focus on games where a large number of players can each choose one of two possible strategies, and the payoffs are i.i.d. with the possibility of ties. We provide asymptotic results about the random number of pure Nash equilibria, such as fast growth and a central limit theorem, with bounds for the approximation error. Moreover, by using a new link between percolation models and game theory, we describe in detail the geometry of Nash equilibria and show that, when the probability of ties is small, a best-response dynamics reaches a Nash equilibrium with a probability that quickly approaches one as the number of players grows. We show that a multitude of phase transitions depend only on a single parameter of the model, that is, the probability of having ties.
Joint work with Ben Amiet, Andrea Collevecchio and Ziwen Zhong.
January 25, MANIPULATION-RESISTANT FALSE-NAME PROOF FACILITY LOCATION MECHANISM FOR COMPLEX GRAPHS, ILAN NEHAMA
In many real-life scenarios, a group of agents needs to agree on a common action, e.g., on a public facility location, while there is some consistency between their preferences, e.g., all preferences are derived from a common metric space. The facility location problem models such scenarios, and it is a well-studied problem in social choice. We study mechanisms for facility location on unweighted undirected graphs that are resistant to manipulations (strategy-proof, abstention-proof, and false-name-proof ) by both individuals and coalitions on one hand and anonymous and efficient (Pareto-optimal) on the other hand. We define a new family of graphs, ZV-line graphs, and show a general facility location mechanism for these graphs satisfying all these desired properties. This mechanism can also be computed in polynomial time, and it can equivalently be defined as the first Pareto-optimal location according to some predefined order. Our main result, the ZV-line graphs family and the mechanism we present for it, unifies all works in the literature of false-name-proof facility location on discrete graphs, including the preliminary (unpublished) works we are aware of. In particular, we show mechanisms for all graphs of at most five vertices, discrete trees, bicliques, and clique tree graphs. Finally, we discuss some generalizations and limitations of our result for facility location problems on other structures: Weighted graphs, large discrete cycles, infinite graphs, and for facility location problems concerning infinite societies.
This is joint work with Taiki Todo and Makoto Yokoo.
January 25, ON SOME CONTINUOUS TIME ALGORITHMS IN OPTIMIZATION AND GAME THEORY, SYLVAIN SORIN
We compare several algorithms in continuous time used in optimization and game theory.
The first three, issued from projected gradient dynamics, correspond no-regret algorithms and cover in particular “Replicator dynamics and “”Local projection dynamics”.
Then we deal with “Conditional gradient dynamics/’’“Global projection dynamics” and finally “Frank-Wolfe algorithm’’/Best reply dynamics .
February 8, GAMES WITH SWITCHING COSTS, STATIONARY VS. HISTORY INDEPENDENT STRATEGIES, YEVGENY TSODIKOVICH
We study zero-sum repeated games where the minimizing player has to pay a certain cost each time he changes his action. We show that the value of the game exists in stationary strategies, which depend solely on the previous action of the player (and not the entire history), and we provide a full characterization of the value and the optimal strategies. The strategies exhibit a robustness property and typically do not change with a small perturbation of the switching costs. We also consider a case where the player is limited to playing completely history-independent strategies. Naturally, this limitation worsens his situation. We deduce a bound on his loss in the general case as well as more precise bounds when more assumptions regarding the game are introduced.
Joint work with Xavier Venel and Anna Zseleva
February 8, SUBSTITUES, LARRY SAMUELSON
We formulate and characterize a notion of substitutes for correspondences, called unified gross substitutes. We show that a correspondence satisfying unified gross substitutes has an inverse that is increasing in the strong set order. The notion of unified gross substitutes and the inverse isotonicity result are related to and connect a number of notions in the literature. We then introduce a network problem that we refer to as the equilibrium flow problem. Several classical economic or game theoretic models, such as assignment problems, matching models, optimal transport, minimum-cost flow problems, and hedonic consumer choice models, are special cases of the equilibrium flow problem. In contrast to many implementations of these special cases, the network flow problem does not require quasilinear (or transferable) utility. We establish conditions for the existence of equilibrium prices in the network flow problem and show that the resulting equilibrium correspondence satisfies unified gross substitutes. Time permitting, applications will be illustrated.
February 22, A FINITE CHARACTERIZATION OF PERFECT EQUILIBRIUM, LUCAS PAHL
Govindan and Klumpp (2002) provided a characterization of perfect equilibria using finite Lexicographic Probability Systems (LPSs). Their characterization was essentially finite in that they showed that there exists a finite bound on the number of levels in the LPS, but they did not compute it explicitly. In this note, we draw on two recent developments in Real Algebraic Geometry to compute this bound.
Joint work with Ivonne Callejas and Hari Govindan
February 22, ROBUST NAIVE LEARNING IN SOCIAL NETWORKS, RON PERETZ
We study a model of opinion exchange in social networks where a state of the world is realized and every agent receives a zero-mean noisy signal of the realized state. It is known from Golub and Jackson (2010) that under the DeGroot (1974) dynamics agents reach a consensus that is close to the state of the world when the network is large. The DeGroot dynamics, however, is highly non-robust and the presence of a single `bot’ that does not adhere to the updating rule, can sway the public consensus to any other value.
We introduce a variant of the DeGroot dynamics which we call ε-DeGroot. The ε-DeGroot dynamics approximates the standard DeGroot dynamics and like the DeGroot dynamics it is Markovian and stationary. We show that in contrast to the standard DeGroot dynamics, the ε-DeGroot dynamics is highly robust both to the presence of bots and to certain types of misspecifications.
Joint work with Gideon Amir, Itai Arieli, and Galit Ashkenazi-Golan.
March 8, STABLE MATCHING GAMES, FELIPE GARRIDO LUCERO
Gale and Shapley (1962) introduced a matching problem between two sets of agents M and W (men/women, students/universities, doctors/hospitals), who need to be paired by taking into account that each agent on one side of the market has an exogenous preference order over the agents of the other side. They defined a matching as stable if no unmatched pair can both improve their payoffs by breaking their couples and forming a new one. They proved the existence of a stable matching using a deferred-acceptance algorithm. Shapley and Shubik (1971) extended the model by allowing monetary transfers (buyers/sellers, workers/firms). Our article offers a further extension by assuming that matched couples obtain their payoff endogenously as the outcome of a strategic-form game they have to play. A matching, together with a strategy profile, is externally stable if no unmatched pair can break their couples, form a new one and play a strategy profile in their game such that both of them improve their payoffs. It is internally stable if no agent, by individually changing its strategy inside its couple, can increase its payoff without breaking the external stability of its couple (e.g. the partner’s payoff decreases below its current market outside option and so credibly prefers to form another couple or become single). By combining a deferred acceptance algorithm with a new algorithm, we prove the existence of an externally and internally stable matching in a large class of problems including zero-sum games, strictly competitive games, potential games and infinitely repeated games. We also discuss other stability notions, the lattice structure, and prove that our main model encompasses and refines matching with monetary transfers (Shapley and Shubik 1971, Kelso and Crawford 1982, Demange and Gale 1985, Demange, Gale and Sotomayor 1986) as well as matching with contracts (Blair 1988, Hatfield and Milgrom 2005).
Joint work with Rida Laraki
March 8, EQUILIBRIA IN REPEATED GAMES WITH COUNTABLY MANY PLAYERS AND TAIL-MEASURABLE PAYOFFS, EILON SOLAN
Nash equilibrium is the most prevalent solution concept in game theory to date. When the set of players is finite, the action sets are compact, and the stage payoff function is bounded and continuous, it exists in one-shot games as well as in repeated games for certain classes of total payoff functions. We prove that an epsilon-equilibrium exists when the set of players is countable, the sets of actions are finite, and the payoff function is bounded and tail-measurable. To this end we combine techniques from stochastic games with techniques from alternating-move games with Borel measurable payoffs.
Joint work with Galit Ashkenazi-Golan, Janos Flesch and Arkadi Predtetchinski.
March 22, TIME CONSISTENT EQUILIBRIA IN DYNAMIC MODELS WITH RECURSIVE PAYOFFS AND BEHAVIORAL DISCOUNTING, LUKASZ WOZNY
We prove existence of time consistent equilibria in a class of dynamic models with recursive payoffs and generalized discounting involving both behavioral and norma-tive applications. Our generalized Bellman equation method identifies and separates both: recursive and strategic aspects of the equilibrium problem and allows to deter-mine the sufficient assumptions on preferences and stochastic transition to establish existence. In particular we show existence of minimal state space stationary Markov equilibrium (a time-consistent solution) in a deterministic model of consumption-saving with beta-delta discounting and its generalized versions involving magnitude effects, non-additive payoffs, semi-hyperbolic or hyperbolic discounting (over pos-sibly unbounded state and unbounded above reward space). We also provide an equilibrium approximation method for a hyperbolic discounting model.
Joint work with Lukasz Balbus and Kevin Reffett
April 5, LEARNING WITH LIMITED MEMORY: BAYESIANISM VS. HEURISTICS, KALYAN CHATTERJEE
Bayesian analysis is considered the optimal way of processing information. However, it often leads to problems for decision-makers with constrained cognitive capacity. Modelling such constrained capacity by finite automata, we answer two questions in the context of Wald’s (1974) sequential analysis, namely in what environments is optimal Bayesian analysis possible even with constraints; also, when it is not possible what simplifications in the analysis enable us to obtain a satisfactory outcome. We identify two features of the simplified analysis: information stickiness (ignoring information) and rule stickiness (ignoring small differences in the environment)..
Joint work with Tai-Wei Hu
April 19, A FOUNDATION FOR EXPECTED UTILITY IN DECISION PROBLEMS AND GAMES, ANDRÉS PEREA
In a decision problem or game we typically fix the person’s utilities but not his beliefs. What, then, do these utilities represent? To explore this question we assume, like Gilboa and Schmeidler (2003), that the decision maker holds a conditional preference relation — a mapping that assigns to every possible probabilistic belief a preference relation over his choices. We impose a list of axioms on such conditional preference relations, and show that it singles out those conditional preference relations that admit an expected utility representation. The key axiom is the existence of coherent uniform preference increases. It states that for every choice there must be an alternative conditional preference relation such that (a) the alternative conditional preference relation uniformly increases the preference intensity for the associated choice by a fixed degree, and (b) at every belief, and between any two choices, the system of uniform preference increases induces a preference intensity that never contradicts the original conditional preference relation. We also present a procedure that can be used to construct, for a given conditional preference relation satisfying the axioms, a utility function that represents it. If there are no weakly dominated choices, the existence of coherent uniform preference increases can be replaced by two easily verifiable conditions: strong transitivity and the line property.
May 3, SCREENING: OPTIMAL METHODS AND ANOMALITIES, DAVID LAGZIEL
The talk will consist of three parts, each based on a different research paper, all concern a decision maker who uses noisy unbiased assessments to screen elements from a general set:
The first part, based on “A Bias of Screening” (AER: Insights, 2019), shows that stricter screening not only reduces the number of accepted elements, but possibly reduces their average expected value.
The second part, based on ”Screening Dominance: A Comparison of Noisy Signals” (forthcoming AEJ: Microeconomics) shows that one can actually generate `lucky coins’ as additional binary noise can strictly improve a screening process. We also provide a comparison of different noisy signals under threshold (screening) strategies and optimal ones, and depict several partial characterizations of cases in which one noise is preferable over another.
The third and last part, based on a working paper entitled ”Sequential Screening”, would try to answer the question of why we use sequential screening. In addition, we would show that one-stage screening is possibly preferable to multi-stage screening.
Joint work with Ehud Lehrer.
May 17, BELIEFS, PLANS AND PERCEIVED INTENTIONS IN DYNAMIC GAMES, PIERPAOLO BATTIGALLI
We adopt the epistemic framework of Battigalli and Siniscalchi (J. Econ. Theory 88:188-230, 1999) to model the distinction between a player’s behavior at each node, which is part of the external state, and his plan, which is described by his beliefs about his own behavior. This allows us to distinguish between intentional and unintentional behavior, and to explicitly model how players revise their beliefs about the intentions of others upon observing their actions. Rational players plan optimally and their behavior is consistent with their plans. We illustrate our approach with detailed examples and some results. We prove that optimal planning, belief in continuation consistency and common full belief in both imply the backward induction strategies and beliefs in games with perfect information and no relevant ties. More generally, we present within our framework relevant epistemic assumptions about backward and forward-induction reasoning, and relate them to similar ones studied in the previous literature.
May 31, RANDOMM PERFECT INFORMATION GAMES, ARKADI PREDTETCHINSKI
The paper proposes a natural measure space of zero-sum perfect information games with upper semicontinuous payoffs. Each game is specified by the game tree, and by the assignment of the active player and of the capacity to each node of the tree. The payoff in a game is defined as the infimum of the capacity over the nodes that have been visited during the play. The active player, the number of children, and the capacity are drawn from a given joint distribution independently across the nodes. We characterize the cumulative distribution function of the value v using the fixed points of the so-called value generating function. The characterization leads to a necessary and sufficient condition for the event v≥k to occur with positive probability. We also study probabilistic properties of the set of Player I’s k-optimal strategies and the corresponding plays.
Joint work with János Flesch and Ville Suomala
June 14, BLACKWELL EQUILIBRIUM, SAMBUDDHA GHOSH
We apply Blackwell optimality to repeated games. A Blackwell (subgameperfect, sequential, etc.) equilibrium is an equilibrium whose strategy pro le is sequentially rational for all high enough discount factors simultaneously. The bite of this requirement depends on the monitoring structure. Under perfect monitoring, a folk theorem holds relative to a new notion of minmax payoff. Under imperfect monitoring, absent public randomization, any perfect public equilibrium must (generically) involve pure action pro files or stage-game Nash equilibria only. Under private monitoring, in certain classes of games, including the prisoner’s dilemma, the stage-game Nash equilibrium must be played in every round.
Joint work with Costas Cavounidis
September 6, HIT ME, BABY, ONE MORE TIME, STEPHAN JAGAU
Transfinite elimination of non-best replies in some infinite games raises the question whether common belief in rationality generally requires higher depths of strategic reasoning than up to k-fold belief in rationality for all finite k. Such a discrepancy would challenge the practice of letting infinite strategy sets stand in for arbitrarily large finite strategy sets in many game-theoretic applications. I prove that there is no such discrepancy. Common belief in rationality is always equal to up to k-fold belief in rationality for all finite k, independent of whether a game is finite or infinite. In particular, distinct transfinite steps of elimination of non-best replies cannot be associated with distinct doxastic states of players.
September 20, THE TREE MODEL: LEARNING, STOCHASTIC DOMINANCE AND SUBJECTIVE OPTIMAL EVALUATION, TAO WANG
An unknown state of nature determines the payoff of a decision maker (DM). The DM has a subjective prior belief about the state. Each period, the DM observes a random outcome, correlated to the true state. The outcome is binary, either up or down. Any history of outcomes thus partially reveals the identity of the realized state and thereby affects the payoffs. Different prior beliefs have different effects on payoffs. We compare between different prior beliefs and consider several well-known stochastic dominance relations among them, including first order stochastic dominance, (reverse) hazard rate dominance, and likelihood ratio dominance. We examine the implications of these stochastic dominance relations on the subjective valuation of options of a few types, including European and American options.
October 4, WHAT IS COMMON TO COMMON KNOWLEDGE AND COMMON PRIORS?, DOV SAMET
The answer is: common priors for probabilistic beliefs are what common knowledge is for knowledge. To show this we draw an analogy between probabilistic belief type spaces and knowledge type spaces. For knowledge type spaces there exists a well known knowledge type function which is the common knowledge type function. We define, analogously, a common belief type function for probabilistic belief type spaces, using Blackwell’s notion of informativeness, and prove its existence and uniqueness. This provides us with a decomposition theorem for probabilistic belief type spaces which is analogous to the decomposition of knowledge spaces defined by the meet. The construction of the meet by applying iteratively accessibility relations is mimicked in the probabilistic case by iterating the probabilistic type functions. The analysis of these iterations requires tools of ergodic theory.
October 18, BEST-RESPONSE EQUILIBRIUM: AN EQUILIBRIUM IS FINITELY ADDITIVE MIXED STRATEGIES, IGAL MILCHTAICH
A generalization of mixed strategy equilibrium is proposed, where mixed strategies need only be finitely additive and payoff functions are not required to be integrable or bounded. It is based on an extension of the idea that an equilibrium strategy is supported in the player’s set of best-response actions, but is applicable also when no best-response actions exist. The proposed notion of best-response equilibrium yields simple, natural mixed equilibria in a number of well-known games where other kinds of mixed equilibrium are complicated or not compelling or they do not exist.
November 1, A NEW CHARACTERIZAION OF REGULAR EQUILIRBIA, DRIEZ VERMEULEN
We show that an equilibrium point of a normal form game is regular in the sense of Harsanyi (1973) if and only if the equilibrium correspondence near to the equilibrium point is the graph of a smooth function.
November 15, ROBUST OPTIMIZATION, CORRELATED EQUILIBRIUM AND EQUILIBRIUM, ABRAHAM NEYMAN
It is well documented that economic agents’ behavior is often incompatible with exact optimization. We believe that economic theory has overemphasized ex- act optimization, especially its implications for economic agents’ behavior. The reason is that in most real-life applications, there is some imprecision in the specification of the model, in particular in the specification of the preference over the possible outcomes. Therefore, a rational economic agent may, or even should, forgo exact optimization in a single economic model with well-defined parameters, and prefer behavior that is approximately optimal in a whole class of economic models whose differences reflect imprecision in specifying the parameters of the model. Moreover, it is desirable that the economic agent’s behavior exhibits gradual change as the model changes. We call this type of behavior robust optimization.
It is proved that: (A) a finite Markov decision process (1) admits a robust optimization when the parameters range over all valuation { linear utilities (over streams of payoffs) that satisfies the time value of money principle, and (2) does not admit robust optimization if the time value of money is replaced by monotonicity and the weak positive time preference; (B) strategic one shot game admit robust correlated equilibrium; and (C) n-person stochastic games and two-person repeated games with incomplete information on one side admit robust correlated equilibrium, when the payoffs are valuations.
December 13, INFORMATION DESIGN IN LARGE GAMES, TRISTAN TOMALA
We define the notion of Bayes Correlated Wardrop Equilibrium for nonatomic games with anonymous players and incomplete information. Bayes Correlated Wardrop Equilibria describe the set of equilibrium outcomes when a mediator, such as a traffic information system, provides information to the players. We relate this notion to Bayes Correlated Equilibria of games with finite number of players as this number tends to infinity. Then, we provide conditions—existence of a convex potential and complete information—under which mediation does not improve equilibrium outcomes. We then study optimal information design and full implementation.
Joint work with F. Koessler and M. Scarsini
January 10, PRIVATE PRIVATE INFORMATION, OMER TAMUZ
In a private private information structure, agents’ signals contain no information about the signals of their peers. We study how informative such structures can be, and characterize those that are on the Pareto frontier, in the sense that it is impossible to give more information to any agent without violating privacy. In our main application, we show how to optimally disclose information about an unknown state under the constraint of not revealing anything about a correlated variable that contains sensitive information
Joint work with Kevin He and Fedor Sandomirskiy
January 24, SOLID OUTCOMES IN FINITE GAMES, KLAUS RITZBERGER
A new solution concept for finite games is presented and analyzed. It is defined terms of outcomes—probability distributions over the plays of the game. Unlike strategy profiles, outcomes are empirically observable. Solid outcomes are robust to the representation of the game, whether in normal or extensive form, and are consistent with backwards induction. They are also unaffected by the removal or addition of dominated strategies. Solid outcomes exist for a generic class of extensive-form games. Solid outcomes have support in minimal “game blocks”, a class of product sets of pure-strategy profiles that are robust set-valued candidates for conventions and social norms in recurrent population play of the game.
Joint work with Jörgen Weibull and Peter Wikmanz
February 7, BEST-RESPONSE REASONING LEADS TO CRITICAL-MASS EQUILIBRIA, EHUD KALAI
Best-response reasoning leads the players of an n-person strategic game to one of n possible critical-mass equilibrium concepts, C 1 , …, Cn, with C 1 =dominant strategy equilibrium and Cn=Nash equilibrium. These concepts were used earlier by Eliaz (2002) and others in studies of robust implementation , large games, and equilibrium viability. For increasing m, the justification of Cm equilibrium requires a larger critical mass of players that adhere to their equilibrium strategies. The use of stag hunt games in the proof of the main theorem provides new insights into the age-old topic of stability of social contracts.
Joint work with Adam Tauman Kalai
February 21, BACK TO BACKWARD INDUCTION, ROBERT J. AUMANN
The Backward Induction (BI) algorithm for Perfect Information (PI) games was formulated well over a hundred years ago, but only toward the end of the last century were its conceptual foundations explored. Common knowlege of rationality (CKR) played a central role in those explorations; specifically, it was shown that in PI games, CKR entails the BI outcome (CKR=>BI). Yet that result is not entirely straightforward: it makes essential use of the idea of “counterfactual conditional” — what a player would do if one of his nodes were reached, even though he knows that it will not be reached — an idea not without its conceptual difficulties. In the seminar talk, we will formulate and prove CKR=>BI in an alternative, entirely straightforward manner, using only the ordinary material conditional of mathematics (p=>q iff q or not p). Time permitting, we’ll also discuss other variations on CKR=>BI, none of which are entirely straightforward.
March 7, STRATEGIC TYPE SPACES, RAFAEL VEIEL
For a fixed finite game with incomplete information and solution concept we define strategic type spaces (STS) as representations of players’ strategically relevant information. We construct the set of all hierarchies of best-replies given by best replies to beliefs on other players’ best replies and show that they form a universal STS that is minimal among all STS. Unlike beliefs-hierarchies, we show that best-reply hierarchies are generated as the orbit of an operator on a finite space.
Joint with Olivier Gosssner
March 7, RATIONALIZABLE DISTRIBUTIONS IN GAMES WITH INCOMPLETE INFORMATION, OLIVIER GOSSNER
We characterize rationalizable strategies that are robust to incomplete information in terms of an optimization problem over transition probabilities on a finite state space automaton subject to a finite system of obedience constraints. We then obtain an algebraic characterization of robust strategies in general games.
Joint with Rafael Veiel.
April 4, EFFICIENT MATCHING IN THE SCHOOL CHOICE PROBLEM, PHILIP J. RENY
Stable matchings in school choice needn’t be Pareto efficient and can leave thousands of students worse off than necessary. Call a matching μ priority-neutral if no matching can make any student whose priority is violated by μ better off without violating the priority of some student who is made worse off. Call a matching priority-efficient if it is priority-neutral and Pareto efficient. We show that there is a unique priority-efficient matching and that it dominates every priority-neutral matching and every stable matching. Moreover, truth-telling is a maxmin optimal strategy for every student in the mechanism that selects the priority-efficient matching.
April 18, REPEATED GAMES WITH MANY PLAYERS, TAKUO SUGAYA
Motivated by the problem of sustaining cooperation in large communities with limited information, we analyze sequences of repeated games where the population size N, the discount factor delta, and the monitoring structure (with channel capacity denoted by C) vary together. We show that if the limit of (1 – delta)N/C is infinity, then all Nash equilibrium payoffs are consistent with approximately myopic play. A folk theorem under a novel identifiability condition provides a near converse. For example, if the limit of (1 – delta)N log (N) /C is 0, then a folk theorem holds under random auditing, where each player’s action is monitored with the same probability in every period. If attention is restricted to linear equilibria (a generalization of strongly symmetric equilibria), cooperation is possible only under much more severe parameter restrictions. Methodologically, we develop connections between repeated games and information theory.
Joint work with Alexander Wolitzky
May 2, GAME THEORETICAL GAPS FOR PRACTICAL MULTI PARTY DECISION MAKING, SEGEV WASSERKRUG
Many real-world decisions in business settings such as business networks, cloud computing and cybersecurity involve situations in which there are multiple parties involved, each attempting to optimize their own objectives, and in which the actions of each party could influence the objectives of the other parties. Currently however, even when advanced mathematical models, such as optimization, are used to make decisions in such settings, typically each party assumes that the environment is stationary in the sense that the impact of the decisions of each party on the other stakeholders is ignored.
Game theory is the scientific basis intended to enable making decisions in such settings. However, game theoretic solution concepts often assume unlimited computational resources (unbounded rationality) and unrealistic assumptions made on the common knowledge of all participants, such as full common knowledge in full information games or common knowledge priors in Bayesian games. In addition, solution concepts such as equilibria may be difficult to justify and apply in real world settings due, for example, to the existence of multiple equilibria. Algorithmic game theory tries to overcome some of the computational limitations of game theory by combining both game theoretical and computational complexity considerations. However, its applications to scenarios such as the ones mentioned above has been very limited. Finally, multi agent reinforcement learning (MARL) can, in principle, be applied to many use cases. However, it lacks a strong theoretical basis providing theoretical convergence and performance results, making it difficult to guarantee its performance in practice.
In this talk, I will give examples of such business scenarios where ignoring the multi-party objectives can lead to poor results, outline some of the gaps in the aforementioned fields, and discuss some of our current research directions in addressing these. The session will also include some time for discussion and brainstorming on how to make game theory more applicable for such settings.
May 30, IDENTIFYING THE DEVIATOR, EILON SOLAN
A group of players are supposed to follow a prescribed profile of strategies. If they follow this profile, they will reach a given target set. We show that if the target is not reached because some player deviates, then an outside observer can identify the deviator. We also construct identification methods in two nontrivial cases.
Joint work with Noga Alon, Benjamin Gunby, Xiaoyu He, and Eran Shmaya
Sept 5, A POPULATION’S FEASIBLE POSTERIOR BELIEFS, YAKOV BABICHENKO
We consider a population of Bayesian agents who share a common prior over some finite state space and each agent is exposed to some information about the state. We ask which distributions over empirical distributions of posteriors beliefs in the population are feasible. We provide a necessary and sufficient condition for feasibility. We apply this result in several domains. First, we study the problem of maximizing the polarization of beliefs in a population. Second, we provide a characterization of the feasible agent-symmetric product distributions of posteriors. Finally, we study an instance of a private Bayesian persuasion problem and provide a clean formula for the sender’s optimal value.
Joint work with Itai Arieli
Sept 5, A POPULATION’S FEASIBLE POSTERIOR BELIEFS, YAKOV BABICHENKO
We consider a population of Bayesian agents who share a common prior over some finite state space and each agent is exposed to some information about the state. We ask which distributions over empirical distributions of posteriors beliefs in the population are feasible. We provide a necessary and sufficient condition for feasibility. We apply this result in several domains. First, we study the problem of maximizing the polarization of beliefs in a population. Second, we provide a characterization of the feasible agent-symmetric product distributions of posteriors. Finally, we study an instance of a private Bayesian persuasion problem and provide a clean formula for the sender’s optimal value.
Joint work with Itai Arieli
Sep 19, LEARNING EFFICIENCY OF MULTI-AGENT INFORMATION STRUCTURES, Mira Frick
We study which multi-agent information structures are more effective at eliminating both first-order and higher-order uncertainty, and hence at facilitating efficient play in incomplete-information coordination games. We consider a learning setting à la Cripps, Ely, Mailath, and Samuelson (2008) where players have access to many private signal draws from an information structure. First, we characterize the rate at which players achieve approximate common knowledge of the state, based on a simple learning efficiency index. Notably, this coincides with the rate at which players’ first-order uncertainty vanishes, as higher-order uncertainty becomes negligible relative to first-order uncertainty after enough signal draws. Based on this, we show that information structures with higher learning efficiency induce more efficient equilibrium outcomes in coordination games that are played after sufficiently many signal draws. We highlight some robust implications for information design in games played in data-rich environments.
Joint work with Ryota Iijima and Yuhta Ishii