English

运筹学学报（中英文） ›› 2025, Vol. 29 ›› Issue (2): 58-67.doi: 10.15960/j.cnki.issn.1007-6093.2025.02.004

• 论文 • 上一篇    下一篇

设施选址装箱博弈问题的机制设计与分析

盖玲1, 张威伟2, 李闽溟3,*()   

  1. 1. 上海理工大学管理学院, 上海 200093
    2. 上海大学管理学院, 上海 200444
    3. 香港城市大学计算机科学系, 香港 999077
  • 收稿日期:2022-02-14 出版日期:2025-06-15 发布日期:2025-06-12
  • 通讯作者: 李闽溟 E-mail:minming.li@cityu.edu.hk
  • 基金资助:
    国家自然科学基金(11201333)

Mechanism design and analysis for facility location bin packing games

Ling GAI1, Weiwei ZHANG2, Minming LI3,*()   

  1. 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:2022-02-14 Online:2025-06-15 Published:2025-06-12
  • Contact: Minming LI E-mail:minming.li@cityu.edu.hk

RichHTML

1

PDF

47

摘要：

本文创新性地将设施选址博弈与装箱问题相结合, 定义了一类新的设施选址装箱博弈问题。与经典模型不同, 我们首次分析了物品在访问设施后仍需进一步接受服务的情形, 并将优化目标设定为最小化所有物品的访问距离与所需装箱总数之和。在此模型中, 物品是博弈参与者, 各自拥有位置信息和尺寸信息。首先, 我们研究了物品尺寸为私有信息的情形, 物品的费用由装箱成本分摊。针对此情形下的纯装箱博弈和选址装箱博弈, 我们分别设计了具有策略证明性(防策略) 的机制, 其近似比分别介于[1.691, 2]和[5/3, 7/4] 之间。其次, 针对物品尺寸信息与位置信息均为私有信息且相互关联的更复杂情形, 我们考虑物品费用即为访问设施的实际距离。在此设定下, 我们设计了三个策略证明机制, 并分别严格证明了它们的近似比上下界：第一个机制为[47/35, 11/8], 第二个为[45/34, 1.7], 第三个为[11/9, 10/9]。本研究拓展了设施选址博弈的理论框架, 提出的机制设计方法能够有效处理物品访问设施距离优化与其后续装箱服务资源优化协同的问题, 并在参与者拥有私有信息且可能策略行事的复杂环境下, 保证方案的防策略性和近似效率。

关键词: 设施选址博弈, 装箱, 防策略机制, 近似比

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

中图分类号: