Cumulative Games: Who is the current player?

Urban Larsson, Reshef Meir, Yair Zick

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.

A game of Nim, a classic combinatorial game involving heaps of pebbles.

The Cumulative Game Framework

The authors propose a three-layered structure for Cumulative Game Forms (CGF) to reconcile the differences between the two fields:

  1. 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.
  2. 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.
  3. 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.

An Extensive Form Game tree for "Squirrel Pebbles," illustrating the complexity of self-interest in a cumulative game.

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

Abstract

Combinatorial Game Theory(CGT)is a branch of Game Theory that has developed largely independently of Economic Game Theory (EGT), and is concerned with deep mathematical properties of two-player zero-sum games recursively defined over various combinatorial structures. The aim of this work is to lay the foundations for bridging the conceptual and technical gaps between CGT and EGT, here interpreted as multiplayer Extensive Form Games, so that they can be treated within a unified framework. More specifically, we introduce a class of $n$-player, general-sum games, called {\sc Cumulative Games}, which can be analyzed using tools from both CGT and EGT. We show how two of the most fundamental definitions of CGT, the outcome function and the disjunctive sum operator, naturally extend to the class of {\sc Cumulative Games}. The outcome function allows for efficient equilibrium computation under certain restrictions, while the disjunctive sum operator lets us define a partial order over games according to the advantage that a given player has. Finally, we show that any Extensive Form Game can be written as a {\sc Cumulative Game}.
BibTeX
@misc{larsson2020cumulative,
  author = {Urban Larsson and Reshef Meir and Yair Zick},
  title = {{Cumulative Games: Who is the current player?}},
  year = {2020},
  eprint = {2005.06326},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2005.06326},
}
Figure