A decomposition algorithm for N-player games

An N-player game can be decomposed by adding a coordinator who interacts bilaterally with each player. The coordinator proposes profiles of strategies to the players, and his payoff is maximized when players’ optimal replies agree with his proposal. When the feasible set of proposals is finite, a solution of an associated linear complementarity problem yields an equilibrium of the approximate game and thus an approximate equilibrium of the original game. Computational efficiency is improved by using vertices of a triangulation of the players’ strategy space for the coordinator’s pure strategies. Computational experience is reported.     

Equilibrium tracing in strategic-form games

We analyze the relationships of the van den Elzen–Talman algorithm, the Lemke–Howson algorithm and the global Newton method for equilibrium computation by Govindan and Wilson. For two-player games, all three can be implemented as complementary pivoting algorithms. The algorithms by Lemke and Howson and by van den Elzen and Talman start at a pair of strategies: the first method at a pure strategy and its best reply, the latter anywhere in the strategy space. However, we show that even with the same starting point they may find different equilibria. Our second result is that the van den Elzen–Talman algorithm is a special case of the global Newton method, which was known only for the Lemke–Howson algorithm. More generally, the global Newton method implements the linear tracing procedure for any number of players. All three algorithms find generically only equilibria of positive index. Even though the van den Elzen–Talman algorithm is extremely flexible in the choice of starting point, we show that there are generic coordination games where the completely mixed equilibrium, which has positive index, is generically not found by the algorithm.     

Simple search methods for finding a Nash equilibrium

We present two simple search methods for computing a sample Nash equilibrium in a normal-form game: one for 2-player games and one for n-player games. Both algorithms bias the search towards supports that are small and balanced, and employ a backtracking procedure to efficiently explore these supports. Making use of a new comprehensive testbed, we test these algorithms on many classes of games, and show that they perform well against the state of the art—the Lemke–Howson algorithm for 2-player games, and Simplicial Subdivision and Govindan–Wilson for n-player games.     

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.     

Functional rational expectations equilibria in market games

The rational expectations equilibrium (REE) has been criticized as an equilibrium concept in market game environments. Such an equilibrium may not exist generically, or it may introduce unrealistic assumptions about an economic agent’s knowledge or computational ability. We define an REE as a probability measure over uncertain states of nature which exploits all available information in a market game, and which exists for almost all economies. Furthermore, if retrading is allowed, it is possible for agents to compute such a ‘functional rational expectations equilibrium’ using straightforward numerical fixed point algorithms. The approach is demonstrated in a detailed numerical example.     

On the existence of a strictly strong Nash equilibrium under the student-optimal deferred acceptance algorithm

This study analyzes a preference revelation game in the student-optimal deferred acceptance algorithm in a college admission problem. We assume that each college's true preferences are known publicly, and analyze the strategic behavior of students. We demonstrate the existence of a strictly strong Nash equilibrium in the preference revelation game through a simple algorithm that finds it. Specifically, (i) the equilibrium outcome from our algorithm is the same matching as in the efficiency-adjusted deferred acceptance algorithm and (ii) in a one-to-one matching market, it coincides with the student-optimal von Neumann–Morgenstern (vNM) stable matching. We also show that (i) when a strict core allocation in a housing market derived from a college admission market exists, it can be supported by a strictly strong Nash equilibrium, and (ii) there exists a strictly strong Nash equilibrium under the college-optimal deferred acceptance algorithm if and only if the student-optimal stable matching is Pareto-efficient for students.     

Price leadership and firm size asymmetry: an experimental analysis

We use laboratory experiments to examine the effect of firm size asymmetry on the emergence of price leadership in a price-setting duopoly with capacity constraints. Independent of the level of size asymmetry, the unique subgame perfect equilibrium of our timing game predicts that the large firm is the price leader. Experimental data show that price leadership by the large firm is frequent, but simultaneous moves are also often observed. Profit outcomes in the previous period affect the subjects’ decisions to announce or wait in a way that hampers convergence to the equilibrium. Furthermore, while both small and large firms display a strong tendency to wait to announce their price when firm size asymmetry is low, they often set prices early when size asymmetry is high. Prices are higher when price setting is sequential rather than simultaneous and when firm size asymmetry is high. Hence, price leadership by either type of firm has an anti-competitive effect that is more pronounced when the size difference between firms is large.     

Correlated Pollutants, Interregional Redistribution and Labor Attachment in a Federation

We examine the efficiency of federal policies in a federation characterized by decentralized leadership, imperfect labor mobility and transboundary pollution. Selfish regional governments regulate correlated pollutant emissions by choosing pollution tax and abatement levels in anticipation of the center’s redistributive policy. The center’s objective function obeys a proportional equity principle, which implies that its choice of interregional transfer satisfies the equalization of weighted regional welfare levels. Regional and central governments make their choices subject to migration incentives. We show that the subgame perfect equilibrium for the sequential game played by regional and central governments yields socially optimal policies. An erratum to this article can be found at     

Demand fluctuations and capacity utilization under duopoly

Summary.  This paper studies the impact of uncertain demand on firms’ capacity decisions when they operate in an oligopolistic environment. We define a two-stage game where firms choose capacity in the first stage without knowing which state of Nature is going to realize, and output levels in the second, knowing which state is realized. We prove the existence of a symmetric subgame perfect equilibrium at which firms are in excess capacity compared with the capacity they would choose in the Cournot certainty equivalent game. Received: May 17, 1996; revised version July 31, 1996     

Policy Bias Equivalence under Common Agency

This paper studies interest group influence on policy making. Lobbying occurs in a first price auction where an interest group wins with certainty, if her bid exceeds the loser’s bid by the policy maker’s valuation for the socially best policy. Otherwise the latter implements the privately known best policy. In equilibrium the size of the policy maker’s valuation does not matter for the size of the policy bias. The idea is to construct a “reference game” and to shift the support of the equilibrium mixed strategies into the original game, without altering the structure of the densities.     

Assignment models and reneging

Summary. We consider a non-cooperative assignment model where we show that any subgame perfect equilibrium is stable, and that an appropriate refinement criterion leads to the p-optimal outcome. We then consider a model with reneging and derive some interesting properties of this game. We show that in this case ‘unraveling’ may occur. Furthermore, the resulting outcome can be either stable, or unstable. Received: July 1, 1997; revised version: May 30, 1998     

Petty corruption

This paper analyzes a petty corruption model in which the entrepreneur’s type is drawn from an absolutely continuous probability distribution function F over [0, 1], and perfect Bayesian equilibrium is adopted as the solution concept for a one-stage game. In the one-stage game, if there is more than one bureaucrat, no project is approved with a strictly positive probability. For an infinitely repeated game, I show that the single window policy strictly increases the social benefits in a socially optimal equilibrium. I would like to thank Mukul Majumdar for valuable guidance and encouragement. I am also grateful to Kaushik Basu, Fernando Vega-Redondo, an anonymous referee, seminar participants at the international meeting for public economic theory (PET07) and especially Ani Guerdjikova and Roy Radner for helpful comments. Thanks are due to Hideaki Goto and Eunkyeong Lee for useful conversation.     

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.     

How Proper Is Sequential Equilibrium?

A strategy profile of a normal form game is proper if and only if it is quasi-perfect in every extensive form (with that normal form). Thus, properness requires optimality along a sequence of supporting trembles, while sequentiality only requires optimality in the limit. A decision-theoretic implementation of sequential rationality, strategic independence respecting equilibrium (SIRE), is defined and compared to proper equilibrium, using lexicographic probability systems. Finally, we give tremble-based characterizations, which do not involve structural features of the game, of the rankings of strategies that underlie proper equilibrium and SIRE.Journal of Economic LiteratureClassification Numbers: C70, C72.     

Bayesian–Walrasian equilibria: beyond the rational expectations equilibrium

In general rational expectations equilibrium (REE), as introduced in Radner (Econometrica 47:655–678, 1978) in an Arrow–Debreu–McKenzie setting with uncertainty, does not exist. Moreover, it fails to be fully Pareto optimal and incentive compatible and is also not implementable as a perfect Bayesian equilibrium of an extensive form game (Glycopantis et al. in Econ Theory 26:765–791, 2005). The lack of all the above properties is mainly due to the fact that the agents are supposed to predict the equilibrium market clearing price (as agent’s expected maximized utility is conditioned on the information that equilibrium prices reveal), which leads inevitably to the presumption that agents know all the primitives in the economy, i.e., random initial endowments, random utility functions and private information sets. To get around this problematic equilibrium notion, we introduce a new concept called Bayesian–Walrasian equilibrium (BWE) which has Bayesian features. In particular, agents try to predict the market-clearing prices using Bayesian updating and evaluate their consumption in terms of Bayesian price estimates, which are different for each individual. In this framework agents maximize expected utility conditioned on their own private information about the state of nature, subject to a Bayesian estimated budget constraint. Market clearing is not an intrinsic part of the definition of BWE. However, both in the case of perfect foresight and in the case of symmetric information BWE leads to a statewise market clearing; it then becomes an ex post Walrasian equilibrium allocation. This new BWE exists under standard assumptions, in contrast to the REE. In particular, we show that our new BWE exists in the well-known example in Kreps (J Econ Theory 14:32–43, 1977), where REE fails to exist. This work was done in the Spring of 2005, when EJB was a visiting professor at the University of Illinois.     

Perfect and imperfect real-time monitoring in a minimum-effort game

This paper presents the results from a minimum-effort game in which individuals can observe the choices of others in real time. We find that under perfect monitoring almost all groups coordinate at the payoff-dominant equilibrium. However, when individuals can only observe the actions of their immediate neighbors in a circle network, monitoring improves neither coordination nor efficiency relative to a baseline treatment without real-time monitoring. We argue that the inefficacy of imperfect monitoring is due to information uncertainty, that is, uncertainty about the correct interpretation of a neighbor’s actions. Information uncertainty prevents individuals from inferring safely that their group has managed to coordinate from the available information.     

Subgame Perfect Equilibria in Stage Games

It is well known that a stage game with infinite choice-sets, unless it contains a public coordination-device in each stage, may have no subgame perfect equilibria. We show that if a game with public coordination-devices has a subgame perfect equilibrium in which two players in each stage use non-atomic strategies, then the game without coordination devices also has a subgame perfect equilibrium. Journal of Economic Literature Classification Numbers: C6, C7, D8.     

Quality competition and entry: a media market case

In this paper, we study the optimal tax policy in a differential oligopoly game where the competing firms share the access to a productive renewable resource. We show that, in a Feedback Nash Equilibrium of the game, a linear Markov tax, imposed on the output, and specified as an affine function of the available resource stock, leads the competing firms to produce the socially optimal quantities over time, thus overcoming the dynamic interplay between the tragedy of the commons and the firms’ market power. The optimal tax turns out to be independent from the resource stock in a monopoly, and it cannot be defined in a duopoly.     

A Theory of Endogenous Coalition Structures

Consider an environment with widespread externalities, and suppose that binding agreements can be written. We study coalition formation in such a setting. Our analysis proceeds by defining on a partition function an extensive-form bargaining game. We establish the existence of a stationary subgame perfect equilibrium for such a game. Our main results are concerned with the characterization of equilibriumcoalition structures. We develop an algorithm that generates (under certain conditions) an equilibrium coalition structure. Our characterization results are especially sharp forsymmetricpartition functions. In particular, we provide a uniqueness theorem and apply our results to a Cournot oligopoly.Journal of Economic LiteratureClassification Numbers: C71, C72, C78, D62.