用神经网络生成个性化匹配菜单,实现公平与稳定兼顾的机制设计。
MenuNet: A Strategy-Proof Mechanism for Matching Markets

- 通过学习生成个性化概率菜单,再按规则分配,确保策略不可操纵。
- 在避免嫉妒和减少资源浪费上优于随机排序和延迟接受算法。
- 适合有复杂约束的现实匹配场景,如学校招生、人才分配等。
策略不可操纵性是机制设计的核心要求,确保参与者诚实申报并保持稳健参与。稳定性也是匹配市场的关键需求,广泛应用于学校录取和劳动力市场。然而,现实中这些市场常受多样性配额、区域平衡、总容量限制等复杂分配约束影响,导致稳定匹配往往不存在。这引出根本问题:如何在不破坏策略不可操纵性的前提下,合理分配不可避免的不稳定性?为此,我们提出 exttt{MenuNet},一种基于神经网络表示菜单的策略不可操纵机制框架。不同于直接构造分配, exttt{MenuNet} 学习生成个性化概率菜单,再通过结构化序列选择规则实现分配,该规则天然保证策略不可操纵。我们将稳定性分解为公平性(无嫉妒)与非浪费性,将其建模为向量值量,并通过可微目标优化其分布,实现对不同公理的合理权衡。实验表明, exttt{MenuNet} 能有效处理该权衡:在嫉妒程度上持续优于随机串行独裁(RSD),在浪费程度上优于延迟接受(DA),同时保持良好的可扩展性和计算效率。结果表明,基于学习的菜单机制为高度受限的真实世界环境提供了灵活且可扩展的机制设计范式。
原文摘要 · Abstract (English)
Strategy-proofness is a fundamental desideratum in mechanism design, ensuring truthful reporting and robust participation. Stability is another central requirement in matching markets, widely adopted in applications such as school choice and labor market clearing. In practice, however, these markets are invariably governed by complex distributional constraints, ranging from diversity quotas and regional balance to global capacity slacks, under which stable matchings often fail to exist. This raises a fundamental question: how to distribute unavoidable instability across agents while preserving strategy-proofness? To address this, we propose \texttt{MenuNet}, a strategy-proof mechanism design framework based on a neural representation of menus. Rather than directly constructing assignments, \texttt{MenuNet} learns to generate personalized probabilistic menus, from which assignments are realized via a structured sequential choice rule that guarantees strategy-proofness by construction. By decomposing stability into fairness (no envy) and non-wastefulness, our approach models these properties as vector-valued quantities and optimizes their distribution through differentiable objectives, providing a principled trade-off between competing axioms. Empirically, \texttt{MenuNet} navigates this trade-off effectively: it consistently outperforms Random Serial Dictatorship (RSD) in terms of envy and Deferred Acceptance (DA) in terms of waste, while maintaining scalability and computational efficiency. These results suggest that learning-based menu mechanisms provide a flexible and scalable paradigm for mechanism design in highly constrained, real-world environments.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。