The Subset Sum Game Revisited
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
- PDF / 280,020 Bytes
- 13 Pages / 439.37 x 666.142 pts Page_size
- 76 Downloads / 211 Views
Department of Computer Science, Eindhoven University of Technology, Eindhoven, Netherlands 2 Department of Computer Science, RWTH Aachen, Aachen, Germany [email protected]
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.
1
Introduction
The subset sum game is a combinatorial game for two players A and B with perfect information. An instance of the game consists of m + n items and a knapsack of capacity c. The A-items have weights a1 , a2 , . . . , am and belong to player A, while the B-items have weights b1 , b2 , . . . , bn and belong to player B. Throughout we assume that every item weight is bounded by the knapsack capacity c. The players move alternately, and the instance specifies whether player A or player B makes the first move. In every move, the active player picks one of his items (which has not been picked in any earlier move) and puts it into the knapsack. As usual, an item can only be added to the knapsack, if the overall weight of all packed items does not exceed the knapsack capacity c. A player may pass on a move, but only in case none of his items fits. The game ends as soon as none of the remaining unpacked items fits into the knapsack. We will always look at this game through the eyes of player A, whose goal is simply to maximize the total weight of A-items in the knapsack. Player B will be considered our adversary and enemy, who behaves in one of the following ways. – Hostile: The objective of adversary B is to hurt player A as much as possible, and to minimize the total weight of A-items in the knapsack. c Springer International Publishing AG 2017 J. Rothe (Ed.): ADT 2017, LNAI 10576, pp. 228–240, 2017. DOI: 10.1007/978-3-319-67504-6 16
The Subset Sum Game Revisited
229
– Selfish: The objective of adversary B is to get as much profit for himself as possible, and hence to maximize the total weight of B-items in the knapsack. – Greedy: The (short-sighted) objective of adversary B is to pack in every single move a B-item of largest possible weight. While the behavior of the greedy adversary is easy to understand (and easy to predict), the behavior of the two other adversaries needs a more precise mat
Data Loading...
