# Multi-agent Adaptive Mechanism Design

arXiv: https://arxiv.org/abs/2512.21794 · HTML: https://mlsanity.com/paper/2512.21794/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 58 references that are in the map.
- First posted on arXiv 25 Dec 2025.

## Builds on (most cited first, 17 of 17)

- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability](https://mlsanity.com/paper/2003.12699/) (2020)
- [Batched Multi-armed Bandits Problem](https://mlsanity.com/paper/1904.01763/) (2019)
- [A Second-order Bound with Excess Losses](https://mlsanity.com/paper/1402.2044/) (2014)
- [What Doubling Tricks Can and Can't Do for Multi-Armed Bandits](https://mlsanity.com/paper/1803.06971/) (2018)
- [Adaptive Contract Design for Crowdsourcing Markets: Bandit Algorithms for Repeated Principal-Agent Problems](https://mlsanity.com/paper/1405.2875/) (2014)
- [Display Advertising with Real-Time Bidding (RTB) and Behavioural Targeting](https://mlsanity.com/paper/1610.03013/) (2016)
- [The Sample Complexity of Online Contract Design](https://mlsanity.com/paper/2211.05732/) (2022)
- [Crowdsourced Judgement Elicitation with Endogenous Proficiency](https://mlsanity.com/paper/1303.0799/) (2013)
- [Informed Truthfulness in Multi-Task Peer Prediction](https://mlsanity.com/paper/1603.03151/) (2016)
- [Truthful Data Acquisition via Peer Prediction](https://mlsanity.com/paper/2006.03992/) (2020)
- [Proper Dataset Valuation by Pointwise Mutual Information](https://mlsanity.com/paper/2405.18253/) (2024)
- [It Takes Two: A Peer-Prediction Solution for Blockchain Verifier's Dilemma](https://mlsanity.com/paper/2406.01794/) (2024)
- [Adaptive Selective Sampling for Online Prediction with Experts](https://mlsanity.com/paper/2302.08397/) (2023)
- [On Adaptivity in Information-constrained Online Learning](https://mlsanity.com/paper/1910.08805/) (2019)
- [An Uncertainty- and Collusion-Proof Voting Consensus Mechanism in Blockchain](https://mlsanity.com/paper/1912.11620/) (2019)
- [Incentive Compatibility in Two-Stage Repeated Stochastic Games](https://mlsanity.com/paper/2203.10206/) (2022)

## Abstract (arXiv)

We study a sequential mechanism design problem in which a principal seeks to elicit truthful reports from multiple rational agents while starting with no prior knowledge of agents' beliefs. We introduce Distributionally Robust Adaptive Mechanism (DRAM), a general framework combining insights from both mechanism design and online learning to jointly address truthfulness and cost-optimality. Throughout the sequential game, the mechanism estimates agents' beliefs and iteratively updates a distributionally robust linear program with shrinking ambiguity sets to reduce payments while preserving truthfulness. Our mechanism guarantees truthful reporting with high probability while achieving tildeO(√T) cumulative regret, and we establish a matching lower bound showing that no feasible adaptive mechanism can asymptotically do better. The framework generalizes to plug-in estimators, supporting structured priors and delayed feedback. To our knowledge, this is the first adaptive mechanism under general settings that maintains truthfulness and achieves optimal regret when incentive constraints are unknown and must be learned.