Research Article

Mechanism design and analysis for facility location bin packing games

Expand
  • 1. Business School, University of Shanghai for Science and Technology, Shanghai 200093, China
    2. School of Management, Shanghai University, Shanghai 200444, China
    3. Department of Computer Science, City University of Hongkong, Hongkong 999077, China

Received date: 2022-02-14

  Online published: 2025-06-12

Copyright

, 2025, All rights reserved. Unauthorized reproduction is prohibited.

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.

Cite this article

Ling GAI, Weiwei ZHANG, Minming LI . Mechanism design and analysis for facility location bin packing games[J]. Operations Research Transactions, 2025 , 29(2) : 58 -67 . DOI: 10.15960/j.cnki.issn.1007-6093.2025.02.004

References

1 Procaccia A , Tennenholtz M . Approximate mechanism design without money[J]. ACM Transactions on Economics and Computation, 2013, 1 (4): 1- 26.
2 Cheng Y , Yu W , Zhang G . Strategy-proof approximation mechanisms for an obnoxious facility game on networks[J]. Theoretical Computer Science, 2013, 497, 154- 163.
3 Lu P, Sun X, Wang Y, et al. Asymptotically optimal strategy-proof mechanisms for two-facility games[C]//Proceedings of the 11th ACM Conference on Electronic Commerce, 2010: 315-324.
4 Dokow E, Feldman M, Meir R, et al. Mechanism design on discrete lines and cycles[C]//Proceedings of the 13th ACM Conference on Electronic Commerce, 2012: 423-440.
5 Fotakis D , Tzamos C . On the power of deterministic mechanisms for facility location games[J]. ACM Transactions on Economics and Computation, 2014, 2 (4): 1- 37.
6 Fotakis D, Kavouras L, Kostopanagiotis P, et al. Reallocating multiple facilities on the line[C]//Proceedings of the Twenty-Seventh International Conference on International Joint Conferences on Artificial Intelligence, 2019.
7 程郁琨, 梅丽丽. 设施选址博弈问题的无支付机制设计研究[J]. 运筹学学报, 2018, 22 (2): 93- 104.
8 Chan H, Filos-Ratsikas A, Li B, et al. Mechanism design for facility location problems: A survey[C]//Proceedings of the 31st International Joint Conference on Artificial Intelligenc, 2021: 4356-4365.
9 Zhang Q , Li M . Strategy proof mechanism design for facility location games with weighted agents on a line[J]. Journal of Combinatorial Optimization, 2014, 28 (4): 756- 773.
10 Duan L, Li B, Li M, et al. Heterogeneous two-facility location games with minimum distance requirement[C]//Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, 2019: 1461-1469.
11 Xu X , Li B , Li M , et al. Two-facility location games with minimum distance requirement[J]. Journal of Artificial Intelligence Research, 2021, 70, 719- 756.
12 Wu X , Mei L , Zhang G . Two homogeneous facility location games with a minimum distance requirement on a circle[J]. Theoretical Computer Science, 2024, 991, 114398.
13 Nehama I, Todo T, Yokoo M. Manipulation-resistant facility location mechanisms for ZV-line graphs[C]//Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, 2019: 1452-1460.
14 Liu W , Ding Y , Chen X , et al. Multiple facility location games with envy ratio[J]. Theoretical Computer Science, 2021, 864 (3): 1- 9.
15 姜秀秀, 姜永, 刘龙城, 等. 路上的半厌恶型设施选址博弈的机制设计[J]. 厦门大学学报(自然科学版), 2021, 60 (6): 996- 1000.
16 Zou S, Li M. Facility location games with dual preference[C]//Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, 2015: 615-623.
17 Mei L , Li M , Ye D , et al. Facility location games with distinct desires[J]. Discrete Applied Mathematics, 2019, 264, 148- 160.
18 Lu P, Yu L. Characterization of truthful mechanisms for one-dimensional single facility location game with payments[C]//Proceedings of the 9th Conference on Web and Internet Economics, 2013: 333-346.
19 Li M, Wang C, Zhang M. Budgeted facility location games with strategic facilities[C]//Proceedings of the 29th International Joint Conference on Artificial Intelligenc, 2020: 400-406.
20 Johnson D S. Near-optimal bin packing algorithms[D]. Amherst: Amherst College, 1967.
Outlines

/