Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userExtended Sprague-Grundy theory for locally finite games, and applications to random game-trees
59
0
0.0
(
0
)
Authors
James B. Martin
Ask ChatGPT about the research
No Arabic abstract
For a collection of papers in memory of Elwyn Berlekamp (1940-2019), John Conway (1937-2020), and Richard Guy (1916-2020). The Sprague-Grundy theory for finite games without cycles was extended to general finite games by Cedric Smith and by Aviezri Fraenkel and coauthors. We observe that the same framework used to classify finite games also covers the case of locally finite games (that is, games where any position has only finitely many options). In particular, any locally finite game is equivalent to some finite game. We then study cases where the directed graph of a game is chosen randomly, and is given by the tree of a Galton-Watson branching process. Natural families of offspring distributions display a surprisingly wide range of behaviour. The setting shows a nice interplay between ideas from combinatorial game theory and ideas from probability.
rate research
Read More
We analyze the Sprague-Grundy functions for a class of almost disjoint selective compound games played on Nim heaps. Surprisingly, we find that these functions behave chaotically for smaller Sprague-Grundy values of each component game yet predictably when any one heap is sufficiently large.
The concept of nimbers--a.k.a. Grundy-values or nim-values--is fundamental to combinatorial game theory. Nimbers provide a complete characterization of strategic interactions among impartial games in their disjunctive sums as well as the winnability. In this paper, we initiate a study of nimber-preserving reductions among impartial games. These reductions enhance the winnability-preserving reductions in traditional computational characterizations of combinatorial games. We prove that Generalized Geography is complete for the natural class, $cal{I}^P$ , of polynomially-short impartial rulesets under nimber-preserving reductions, a property we refer to as Sprague-Grundy-complete. In contrast, we also show that not every PSPACE-complete ruleset in $cal{I}^P$ is Sprague-Grundy-complete for $cal{I}^P$ . By considering every impartial game as an encoding of its nimber, our technical result establishes the following striking cryptography-inspired homomorphic theorem: Despite the PSPACE-completeness of nimber computation for $cal{I}^P$ , there exists a polynomial-time algorithm to construct, for any pair of games $G_1$, $G_2$ of $cal{I}^P$ , a prime game (i.e. a game that cannot be written as a sum) $H$ of $cal{I}^P$ , satisfying: nimber($H$) = nimber($G_1$) $oplus$ nimber($G_2$).
We present a bijection between some quadrangular dissections of an hexagon and unrooted binary trees, with interesting consequences for enumeration, mesh compression and graph sampling. Our bijection yields an efficient uniform random sampler for 3-connected planar graphs, which turns out to be determinant for the quadratic complexity of the current best known uniform random sampler for labelled planar graphs [{bf Fusy, Analysis of Algorithms 2005}]. It also provides an encoding for the set $mathcal{P}(n)$ of $n$-edge 3-connected planar graphs that matches the entropy bound $frac1nlog_2|mathcal{P}(n)|=2+o(1)$ bits per edge (bpe). This solves a theoretical problem recently raised in mesh compression, as these graphs abstract the combinatorial part of meshes with spherical topology. We also achieve the {optimal parametric rate} $frac1nlog_2|mathcal{P}(n,i,j)|$ bpe for graphs of $mathcal{P}(n)$ with $i$ vertices and $j$ faces, matching in particular the optimal rate for triangulations. Our encoding relies on a linear time algorithm to compute an orientation associated to the minimal Schnyder wood of a 3-connected planar map. This algorithm is of independent interest, and it is for instance a key ingredient in a recent straight line drawing algorithm for 3-connected planar graphs [bf Bonichon et al., Graph Drawing 2005].
We consider the localization game played on graphs in which a cop tries to determine the exact location of an invisible robber by exploiting distance probes. The corresponding graph parameter $zeta(G)$ for a given graph $G$ is called the localization number. In this paper, we improve the bounds for dense random graphs determining an asymptotic behaviour of $zeta(G)$. Moreover, we extend the argument to sparse graphs.
In this note, we present a compatibility test based on John Nashs game-theoretic notion of equilibrium strategy. The test must be taken separately by both partners, making it difficult for either partner alone to control the outcome. The mathematics behind the test including Nashs celebrated theorem and an example from the film, A Beautiful Mind, are discussed as well as how to customize the test for more accurate results and how to modify the test to evaluate interpersonal relationships in other settings, not only romantic. To investigate the long-term dynamics of give and take in a relationship we introduce the iterated dating dilemma and apply the notion of zero-determinant payoff strategy introduced by Dyson and Press in 2012 for the iterated prisoners dilemma.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
