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.

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.

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.