Spieksma, Frits C. R.; Woeginger, Gerhard J. The computational complexity of a bin packing game. (English) Zbl 0966.91012 Cent. Eur. J. Oper. Res. Econ. 3(1994-95), No. 1, 39-49 (1995). Summary: In this paper we investigate the following game: two players I and II must alternately pack items into two equal-sized bins. In one variant, the first player who is not able to move loses the game, in the other variant, player I wins the game if and only if the game ends with all items packed. We show that for both variants the problem of deciding which player has a winning strategy is PSPACE-complete. We also give polynomial time results for some special cases of the problem. MSC: 91A46 Combinatorial games 91A12 Cooperative games 68Q25 Analysis of algorithms and problem complexity Keywords:polynomial time results PDFBibTeX XMLCite \textit{F. C. R. Spieksma} and \textit{G. J. Woeginger}, Cent. Eur. J. Oper. Res. Econ. 3(1994--95), No. 1, 39--49 (1995; Zbl 0966.91012)