The Dynamics of Debt

Consider a chain of companies linked by trade credit. In this case, a supplier extends credit to a manufacturer, the manufacturer to a distributor, and the distributor to a retailer, with additional cross-credit occurring between some of them. Some firms hold cash, while others carry net debt. The system is dynamic: a company in distress might receive payment from a neighbor or extend credit to stabilize the chain. The central question is one of global stability. Given this topology of who trades with whom, and an initial distribution of cash and debt, is there a sequence of payments (or debt restructurings) that restores solvency to every company (i.e., node) in the network?

Until now, simulating these complex, cascading network dynamics required researchers to rely on manual calculations or bespoke, computationally expensive scripts. The open-source chipfiring Python package [5] changes this paradigm by providing a standardized and highly-optimized software ecosystem that makes the simulation and analysis of these discrete network flows accessible, visual, and computationally tractable at scale.

Chip-firing sits at the intersection of combinatorics, physics (specifically self-organized criticality), and algebraic geometry. Despite the successes that came with the generalized Riemann-Roch theorem for graphs, which identified structural relationships between discrete topologies [1], the bridge between theoretical abstraction and experimental verification has historically been precarious. By standardizing the algorithms used in previous systems, the chipfiring package enables researchers to cast their hypotheses onto complex graph structures, bringing mathematical capabilities from ad-hoc analysis to robust experimentation. 

The Abstraction: From Supply Chains to Matrices

In the language of the software, a network is modeled as a multigraph, and the distribution of resources across that network is called a divisor — a term borrowed from algebraic geometry that hints at the deep connections between discrete games and the study of algebraic curves [2].

The rules of this economy are purely local. A move occurs when a vertex either simultaneously lends to or borrows from all of its neighbors. Mathematically, the system’s transitions are represented using discrete Laplacian matrices. This formulation reveals the system’s Abelian property, as the order in which nodes lend or borrow does not alter the final state. This critical property transforms what could be a chaotic, path-dependent sequence of transactions into a structured algebraic problem, allowing the software to definitively answer if a configuration is “winnable,” i.e, it can reach a state where no node is in debt.

Automating the Firefighters: Dhar’s Algorithm

Determining if a game is winnable by brute force is highly inefficient due to the combinatorial explosion of possible moves. To solve this, the chipfiring package implements Dhar’s Algorithm, a method originally motivated by the study of sandpile models in physics [3].

The algorithm employs a vivid “burning” metaphor that is modeled directly in the software’s architecture. To test the stability of a network configuration, the system designates a specific node as the “sink” and imagines setting it on fire. The edges of the graph act as combustible material, attempting to carry the fire to neighboring nodes. However, each node is defended by “firefighters,” which represent the amount of cash currently held at that vertex.

As the fire attempts to spread, the defenses are tested. If a node possesses more cash than the number of incoming burning edges, the firefighters hold the line, and the node remains safe. If the cash is insufficient, the defense fails, the node burns, and the fire propagates further to its neighbors. If the fire consumes the entire graph, the financial configuration is deemed globally unstable. However, if the fire is contained, the unburnt nodes form a “legal firing set,” a specific group of companies that can simultaneously extend credit to stabilize the network without driving themselves into insolvency. Crucially, the algorithm returns an acyclic orientation of the graph, leaving a topological footprint of how the fire traveled, which is essential for researchers who aim to study the geometric properties of the network.

Algorithmic Benevolence and Efficiency

Beyond standard stability checks, the package introduces efficient algorithms for “winnability determination.” A key strategy implemented is the notion of \(q\)-reduction or “benevolence” [5]. In a financial network, this strategy asks if an one “benevolent” institution (vertex \(q\)) could volunteer to absorb all the debt in the system and dictate how it would impact the network. The algorithm concentrates all system debt onto \(q\) and iteratively checks if the remaining nodes can “bail out” \(q\) through a sequence of moves.

The package includes a specialized efficient winnability determination (EWD) module. Instead of random firing, EWD employs a reverse-distance prioritized approach [5]. It calculates a breadth-first search (BFS) from the source node and processes debt strictly from the furthest nodes inward. This ensures that once a peripheral node becomes solvent, it remains solvent, thus preventing the redundant cycles of debt that easily choke naive, brute-force scripts. This optimization allows the software to handle graphs of significant size and complexity.

From Simulation to Research: Rank and Gonality

While the underlying game makes for an excellent pedagogical puzzle, chipfiring is built to handle rigorous research demands, particularly regarding graph gonality [2].

Gonality is a measure of a graph’s complexity, defined as the minimum degree of a divisor with a rank of at least one. In the supply chain analogy, “rank” measures the robustness of a network’s solvency: a rank of \(k\) means the network can remain solvent even if \(k\) arbitrary units of cash are removed from the system. 

Calculating rank is an non-deterministic polynomial-time hard problem for general graphs. For years, mathematicians relied on manual calculations for small graphs or wrote one-off, unoptimized scripts for specific research questions. The lack of tools created a barrier to entry; one could not easily test a hypothesis on a graph with hundreds of nodes or verify edge cases on complex topologies like “chains of loops” or fractal-like structures. By heavily optimizing the underlying firing algorithms, the chipfiring package makes these computations tractable for significant families of graphs.

Accessibility and Verification

A core design philosophy of chipfiring is accessibility. The tool leverages the Python ecosystem to easily integrate existing data science workflows with pip install chipfiring. For further intuition-building, the package includes an interactive, web-based visualizer that allows users to manually step through firing sequences, observe Dhar’s algorithm spreading in real-time, and visually track the flow of resources across the network.

While the Python package focuses on simulation and experimentation, we have paralleled this work with the first-ever formal verification framework in Lean 4, a functional programming language and theorem prover. ChipFiringWithLean formally verifies the correctness of the chip-firing dynamics and the Riemann-Roch theorem itself. While the Python package allows for rapid hypothesis testing, the Lean formalization ensures that the underlying mathematical logic is unassailable [4]. 

Conclusion & Try It Out!

The bridge between abstract graph theory and computational implementation has often been precarious. With chipfiring, we aim to solidify this connection and provide a standardized, efficient, and visual set of tools for the applied mathematics community. Whether you are a student trying to win a chip-firing game with your friends, an applied mathematician modeling financial stability, or an algebraic geometer investigating the moduli space of tropical curves, chipfiring offers the algorithmic machinery to let you focus on the mathematics.

The package is open source and available on PyPI and GitHub. We invite the SIAM community to experiment with it, contribute to the codebase, and explore the fascinating dynamics of debt and benevolence on graphs.

References
[1] Baker, M. & Norine, S. (2007). Riemann–Roch and Abel–Jacobi theory on a finite graph. Adv. Math., 215(2), 766-788.
[2] Corry, S. & Perkinson, D. (2018). Divisors and Sandpiles: An Introduction to Chip-Firing. Providence, Rhode Island: American Mathematical Society.
[3] Dhar, D. (1990). Self-organized critical state of sandpile automaton models. Phys. Rev. Lett., 64(14), 1613. 
[4] Mavani, D.D. (2025). Lean4 Machine Assisted Proof Framework for Chip Firing Game & Graphical Riemann-Roch [Undergraduate thesis, Department of Mathematics and Statistics, Amherst College].
[5] Mavani, D.D., Ji, T., & Pflueger, N. (2025). chipfiring: A Python package for efficient mathematical analysis of chip-firing games on multigraphs. Preprint, arXiv:2508.00269.