# VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedback

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Apr 2020.

## Built on by (most cited first, 6 of 6)

- [Bandits Meet Mechanism Design to Combat Clickbait in Online Recommendation](https://mlsanity.com/paper/2311.15647/) (2023)
- [Online Learning in Contextual Second-Price Pay-Per-Click Auctions](https://mlsanity.com/paper/2310.05047/) (2023)
- [Incentivized Truthful Communication for Federated Bandits](https://mlsanity.com/paper/2402.04485/) (2024)
- [Leveraging Reviews: Learning to Price with Buyer and Seller Uncertainty](https://mlsanity.com/paper/2302.09700/) (2023)
- [Online Learning for Dynamic Vickrey-Clarke-Groves Mechanism in Unknown Environments](https://mlsanity.com/paper/2506.19038/) (2025)
- [Optimal Exploration of New Products under Assortment Decisions](https://mlsanity.com/paper/2604.18800/) (2026)

## Abstract (arXiv)

We study a multi-round welfare-maximising mechanism design problem in instances where agents do not know their values. On each round, a mechanism first assigns an allocation each to a set of agents and charges them a price; at the end of the round, the agents provide (stochastic) feedback to the mechanism for the allocation they received. This setting is motivated by applications in cloud markets and online advertising where an agent may know her value for an allocation only after experiencing it. Therefore, the mechanism needs to explore different allocations for each agent so that it can learn their values, while simultaneously attempting to find the socially optimal set of allocations. Our focus is on truthful and individually rational mechanisms which imitate the classical VCG mechanism in the long run. To that end, we first define three notions of regret for the welfare, the individual utilities of each agent and that of the mechanism. We show that these three terms are interdependent via an Omega(T^frac23) lower bound for the maximum of these three terms after T rounds of allocations, and describe an algorithm which essentially achieves this rate. Our framework also provides flexibility to control the pricing scheme so as to trade-off between the agent and seller regrets. Next, we define asymptotic variants for the truthfulness and individual rationality requirements and provide asymptotic rates to quantify the degree to which both properties are satisfied by the proposed algorithm.