MIT researchers design audit-based mechanism for efficient resource allocation without money or priors

In a new paper accepted to COLT 2025, MIT researchers Yan Dai, Moise Blanchard, and Patrick Jaillet tackle a fundamental problem in mechanism design: how to allocate resources efficiently when monetary payments are banned and the planner has no prior information about agents' valuations. Drawing on costly state verification literature, they introduce a mechanism that requests audits on the winning agent after allocation (revealing true utility, but not revoking the allocation).

The mechanism achieves T-independent O(K²) regret in social welfare while requesting O(K³ log T) audits in expectation, where K is the number of agents and T the number of rounds. The authors prove lower bounds of Ω(K) on regret and Ω(1) on audits for low regret. They extend the analysis to imperfect audit models. Algorithmically, they incentivize truthful behavior by estimating agents' truthful winning probability online, using future punishments via adaptive audits and a novel flagging component that allows agents to correct biased estimates—proving it is in their best interest to do so. The work provides technical tools for robust mechanism design where the revelation principle does not apply.