The subset sum game revisited

Theory of Computing Systems, vol. 65, pp. 884–900

Abstract

Abstract We discuss a game theoretic variant of the subset sum problem, in which two players compete for a common resource represented by a knapsack. Each player owns a private set of items, players pack items alternately, and each player either wants to maximize the total weight of his own items packed into the knapsack or to minimize the total weight of the items of the other player. We show that finding the best packing strategy against a hostile or a selfish adversary is PSPACE-complete, and that against these adversaries the optimal reachable item weight for a player cannot be approximated within any constant factor (unless P=NP). The game becomes easier when the adversary is short-sighted and plays greedily: finding the best packing strategy against a greedy adversary is NP-complete in the weak sense. This variant forms one of the rare examples of pseudo-polynomially solvable problems that have a PTAS, but do not allow an FPTAS (unless P=NP).

Authors 2

1. Astrid Pieterse

   Humboldt-Universität zu Berlin

   Affiliation as printed

   Department of Computer Science, Humboldt University Berlin, Berlin, Germany

2. Gerhard J. Woeginger corresponding Aachen Department of Computer Science

   RWTH Aachen University

   Affiliation as printed

   Department of Computer Science, RWTH Aachen, Aachen, Germany