Approximate core allocation for binpacking games

A binpacking game is a cooperative N-person game, where the set of players consists of k bins of size 1 and n items of sizes a1,..., an. The value of a coalition of bins and items is the maximum total size of items in the coalition that can be packed into the bins of the coalition. Our main result asserts that for every $\epsilon > 0$, there exist $\epsilon$-approximate core allocations provided k is large enough. Moreover, for every fixed $\delta > 0$, the smallest $\epsilon$ for which the $\epsilon$-approximate core of a given binpacking game is nonempty can be computed in polynomial time with error at most $\delta$, provided k is sufficiently large. We furthermore derive more specialized results for some subclasses of binpacking games.