The Category of Node-and-Choice Forms, with Subcategories for Choice-Sequence Forms and Choice-Set Forms

Streufert, Peter (2018): The Category of Node-and-Choice Forms, with Subcategories for Choice-Sequence Forms and Choice-Set Forms.

Abstract

The literature specifies extensive-form games in several styles, and eventually I hope to formally translate games across those styles. Toward that end, this paper defines NCF, the category of node-and-choice forms. The category's objects are game forms in any style, and the category's isomorphisms are made to accord with the literature's small handful of ad hoc style equivalences.

More specifically, the paper develops two full subcategories: CsqF for forms whose nodes are choice-sequences, and CsetF for forms whose nodes are choice-sets. I show that NCF is ``isomorphically enclosed'' in CsqF in the sense that each NCF form is isomorphic to a CsqF form. Similarly, I show that CsqF_\tilde{a} is isomorphically enclosed in CsetF in the sense that each CsqF form with no-absentmindedness is isomorphic to a CsetF form. The converses are found to be almost immediate, and the resulting equivalences unify and simplify two ad hoc style equivalences in Kline and Luckraz (Economic Theory Bulletin, 2016) and Streufert (International Journal of Game Theory, forthcoming).

Aside from the larger agenda, this paper makes three practical contributions. Style equivalences are made easier to derive by [1] a natural concept of isomorphic invariance and [2] the composability of isomorphic enclosures. In addition, [3] some new consequences of equivalence are systematically deduced.

• Item Type: MPRA Paper
• Language: English
• Keywords: extensive form, game form, isomorphic enclosure
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C73 - Stochastic and Dynamic Games ; Evolutionary Games ; Repeated Games

References

Abramsky, S., R. Jagadeesan, and P. Malacaria (2000): “Full Abstraction for PCF,” Information and Computation, 163, 409–470.

Alo ́s-Ferrer, C., and K. Ritzberger (2016): The Theory of Extensive Form Games. Springer.

Awodey, S. (2010): Category Theory (Second Edition). Oxford.

Harris, C. (1985): “Existence and Characterization of Perfect Equilibrium in Games of Perfect Information,” Econometrica, 53, 613–628.

Hedges, J. (2017): “Morphisms of Open Games,” ArXiv:1711.07059v2, 25 pages.

Hyland, J., and C.-H. L. Ong (2000): “On Full Abstraction for PCF: I, II, and III,” Information and Computation, 163, 285–408.

Jime ́nez, A. (2014): “Game Theory from the Category Theory Point of View,” Universidad Distrital Francisco Jose ́ de Caldas, Colombia, 20 pages.

Kline, J. J., and S. Luckraz (2016): “Equivalence between Graph-Based and Sequence-Based Extensive Form Games,” Economic Theory Bulletin, 4, 85–94.

Kuhn, H. W. (1953): “Extensive Games and the Problem of Information,” in Classics in Game Theory, ed. by H. W. Kuhn, pp. 46–68. Princeton (1997). Originally in Contributions to the Theory of Games, ed. by H. W. Kuhn and A. W. Tucker, pp. 193–216. Princeton (1953).

Lapitsky, V. (1999): “On Some Categories of Games and Corresponding Equilibria,” International Game Theory Review, 1, 169–185.

MacLane, S. (1998): Categories for the Working Mathematician (Second Edition). Springer.

Machover, M., and S. D. Terrington (2014): “Mathematical Structures of Simple Voting Games,” Mathematical Social Sciences, 71, 61–68.

McCusker, G. (2000): “Games and Full Abstraction for FPC,” Information and Computation, 160, 1–61.

Osborne, M. J., and A. Rubinstein (1994): A Course in Game Theory. MIT.

Piccione, M., and A. Rubinstein (1997): “On the Interpretation of Decision Problems with Imperfect Recall,” Games and Economic Behavior, 20, 3–24.

Selten, R. (1975): “Reexamination of the Perfectness Concept for Equilibrium Points in Extensive Games,” International Journal of Game Theory, 4, 25–55.

Streufert, P. A. (2016): “The Category of Node-and-Choice Forms for Extensive-Form Games,” Western University, Department of Economics Research Report 2016-5, October, 20 pages.

Streufert, P. A. (2018): “Equivalences among Five Game Specifications, including a New Specification whose Nodes are Sets of Past Choices,” International Journal of Game Theory, forthcoming, 30 pages.

Streufert, P.A. (2018): “The Category of Node-and-Choice Preforms for Extensive-Form Games,” Studia Logica (Special Issue: Logics for Social Behaviour), 106, 1001–1064.

Tutte, W. T. (1984): Graph Theory. Addison-Wesley.

Vannucci, S. (2007): “Game Formats as Chu Spaces,” International Game Theory Review, 9, 119–138.

von Neumann, J., and O. Morgenstern (1944): Theory of Games and Economic Behavior. Princeton.