A Category for Extensive-Form Games
This paper introduces Gm, which is a category for extensive-form games. It also provides some applications. The category's objects are games, which are understood to be sets of nodes which have been endowed with edges, information sets, actions, players, and utility functions. Its arrows are functions from source nodes to target nodes that preserve the additional structure. For instance, a game's information-set collection is newly regarded as a topological basis for the game's decision-node set, and thus a morphism's continuity serves to preserve information sets. Given these definitions, a game monomorphism is characterized by the property of not mapping two source runs (plays) to the same target run. Further, a game isomorphism is characterized as a bijection whose restriction to decision nodes is a homeomorphism, whose induced player transformation is injective, and which strictly preserves the ordinal content of the utility functions. The category is then applied to some game-theoretic concepts beyond the definition of a game. A Selten subgame is characterized as a special kind of categorical subgame, and game isomorphisms are shown to preserve strategy sets, Nash equilibria, Selten subgames, subgame-perfect equilibria, perfect-information, and no-absentmindedness. Further, it is shown that the full subcategory for distinguished-action sequence games is essentially wide in the category of all games, and that the full subcategory of action-set games is essentially wide in the full subcategory for games with no-absentmindedness.
Code (0)
등록된 구현이 없습니다.
Tasks
FormSimilar Papers 제목 키워드 기반
The Category of Node-and-Choice Extensive-Form Games
This paper develops the category $\mathbf{NCG}$. Its objects are node-and-choice games, which include essentially all extensive-form games. Its morphisms allow arbitrary transformations of a game's nodes, choices, and pl…
FormTowards Functorial Language-Games
In categorical compositional semantics of natural language one studies functors from a category of grammatical derivations (such as a Lambek pregroup) to a semantic category (such as real vector spaces). We compositional…
The Category of Node-and-Choice Forms, with Subcategories for Choice-Sequence Forms and Choice-Set Forms
The literature specifies extensive-form games in many styles, and eventually I hope to formally translate games across those styles. Toward that end, this paper defines $\mathbf{NCF}$, the category of node-and-choice for…
FormAutomatic Bug Detection in Games using LSTM Networks
We introduced a new framework to detect perceptual bugs using a Long Short-Term Memory (LSTM) network, which detects bugs in video games as anomalies. The detected buggy frames are then clustered to determine the categor…
FPS GamesConversation Games and a Strategic View of the Turing Test
Although many game-theoretic models replicate real interactions that often rely on natural language, explicit study of games where language is central to strategic interaction remains limited. This paper introduces the \…