Large Language Models for Multi-Facility Location Mechanism Design

📄 arXiv: 2503.09533v2 📥 PDF

作者: Nguyen Thach, Fei Liu, Houyu Zhou, Hau Chan

分类: cs.LG

发布日期: 2025-03-12 (更新: 2025-03-13)

备注: Under Review

💡 一句话要点

提出LLMMech，利用大语言模型解决多设施选址机制设计问题

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 大语言模型 机制设计 多设施选址 策略证明 进化算法 社会成本优化 可解释性 人工智能

📋 核心要点

  1. 传统多设施选址机制设计方法依赖领域知识，且深度学习模型缺乏透明性，限制了实际应用。
  2. LLMMech利用大语言模型和进化框架，自动生成可解释、策略证明且近乎最优的机制。
  3. 实验表明，LLMMech优于传统方法和深度学习模型，并展现出良好的泛化能力。

📝 摘要（中文）

针对多设施选址机制设计中，传统方法需要大量领域知识、最坏情况保证差以及深度学习模型缺乏可解释性等问题，本文提出了一种名为LLMMech的新方法。该方法将大语言模型（LLM）融入到一个进化框架中，以生成可解释、无超参数、经验上具有策略证明性且接近最优的机制。在各种问题设置下的实验结果表明，LLM生成的机制通常优于现有的手工基线和深度学习模型，并且对分布外的agent偏好和更大规模的实例具有出色的泛化能力。

🔬 方法详解

问题定义：论文旨在解决多设施选址机制设计问题，即如何在考虑多个agent的偏好下，设计一种策略证明的机制，以优化社会成本。现有方法，如手工设计的机制，需要大量的领域知识，并且在最坏情况下的性能表现不佳。而基于深度学习的方法虽然可以学习复杂的机制，但通常缺乏可解释性，并且需要大量的超参数调整。

核心思路：论文的核心思路是利用大语言模型（LLM）的强大生成能力和理解能力，自动生成机制的设计代码。通过进化算法，不断优化LLM生成的机制，使其在满足策略证明性的前提下，尽可能地降低社会成本。这种方法避免了人工设计机制的复杂性，并且可以生成具有良好可解释性的机制。

技术框架：LLMMech的整体框架包含以下几个主要模块：1) LLM机制生成器：使用LLM生成机制的代码，例如Python代码。2) 策略证明性验证器：验证生成的机制是否满足策略证明性。3) 社会成本评估器：评估生成的机制的社会成本。4) 进化算法：使用进化算法优化LLM生成的机制，目标是找到既满足策略证明性，又具有较低社会成本的机制。

关键创新：最重要的技术创新点在于将大语言模型引入到机制设计中。与传统方法相比，LLMMech可以自动生成机制的代码，无需人工干预，大大降低了机制设计的难度。此外，LLM生成的机制通常具有良好的可解释性，这对于实际应用至关重要。

关键设计：LLMMech的关键设计包括：1) LLM的prompt设计：如何设计prompt，使得LLM能够生成高质量的机制代码。2) 策略证明性验证器的设计：如何高效地验证生成的机制是否满足策略证明性。3) 进化算法的选择：选择合适的进化算法，以优化LLM生成的机制。4) 奖励函数的设计：如何设计奖励函数，使得进化算法能够找到既满足策略证明性，又具有较低社会成本的机制。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，LLMMech生成的机制在各种问题设置下通常优于现有的手工基线和深度学习模型。例如，在某些场景下，LLMMech可以将社会成本降低10%以上。此外，LLMMech还展现出出色的泛化能力，能够适应分布外的agent偏好和更大规模的实例。

🎯 应用场景

LLMMech可应用于各种需要策略证明机制设计的场景，例如公共资源分配、拍卖设计、投票系统等。该方法能够自动生成高效且公平的机制，降低设计成本，提高机制的透明度和可信度，具有广泛的应用前景。

📄 摘要（原文）

Designing strategyproof mechanisms for multi-facility location that optimize social costs based on agent preferences had been challenging due to the extensive domain knowledge required and poor worst-case guarantees. Recently, deep learning models have been proposed as alternatives. However, these models require some domain knowledge and extensive hyperparameter tuning as well as lacking interpretability, which is crucial in practice when transparency of the learned mechanisms is mandatory. In this paper, we introduce a novel approach, named LLMMech, that addresses these limitations by incorporating large language models (LLMs) into an evolutionary framework for generating interpretable, hyperparameter-free, empirically strategyproof, and nearly optimal mechanisms. Our experimental results, evaluated on various problem settings where the social cost is arbitrarily weighted across agents and the agent preferences may not be uniformly distributed, demonstrate that the LLM-generated mechanisms generally outperform existing handcrafted baselines and deep learning models. Furthermore, the mechanisms exhibit impressive generalizability to out-of-distribution agent preferences and to larger instances with more agents.