The subset sum game revisited

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Downloads (Pure)

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.

Original languageEnglish
Title of host publicationAlgorithmic Decision Theory
Subtitle of host publication5th International Conference, ADT 2017, Luxembourg, Luxembourg, October 25–27, 2017, Proceedings
EditorsJorg Rothe
Place of PublicationDordrecht
PublisherSpringer
Pages228-240
Number of pages13
ISBN (Electronic)978-3-319-67504-6
ISBN (Print)978-3-319-67503-9
DOIs
Publication statusPublished - 2017
Event5th International Conference on Algorithmic Decision Theory (ADT 2017) - Luxembourg, Luxembourg
Duration: 25 Oct 201727 Oct 2017
Conference number: 5
https://sma.uni.lu/adt2017/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Link
Volume10576

Conference

Conference5th International Conference on Algorithmic Decision Theory (ADT 2017)
Abbreviated titleADT 2017
CountryLuxembourg
CityLuxembourg
Period25/10/1727/10/17
Internet address

Fingerprint

Dive into the research topics of 'The subset sum game revisited'. Together they form a unique fingerprint.

Cite this