Optimization Online


The Subset Sum Game

Andreas Darmann(andreas.darmann***at***uni-graz.at)
Gaia Nicosia(nicosia***at***dia.uniroma3.it)
Ulrich Pferschy(pferschy***at***uni-graz.at)
Joachim Schauer(joachim.schauer***at***uni-graz.at)

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 NP-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.

Keywords: Subset Sum problem, multi-agent optimization, performance analysis, Game Theory

Category 1: Combinatorial Optimization

Category 2: Other Topics (Game Theory )


Download: [PDF]

Entry Submitted: 12/14/2012
Entry Accepted: 12/14/2012
Entry Last Modified: 12/14/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society