Abstract:

This paper innovatively integrates facility location games with the bin packing problem, defining a novel class of facility location bin packing games (FLBPG). Departing from classical models, we are the first to analyze a scenario in which items require further service after visiting a facility. Our optimization objective is to minimize the total access distances of all items to the facilities, as well as the overall number of bins required for this subsequent service. In this model, items act as strategic agents, each possessing information about their location and size. First, we study the scenario in which item size is private information, and the item cost is determined by sharing the bin packing cost. For the resulting pure bin packing game and facility location bin packing game, we design strategy-proof mechanisms with approximation ratios bounded within [1.691, 2] and [5/3, 7/4], respectively. Second, we address a more complex scenario in which both item size and location are private, correlated pieces of information, and the item cost is defined as the actual access distance to the assigned facility. In this context, we design three distinct strategy-proof mechanisms. We rigorously establish their approximation ratio bounds: the first mechanism achieves bounds of [47/35, 11/8], the second [45/34, 1.7], and the third [11/9, 10/9]. This work expands the theoretical framework of facility location games. The proposed mechanism design methodology effectively addresses the integrated optimization of facility location and bin packing within a complex strategic environment. Our mechanisms offer robust solutions by ensuring both strategy-proofness and demonstrable approximation efficiency.

Key words: facility location game, bin packing, strategy-proof mechanism, approximation ratio