A Rota–Baxter equation for winning games

Games as recursive coalgebras and integral invariants

Ryuya Hora

Assistant professor at ZEN University

September 29, 2026

ItaCa Fest 2026

Partially based on joint work with Ryo Suzuki.

Slides

The (too simplified) dichotomy in this talk

Motivation (1/2): Game-theoretic context

We want to win games! (cf. Circular Nim)

study interactions between algebras and recursions

Circular Nim remains unsolved (Kadam–Dufour–Heubach 2026).

cf. Joyal 1977 (English translation); Honsell and Lenisa 2009

I am an organizer of the Japan Combinatorial Game Theory Workshop (JCGTW).

Motivation (2/2): Today: Providing a phenomenon

This talk aims to provide a game-theoretic phenomenon:

Summary of this talk

The winning strategy for Nim comes from a “differential structure” on a category of “games” ( recursive coalgebras) and an “integral structure” on .

How does this phenomenon connect with game semantics, internal logic, double categories, toposes, or species?

I would appreciate your insights!

1
Play vs Analysis: Rota–Baxter equation in Game theory!
- Preliminaries: Winning Nim!
- Impartial Games
2
Coalgebra vs Algebra: Category of games as recursive coalgebras
- Preliminaries: Coalgebra-Algebra morphisms
- Games as recursive coalgebras
3
Differentiation vs Integration: Differential -rig of pointed game families
- Differential -rig of games
- Invariants in Rota–Baxter rig
- Examples Winning nim!

1
Play vs Analysis: Rota–Baxter equation in Game theory!
- Preliminaries: Winning Nim!
- Impartial Games
2
Coalgebra vs Algebra: Category of games as recursive coalgebras
- Preliminaries: Coalgebra-Algebra morphisms
- Games as recursive coalgebras
3
Differentiation vs Integration: Differential -rig of pointed game families
- Differential -rig of games
- Invariants in Rota–Baxter rig
- Examples Winning nim!

Nim (1/2): Rule of -heap nim

heaps of stones are given.
Two players take turns choosing one heap and removing at least one stone from that heap.
The player who is unable to take a stone loses.

Nim (2/2): Bouton's winning strategy

Definition (Nim-sum)

The Nim-sum is a binary operation on defined by the “bit-wise xor.”

Theorem ([Bouton, 1901])

A state of -heap nim is a winning state for the player who moves into it (a “P-position”) if and only if .

... Where is category theory?

Definitions (1/3): (Today's) Games

Definition ((Impartial) Game)

A game is a pair of a (possibly infinite) set and a binary relation that satisfies the following two finiteness conditions

(finite options) is finite, for any .
(finite time) There is no infinite path .

Example (Nim)

The -heap nim is defined by

Definitions (2/3): Box product of games (+ Leibniz rule)

Definition (Box product a.k.a. Conway “addition”)

The box product of two games, and , is the game , where

the underlying set is the cartesian product , and
the relation is defined by

...?

Example (Nim)

Definitions (3/3): Mex, Grundy number and Rota–Baxter eq.

Definition (mex)

The mex of a finite subset is .

Definition (Grundy number)

For a game , the Grundy number is recursively defined by

Proposition (Grundy number is enough to win!)

For a game , a state is a winning state for the player who moves into it if and only if .

Analyze backwards!

Rota–Baxter equation in Bouton's theorem!

Theorem (Sprague–Grundy; see Siegel 2013)

For two games and , we have

Since , this recovers Bouton's winning strategy for Nim.

Sketch of the proof

The only non-trivial part is that, for any ,

This is a Rota–Baxter equation!

There is an analogy here, so there should be category theory behind it.

1
Play vs Analysis: Rota–Baxter equation in Game theory!
- Preliminaries: Winning Nim!
- Impartial Games
2
Coalgebra vs Algebra: Category of games as recursive coalgebras
- Preliminaries: Coalgebra-Algebra morphisms
- Games as recursive coalgebras
3
Differentiation vs Integration: Differential -rig of pointed game families
- Differential -rig of games
- Invariants in Rota–Baxter rig
- Examples Winning nim!

Coalgebras (1/2): Coalgebras and Algebras of an endofunctor

Definition (-Algebras and -Coalgebras)

For a category and an endofunctor ,

A -coalgebra is a pair of an object of and a morphism .
A -algebra is a pair of an object of and a morphism .

Today, we consider

and
: The covariant finite powerset functor.

Coalgebras (2/2): Recursive coalgebra

Definition (Coalgebra-algebra morphism)

A coalgebra-algebra morphism from a -coalgebra to a -algebra is a morphism in such that the following diagram commutes.

Definition (Recursive coalgebra)

A -coalgebra is recursive if for any -algebra , there uniquely exists a coalgebra-algebra morphism .

Osius (1974); Taylor (1999, §6.3).

Games = Recursive -coalgebras

Definition (Games as Recursive coalgebras)

(Today,) we define a category of games to be the category of recursive -coalgebras.

Obs 1.: Defining , recursive -coalgebras are exactly the “games” defined in Section 1.
Obs 2.
Obs 3.: Many other “game values” are induced by -algebras. (cf. Bašić et al. 2024)
Obs 4.: Every game morphism preserves all game values induced by a -algebra.
Obs 5.: For a -algebra morphism , the unique evaluations satisfy .
Thus Grundy numbers determine outcomes via the algebra morphism (: next player loses).

Unlike general graph homomorphisms, game morphisms preserve edges and also lift every outgoing edge (Adámek 2005, Example 2.7).

Categorical structures of games

The category of games has good categorical properties, including:

Proposition ( is a l.f.p. s.m.c.c. w/ a subobject classifier)

The category of games is locally finitely presentable.
- In particular, it is complete and cocomplete.
The box product is a symmetric monoidal closed structure on .
has a subobject classifier.

My context: [Hora 2025]

I have given a way to calculate “game values” induced by any -algebra and any monoidal structure on (which makes the forgetful functor lax monoidal).
This talk is about “Question 5.1” in the preprint.

1
Play vs Analysis: Rota–Baxter equation in Game theory!
- Preliminaries: Winning Nim!
- Impartial Games
2
Coalgebra vs Algebra: Category of games as recursive coalgebras
- Preliminaries: Coalgebra-Algebra morphisms
- Games as recursive coalgebras
3
Differentiation vs Integration: Differential -rig of pointed game families
- Differential -rig of games
- Invariants in Rota–Baxter rig
- Examples Winning nim!

Diff. of games (1/2): Differential operator on

Definition (Pointed games)

A pointed game is a pair of a game and a state .

We write

for the category of pointed games, and
for the category of finite families of pointed games.

Definition (Differential operator)

We define the differential operator by (linearly extending)

Diff. of games (2/2): Leibniz rule for Box product

has

addition: = formal sum of families
multiplication: = (indexwise) box product.

Proposition ( forms a differential -rig!)

The differential operator satisfies the categorified Leibniz rule:

(cf. Joyal 1981, Loregian and Trimble 2023)

Integral rigs (1/2): Definition and “Generating function”

Definition (Integral rig)

An integral rig is a rig with a map (not assumed additive) satisfying and — a non-additive, unital variant of Rota–Baxter operators of weight .

Definition (“Generating function”)

Let be an integral rig. For a pointed game , we recursively define by

We extend linearly to finite families by summing their values.

Integral rigs (2/2): respects the rig structure.

The following “theorems” are easily proven.

Theorem ( is a rig homomorphism)

This assignment preserves the rig operations:

Theorem

In addition, if an integral rig is equipped with a unary operator preserving finite sums satisfying (“Fundamental theorem of calculus”), we also have

Examples (1/3): -functions

Example ()

	const. at
	const. at

The “generating function” is the actual
generating function of the -turn plays.

(This reminds me of Joyal's species...)

Examples (2/3): Nim-sum and form an integral rig

The Rota–Baxter equation

is a part of the following structure.

Example ()





	does not exist

Theorem ( as integration)

This makes into an integral rig.

The induced generating function recovers the Grundy number: .

Since is multiplicative (p. 22) and (p. 10), ; Obs. 5 then gives

Corollary

Bouton's winning strategy for Nim!

Examples (3/3): Hereditarily finite sets

Let be the set of all hereditarily finite sets.

Example ()




	complicated

Capretta, Uustalu and Vene (2006), Props. 2 and 7

Remark (Why ?)

For any monoid , there is a bij. corresp. between

locally nilpotent differential operators on the rig , and
-enrichment of

This talk in one slide

Box product satisfies the Leibniz rule, and mex and the Nim-sum satisfy the Rota–Baxter equation.
Games are recursive coalgebras, and Grundy numbers^* arise as unique coalgebra–algebra morphisms.
The classical winning strategy for Nim follows from this calculus.

Questions

Which parts of existing category theory does this connect with?

^*or any other “recursively defined” value.

References

Bašić, Bojan et al. (2024). “Categories of impartial rulegraphs and gamegraphs”. In: International Journal of Game Theory 53.4, pp. 1407–1433. doi: 10.1007/s00182-024-00921-3.
Bouton, Charles L. (1901). “Nim, a game with a complete mathematical theory”. In: Annals of Mathematics 3.1/4, pp. 35–39. doi: 10.2307/1967631.
Honsell, Furio and Marina Lenisa (2009). “Conway games, coalgebraically”. In: Algebra and Coalgebra in Computer Science. CALCO 2009. Vol. 5728. Lecture Notes in Computer Science. Springer, pp. 300–316. doi: 10.1007/978-3-642-03741-2_21.
Hora, Ryuya (2025). “Games as recursive coalgebras: A categorical view on the Nim-sum”. In: arXiv:2510.22886.
Joyal, André (1977). “Remarques sur la théorie des jeux à deux personnes”. In: Gazette des sciences mathématiques du Québec 1.4, pp. 46–52. English translation by Robin Houston (2003).
— (1981). “Une théorie combinatoire des séries formelles”. In: Advances in Mathematics 42.1, pp. 1–82. doi: 10.1016/0001-8708(81)90052-9.
Kadam, Balaji R., Matthieu Dufour and Silvia Heubach (2026). “The Invariance Reduction Process — a New Tool to Solve Circular Nim and Related Games”. arXiv:2604.02587.
Loregian, Fosco and Todd Trimble (2023). “Differential 2-rigs”. In: Electronic Proceedings in Theoretical Computer Science 380, pp. 159–182. doi: 10.4204/EPTCS.380.10.
Siegel, Aaron N. (2013). Combinatorial Game Theory. Vol. 146. Graduate Studies in Mathematics. American Mathematical Society. doi: 10.1090/gsm/146.

A Rota–Baxter equation for winning games

The (too simplified) dichotomy in this talk

Motivation (1/2): Game-theoretic context

Motivation (2/2): Today: Providing a phenomenon

Table of Contents

Table of Contents

Nim (1/2): Rule of -heap nim

Nim (2/2): Bouton's winning strategy

Definitions (1/3): (Today's) Games

Definitions (2/3): Box product of games (+ Leibniz rule)

Definitions (3/3): Mex, Grundy number and Rota–Baxter eq.

Rota–Baxter equation in Bouton's theorem!

Table of Contents

Coalgebras (1/2): Coalgebras and Algebras of an endofunctor

Coalgebras (2/2): Recursive coalgebra

Games = Recursive -coalgebras

Categorical structures of games

Table of Contents

Diff. of games (1/2): Differential operator on

Diff. of games (2/2): Leibniz rule for Box product

Integral rigs (1/2): Definition and “Generating function”

Integral rigs (2/2): respects the rig structure.

Examples (1/3): -functions

Examples (2/3): Nim-sum and form an integral rig

Examples (3/3): Hereditarily finite sets

This talk in one slide

References