The subset sum game revisited

A. Pieterse; G.J. Woeginger

doi:10.1007/978-3-319-67504-6_16

The subset sum game revisited

A. Pieterse, G.J. Woeginger

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

1 Citation (Scopus)

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 language	English
Title of host publication	Algorithmic Decision Theory
Subtitle of host publication	5th International Conference, ADT 2017, Luxembourg, Luxembourg, October 25–27, 2017, Proceedings
Editors	Jorg Rothe
Place of Publication	Dordrecht
Publisher	Springer
Pages	228-240
Number of pages	13
ISBN (Electronic)	978-3-319-67504-6
ISBN (Print)	978-3-319-67503-9
DOIs	https://doi.org/10.1007/978-3-319-67504-6_16
Publication status	Published - 2017
Event	5th International Conference on Algorithmic Decision Theory (ADT 2017) - Luxembourg, Luxembourg Duration: 25 Oct 2017 → 27 Oct 2017 Conference number: 5 https://sma.uni.lu/adt2017/

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Link
Volume	10576

Conference

Conference	5th International Conference on Algorithmic Decision Theory (ADT 2017)
Abbreviated title	ADT 2017
Country/Territory	Luxembourg
City	Luxembourg
Period	25/10/17 → 27/10/17
Internet address	https://sma.uni.lu/adt2017/

Access to Document

10.1007/978-3-319-67504-6_16

Cite this

@inproceedings{6cb3078e832b439a84e8fccbf63de8ca,

title = "The subset sum game revisited",

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.",

author = "A. Pieterse and G.J. Woeginger",

year = "2017",

doi = "10.1007/978-3-319-67504-6_16",

language = "English",

isbn = "978-3-319-67503-9",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "228--240",

editor = "Jorg Rothe",

booktitle = "Algorithmic Decision Theory",

address = "Germany",

note = "5th International Conference on Algorithmic Decision Theory (ADT 2017), ADT 2017 ; Conference date: 25-10-2017 Through 27-10-2017",

url = "https://sma.uni.lu/adt2017/",

}

Pieterse, A & Woeginger, GJ 2017, The subset sum game revisited. in J Rothe (ed.), Algorithmic Decision Theory: 5th International Conference, ADT 2017, Luxembourg, Luxembourg, October 25–27, 2017, Proceedings. Lecture Notes in Computer Science, vol. 10576, Springer, Dordrecht, pp. 228-240, 5th International Conference on Algorithmic Decision Theory (ADT 2017), Luxembourg, Luxembourg, 25/10/17. https://doi.org/10.1007/978-3-319-67504-6_16

The subset sum game revisited. / Pieterse, A.; Woeginger, G.J.
Algorithmic Decision Theory: 5th International Conference, ADT 2017, Luxembourg, Luxembourg, October 25–27, 2017, Proceedings. ed. / Jorg Rothe. Dordrecht: Springer, 2017. p. 228-240 (Lecture Notes in Computer Science; Vol. 10576).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - The subset sum game revisited

AU - Pieterse, A.

AU - Woeginger, G.J.

N1 - Conference code: 5

PY - 2017

Y1 - 2017

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

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

UR - http://www.scopus.com/inward/record.url?scp=85032500632&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-67504-6_16

DO - 10.1007/978-3-319-67504-6_16

M3 - Conference contribution

SN - 978-3-319-67503-9

T3 - Lecture Notes in Computer Science

SP - 228

EP - 240

BT - Algorithmic Decision Theory

A2 - Rothe, Jorg

PB - Springer

CY - Dordrecht

T2 - 5th International Conference on Algorithmic Decision Theory (ADT 2017)

Y2 - 25 October 2017 through 27 October 2017

ER -

The subset sum game revisited

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this