Titles and abstracts 2022-2023
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 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
OCT 3, ZERO-SUM GAMES AND LINEAR PROGRAMMING, BERNHARD VON STENGEL
LP duality (the strong duality theorem of linear programming) and the minimax theorem for zero-sum games are considered "equivalent" in the sense that one can easily be proved from the other. However, the classic proof by Dantzig (1951) of LP duality from the minimax theorem is flawed. It needs an additional assumption of strict complementarity. We show that this assumption amounts to assuming the Lemma of Farkas, which proves LP duality directly. We fix this with a new, different proof via the Theorems of Gordan (1873) and Tucker (1956), distilled from Adler (2013). We also describe some lesser known beautiful existing direct proofs of the minimax theorem and the Lemma of Farkas. This is a mostly expository talk on a rather general but fundamental topic and is not too technical.
OCT 17, STRUCTURE OF THE SETS OF NASH EQUILIBRIA OF FINITE GAMES : APPLICATIONS TO THE COMPLEXITY OF SOME DECISION PROBLEMS IN GAME-THEORY, GUILLAUME VIGERAL
The set of Nash equilibrium payoffs of a one-shot finite game is always non empty, compact and semialgebraic. For 3 players or more, the reverse also holds : given E a subset of R^N that is non empty, compact and semialgebraic, one constructs a finite N player game such that E is its set of equilibrium payoffs. Related results also holds when one consider only games with integral payoffs, or when the focus is on equilibria instead of equilibrium payoffs. We apply this to understand the complexity class of some natural decision problems on finite games.
NOV 7, STATISTICAL FOUNDATIONS OF COMMON KNOWLEDGE, EDUARDO FAIGOLD
Common knowledge plays a central role in the analysis of strategic behavior. But when, and how, does common knowledge obtain? To answer these questions, we follow Cripps, Ely, Mailath and Samuelson (ECMA 2008) and seek a Bayesian learning foundation of common knowledge. In a general multi-agent setting with private signals, we find conditions for ``common learning'' that allow for rich signal spaces and unbounded log-likelihood ratios, extending their result beyond the finite signal case.
Our main result asserts that the agents commonly learn the true state of the world whenever the joint distribution over signals satisfies the following three conditions: (i) the marginal distribution over each agent's signals identifies the state, (ii) restricted to each common knowledge component of the signal space the Markov chains of iterated expected beliefs are geometrically ergodic, and (iii) these chains admit Lyapunov functions with sublevel sets that are arbitrarily close to common knowledge (in the sense of Monderer and Samet (GEB 1989)). Conditions (ii) and (iii) are automatically satisfied in the finite signal case, and are shown to hold whenever the signal spaces are compact metrizable and the joint distribution over signals (under the true state) has a positive continuous density with respect to a sigma-finite product measure. A leading example with unbounded support that satisfies our general conditions is the case when the agents' signals are arbitrarily correlated Gaussian distributions and the agents are learning about a common location parameter. Finally, we show that in the countably infinite signal example of Cripps, Ely, Mailath and Samuelson (2008) where common learning fails, the Markov chains of iterated expected beliefs are geometrically ergodic but the sublevel sets of any Lyapunov function must be bounded away from common knowledge.
Joint work with Omer Tamuz
NOV 21, Junior talk: ADDITIVE CONTEXT-DEPENDENT PREFERENCES, STEPHAN JAGAU
“Money equals utility” is a much criticized ‘axiom’ that is central across a vast range of economic experiments and theory. Subjecting this ‘axiom’ to experimental testing requires an empirically tractable theory of context-dependent preferences. This paper presents novel behavioral foundations for additive context-dependent preferences and state-dependent expected utility. Crucially, these behavioral foundations do not require empirically implausible comparisons of alternatives across different states. Moreover, they can handle any state-dependent, multi-alternative decision problem. In particular, no diversity-type assumptions are used. A central application is to direct utility measurement in games, enabling a causal understanding of how e.g. risk attitudes and other-regarding concerns affect strategic choice.
NOV 21, AGREEMENT AND DISAGREEMENT IN A NON-CLASSICAL WORLD, ADAM BRANDENBURGER
The Agreement Theorem (Aumann, 1976) states that if two Bayesian agents start with a common prior, then they cannot have common knowledge that they hold different posterior probabilities of some underlying event of interest. In short, the two agents cannot “agree to disagree.” This result applies in the classical domain where classical probability theory applies. But in non-classical domains (such as the quantum world), classical probability theory does not apply, and so we cannot assume that the same result holds when agents observe non-classical phenomena. Inspired by their use in quantum mechanics (Wigner, 1932; Dirac, 1942; Feynman, 1987; Wooters, 1987), we employ signed probability measures (“quasi-probabilities”) to investigate the epistemics of the non-classical world and ask, in particular: What conditions lead to agreement or allow for disagreement when agents may use signed probabilities?
Joint work with Patricia Contreras-Tejada, Pierfrancesco La Mura, Giannicola Scarpa, and Kai Steverson
DEC 5, SEQUENTIAL EQUILIBRIA IN A CLASS OF INFINITE EXTENSIVE FORM GAMES, MICHAEL GREINECKER
Sequential equilibrium is one of the most fundamental refinements of Nash equilibrium for games in extensive form but is only defined for finite extensive-form games and is inapplicable whenever a player can choose among a continuum of actions. We define a class of infinite extensive form games in which information behaves continuously as a function of past actions and define a natural notion of sequential equilibrium for this class. Sequential equilibria exist in this class and refine Nash equilibria. In finite extensive-form games, our definition selects the same strategy profiles as the traditional notion of a sequential equilibrium.
Joint work with Martin Meier and Konrad Podczeck.
DEC 19, ASYMPTOTIC REVENUE EQUIVALENCE OF ASYMMETRIC AUCTIONS, GADI FIBICH
A classical result in auction theory is that under quite general conditions, all symmetric auctions are revenue equivalent. More often than not, however, auctions are asymmetric. In this talk I will show that even though asymmetric auctions are not revenue equivalent, their revenue inequivalence is O(epsilon^2/n^3) small, where epsilon is the level of asymmetry, and n is the number of players.
joint work with Nir Gavish, Arieh Gavious, Aner Sela and Eilon Solan
JAN 2, OBJECTS IN REARVIEW MIRROR - INFORMATION ACQUISITION WITH PAYOFF RIVALRIES AND OBSERVATION LAGS - NICOLAS KLEIN
We analyze a dynamic investment model in which short-lived agents sequentially choose to invest in an innovation whose feasibility is uncertain. The outcome of the investment (success/failure) is observed after a fixed time period. We characterize the equilibrium and show that, unlike for the case without observation delay, the equilibrium profile is not in threshold strategies. If the prior belief is high, investment decreases monotonically as agents become more pessimistic about the feasibility of the innovation. For intermediate priors, equilibrium investment is non-monotonic. We compare the total investment obtained in this equilibrium with that which would be played under a "hidden equal sharing" mechanism.
Joint work with Chantal Marlats and Lucie Ménager
JAN 16, 2023, "CALIBEATING": BEATING FORECASTERS AT THEIR OWN GAME - SERGIU HART
In order to identify expertise, forecasters should not be tested by their calibration score, which can always be made arbitrarily small, but rather by their Brier score. The Brier score is the sum of the calibration score and the refinement score; the latter measures how good the sorting into bins with the same forecast is, and thus attests to "expertise." This raises the question of whether one can gain calibration without losing expertise, which we refer to as "calibeating." We provide an easy way to calibeat any forecast, by a deterministic online procedure. We moreover show that calibeating can be achieved by a stochastic procedure that is itself calibrated, and then extend the results to simultaneously calibeating multiple procedures, and to deterministic procedures that are continuously calibrated.
Joint work with Dean P. Foster
FEB 6, 2023, OPTIMISTIC GRADIENT DESCENT ASCENT IN BILINEAR GAMES - JÉRÔME RENAULT
We study the convergence of Optimistic Gradient Descent Ascent (OGDA) in unconstrained bilinear games. For zero-sum games, we clarify and extend earlier results by proving the exponential convergence of OGDA to a saddle-point, and provide the exact ratio of convergence as a function of the step size. Then we introduce OGDA for general-sum games, and show that in many cases, either OGDA converges to a Nash equilibrium, or the payoffs for both players converge to infinity. We also show how to increase drastically the speed of convergence of a zero-sum problem, by introducing a general-sum game using the Moore-Penrose inverse of the original payoff matrix. Hence, general-sum games can be used here to optimally improve algorithms designed for min-max problems. We finally illustrate our results on a stylized example of Generative Adversarial Network.
Joint work with Étienne de Montbrun
FEB 20, 2023, BAYESIAN EQUILIBRIUM: FROM LOCAL TO GLOBAL - YEHUDA JOHN LEVY
We study games of incomplete information in which the players observe a public signal in addition to their private information. We show that if a measurable Bayesian equilibrium exists conditional on each public signal, then a measurable Bayesian equilibrium exists for the entire game. The proof involves transitioning back-and-forth between behavioural strategies and the distributional strategies and demonstrating that appropriate measurable selection theorems apply.
MARCH 20, 2023, ENVY-DRIVEN DYNAMICS IN SINGLE-PEAKED, SINGLE-CROSSING CHEAP TALK GAMES - FRANÇOISE FORGES
Abstract: We study pure perfect Bayesian equilibria (PBE) in sender-receiver games with finitely many types for the sender. Such equilibria are characterized by incentive compatible (IC) partitions of the sender’s types, in which no type envies a type that is not in its own cell.
In the case of ordered types, real-valued decisions and well-behaved utility functions (namely, strictly concave, single-peaked, single-crossing and with an upward bias for the sender), we propose a family of algorithms that all converge to a unique IC partition. This partition satisfies equilibrium selection criteria (variants of neologism-proofness).
The previous algorithms start at the fully revealing partition. At every step, the basic idea is to move a type that envies some other type to the cell it envies. We also investigate the associated "envy driven dynamics" when the initial partition is arbitrary.
Joint work with Stéphan Sémirat
April 3, 2023, Decision Theory as a Test of Coherence - Itzhak Gilboa
Abstract: Decision theory can be used to test the logic of decision making: one may ask whether a given set of decisions can be justified by a decision-theoretic model. Indeed, in principal-agent settings, such justifications may be required -- for example, a manager of an investment fund may be asked what beliefs she used when valuing assets and a government may be asked whether a portfolio of rules and regulations is coherent. The paper asks which collections of uncertain-act evaluations can be simultaneously justified under the maxmin expected utility criterion by a single set of probabilities. We draw connections to the Fundamental Theorem of Finance (for the special case of a Bayesian agent) and to revealed-preference results. This type of results can also be used to discuss the role of (decision, game, economic) theory more generally.
April 17, 2023, Growth and Likelihood - Larry Samuelson
Abstract: We investigate economic growth by employing information theory techniques beyond their conventional scope. We find that the growth-maximizing policy satisfies a meritocracy principle: it minimizes the discrepancy between the shares of aggregate wealth and merits of economic agents. An analogous consistency principle arises in the statistical literature on predictive processing. There, an artificial or biological system chooses a statistical model that minimizes the discrepancy between the predicted and observed signal distributions. We demonstrate that, in fact, the models of economic growth and predictive coding are equivalent, as are the two principles.
May 1, 2023, Dominance Solvability in Random Games - Leeat Yariv
Abstract: We study the effectiveness of iterated elimination of strictly-dominated actions in random games. We show that dominance solvability of games is vanishingly small as the number of at least one player’s actions grows. Furthermore, conditional on dominance solvability, the number of iterations required to converge to Nash equilibrium grows rapidly as action sets grow. Nonetheless, when games are highly imbalanced, iterated elimination simplifies the game substantially by ruling out a sizable fraction of actions. Technically, we illustrate the usefulness of recent combinatorial methods for the analysis of general games.
Joint work with Noga Alon and Kirill Rudov
May 15, 2023, A Constant Factor Prophet Inequality for Online Combinatorial Auctions - José Correa
Abstract: In online combinatorial auctions $m$ indivisible items are to be allocated to $n$ agents who arrive online. Agents have random valuations for the different subsets of items, and the goal is to allocate the items on the fly so as to maximize the total value of the assignment. A prophet inequality in this setting refers to the existence of an online algorithm guaranteed to obtain, in expectation, a certain fraction of the expected value obtained by an optimal solution in hindsight. The study of prophet inequalities for online combinatorial auctions has been an intensive area of research in recent years, and constant factor prophet inequalities are known when the agents' valuation functions are submodular or fractionally subadditive. Despite many efforts, for the more general case of subadditive valuations, the best-known prophet inequality has an approximation guarantee of $O(\log\log m)$. In this paper, we prove the existence of a constant factor prophet inequality for the subadditive case, resolving a central open problem in the area.
Our prophet inequality is achieved by a novel, but elementary, sampling idea, which we call the Mirror Lemma. This lemma is essentially concerned with understanding online algorithms for which the set of items that are allocated and those that are not, distribute equally. The other main ingredient is a nonstandard application of Kakutani's fixed point theorem. Finally, we note that our prophet inequality works against an almighty adversary and even can be implemented in an incentive-compatible way.
Joint work with Andres Cristi
May 29, 2023, Level-Strategyproof Belief Aggregation and Application to Majority Judgment under Uncertainty - Rida Laraki
Abstract: In the context of aggregating probabilistic predictions or opinions from experts regarding an ordered set of outcomes, we introduce the concept of level-strategyproofness (Level-SP) as an axiom. We argue that Level-SP is not only applicable in various real-life scenarios, but also robust as a notion. It guarantees truthfulness in a wide range of single-peaked preferences over cumulative distributions, which is in contrast to the existing literature that typically assumes single-peaked preferences over probability distributions. Our main contributions can be summarized as follows:
• We provide explicit characterizations of all Level-SP methods, both with and without the incorporation of additional axioms such as certainty preservation, plausibility preservation or proportionality
• We compare and provide axiomatic characterizations for two novel Level-SP methods: proportional-cumulative and middlemost-cumulative.
• We utilize the proportional-cumulative method to construct a new voting method called Majority Judgment under Uncertainty (MJU), which extends majority judgment (MJ). In MJ, voters assign grades from a merit scale (e.g., "Great," "Good," "Average," "Poor," "Terrible") to each candidate/alternative. In MJU, voters have the flexibility to express their uncertainties regarding the merits by submitting probability distributions over the merit scale for each candidate. We demonstrate that MJU retains most of the prominent properties of MJ, such as avoiding Arrow and Condorcet paradoxes and being resistant to certain strategic manipulations.
Joint work with Estelle Varloot (University of Liverpool)