用生成流网络实现高效又难操纵的资源匹配
EMERGENT: Efficient and Manipulation-resistant Matching using GFlowNets
- 基于生成流网络采样多样高收益解，自然平衡效率与抗操纵性
- 实验显示匹配效率高于随机串行轮选，操纵风险显著低于现有方法
- 适合关注公平分配与激励相容的政策设计者和算法研究者
公共资源配置（如学校录取、住房分配、医学生实习）的算法设计具有深远社会影响。在单边匹配问题中，个体根据偏好排序分配资源时，效率与防操纵性存在根本权衡：现有算法如随机串行轮选（RSD）具备策略抵抗性但效率低，而概率串行（PS）和排名最小化（RM）虽高效却易被操纵。本文提出EMERGENT，首次将生成流网络（GFlowNets）应用于单边匹配，利用其生成多样化高奖励解的能力。高奖励解对应高效匹配，而生成过程的随机性降低了操纵动机。实验表明，EMERGENT在排名效率上优于RSD，同时相比RM和PS显著降低策略脆弱性。本工作揭示了GFlowNets在社会选择机制中的潜力，尤其适用于需兼顾效率与可操纵性的场景。
原文摘要 · Abstract (English)
The design of fair and efficient algorithms for allocating public resources, such as school admissions, housing, or medical residency, has a profound social impact. In one-sided matching problems, where individuals are assigned to items based on ranked preferences, a fundamental trade-off exists between efficiency and strategyproofness. Existing algorithms like Random Serial Dictatorship (RSD), Probabilistic Serial (PS), and Rank Minimization (RM) capture only one side of this trade-off: RSD is strategyproof but inefficient, while PS and RM are efficient but incentivize manipulation. We propose EMERGENT, a novel application of Generative Flow Networks (GFlowNets) to one-sided matching, leveraging its ability to sample diverse, high-reward solutions. In our approach, efficient and manipulation-resistant matches emerge naturally: high-reward solutions yield efficient matches, while the stochasticity of GFlowNets-based outputs reduces incentives for manipulation. Experiments show that EMERGENT outperforms RSD in rank efficiency while significantly reducing strategic vulnerability compared to matches produced by RM and PS. Our work highlights the potential of GFlowNets for applications involving social choice mechanisms, where it is crucial to balance efficiency and manipulability.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。