Non-Monetary Mechanism Design without Priors: Achieving Efficiency via Adaptive Costly Audits

Yan Dai, Moise Blanchard and Patrick Jaillet

Papers from arXiv.org

Abstract: We study repeated resource allocation with strategic agents, where monetary transfers are disallowed and the planner has no prior information on agents' utility distributions. Inspired by the costly state verification literature, we assume the planner can request costly audits on the winning agent after allocation, revealing their true utility but without the ability to revoke the allocation. We design a mechanism achieving $T$-independent $\mathcal O(K^2)$ regret in social welfare while requesting $\mathcal O(K^3 \log T)$ audits in expectation, where $K$ is the number of agents and $T$ is the number of rounds. We further show an $\Omega(K)$ lower bound on the regret and an $\Omega(1)$ lower bound on the number of audits required for low regret. We also generalize our mechanism and analysis to imperfect audit models. Algorithmically, we show that incentivizing truthful behavior relies on accurately estimating agents' truthful winning probability online. To achieve this, we impose future punishments via adaptive audits; we also introduce an incentive-aligned flagging component allowing agents to flag biased estimates, which we prove is in their best interest. Analytically, without distributional information, the revelation principle cannot dictate a truth-telling equilibrium. Instead, we characterize a Perfect Bayesian Equilibrium via a reduction to an auxiliary game with only benign strategies. The technical tools developed herein can be of independent interest for other robust mechanism design problems where the revelation principle is inapplicable.

Date: 2025-02, Revised 2026-05
New Economics Papers: this item is included in nep-des, nep-mic and nep-upt
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://arxiv.org/pdf/2502.08412 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2502.08412

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().