EMERGENT: Efficient and Manipulation-resistant Matching using GFlowNets

2025-05-22 · Mayesha Tasnim, Erman Acar, Sennay Ghebreab

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.

📄 PDF Abstract BibTeX arXiv:2506.12033

Code (0)

등록된 구현이 없습니다.

Rectifying Reinforcement Learning for Reward Matching

2024-06-04 · Haoran He, Emmanuel Bengio, Qingpeng Cai, Ling Pan

The Generative Flow Network (GFlowNet) is a probabilistic framework in which an agent learns a stochastic policy and flow functions to sample objects with probability proportional to an unnormalized reward function. GFlo…

Decision Making reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)+1

On Divergence Measures for Training GFlowNets

2024-10-12 · Tiago da Silva, Eliezer de Souza da Silva, Diego Mesquita

Generative Flow Networks (GFlowNets) are amortized inference models designed to sample from unnormalized distributions over composable objects, with applications in generative modeling for tasks in fields such as causal …

Causal Discovery Drug Discovery Variational Inference

Trajectory balance: Improved credit assignment in GFlowNets

2022-01-31 · Nikolay Malkin, Moksh Jain, Emmanuel Bengio, Chen Sun 외

Generative flow networks (GFlowNets) are a method for learning a stochastic policy for generating compositional objects, such as graphs or strings, from a given unnormalized density by sequences of actions, where many po…

Diversity

The Devil in the Details: Emergent Misalignment, Format and Coherence in Open-Weights LLMs

2025-11-25 · Craig Dickson arxiv

Prior work has shown that fine-tuning models on a narrow domain with misaligned data can lead to broad misalignment - a phenomenon termed "emergent misalignment" (Betley et al. 2025). While all tested models were suscept…

Code Generation

CFlowNets: Continuous Control with Generative Flow Networks

2023-03-04 · Yinchuan Li, Shuang Luo, Haozhi Wang, Jianye Hao

Generative flow networks (GFlowNets), as an emerging technique, can be used as an alternative to reinforcement learning for exploratory control tasks. GFlowNet aims to generate distribution proportional to the rewards ov…

Active Learning continuous-control Continuous Control reinforcement-learning+2