Lattice games without rational strategies

DOI10.1016/J.JCTA.2011.10.005zbMATH Open1356.91033arXiv1106.1883OpenAlexW2001471083WikidataQ57432796 ScholiaQ57432796MaRDI QIDQ654900FDOQ654900

Authors: Alex Fink 

Publication date: 23 December 2011

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: We show that the lattice games of Guo and Miller support universal computation, disproving their conjecture that all lattice games have rational strategies. We also state an explicit counterexample to that conjecture: a three dimensional lattice game whose set of winning positions does not have a rational generating function.

Full work available at URL: https://arxiv.org/abs/1106.1883

Recommendations

• Lattices of games
• scientific article; zbMATH DE number 4059172
• scientific article; zbMATH DE number 912638
• The lattice structure of \(n\)-player games
• Algorithms for lattice games
• Hybrid Systems: Computation and Control
• On games without approximate equilibria
• scientific article; zbMATH DE number 4055409
• scientific article; zbMATH DE number 1944386
• Game Theory without Decision-Theoretic Paradoxes

zbMATH Keywords

cellular automatacombinatorial gameslattice gamescomputational universality

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Cellular automata (computational aspects) (68Q80) Positional games (pursuit and evasion, etc.) (91A24) Combinatorial games (91A46)

Cites Work

• Simple Computation-Universal Cellular Spaces
• Misère quotients for impartial games
• Title not available (Why is that?)
• Short rational generating functions for lattice point problems
• Lattice point methods for combinatorial games

Cited In (10)

• The cardinality of the sets involved in lattice games
• A cellular automaton for blocking queen games
• On lattices from combinatorial game theory: infinite case
• Subtraction games in more than one dimension
• Combinatorics of \textsc{jenga}
• Affine stratifications from finite misère quotients.
• Algorithms for lattice games
• The Ungar games
• Impartial games emulating one-dimensional cellular automata and undecidability
• From heaps of matches to the limits of computability

This page was built for publication: Lattice games without rational strategies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q654900)