Recall in extensive form games

This paper considers characterizations of perfect recall in extensive form games. It is shown that perfect recall can be expressed in terms of choices without any reference to infomation sets. When information sets are taken into account, it is decomposable into an ordering of information sets and that players do not forget what they knew nor what they did. Thus, if information sets are partially ordered, then perfect recall is implied by the player's inability to refine her information from the memory. Received: August 1997/final version: September 1998     

Lexicographic domination in extensive games

We extend a notion of a lexicographic domination between strategies, introduced for normal form games in Okada (1988), to extensive games via the transformation from the extensive form to the agent normal form. It is shown that lexicographically undominatedness implies subgame perfection of an equilibrium point in extensive games with perfect recall.I am grateful to an anonymous referee for very helpful comments and suggestions. A preliminary draft of this paper was written while I was visiting the MEDS Department of Northwestern University in 1986–87. The warm hospitality of that department is gratefully acknowledged.     

Simplification of games in extensive form

Thevon Neumann-Morgenstern normal form of a game is conceptually and theoretically useful, but in practice leads to enormous matrix games. We discuss new methods of simplifying games in extensive form that should be useful for solving actual games. The first method is that of partially normalizing the game at an information set and, if dominations are found, making local “negative” decisions not to choose certain alternatives at the information set. Coupled with this idea is the reduction operation which eliminates parts of the game tree. These methods are shown to be powerful enough to eliminate all dominations in the strategy matrix, where we consider domination in three senses.     

Almost strict competitiveness in extensive games

We consider an extension of an almost strictly competitive game, introduced by Aumann (1961), inn-person extensive games by incorporating Selten's subgame perfection. We call it a subgame perfect weakly-almost (SPWA) strictly competitive game, in particular, an SPWA strictly competitive game in strategic form is simply called a WA strictly competitive game. We give some general results on the structure of this class of games. One result gives an easy way to verify almost strict competitiveness of a given extensive game. We show that a two-person weakly unilaterally competitive extensive game, introduced by Kats and Thisse (1992) for normal form games, is SPWA strictly competitive. We remark that some of our main results for SPWA strictly competitive games do not hold for the modification of almost strict competitiveness with trembling-hand perfection.The author is indebted to Mamoru Kaneko for valuable discussions, comments and criticism throughout the paper. He thanks N. Bose, M. Frascatore, R. Gilles, H. Haller, A. Kats, J. Kline and an anonymous referee for helpful comments on earlier drafts. The usual disclaimer applies.     

Player splitting in extensive form games

By a player splitting we mean a mechanism that distributes the information sets of a player among so-called agents. A player splitting is called independent if each path in the game tree contains at most one agent of every player. Following Mertens (1989), a solution is said to have the player splitting property if, roughly speaking, the solution of an extensive form game does not change by applying independent player splittings. We show that Nash equilibria, perfect equilibria, Kohlberg-Mertens stable sets and Mertens stable sets have the player splitting property. An example is given to show that the proper equilibrium concept does not satisfy the player splitting property. Next, we give a definition of invariance under (general) player splittings which is an extension of the player splitting property to the situation where we also allow for dependent player splittings. We come to the conclusion that, for any given dependent player splitting, each of the above solutions is not invariant under this player splitting. The results are used to give several characterizations of the class of independent player splittings and the class of single appearance structures by means of invariance of solution concepts under player splittings. Received: December 1996/Revised Version: January 2000     

Dynamic stability in symmetric extensive form games

Dynamic stability under the replicator dynamic of evolutionary game theory is investigated for certain symmetric extensive form games whose subgame structure exhibits a high degree of decomposability. It is shown that a pervasive equilibrium strategy is locally asymptotically stable (l.a.s.) if and only if it is given by backwards induction applied to the l.a.s. pervasive equilibria of the subgames and their corresponding truncations. That is, this dynamic backwards induction procedure provides a rational basis on which to predict the evolutionary outcome of the replicator dynamic for these symmetric games.     

On finding curb sets in extensive games

We characterize strategy sets that are closed under rational behavior (curb) in extensive games of perfect information and finite horizon. It is shown that any such game possesses only one minimal curb set, which necessarily includes all its subgame perfect Nash equilibria. Applications of this result are twofold. First, it lessens computational burden while computing minimal curb sets. Second, it implies that the profile of subgame perfect equilibrium strategies is always stochastically stable in a certain class of games.I am grateful to J. Kamphorst, G. van der Laan and X. Tieman, who commented on the earlier versions of the paper. I also thank an anonymous referee and an associate editor for their helpful remarks. The usual disclaimer applies.     

On extensive games and almost complete information

Our main result for finite games in extensive form is that strict determinacy for a playeri in a completely inflated game structure implies almost complete information for playeri, even if we allow for certain type of overlapping for information sets.     

A convex representation of totally balanced games

We analyze the least increment function, a convex function of n variables associated to an n-person cooperative game. Another convex representation of cooperative games, the indirect function, has previously been studied. At every point the least increment function is greater than or equal to the indirect function, and both functions coincide in the case of convex games, but an example shows that they do not necessarily coincide if the game is totally balanced but not convex. We prove that the least increment function of a game contains all the information of the game if and only if the game is totally balanced. We also give necessary and sufficient conditions for a function to be the least increment function of a game as well as an expression for the core of a game in terms of its least increment function.     

On the minimal representation of homogeneous games

It is known that the lattice-minimal representation (by natural numbers) of a weighted majority game may be not unique and may lack of equal treatment (Isbell 1959). The same is true for the total-weight minimal representation. Both concepts coincide on the class of homogeneous games. The main theorem of this article is that for homogeneous games there is a unique minimal representation. This result is given by means of a construction that depends on the natural order on the set of player types. This order coincides with one induced by the “desirability relation”. In order to compute the minimal representation inductively, while proceeding from smaller players to the greater one, we are led to distinguish two different kinds of players: some players are “replacable” by smaller ones, some not.     

Complete inflation and perfect recall in extensive games

This paper considers the relation between complete inflation and perfect recall of information partitions in extensive games. It is proved that an information partition with perfect recall is completely inflated. This result, combined with Dalkey's theorem, shows that in the class of games (without chance moves) with perfect recall, a game is determinate if and only if every player has perfect information. A necessary and sufficient condition is provided for information partitions whose complete inflations have perfect recall.     

A reinforcement learning process in extensive form games

The CPR (“cumulative proportional reinforcement”) learning rule stipulates that an agent chooses a move with a probability proportional to the cumulative payoff she obtained in the past with that move. Previously considered for strategies in normal form games (Laslier, Topol and Walliser, Games and Econ. Behav., 2001), the CPR rule is here adapted for actions in perfect information extensive form games. The paper shows that the action-based CPR process converges with probability one to the (unique) subgame perfect equilibrium.Received: October 2004     

On Pareto equilibria in vector-valued extensive form games

In this paper we investigate the existence of Pareto equilibria in vector-valued extensive form games. In particular we show that every vector-valued extensive form game with perfect information has at least one subgame perfect Pareto equilibrium in pure strategies. If one tries to prove this and develop a vector-valued backward induction procedure in analogy to the real-valued one, one sees that different effects may occur which thus have to be taken into account: First, suppose the deciding player at a nonterminal node makes a choice such that the equilibrium payoff vector of the subgame he would enter is undominated under the equilibrium payoff vectors of the other subgames he might enter. Then this choice need not to lead to a Pareto equilibrium. Second, suppose at a nonterminal node a chance move may arise. The combination of the Pareto equilibria of the subgames to give a strategy combination of the entire game need not be a Pareto equilibrium of the entire game.     

An algebraical system for polynomial representation of k-valued logical functions

An algebraical system < A_k;+; >, in which ‘almost each’ k-valued logical function (k-composite integer) had representation in the form of polynomial in modulo k, is presented.     

Population monotonicity and consistency in convex games: Some logical relations

On the domain of convex games, many desirable properties of solutions are compatible and there are many single-valued solutions that are intuitively appealing. We establish some interesting logical relations among properties of single-valued solutions. In particular, we introduce a new property, weak contribution-monotonicity, and show that this property is a key property that links other properties such as population-monotonicity, max consistency, converse max consistency, and dummy-player-out. Received: July 2002/Revised: March 2003     

Hospital management games: a taxonomy and extensive review

Hospital management games have gained importance in better planning for scarce resources in times of growing health care demand and increasing technology costs. We classify and investigate the main characteristics of these games from an Operations Research (OR) perspective. Hospital management games model the complex decision making process of internal resource, process, and financial management all influenced by the external hospital environment (e.g., purchasing markets, job markets, legal/political conditions, competition) and simulate situations of the real world. We also highlight the potential of these games for teaching OR in the classroom. Experiencing the advantages of OR may reduce the reservations policy makers have and could make them increasingly open to promoting OR applications in practice. We also disclose potential for new applications.     

Order of play in strategically equivalent games in extensive form

“Can we find a pair of extensive form games that give rise to the same strategic form game such that, when played by a reasonable subject population, there is a statistically significant difference in how the games are played?” (Kreps, 1990, p. 112). And if yes, “can we organize these significant differences according to some principles that reflect recognizable differences in the extensive forms?” Both questions are answered positively by reporting results from three different experiments on public goods provision, resource dilemmas, and pure coordination games.     

On the non-existence of a rationality definition for extensive games

Standard solution concepts, like subgame perfection, implicitly require that players will continue to assume everybody is rational even if this has been revealed to be false by virtue of having reached a node that could not have been reached had all players behaved rationally. Several attempts have been made in the literature to solve this problem. The present paper shows that the problem is insoluble.