Integrality gap analysis for bin packing games

A cooperative bin packing game is an NN-person game, where the player set NN consists of kk bins of capacity 11 each and nn items of sizes a1,…,ana1,…,an. The value v(S)v(S) of a coalition SS of players is defined to be the maximum total size of items in SS that can be packed into the bins of SS. We analyze the integrality gap of the corresponding 0–1 integer program of the value v(N)v(N), thereby presenting an alternative proof for the non-emptiness of the 1/31/3-core for all bin packing games. Further, we show how to improve this bound ϵ≤1/3ϵ≤1/3 (slightly) and point out that the conclusion in Matsui (2000) [9] is wrong (claiming that the bound 1/31/3 was tight). We conjecture that the true best possible value is ϵ=1/7ϵ=1/7. The results are obtained using a new “rounding technique” that we develop to derive good (integral) packings from given fractional ones.