
arXiv: 2112.00522
The following game in a similar formulation to Petri nets and chip-firing games is studied: Given a finite collection of baskets, each has an infinite number of balls of the same value. Initially, a ball from some basket is chosen to put on the table. Subsequently, in each step a ball from the table is chosen to be replaced by some $2$ balls from some baskets. Which baskets to take depend only on the ball to be replaced and they are decided in advance. Given some $n$, the object of the game is to find the maximum possible sum of values $g(n)$ for a table of $n$ balls. In this article, the sequence $g(n)/n$ for $n=1,2,\dots$ will be shown to converge to a growth rate $\lambda$. Furthermore, this value $\lambda$ is also the rate of a structure called pseudo-loop and the solution of a rather simple linear program. The structure and the linear program are closely related, e.g. a solution of the linear program gives a pseudo-loop with the rate $\lambda$ in linear time of the number of baskets, and vice versa with the pseudo-loop giving a solution to the dual linear program. A method to test in quadratic time whether a given $\lambda_0$ is smaller than $\lambda$ is provided to approximate $\lambda$. When the values of the balls are all rational, we can compute the precise value of $\lambda$ in cubic time, using the quadratic time rate test algorithm and the binary search with a special condition to stop. Four proofs of the limit $\lambda$ are given: one just uses the relation between the baskets, one uses pseudo-loops, one uses the linear program and one uses Fekete's lemma (the latest proof assumes a condition on the rule of replacements).
Games on graphs (graph-theoretic aspects), growth, replacements, 500 Naturwissenschaften und Mathematik::510 Mathematik::510 Mathematik, Discrete-time games, 91A50, 05C57, FOS: Mathematics, Mathematics - Combinatorics, game, Combinatorics (math.CO), Games involving graphs
Games on graphs (graph-theoretic aspects), growth, replacements, 500 Naturwissenschaften und Mathematik::510 Mathematik::510 Mathematik, Discrete-time games, 91A50, 05C57, FOS: Mathematics, Mathematics - Combinatorics, game, Combinatorics (math.CO), Games involving graphs
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
