No Cover Image

Journal article 293 views 85 downloads

Minkowski Games / Stéphane Le Roux; Arno Pauly; Jean-François Raskin

ACM Transactions on Computational Logic, Volume: 19, Issue: 3, Pages: 1 - 29

Swansea University Author: Arno, Pauly

Check full text

DOI (Published version): 10.1145/3230741

Abstract

We introduce and study Minkowski games. These are two player games, where the players take turns to choose positions in R^d 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 game...

Full description

Published in: ACM Transactions on Computational Logic
ISSN: 1529-3785 1557-945X
Published: Association for Computing Machinery (ACM) 2018
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa40809
Tags: Add Tag
No Tags, Be the first to tag this record!
Abstract: We introduce and study Minkowski games. These are two player games, where the players take turns to choose positions in R^d 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.
Keywords: game theory; verification of hybrid systems; polytopes
Issue: 3
Start Page: 1
End Page: 29