Weak isomorphisms of extensive games
by
André Casajus
University of Hohenheim

As Harsanyi & Selten's (1988) isomorphisms of strategic games, isomorphisms of extensive games can be viewed as a means to identify structurally similar extensive games and to identify corresponding structural elements of these games-players, information sets, actions, and nodes. And it is this emphasis of structural features that distinguishes isomorphisms from considerations of strategic equivalence as Kohlberg & Mertens' (1986) invariance requirement or Elmes & Reny's (1994)  transformations. As for strategic games, isomorphisms are bijective mappings of the players' pure-strategy sets that preserve the player structure and the payoff structure. In extensive games, basically, these mappings can be based either on the action partitions or on the node sets. Actually, both approaches have been adopted in the literature.

Like Elmes & Reny (1994),  Peleg, Rosenmüller & Sudhölter (1999)  introduce (strong) isomorphisms of extensive games that rest upon bijections of the node sets which respect the order of moves in a very strong sense. As it turns out, these strong isomorphisms are incompatible with the traditional extensive representations of strategic games -symmetric strategies in a strategic game may not be symmetric in the extensive representation. Thus, one could argue that Peleg et al. (1999) strong isomorphisms are too strong. In order to remedy this incompatibility, Peleg, Rosenmüller & Sudhölter (2000) introduce a new kind of extensive representation-canonical extensive forms of game forms-for which both notions of symmetry coincide. But these representations are considerably more complex and more difficult to deal with than the traditional ones. So a notion of isomorphisms of extensive games that fits the traditional representation of strategic games seems to be desirable.

In contrast, Selten (1983), Oh (1995), and Casajus (1998) base their (weak) symmetries of extensive games on bijective mappings of the action partitions. In addition, these (weak) symmetries do not respect the order of moves in the very strict sense of Peleg et al. (1999). This way, their symmetries are fully compatible with the traditional extensive representations of strategic games (Casajus 1998, Theorem 4.8). Additionally, in non-pathological cases, weak symmetries are subgame preserving Selten (1983, Theorem 1). Also, (weakly) symmetry invariant equilibria do always exist (Casajus 1998, Theorem 4.9). Beyond these appealing properties, however, no further justification for weak symmetries is given. So it is not clear, whether weak symmetries respect the order of moves in the essential extent. Of course, subgame preservation goes some way to answer this question in the affirmative.

The crucial issue now is: To what extent is the sequence of moves inessential? Or, to put it differently: When does an isomorphism respect the order of moves to the essential extent?

The following criterion is suggested: A certain concept of isomorphisms respects the order of moves to the essential extent if its isomorphisms always carry equilibria of the kind under consideration into equilibria of the same kind, i.e., if the equilibrium concept is invariant with respect to these isomorphisms. Of course, this property is especially important with respect to those equilibrium concepts that explicitly refer to the sequential nature of moves as the concepts of subgame perfect equilibria (Selten 1975) or sequential equilibria (Kreps & Wilson 1982). Beyond that, the order of moves seems to be rather inessential, i.e., it only constitutes a pure labelling of players and therefore should not affect isomorphisms. Note that this criterion reverses the relation between equilibrium/solution concepts and invariance with respect to isomorphisms: Usually, invariance with respect to isomorphisms serves as a measure to assess solution concepts or as a requirement on solution concepts. Here, in contrast, the solution concepts are exploited to assess some concept of isomorphisms. Of course, this reversal is based on the assumption that the equilibrium concepts used for this kind of assessment are sound in the sense that they do not contradict our intuitions.

In this paper, we extend Casajus' (1998) symmetries into weak isomorphisms of extensive games in a straightforward way and explores some of their properties. Besides the features above, we show:

(a) In non-pathological cases, weak isomorphisms are equivalent to the weakest conceivable requirement upon the sequence ofv moves.

(b) Weakly symmetry invariant perfect equilibria do always exist.

(c) The concepts of Nash equilibria, sequential equilibria, and of perfect equlibria are invariant with respect to weak isomorphisms. In non-pathological cases, also, the concept of subgame perfect equilibria shows this invariance property. I.e., weak isomorphisms respect the order of moves according to criterion above.

So weak isomorphisms are an adequate means to describe structural similarities of extensive games if one views the sequential nature of moves as a technical peculiarity of extensive games rather than a representation of real world facts. Of course, this does not mean that sequential moves in a game never correspond to sequential actions in real life.

Bibliography

Casajus (1998), Focal Points in Framed Extensive Games, Paper presented at the 3rd Spanish Meeting on Game Theory and Applications, June 15-18, Barcelona, Spain.

Elmes & Reny (1994), On the Strategic Equivalence of Extensive Form Games, Journal of Economic Theory 62, 1-23.

Harsanyi & Selten (1988), A General Theory of Equilibrium Selection in Games, MIT Press.

Kohlberg & Mertens (1986), On the strategic Stability of Equilibria, Econometrica 54, 1003-1037.

Kreps & Wilson (1982), Sequential Equilibria, Econometrica 50, 863-894. Oh (1995), Three Essay on Equilibrium Selection in Games, PhD Thesis, Graduate College of The University of Iowa.

Peleg, Rosenmüller & Sudhölter (1999), The Canonical Extensive Form of a Game Form: Symmetries, in: Alkan, Aliprantis & Yannelis, Current Trends in Economics: Theory and Applications, Springer, 367-387.

Peleg, Rosenmüller & Sudhölter (2000), The Canonical Extensive Form of a Game Form: Representation, Journal of Mathematical Economics 33(3), 299-338.

Selten (1975), Reexamination of the Perfectness Concept for Equilibrium Points in Extensive Games, International Journal of Game Theory, 25-55.

Selten (1983), Evolutionary Stability in Extensive Two-Person Games, Mathematical Social Sciences 5, 269-363.

Date received: May 2, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caez-92.