[1912.03295v1] Tools for Mathematical Ludology
In this paper we have developed some basic mathematical formalism that allows the compact description of complex, finite discrete games, with notation that helps to expose their structure for later comparison and analysis

*Abstract We propose the study of mathematical ludology, which aims to formally interrogate questions of interest to game studies and game design in particular. The goal is to extend our mathematical understanding of complex games beyond decision-making—the typical focus of game theory and artificial intelligence efforts—to explore other aspects such as game mechanics, structure, relationships between games, and connections between game rules and user-interfaces, as well as exploring related gameplay phenomena and typical player behavior. In this paper, we build a basic foundation for this line of study by developing a hierarchy of game descriptions, mathematical formalism to compactly describe complex discrete games, and equivalence relations on the space of game systems.
‹Figure 1: The game description hierarchy. We focus on Underlying Game Systems in this paper. (Game Description Hierarchy)Figure 2: The game tree for the coin flipping game system in ??, with all nodes and edges fully labeled: the root state node with state (−)coin, the decision edge with tuple (flip, flip), the chance edges both with probability 1/2, and the terminal state nodes (heads)coin (outcome: P1 win) and (tails)coin (outcome: P2 win). Solid nodes are state nodes, while the open node is a chance node. (Game Trees and Automata)Figure 3: The game tree for the guessing game system in ??, with only a few state nodes and decision edges labeled, for brevity. Each of the five bottom subtrees have the same five decision tuples on their edges: (0, 1P2), (0, 2P2), . . . , (0, 5P2). There are no chance nodes; this is a deterministic game. (Game Trees and Automata)Figure 4: “Magic square” correspondence between the arithmetic and grid-based versions of tic-tac-toe. (Examples with Structured Notation)Figure 5: Sample illustration of a decision matrix. (Game Tree Correspondences and Equivalence)Figure 7: These are two full game trees, with state labels suppressed, outcomes oi on each terminal node, probabilities (1/3 and 2/3) on chance edges, and decision edges labeled with decision matrix outcomes instead of sets of decision tuples, for brevity (e.g., as ?? relabels ??). All decision matrices are illustrated on non-terminal state nodes. Some (but not all) of the decision matrices match: A ∼ A0 , B 6∼ B0 , C ∼ C0 , and D 6∼ D0 . However, all of them match after reduction by ??: in particular, B red. ∼ B0 , D red. ∼ D0 (the blank matrix B is a decision matrix with empty domain). In fact, B (D) is the reduced form of B0 (D0 ), after some relabeling. Thus, after these reductions, the trees have matching decision matrices (??) under the player correspondence P1 ↔ p2 and P2 ↔ p1. Incidentally, because the probabilities also correspond and the outcomes are similarly distinct, these trees are equivalent up to relabeling (??) after appropriate reductions: i.e., the two trees are agency equivalent (??). (Game Tree Correspondences and Equivalence)Figure 8: Bookkeeping subtree reduction example. Dotted lines highlight the bookkeeping subtrees before and after being reduced, exemplifying the different cases in ??. Solid dots are state nodes, circles are chance nodes, and chance edges are labeled with probabilities pi. The labels on most state nodes and all decision edges have been omitted. Dashed lines connect to other parts of the game tree. (Game Tree Reductions)Figure 9: Single-player subtree reduction example, illustrating ??. All state nodes, except possibly the leaves, belong to the same player. Internal state node labels have been omitted. Edges have been labeled only with this player’s decisions, for brevity, since all other players take the null decision everywhere. Dashed lines connect to other parts of the game tree. (Game Tree Reductions)›