Protective and Nonprotective Subset Sum Games: A Parameterized Complexity Analysis

Abstract

In Subset Sum Game as studied by Pieterse and Woeginger [Theory of Computing Systems, 2021], two players alternatingly fill a common knapsack each with items from a private collection. The goal of Player A is to reach a value of at least $T_{{ \texttt {A}}}$, whereas Player B may follow different strategies. Subset Sum Game is NP-complete and solvable in pseudopolynomial time if Player B greedily selects the biggest available item in each turn; the game is PSPACE-complete, however, if Player B plays a hostile strategy where the only aim is to avoid that Player A wins. We continue the study of the game with these two strategies for Player B.

First, we provide a faster pseudopolynomial-time algorithm for a greedy Player B and show that the problem with a hostile Player B is fixed-parameter tractable with respect to the knapsack capacity C. Moreover, we study the influence of further parameters such as $T_{{ \texttt {A}}}$, the number of rounds in the game, and the number of different numbers in the input on the complexity of the problem. Second, we consider a further variant of the game, called Protective Subset Sum Game, where Player A additionally has the goal that Player B reaches a value of at least $T_{{ \texttt {B}}}$. In a nutshell, we show that most algorithms for the nonprotective variant can be transferred to Protective Subset Sum Game.