Homotopy methods to compute equilibria in game theory

This paper presents a survey of the use of homotopy methods in game theory. Homotopies allow for a robust computation of game-theoretic equilibria and their refinements. Homotopies are also suitable to compute equilibria that are selected by various selection theories. We present the relevant techniques underlying homotopy algorithms. We give detailed expositions of the Lemke–Howson algorithm and the van den Elzen–Talman algorithm to compute Nash equilibria in 2-person games, and the Herings–van den Elzen, Herings–Peeters, and McKelvey–Palfrey algorithms to compute Nash equilibria in general n-person games. We explain how the main ideas can be extended to compute equilibria in extensive form and dynamic games, and how homotopies can be used to compute all Nash equilibria.     

The supercore for normal-form games

This paper analyzes the supercore of a system derived from a normal-form game. For the case of a finite game with pure strategies, we define a sequence of games and show that the supercore coincides with the set of Nash equilibria of the last game in that sequence. This result is illustrated with the characterization of the supercore for the n-person prisoner's dilemma. With regard to the mixed extension of a normal-form game, we show that the set of Nash equilibrium profiles coincides with the supercore for games with a finite number of Nash equilibria.     

Competitive behavior in market games: Evidence and theory

We explore whether competitive outcomes arise in an experimental implementation of a market game, introduced by Shubik (1973) [21]. Market games obtain Pareto inferior (strict) Nash equilibria, in which some or possibly all markets are closed. We find that subjects do not coordinate on autarkic Nash equilibria, but favor more efficient Nash equilibria in which all markets are open. As the number of subjects participating in the market game increases, the Nash equilibrium they achieve approximates the associated competitive equilibrium of the underlying economy. Motivated by these findings, we provide a theoretical argument for why evolutionary forces can lead to competitive outcomes in market games.     

Games of fixed rank: a hierarchy of bimatrix games

We propose and investigate a hierarchy of bimatrix games (A, B), whose (entry-wise) sum of the pay-off matrices of the two players is of rank k, where k is a constant. We will say the rank of such a game is k. For every fixed k, the class of rank k-games strictly generalizes the class of zero-sum games, but is a very special case of general bimatrix games. We study both the expressive power and the algorithmic behavior of these games. Specifically, we show that even for k = 1 the set of Nash equilibria of these games can consist of an arbitrarily large number of connected components. While the question of exact polynomial time algorithms to find a Nash equilibrium remains open for games of fixed rank, we present polynomial time algorithms for finding an ε-approximation.     

Learning to alternate

The Individual Evolutionary Learning (IEL) model explains human subjects’ behavior in a wide range of repeated games which have unique Nash equilibria. Using a variation of ‘better response’ strategies, IEL agents quickly learn to play Nash equilibrium strategies and their dynamic behavior is like that of humans subjects. In this paper we study whether IEL can also explain behavior in games with gains from coordination. We focus on the simplest such game: the 2 person repeated Battle of Sexes game. In laboratory experiments, two patterns of behavior often emerge: players either converge rapidly to one of the stage game Nash equilibria and stay there or learn to coordinate their actions and alternate between the two Nash equilibria every other round. We show that IEL explains this behavior if the human subjects are truly in the dark and do not know or believe they know their opponent’s payoffs. To explain the behavior when agents are not in the dark, we need to modify the basic IEL model and allow some agents to begin with a good idea about how to play. We show that if the proportion of inspired agents with good ideas is chosen judiciously, the behavior of IEL agents looks remarkably similar to that of human subjects in laboratory experiments.     

Properties and applications of dual reduction

The dual reduction process, introduced by Myerson, allows a finite game to be reduced to a smaller-dimensional game such that any correlated equilibrium of the reduced game is an equilibrium of the original game. We study the properties and applications of this process. It is shown that generic two-player normal form games have a unique full dual reduction (a known refinement of dual reduction) and all strategies that have probability zero in all correlated equilibria are eliminated in all full dual reductions. Among other applications, we give a linear programming proof of the fact that a unique correlated equilibrium is a Nash equilibrium, and improve on a result due to Nau, Gomez-Canovas and Hansen on the geometry of Nash equilibria and correlated equilibria.     

Adaptation and complexity in repeated games

The paper presents a learning model for two-player infinitely repeated games. In an inference step players construct minimally complex inferences of strategies based on observed play, and in an adaptation step players choose minimally complex best responses to an inference. When players randomly select an inference from a probability distribution with full support the set of steady states is a subset of the set of Nash equilibria in which only stage game Nash equilibria are played. When players make ‘cautious’ inferences the set of steady states is the subset of self-confirming equilibria with Nash outcome paths. When players use different inference rules, the set of steady states can lie between the previous two cases.     

The number of pure Nash equilibria in a random game with nondecreasing best responses

We randomly draw a game from a distribution on the set of two-player games with a given size. We compute the distribution and the expectation of the number of pure-strategy Nash equilibria of the game conditional on the game having nondecreasing best-response functions. The conditional expected number of pure-strategy Nash equilibria becomes much larger than the unconditional expected number as the size of the game grows.     

On ‘Informationally Robust Equilibria’ for Bimatrix Games

Informationally robust equilibria (IRE) are introduced in Robson (Games Econ Behav 7: 233–245, 1994) as a refinement of Nash equilibria for strategic games. Such equilibria are limits of a sequence of (subgame perfect) Nash equilibria in perturbed games where with small probability information about the strategic behavior is revealed to other players (information leakage). Focusing on bimatrix games, we consider a type of informationally robust equilibria and derive a number of properties they form a non-empty and closed subset of the Nash equilibria. Moreover, IRE is a strict concept in the sense that the IRE are independent of the exact sequence of probabilities with which information is leaked. The set of IRE, like the set of Nash equilibria, is the finite union of polytopes. In potential games, there is an IRE in pure strategies. In zero-sum games, the set of IRE has a product structure and its elements can be computed efficiently by using linear programming. We also discuss extensions to games with infinite strategy spaces and more than two players. The authors would like to thank Marieke Quant for her helpful comments.     

Competitive environments and protective behavior

The class of two-person competition games is introduced and analyzed. For any game in this class the set of Nash equilibria is convex and all Nash equilibria lead to the same payoff vector. Competition games are compared to other competitive environments such as unilaterally competitive games and rivalry games. Moreover, protective behavior within competitive environments is analyzed. For matrix games it is known that protective strategies profiles exactly correspond to proper equilibria. It is shown that this result can be extended to the class of unilaterally competitive games.     

Existence of perfect equilibria: a direct proof

We provide a direct proof of the existence of perfect equilibria in finite normal form games and extensive games with perfect recall. It is done by constructing a correspondence whose fixed points are precisely the perfect equilibria of a given finite game. Existence of a fixed point is secured by a generalization of Kakutani theorem, which is proved in this paper. This work offers a new approach to perfect equilibria, which would hopefully facilitate further study on this topic. We also hope our direct proof would be the first step toward building an algorithm to find the set of all perfect equilibria of a strategic game.     

Strategic approximations of discontinuous games

An infinite game is approximated by restricting the players to finite subsets of their pure strategy spaces. A strategic approximationof an infinite game is a countable subset of pure strategies with the property that limits of all equilibria of all sequences of approximating games whose finite strategy sets eventually include each member of the countable set must be equilibria of the infinite game. We provide conditions under which infinite games admit strategic approximations.     

Stochastic better-reply dynamics in finite games

In this paper, we analyze a model where individuals from finite populations are repeatedly drawn to play a finite game and in every period choose a weakly better reply to a sample distribution from a finite history of past play. For all finite games and sufficiently incomplete information, we prove convergence to minimal sets closed under better replies. This result complements previous findings in a deterministic continuous-time framework and implies convergence to strict Nash equilibria in many well-known classes of games.     

Equivalence and Invariance of the Index and Degree of Nash Equilibria

Associated with each component of the Nash equilibria of a game are its index and degree. Its index is the local degree of the displacement map whose roots are the Nash equilibria of the game. Its degree is the local degree of the projection map from the Nash graph to the space of games. We show that the index and the degree of each component are the same. Further, they are invariant to adding or deleting redundant strategies, so they depend only on the reduced normal form of the game. Applications include Kohlberg and Mertens' existence theorems for stable sets and a simple procedure for calculating the degree of a component.Journal of Economic LiteratureClassification Number: C72.     

Bilateral commitment

We consider non-cooperative environments in which two players have the power to gradually and unilaterally rule out some of their actions. Formally, we embed a strategic-form game into a multi-stage game, in which players can restrict their action spaces in all but the final stage, and select among the remaining actions in the last stage. We say that an action profile is implementable by commitment if this action profile is played in the last stage of a subgame-perfect equilibrium path. We provide a complete characterization of all implementable action profiles and a simple method to find them. It turns out that the set of implementable profiles does not depend on the length of the commitment process. We show, furthermore, that commitments can have social value in the sense that in some games there are implementable action profiles that dominate all Nash equilibria of the original game.     

Bayesian games with unawareness and unawareness perfection

Applying unawareness belief structures introduced in Heifetz et al. (Games Econ Behav 77:100–121, 2013a), we develop Bayesian games with unawareness, define equilibrium, and prove existence. We show how equilibria are extended naturally from lower to higher awareness levels and restricted from higher to lower awareness levels. We apply Bayesian games with unawareness to investigate the robustness of equilibria to uncertainty about opponents’ awareness of actions. We show that a Nash equilibrium of a strategic game is robust to unawareness of actions if and only if it is not weakly dominated. Finally, we discuss the relationship between standard Bayesian games and Bayesian games with unawareness.     

Evolutionary stability and lexicographic preferences

We explore the interaction between evolutionary stability and lexicographic preferences. To do so, we define a limit Nash equilibrium for a lexicographic game as the limit of Nash equilibria of nearby games with continuous preferences. Nash equilibria of lexicographic games are limit Nash equilibria, but not conversely. Modified evolutionarily stable strategies (Binmore and Samuelson, 1992. J. Econ. Theory 57, 278–305) are limit Nash equilibria. Modified evolutionary stability differs from “lexicographic evolutionarily stability” (defined by extending the common characterization of evolutionary stability to lexicographic preferences) in the order in which limits in the payoff space and the space of invasion barriers are taken.     

Equilibrium play in matches: Binary Markov games

We study two-person extensive form games, or “matches,” in which the only possible outcomes (if the game terminates) are that one player or the other is declared the winner. The winner of the match is determined by the winning of points, in “point games.” We call these matches binary Markov games. We show that if a simple monotonicity condition is satisfied, then (a) it is a Nash equilibrium of the match for the players, at each point, to play a Nash equilibrium of the point game; (b) it is a minimax behavior strategy in the match for a player to play minimax in each point game; and (c) when the point games all have unique Nash equilibria, the only Nash equilibrium of the binary Markov game consists of minimax play at each point. An application to tennis is provided.     

Equivalence of strong and coalition-proof Nash equilibria in games without spillovers

Summary This paper examines the conditions which guarantee that the set of coalition-proof Nash equilibria coincides with the set of strong Nash equilibria in the normal form games withoutspillovers. We find thatpopulation monotonicity properties of the payoff functions, when the payoff of a player changes monotonically when the size of the group of players choosing the same strategy increases, are crucial to obtain the equivalence of these two solution concepts. We identify the classes of games, satisfying population monotonicity properties, which yield the equivalence of the set of coalition-proof Nash equilibria and the set of strong Nash equilibria. We also provide sufficient conditions for the equivalence result even when the population monotonicity assumptions are relaxed.We wish to thank Mamoru Kaneko, Akihiko Matsui, Tomoichi Shinotsuka, Benyamin Shitoviz, Tayfun Sonmez, William Thomson, the participants of the Southeastern Economic Theory Meeting in Charlottesville and the seminars at CORE and University of Tsukuba for useful discussions and comments. Our special thanks due anonymous referee for the suggestion to add a section addressing the issue of existence of a strong Nash equilibrium.     

The envelope theorem for locally differentiable Nash equilibria of finite horizon differential games

Envelope theorems are established for a ubiquitous class of finite horizon differential games. The theorems cover open-loop and feedback information patterns in which the corresponding Nash equilibria are locally differentiable with respect to the parameters of the game. Their relationship with extant envelope results is discussed and an application of them to a generalized capital accumulation game is provided. An important implication of the theorems is that, in general, the archetypal economic interpretation of the costate vector, namely, as the shadow value of the state vector along the Nash equilibrium, is valid for feedback Nash equilibria, but not for open-loop Nash equilibria.