Abstract
This paper introduces Cumulative Games, a novel framework that bridges the gap between Combinatorial Game Theory (CGT) and Economic Game Theory (EGT). By extending CGT's powerful "disjunctive sum" and "outcome functions" to $n$-player, general-sum settings, the authors provide a unified way to represent and efficiently solve complex games that were previously difficult to analyze.
Introduction
For decades, Game Theory has been split into two largely independent branches. Combinatorial Game Theory (CGT) focuses on "recreational" games like Nim or Go. These are typically two-player, zero-sum, and have perfect information. CGT is famous for its recursive structures and the "disjunctive sum," which allows players to combine independent game components. In contrast, Economic Game Theory (EGT) focuses on self-interested agents in $n$-player, general-sum scenarios, such as auctions or market competition. EGT typically utilizes "Extensive Form Games" (EFGs)—large trees representing every possible move—and focuses on finding Nash Equilibria.
The challenge lies in the fact that EFG representations are often "excessively large and inefficient" for games with combinatorial structures, such as multiple heaps of items. Conversely, standard CGT tools do not naturally handle the general-sum, multi-player incentives found in economic contexts. This research seeks to bridge this conceptual and technical divide by introducing Cumulative Games.
The Cumulative Game Framework
The authors propose a three-layered structure for Cumulative Game Forms (CGF) to reconcile the differences between the two fields:
- Layer 1 (Heap Space): This defines the physical state of the game, such as the number of pebbles in a heap and the "pockets" (cumulations) of each player.
- Layer 2 (Heap Position/Ruleset): This layer defines the available moves and rewards, independent of whose turn it is. This mirrors the CGT approach where a position is neutral until a player is assigned.
- Layer 3 (Grounded Position): This adds the "grounding" details—the specific turn function (who moves next) and the starting player.
By treating the "turn function" as a separate layer, the framework addresses the fundamental question: "Who is the current player?" In EGT, every node in a game tree is pre-assigned to a player. In Cumulative Games, the position remains abstract until grounded, allowing for more flexible analysis of turn-taking dynamics.
Strategic Outcomes and Efficiency
A central contribution of the paper is the generalized outcome function. This function can compute utilities for any strategy profile, including Pure Subgame Perfect Equilibrium (PSPE). Crucially, the authors extend the disjunctive sum operator to these $n$-player games. This allows a player to choose which "component" (e.g., which heap) to move in during their turn, a hallmark of CGT now applied to general-sum settings.
The authors identify a subclass called Heap Dynamic games. In these games, moves and rewards depend only on the heap size, not on the current accumulation of pebbles by the players. For these games, the paper proves that equilibrium outcomes can be computed using a "tabular approach" (dynamic programming). This method is linear in heap size, offering a significant performance advantage over traversing an exponential game tree.
Universality and Economic Modeling
The framework's power is demonstrated through several key results:
- Theorem 6 (Outcome-Utility Connection): Proves that the generalized outcome function correctly finds the vector of game values (utilities) for self-interested players in PSPE.
- Theorem 8 (Efficient Outcome): Demonstrates the recursive dynamic programming algorithm for Heap Dynamic games.
- Theorems 11 & 12 (Strategic Equivalence): Establish that any Extensive Form Game can be rewritten as a single-heap Cumulative Game. This proves the framework is universal and not limited to simple "pebble games."
Furthermore, by allowing general-sum utilities, the authors can model classic economic problems like the "Tragedy of the Commons" within a combinatorial framework. This shows how individual incentives can lead to sub-optimal resource depletion in a structured, sequential environment.
Limitations and Future Work
While the framework is robust, it currently focuses on deterministic games. It does not yet include "nature nodes" (chance moves), hidden information, or simultaneous moves, which are common in many EGT applications. Additionally, the authors note that in the broader class of Cumulative Games, many games may be "incomparable," making the search for a simple "game value" (a common goal in CGT) more difficult.
Future research directions include exploring "Wealth Games," where rules depend on current cumulations, and games with cycles (infinite play). By continuing to merge these two fields, the authors aim to provide even more efficient tools for analyzing complex strategic interactions.
Summary updated