Firing games and greedoid languages

In an earlier post, I described the dollar game played on a finite graph $G$ , and mentioned (for the “borrowing binge variant”) that the total number of borrowing moves required to win the game is independent of which borrowing moves you do in which order. A similar phenomenon occurs for the pentagon game described in this post.

In this post, I’ll first present a simple general theorem due to Mikkel Thorup which implies both of these facts (and also applies to many other ‘chip firing games’ in the literature). Then, following Anders Björner, Laszlo Lovasz, and Peter Shor, I’ll explain how to place such results into the context of greedoid languages, which have interesting connections to matroids, Coxeter groups, and other much-studied mathematical objects.

Firing games and strong convergence

As motivation for the general theorem, we quickly recall the “borrowing binge” variant of the dollar game. Let $G$ be a connected finite graph with vertex set $V(G)$ . (For simplicity, we assume that $G$ is simple, i.e., that it has no parallel or loop edges.) Let $D = \{ D(v) \}_{v \in V(G)}$ be an initial configuration, which is an assignment of some integer number of dollars to each vertex. A vertex with a negative number of dollars is said to be in debt. A legal move in the game consists of selecting a vertex $v$ which is in debt and then “borrowing” a dollar from each neighbor (which means replacing $D(v)$ with $D(v) + {\rm deg}(v)$ and $D(w)$ , for each neighbor $w$ of $v$ , with $D(w) - 1$ ). The goal of the game is to get every vertex out of debt.

Here is an abstraction of this game. A firing game consists of a set $A$ and a firing rule which assigns to each finite sequence $(a_1,a_2,\ldots,a_k)$ (including the empty sequence $\emptyset$ ) of (not necessarily distinct) elements of $A$ a subset $\lambda(a_1,\ldots,a_k)$ of $A$ . (In the context of the dollar game described in the previous paragraph, $A = V(G)$ and $\lambda(a_1,\ldots,a_k)$ is the set of vertices which are in debt after performing borrowing moves at $a_1, a_2,\ldots a_k$ in that order.)

We think of $\lambda(a_1,\ldots,a_k)$ as the set of “legal moves” in the game once the sequence of moves $a_1,\ldots,a_k$ has been played. More formally, a sequence of legal moves is either a finite sequence $\alpha = (\alpha_1,\ldots,\alpha_k)$ with $\alpha_1 \in \lambda(\emptyset)$ and $\alpha_i \in \lambda(\alpha_1,\ldots,\alpha_{i-1})$ for all $2 \leq i \leq k$ or an infinite sequence $\alpha = (\alpha_1,\alpha_2,\ldots)$ with $\alpha_1 \in \lambda(\emptyset)$ and $\alpha_i \in \lambda(\alpha_1,\ldots,\alpha_{i-1})$ for all $i \geq 2$ .

A legal game is either (i) the empty sequence (if $\lambda(\emptyset) = \emptyset$ ), (ii) a finite sequence of legal moves $\alpha = (\alpha_1,\ldots,\alpha_k)$ with $\lambda(\alpha_1,\ldots,\alpha_k) = \emptyset$ , or (iii) an infinite sequence of legal moves $\alpha = (\alpha_1,\alpha_2,\ldots)$ . For a legal game $\alpha$ , we define ${\rm length}(\alpha)$ to be 0 in case (i), $k$ in case (ii), and $\infty$ in case (iii). We call a legal game finite (or terminating) if it has finite length, and infinite (or non-terminating) otherwise.

A firing game is called strongly convergent if either all legal games are infinite, or all legal games are finite and for every legal game $\alpha$ and every $x \in A$ the natural number $\alpha[x] := \# \{ i \; | \; \alpha_i = x \}$ is independent of $\alpha$ . (In the context of the dollar game, the latter condition means that the number of times each vertex of $G$ performs a borrowing move is independent of the sequence of legal moves played. This, in turn, implies that both the total number of moves and the final configuration of dollars are independent of any choices made, assuming that the game is winnable.) In particular, when the firing game is strongly convergent, all legal firing games have the same length.

Following Thorup, we say that a firing rule is monotone if if for any two finite sequences $(\alpha_1,\ldots,\alpha_k)$ and $(\beta_1,\ldots,\beta_\ell)$ of legal moves such that $\beta[x] \geq \alpha[x]$ for all $x \in A$ and $\beta[a] = \alpha[a]$ for some $a \in A$ , the assertion $a \in \lambda(\alpha)$ implies $a \in \lambda(\beta)$ . Note that the dollar game is monotone, since if Alice plays the sequence of moves $(\alpha_1,\ldots,\alpha_k)$ and Bob plays $(\beta_1,\ldots,\beta_\ell)$ , the conditions $\beta[x] \geq \alpha[x]$ for all $x \in A$ and $\beta[a] = \alpha[a]$ imply that Bob has borrowed from each vertex at least as many times as Alice has, and they have borrowed the same number of times from vertex $a$ . In this case, it’s easy to see that if $a$ is in debt for Alice then it must also be in debt for Bob.

Theorem 1: Every monotone firing game is strongly convergent.

Proof (Thorup): Let $\alpha = (\alpha_1,\ldots,\alpha_m), \beta = (\beta_1,\ldots,\beta_n)$ be legal games. Without loss of generality, we may assume that $\lambda(\emptyset) \neq \emptyset$ and that $m = {\rm length}(\alpha) \geq n = {\rm length}(\beta)$ . We need to show that $\alpha[x] = \beta[x]$ for every $x \in A$ .

If $\alpha[x] \leq \beta[x]$ for all $x \in A$ then we’re done. So assume, for the sake of contradiction, that this is not the case. Let $k$ be the smallest index such that $(\alpha_1,\ldots,\alpha_{k+1})[a] > (\beta_1,\ldots,\beta_{k+1})[a] = (\beta_1,\ldots,\beta_n)[a]$ for some $a \in A$ . Then $a = \alpha_{k+1}$ , $(\beta_1,\ldots,\beta_n)[x] \geq (\beta_1,\ldots,\beta_k)[x] \geq (\alpha_1,\ldots,\alpha_k)[x]$ for all $x \in A$ , and $(\beta_1,\ldots,\beta_n)[a] = (\alpha_1,\ldots,\alpha_k)[a]$ . Moreover, since $(\alpha_1,\ldots,\alpha_{k+1})$ is a legal sequence of moves we must have $a \in \lambda(\alpha_1,\ldots,\alpha_k)$ . By monotonicity, it follows that $a \in \lambda(\beta_1,\ldots,\beta_n)$ , contradicting the fact that ${\rm length}(\beta) = n$ . Q.E.D.

Application to other games

We give three sample applications of Theorem 1:

Consider the same dollar game described above, but where the initial configuration $D$ is allowed to take arbitrary real values, as opposed to integer values, at each vertex. The integrality condition was never used in verifying the hypotheses of Theorem 1, so we conclude that this generalized dollar game is also strongly convergent.
Following Mozes, consider the generalization of the “pentagon game” in which we’re given an $n$ -gon $G$ and an initial configuration $D$ consisting of a real number $D(v)$ for each vertex $v$ of $G$ . This time, a legal move consists of choosing a vertex $v$ with $D(v) < 0$ , and replacing $D(v)$ with $-D(v)$ and each $D(w)$ with $w$ a neighbor of $v$ with $D(w) + D(v)$ . Theorem 1 implies (as originally proved by Mozes by a more complicated argument) that this game is strongly convergent, and in particular that if the game is finite then both the total number of moves and the final configuration are independent of any choices made.
Following Diaconis and Fulton, consider the firing game where for each $a \in A$ we are given an infinite deck of cards, with each card labeled by an element of $A$ . (Technical hypothesis: assume that for any infinite subset $S$ of $A$ , there are infinitely many cards belonging to decks at elements of $S$ which are labeled by elements not in $S$ .) Suppose that a finite number of chips are placed at each element of $A$ , and that to each $x \in A$ we have associated a positive integer $t(x)$ called the tolerance of $x$ . A legal move consists of choosing some $a \in A$ having more than $t(a)$ chips, moving one of the chips at $a$ to the site labeled by the top card of the deck at $a$ , and throwing this card away. Theorem 1 implies (as originally proved by Diaconis and Fulton) that this game is strongly convergent, and in particular that if the game is finite then both the total number of moves and the final configuration are independent of any choices made.

Greedoid languages

Let $A$ be a set, which for simplicity we take to be finite. Let $A^*$ denote the set of all words in the alphabet $A$ , including the empty word $\emptyset$ . (In technical jargon, $A^*$ is the underlying set of the free monoid over $A$ .) By convention, we will use Greek letters $\alpha, \beta,\ldots$ to denote words and Latin letters $x,y,\ldots$ to denote letters.

Notation:

$\alpha\beta$ denotes the concatenation of $\alpha,\beta \in A^*$ .
$|\alpha|$ denotes the length of $\alpha$ .
$[\alpha] : A \to {\mathbb N}$ denotes the letter count of $\alpha$ , i.e., $[\alpha]_x$ is the number of times $x \in A$ appears in $\alpha$ .

A language is a non-empty subset $L$ of words in $A^*$ . A language is called simple if no word contains any repeated letters.

A greedoid language is a language $L$ satisfying the following two axioms:

(Left hereditary) If $\alpha \beta \in L$ then $\alpha \in L$ .
(Augmentation) If $\alpha, \beta \in L$ and $|\alpha| > |\beta|$ , there exists a letter $x \in \alpha$ such that $\beta x \in L$ .

The name comes from the fact that there is a bijection between simple greedoid languages and greedoids.

A maximal word in $L$ is a word $\alpha \in L$ such that $\alpha \beta \in L$ implies $\beta = \emptyset$ . It is possible for the set of maximal words in $L$ to be empty (which implies that there are arbitrarily long words in $L$ ). A basic property of greedoid languages is the following fact, whose proof we leave as an exercise:

Lemma 1: In a greedoid language, any two maximal words have the same length.

Examples of greedoid languages

The following are examples of greedoid languages (the list is by no mean exhaustive):

The language consisting of the empty word, together with all words $\alpha_1 \alpha_2 \cdots \alpha_k$ such that $(\alpha_1,\ldots,\alpha_k)$ is a legal sequence of moves in the (borrowing-only version of the) dollar game associated to a pair $(G,D)$ , is a greedoid language. This language is, in general, not simple. The dollar game is winnable if and only if there exists a maximal word.
If $M$ is a matroid on $E$ , the language whose alphabet is $E$ and whose words are all permutations of independent sets in $M$ is a simple greedoid language.
An antimatroid on $E$ is a non-empty collection of subsets of $E$ , called the feasible sets, such that (i) the union of two feasible sets is feasible, and (ii) if $X$ is a non-empty feasible set, there exists $x \in X$ such that $X \backslash \{ x \}$ is also feasible. If ${\mathcal F}$ is an antimatroid on $E$ , the language whose alphabet is $E$ and whose words are all permutations of feasible sets is a simple greedoid language.
A Coxeter group is a pair $(W,S)$ consisting of a group $W$ and a finite generating subset $S$ such that (i) every element of $S$ has order 2, and (ii) $W$ has a presentation using generators from $S$ and relations of the form $(st)^m = e$ with $s,t \in S$ and $m \geq 1$ . Examples include the symmetries of a regular convex polytope and the Weyl group of a simple complex Lie group. A word $w$ in the alphabet $S$ is reduced if there is no shorter word representing the same element of $W$ . If $(W,S)$ is a finite Coxeter group, the set of reduced words is a (non-simple) greedoid language; this follows from the strong exchange condition, which characterizes Coxeter groups among all groups generated by involutions. In particular, any two maximal reduced words in a Coxeter group have the same length.

The connection to firing games

Björner, Lovasz, and Shor proved a general result about greedoid languages which is similar in spirit to Theorem 1. In order to state their result, we make the following definition:

A language $L$ is called an antimatroid with repetition if it is left-hereditary and satisfies the following additional axioms:

If $\alpha, \beta \in L$ , $[\alpha] = [\beta]$ , and $\alpha x \in L$ then $\beta x \in L$ .
If $\alpha \in L$ and $x,y$ are distinct elements of $A$ with $\alpha x \in L$ and $\alpha y \in L$ , then $\alpha xy \in L$ .

(The reason for the name is that there is a bijection between simple antimatroids with repetion and antimatroids.)

Theorem 2 (Björner-Lovasz-Shor): If $L$ is an antimatroid with repetition, then $L$ is a greedoid language and any two maximal words have the same letter count (i.e., are rearrangements of each other).

This implies Theorem 1, since it is straightforward to check that the language consisting of the empty word, together with all words $\alpha_1 \alpha_2 \cdots \alpha_k$ such that $(\alpha_1,\ldots,\alpha_k)$ is a legal sequence of moves in some monotone firing game, is an antimatroid with repetition.

Concluding remarks:

(1) The greedoid language associated to a matroid or Coxeter group is typically not an antimatroid with repetition. It’s clear that the conclusion of Theorem 2 is not true for matroids, since maximal words correspond to bases. An example of a Coxeter group whose associated language is not an antimatroid with repetition is the symmetric group $W = S_3$ with $S = \{ a=(12), b=(23) \}$ . In this case, $L = \{ \emptyset, a, b, ab, ba, aba, bab \}$ , and in particular $aba$ and $bab$ are maximal words which are not rearrangements of one another.

(2) There are many greedoids which are neither matroids nor antimatroids. For example, let $G$ be a directed graph rooted at $r$ . Then the edge sets of directed subtrees rooted at $r$ and directed away from $r$ are the feasible sets of a greedoid which is neither a matroid nor an antimatroid. For many more examples, theorems, and motivation (including an explanation for the name “greedoid”), see this survey paper by Björner and Lovasz.

(3) The greedoids associated to both matroids and antimatroids are examples of interval greedoids, which Chan and Pak have recently shown (using a completely new method) satisfy log-concavity properties analogous to those established by Adiprasito-Huh-Katz, Brändén-Huh, et. al. in their celebrated work on combinatorial Hodge theory. Interval greedoids can be thought of as simple greedoid languages satisfying the following strong augmentation property:

(Strong augmentation) If $\alpha, \beta \in L$ and $|\alpha| > |\beta|$ , then $\alpha$ contains a subword $\alpha'$ of length $|\alpha| - |\beta|$ such that $\beta \alpha' \in L$ .

(Here $\alpha'$ is a subword of $\alpha = a_1 \cdots a_k$ if $\alpha' = a_1 \cdots \hat{a}_{i_1} \cdots \hat{a}_{i_j} \cdots a_k$ for some indices $1 \leq i_1 < \cdots i_j \leq k$ .) Examples of greedoid languages satisfying the strong augmentation property include matroid languages, antimatroids with repetition (so in particular the greedoid languages coming from monotone firing games), and the greedoid languages associated to a Coxeter group.

(4) There is a generalization of the $n$ -gon game called the “numbers game” which Eriksson has shown to be intimately related to the theory of Coxeter groups. In this related paper, Eriksson presents a theorem and proof very similar to Theorem 1 above which he discovered independently of Thorup.

(5) There is a series of papers by Bond and Levine on Abelian networks which provides another general framework for understanding strongly convergent games.

Matt Baker's Math Blog

Thoughts on number theory, graphs, dynamical systems, tropical geometry, pedagogy, puzzles, and the p-adics

Firing games and greedoid languages

Leave a comment Cancel reply

Share this:

Related

Leave a comment Cancel reply