Non-Monetary Mechanism Design without Distributional Information: Using Scarce Audits Wisely

Yan Dai, Moise Blanchard and Patrick Jaillet

Papers from arXiv.org

Abstract: We study a repeated resource allocation problem with strategic agents where monetary transfers are disallowed and the central planner has no prior information on agents' utility distributions. In light of Arrow's impossibility theorem, acquiring information about agent preferences through some form of feedback is necessary. We assume that the central planner can request powerful but expensive audits on the winner in any round, revealing the true utility of the winner in that round. We design a mechanism achieving $T$-independent $O(K^2)$ social welfare regret while only requesting $O(K^3 \log T)$ audits in expectation, where $K$ is the number of agents and $T$ is the number of rounds. We also show an $\Omega(K)$ lower bound on the regret and an $\Omega(1)$ lower bound on the number of audits when having low regret. Algorithmically, we show that incentive-compatibility can be mostly enforced via the imposition of adaptive future punishments, where the audit probability is inversely proportional to the winner's future winning probability. To accurately estimate such probabilities in presence of strategic agents, who may adversely react to any potential misestimate, we introduce a flagging component that allows agents to flag any biased estimate (we show that doing so aligns with individual incentives). On the technical side, without a unique and known distribution, one cannot apply the revelation principle and conclude that truthful reporting is exactly an equilibrium. Instead, we characterize the equilibrium via a reduction to a simpler auxiliary game, in which agents cannot strategize until close to the end of the game; we show equilibria in this game can induce equilibria in the actual, fully strategic game. The tools developed therein may be of independent interest for other mechanism design problems in which the revelation principle cannot be readily applied.

Date: 2025-02, Revised 2025-06
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 ().