Imperfect recall and the relationships between solution concepts in extensive games

Summary. In a game of imperfect recall, a sequential equilibrium may not be a Nash equilibrium, and a perfect equilibrium may not be a sequential equilibrium. Sufficiency conditions weaker than perfect recall are given to ensure the standard relationships hold between perfect equilibrium, sequential equilibrium and Nash equilibrium.Received: 22 October 2003, Revised: 18 November 2003, JEL Classification Numbers: C72.     

Trees and decisions

Summary. The traditional model of sequential decision making, for instance, in extensive form games, is a tree. Most texts define a tree as a connected directed graph without loops and a distinguished node, called the root. But an abstract graph is not a domain for decision theory. Decision theory perceives of acts as functions from states to consequences. Sequential decisions, accordingly, get conceptualized by mappings from sets of states to sets of consequences. Thus, the question arises whether a natural definition of a tree can be given, where nodes are sets of states. We show that, indeed, trees can be defined as specific collections of sets. Without loss of generality the elements of these sets can be interpreted as representing plays. Therefore, the elements can serve as states and consequences at the same time.Received: 23 January 2003, Revised: 2 November 2003, JEL Classification Numbers: C72, D70. Correspondence to: Klaus RitzbergerWe are grateful to Larry Blume, Ariel Rubinstein, Jörgen Weibull, an anonymous referee, and seminar participants at the universities of Vienna, Salamanca, and Heidelberg for helpful comments. Financial support from the Austrian Science Fund (FWF) under project P15281 is also gratefully acknowledged.     

Asymptotic expected number of Nash equilibria of two-player normal form games

The formula given by McLennan [The mean number of real roots of a multihomogeneous system of polynomial equations, Amer. J. Math. 124 (2002) 49–73] is applied to the mean number of Nash equilibria of random two-player normal form games in which the two players have M and N pure strategies respectively. Holding M fixed while N→∞, the expected number of Nash equilibria is approximately . Letting M=N→∞, the expected number of Nash equilibria is , where is a constant, and almost all equilibria have each player assigning positive probability to approximately 31.5915 percent of her pure strategies.     

Equilibrium play and best response to (stated) beliefs in normal form games

We report experimental results on a series of ten one-shot two-person 3×3 normal form games with unique equilibrium in pure strategies played by non-economists. In contrast to previous experiments in which game theory predictions fail dramatically, a majority of actions taken coincided with the equilibrium prediction (70.2%) and were best-responses to subjects' stated beliefs (67.2%). In constant-sum games, 78% of actions taken were predicted by the equilibrium model, outperforming simple K-level reasoning models. We discuss how non-trivial game characteristics related to risk aversion, efficiency concerns and social preferences may affect the predictive value of different models in simple normal form games.     

On forward induction in money-burning games

Summary. We first consider money-burning games studied by Ben-Porath and Dekel [6]. We show that iterative weak dominance and extensive form rationalizability yield the same unique outcome in this class of games. This result suggests that weak dominance captures the forward induction logic implied by extenisve form rationalizability. Next, we consider an example of entry model by Arvan [1] to demonstrate the power of forward induction. In this example, despite the presence of multiple equilibria, forward induction chooses a unique outcome. Received: January 25, 2000; revised version: January 5, 2001     

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.     

Two more classes of games with the continuous-time fictitious play property

Fictitious Play is the oldest and most studied learning process for games. Since the already classical result for zero-sum games, convergence of beliefs to the set of Nash equilibria has been established for several classes of games, including weighted potential games, supermodular games with diminishing returns, and 3×3 supermodular games. Extending these results, we establish convergence of Continuous-time Fictitious Play for ordinal potential games and quasi-supermodular games with diminishing returns. As a by-product we obtain convergence for 3×m and 4×4 quasi-supermodular games.     

Adaptive learning in extensive form games and sequential equilibrium

Summary. This paper studies adaptive learning in extensive form games and provides conditions for convergence points of adaptive learning to be sequential equilibria. Precisely, we present a set of conditions on learning sequences such that an assessment is a sequential equilibrium if and only if there is a learning sequence fulfilling the conditions, which leads to the assessment. Received: November 5, 1996; revised version: May 28, 1997     

Stochastic evolutionary stability in extensive form games of perfect information

Nöldeke and Samuelson [Games Econ. Behav. 5 (1993) 425] investigate a stochastic evolutionary model for extensive form games and show that even for games of perfect information with a unique subgame perfect equilibrium, non-subgame perfect equilibrium-strategies may well survive in the long run even when mutation rates tend to zero. In a different model of evolution in the agent normal form of these games Hart [Games Econ. Behav. 41 (2002) 227] shows that under suitable limit-taking, where small mutation rates are accompanied by large population sizes in a particular way, the unique prediction is again the subgame perfect equilibrium. This paper provides a proof of a similar result for the model of Nöldeke and Samuelson.     

A geometric approach to the price of anarchy in nonatomic congestion games

We present a short, geometric proof for the price-of-anarchy results that have recently been established in a series of papers on selfish routing in multicommodity flow networks and on nonatomic congestion games. This novel proof also facilitates two new types of theoretical results: On the one hand, we give pseudo-approximation results that depend on the class of allowable cost functions. On the other hand, we derive stronger bounds on the inefficiency of equilibria for situations in which the equilibrium costs are within reasonable limits of the fixed costs. These tighter bounds help to explain empirical observations in vehicular traffic networks. Our analysis holds in the more general context of nonatomic congestion games, which provide the framework in which we describe this work.     

Existence of Nash equilibria in finite extensive form games with imperfect recall: A counterexample

This paper provides an example showing that for finite extensive form games without perfect recall existence of Nash equilibria in behaviour strategies is not guaranteed in general.     

On the equivalence of weak dominance and sequential best response

In this paper, we identify the conditions under which a strategy is weakly dominated if and only if it is not sequential best response. In addition, we explore the implication for extensive form rationalizability.     

On extensive form implementation of contracts in differential information economies

Summary. In the context of differential information economies, with and without free disposal, we consider the concepts of Radner equilibrium, rational expectations equilibrium, private core, weak fine core and weak fine value. We look into the possible implementation of these concepts as perfect Bayesian or sequential equilibria of noncooperative dynamic formulations. We construct relevant game trees which indicate the sequence of decisions and the information sets, and explain the rules for calculating ex ante expected payoffs. The possibility of implementing an allocation is related to whether or not it is incentive compatible. Implementation through an exogenous third party or an endogenous intermediary is also considered. Received: November 19, 2001; revised version: April 17, 2002 RID="*" ID="*" This paper comes out of a visit by Nicholas Yannelis to City University, London, in December 2000. We are grateful to Dr A. Hadjiprocopis for his invaluable help with the implementation of Latex in a Unix environment. We also thank Leon Koutsougeras and a referee for several, helpful comments. Correspondence to: N.C. Yannelis     

Non-cooperative bargaining in apex games and the kernel

This paper studies non-cooperative bargaining with random proposers in apex games. Two different protocols are considered: the egalitarian protocol, which selects each player to be the proposer with equal probability, and the proportional protocol, which selects each player with a probability proportional to his number of votes. Expected equilibrium payoffs coincide with the kernel for the grand coalition regardless of the protocol. The equilibrium is in mixed strategies and the indifference conditions can be reinterpreted in the language of the kernel.     

政治理论教学中游戏式教学探析

在新世纪,政治理论教学作为院校思想政治建设的重要环节,缺乏吸引力,教学效果不佳。游戏式教学法能够营造出良好的教学氛围,激发学生强烈的求知欲和兴趣。在政治理论课上采用游戏教学法,可以提高政治理论课的教学质量,增强教学效果。     

Noncooperative foundations of the nucleolus in majority games

This paper studies coalition formation, payoff division and expected payoffs in a “divide the dollar by majority rule” game with random proposers. A power index is called self-confirming if it can be obtained as an equilibrium of the game using the index itself as probability vector. Unlike the Shapley value and other commonly used power indices, the nucleolus has this property. The proof uses a weak version of Kohlberg's [SIAM J. Appl. Math. 20 (1971) 62] balancedness result reinterpreting the balancing weights as probabilities in a mixed strategy equilibrium.     

A note on public debt, tax-exempt bonds, and Ponzi games

By issuing tax-exempt bonds, the government can incur debt and never pay back any principal or interest, even if the economy without public debt evolves on a dynamically efficient growth path. The welfare effects of such a Ponzi type borrowing scheme are mixed. The current young will unambiguously benefit. Depending on preferences and the aggregate technology, a finite number of subsequent generations may also benefit. However, the welfare of all generations thereafter will be lower than in the economy without public debt.     

Revision of conjectures about the opponent’s utilities in signaling games

In this paper we apply the concept of preference conjecture equilibrium introduced in Perea (2005) to signaling games and show its relation to sequential equilibrium. We introduce the concept of minimum revision equilibrium and show how this can be interpreted as a refinement of sequential equilibrium     

Polling games and information revelation in the Downsian framework

We investigate the incentives faced by poll respondents when candidates use polling data to inform their selection of policy platforms. Focusing on models with a unidimensional policy space, single peaked preferences and two office-seeking candidates observing a summary statistic from polls that ask respondents their preferences, we find that for most environments honest poll response cannot occur in a perfect Bayesian equilibrium. However, simple partially-revealing equilibria exist when the poll only asks respondents which party or candidate they prefer. When the candidates learn the sample average or see all the data, there are partially revealing equilibria that mimic those of the binary message game. Interpretation of polling data requires knowledge of the equilibrium played as the meanings of poll responses are endogenously determined. The analysis suggests that naive use of polling data may be misleading.     

Incentives in market games with asymmetric information: the core

Summary. This paper examines the ex ante core of a pure exchange economy with asymmetric information in which state-dependent allocations are required to satisfy incentive compatibility. This restriction on players' strategies in the cooperative game can be interpreted as incomplete contracts or partial commitment. An example is provided in which the incentive compatible core with nontransferable utility is empty; the game fails to be balanced because convex combinations of incentive compatible net trades can violate incentive compatibility. However, randomization of such strategies leads to ex post allocations which satisfy incentive compatibility and are feasible on average. Hence, convexity is preserved in such a model and the resulting cooperative games are balanced. In this framework, an incentive compatible core concept is defined for NTU games derived from economies with asymmetric information. The main result is nonemptiness of the incentive compatible core. Received: December 26, 2001; revised version: June 11, 2002 RID="*" ID"*" This work was financed, in part, by contract No 26 of the programme “P?le d'attraction interuniversitaire” of the Belgian government, and, in part, by research grant SBR93-09854 from the U.S. National Science Foundation. Much of my thinking about this topic was developed during a wonderful visit to CORE for the 1991–1992 academic year (on sabbatical from the University of Pennsylvania). This paper was originally circulated in December 1991 as CARESS Working Paper #91-38, Center for Analytic Research in Economics and the Social Sciences, Department of Economics, University of Pennsylvania and in February 1992 as CORE Discussion Paper 9221, Center for Operations Research and Econometrics, Université Catholique de Louvain, Louvain-la-Neuve, Belgium. RID="*" ID="*" At the very start of my research, Jean-Fran?ois Mertens was almost a co-author. Fran?ois Forges provided detailed comments at a later stage, during my visit to THEMA, Université Cergy-Pontoise, in Spring 1997. They are entitled to the customary disclaimer.