title: The Subset Sum game.
abstract: In this work we address a game theoretic variant of the Subset Sum problem, in which two decision makers (agents/players) compete for the usage of a common resource represented by a knapsack capacity. Each agent owns a set of integer weighted items and wants to maximize the total weight of its own items included in the knapsack. The solution is built as follows: Each agent, in turn, selects one of its items (not previously selected) and includes it in the knapsack if there is enough capacity. The process ends when the remaining capacity is too small for including any item left. We look at the problem from a single agent point of view and show that finding an optimal sequence of items to select is an [Formula: see text]-hard problem. Therefore we propose two natural heuristic strategies and analyze their worst-case performance when (1) the opponent is able to play optimally and (2) the opponent adopts a greedy strategy. From a centralized perspective we observe that some known results on the approximation of the classical Subset Sum can be effectively adapted to the multi-agent version of the problem.
authors.affiliation: University of Graz, Institute of Public Economics, Universitaetsstr. 15, A-8010 Graz, Austria.
authors.forename: Andreas
authors.initials: A
authors.lastname: Darmann
authors.affiliation: Dipartimento di Ingegneria, Università degli Studi "Roma Tre", via della Vasca Navale 79, 00146 Rome, Italy.
authors.forename: Gaia
authors.initials: G
authors.lastname: Nicosia
authors.affiliation: University of Graz, Department of Statistics and Operations Research, Universitaetsstr. 15, A-8010 Graz, Austria.
authors.forename: Ulrich
authors.initials: U
authors.lastname: Pferschy
authors.affiliation: University of Graz, Department of Statistics and Operations Research, Universitaetsstr. 15, A-8010 Graz, Austria.
authors.forename: Joachim
authors.initials: J
authors.lastname: Schauer
keywords: Game theory; Multi-agent optimization; Performance analysis; Subset Sum problem