
arXiv: 1609.07048
We introduce and study Minkowski games. These are two-player games, where the players take turns to choose positions in R<sup<d</sup< based on some rules. Variants include boundedness games, where one player wants to keep the positions bounded, and the other wants to escape to infinity; as well as safety games, where one player wants to stay within a prescribed set, while the other wants to leave it. We provide some general characterizations of which player can win such games and explore the computational complexity of the associated decision problems. A natural representation of boundedness games yields coNP-completeness, whereas the safety games are undecidable.
Logique mathématique, FOS: Computer and information sciences, Computer Science - Logic in Computer Science, Control in ℝd, polytopic/arbitrary, Computational Complexity (cs.CC), Control in Rd, 91A44, 68Q25, 68U05, coNP-complete, CoNP-complete, CoNPcomplete, undecidable, Computer Science - Computer Science and Game Theory, Informatique mathématique, Undecidable, Informatique générale, Généralités, (stochastic) determinacy, 004, Logic in Computer Science (cs.LO), Computer Science - Computational Complexity, Polytopic/arbitrary, Determinacy, Control in R^d, determinacy, Computer Science and Game Theory (cs.GT)
Logique mathématique, FOS: Computer and information sciences, Computer Science - Logic in Computer Science, Control in ℝd, polytopic/arbitrary, Computational Complexity (cs.CC), Control in Rd, 91A44, 68Q25, 68U05, coNP-complete, CoNP-complete, CoNPcomplete, undecidable, Computer Science - Computer Science and Game Theory, Informatique mathématique, Undecidable, Informatique générale, Généralités, (stochastic) determinacy, 004, Logic in Computer Science (cs.LO), Computer Science - Computational Complexity, Polytopic/arbitrary, Determinacy, Control in R^d, determinacy, Computer Science and Game Theory (cs.GT)
| 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). | 1 | |
| 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 |
