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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Protective and Nonprotective Subset Sum Games: A Parameterized Complexity Analysis

  • Jaroslav Garvardt,
  • Christian Komusiewicz,
  • Berthold Blatt Lorke,
  • Jannik Schestag

摘要

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.