Petra van den Bos ; Marielle Stoelinga - With a little help from your friends: semi-cooperative games via Joker moves

lmcs:12944 - Logical Methods in Computer Science, March 18, 2025, Volume 21, Issue 1 - https://doi.org/10.46298/lmcs-21(1:26)2025
With a little help from your friends: semi-cooperative games via Joker movesArticle

Authors: Petra van den Bos ; Marielle Stoelinga

    This paper coins the notion of Joker games, a variant of concurrent games where the players are not strictly adversarial. Instead, Player 1 can get help from Player 2 by playing a Joker move. We formalize these games as cost games and develop strategies that minimize the use of Jokers - viewed as costs - to secure a win with the least possible help. Our investigation studies the theoretical underpinnings of these games and their associated Joker strategies. In particular, when comparing our cost-minimal strategies with admissible strategies, we find out that they differ. Moreover, while randomization can be beneficial in conventional concurrent games, it does not aid in winning Joker games, although it can help reduce the number of needed Jokers. We also enhance our framework by introducing a secondary objective, namely by minimizing the number of moves executed by a Joker strategy. Finally, we demonstrate the practical advantages of our approach by applying it to test generation in model-based testing.


    Volume: Volume 21, Issue 1
    Published on: March 18, 2025
    Accepted on: February 12, 2025
    Submitted on: January 26, 2024
    Keywords: Computer Science - Computer Science and Game Theory

    Consultation statistics

    This page has been seen 271 times.
    This article's PDF has been downloaded 115 times.