Learning Truthful Mechanisms without Discretization

This paper introduces TEDI (Truthful, Expressive, and Dimension-Insensitive approach), the first discretization-free algorithm to learn 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-to-large scale problems.