Related papers: Multi-agent Adaptive Mechanism Design

Multi-agent Adaptive Mechanism Design

URL: http://arxiv.org/abs/2512.21794v1
Date: Thu, 25 Dec 2025 21:59:51 GMT
Title: Multi-agent Adaptive Mechanism Design
Authors: Qiushi Han, David Simchi-Levi, Renfei Tan, Zishuo Zhao,
Abstract summary: We introduce Distributionally Robust Adaptive Mechanism (DRAM), a general framework combining insights from both mechanism design and online learning.<n>Our mechanism guarantees truthful reporting with high probability while achieving $tildeO(sqrtT)$ optimal cumulative regret.
Score: 13.027684227860322
License: http://creativecommons.org/licenses/by/4.0/
Abstract: 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 $\tilde{O}(\sqrt{T})$ cumulative regret, and we establish a matching lower bound showing that no truthful 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.

Related papers

Towards Efficient Agents: A Co-Design of Inference Architecture and System [66.59916327634639]
This paper presents AgentInfer, a unified framework for end-to-end agent acceleration.<n>We decompose the problem into four synergistic components: AgentCollab, AgentSched, AgentSAM, and AgentCompress.<n>Experiments on the BrowseComp-zh and DeepDiver benchmarks demonstrate that through the synergistic collaboration of these methods, AgentInfer reduces ineffective token consumption by over 50%.
arXiv Detail & Related papers (2025-12-20T12:06:13Z)
Coherence Mechanisms for Provable Self-Improvement [38.3455527898461]
We propose a principled framework for self-improvement based on the concept of emphcoherence<n>We formalize this concept using projection-based mechanisms that update a baseline model to be coherent while remaining as close as possible to its original behavior.<n>Our analysis is comprehensive, covering both emphdirect and emphtwo-step projection methods, and robustly extends these guarantees to non-realizable settings.
arXiv Detail & Related papers (2025-11-11T16:45:14Z)
Stochastically Dominant Peer Prediction [11.183872292320824]
We propose dominantally dominant (SD-truthfulness) as a stronger guarantee of truthful reporting.<n>A simple solution -- rounding into binary lotteries -- can enforce SD-truthfulness, but often degrades sensitivity.<n>We demonstrate how a more careful application of rounding can better preserve sensitivity.
arXiv Detail & Related papers (2025-06-02T21:07:24Z)
Refined Mechanism Design for Approximately Structured Priors via Active Regression [50.71772232237571]
We consider the problem of a revenue-maximizing seller with a large number of items for sale to $n$ strategic bidders. It is well-known that optimal and even approximately-optimal mechanisms for this setting are notoriously difficult to characterize or compute.
arXiv Detail & Related papers (2023-10-11T20:34:17Z)
Pessimism meets VCG: Learning Dynamic Mechanism Design via Offline Reinforcement Learning [114.36124979578896]
We design a dynamic mechanism using offline reinforcement learning algorithms. Our algorithm is based on the pessimism principle and only requires a mild assumption on the coverage of the offline data set.
arXiv Detail & Related papers (2022-05-05T05:44:26Z)
Learning Dynamic Mechanisms in Unknown Environments: A Reinforcement Learning Approach [123.55983746427572]
We propose novel learning algorithms to recover the dynamic Vickrey-Clarke-Grove (VCG) mechanism over multiple rounds of interaction.<n>A key contribution of our approach is incorporating reward-free online Reinforcement Learning (RL) to aid exploration over a rich policy space.
arXiv Detail & Related papers (2022-02-25T16:17:23Z)
VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedback [104.06766271716774]
We study a multi-round welfare-maximising mechanism design problem in instances where agents do not know their values. We first define three notions of regret for the welfare, the individual utilities of each agent and that of the mechanism. Our framework also provides flexibility to control the pricing scheme so as to trade-off between the agent and seller regrets.
arXiv Detail & Related papers (2020-04-19T18:00:58Z)
Target-Embedding Autoencoders for Supervised Representation Learning [111.07204912245841]
This paper analyzes a framework for improving generalization in a purely supervised setting, where the target space is high-dimensional. We motivate and formalize the general framework of target-embedding autoencoders (TEA) for supervised prediction, learning intermediate latent representations jointly optimized to be both predictable from features as well as predictive of targets.
arXiv Detail & Related papers (2020-01-23T02:37:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.