Learning Truthful Mechanisms without Discretization

This paper introduces TEDI (Truthful, Expressive, and Dimension- Insensitiveapproach), thefirstdiscretization-freealgorithmtolearn truthful mechanisms. Existing learning-based algorithms rely on discretization of outcome spaces to ensure truthfulness, which suffers from inefficiency as problem size increases. To address this limitation, we formalize the concept of pricing rules, defined as functions that map outcomes to prices. We then parameterize pricing rules using Partial GroupMax Network, a novel network architecture designed to universally approximate partial convex functions. To enable optimization, we develop two training techniques: covariance trick and continuous sampling, to derive unbiased gradient estimators compatible with first-order optimization. Together, these design choices ensure the truthfulness, expressiveness and dimension-insensitivity of TEDI, and our experiments show that it consistently outperforms state-of-the-art methods in medium-tolarge scale problems. 1

Authors

• Yunxuan Ma CFCS, School of Computer Science, Peking University
• Steven (Siqiang) Wang Foster School of Business, University of Washington
• Zhijian Duan CFCS, School of Computer Science, Peking University
• Yukun Cheng School of Business, Jiangnan University
• Xiaotie Deng CFCS, School of Computer Science & CMAR, Institute for AI, Peking University

Keywords

• Automated Mechanism Design
• Differentiable Economics
• Deep Learning
• First-Order Algorithm