# Online Learning for Dynamic Vickrey-Clarke-Groves Mechanism in Unknown Environments

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 49 references that are in the map.
- First posted on arXiv 23 Jun 2025.

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

- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Learning Adversarial MDPs with Bandit Feedback and Unknown Transition](https://mlsanity.com/paper/1912.01192/) (2019)
- [Online Convex Optimization in Adversarial Markov Decision Processes](https://mlsanity.com/paper/1905.07773/) (2019)
- [Dynamic Incentive-aware Learning: Robust Pricing in Contextual Auctions](https://mlsanity.com/paper/2002.11137/) (2020)
- [Oracle-Efficient Online Learning and Auction Design](https://mlsanity.com/paper/1611.01688/) (2016)
- [Optimal No-regret Learning in Repeated First-price Auctions](https://mlsanity.com/paper/2003.09795/) (2020)
- [Contextual Bandits with Cross-learning](https://mlsanity.com/paper/1809.09582/) (2018)
- [Fictitious play in zero-sum stochastic games](https://mlsanity.com/paper/2010.04223/) (2020)
- [Learning Simple Auctions](https://mlsanity.com/paper/1604.03171/) (2016)
- [Independent Learning in Stochastic Games](https://mlsanity.com/paper/2111.11743/) (2021)
- [Learning Multi-item Auctions with (or without) Samples](https://mlsanity.com/paper/1709.00228/) (2017)
- [Incentive-aware Contextual Pricing with Non-parametric Market Noise](https://mlsanity.com/paper/1911.03508/) (2019)
- [Reinforcement Learning in Non-Stationary Discrete-Time Linear-Quadratic Mean-Field Games](https://mlsanity.com/paper/2009.04350/) (2020)
- [Learning Stationary Nash Equilibrium Policies in n-Player Stochastic Games with Independent Chains](https://mlsanity.com/paper/2201.12224/) (2022)
- [VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedback](https://mlsanity.com/paper/2004.08924/) (2020)
- [Learning Dynamic Mechanisms in Unknown Environments: A Reinforcement Learning Approach](https://mlsanity.com/paper/2202.12797/) (2022)
- [Learning and Collusion in Multi-unit Auctions](https://mlsanity.com/paper/2305.17402/) (2023)
- [On Incentive Compatibility in Dynamic Mechanism Design With Exit Option in a Markovian Environment](https://mlsanity.com/paper/1909.13720/) (2019)
- [Pessimism meets VCG: Learning Dynamic Mechanism Design via Offline Reinforcement Learning](https://mlsanity.com/paper/2205.02450/) (2022)
- [Learning in Repeated Multi-Unit Pay-As-Bid Auctions](https://mlsanity.com/paper/2307.15193/) (2023)

## Abstract (arXiv)

We consider the problem of online dynamic mechanism design for sequential auctions in unknown environments, where the underlying market and, thus, the bidders' values vary over time as interactions between the seller and the bidders progress. We model the sequential auctions as an infinite-horizon average-reward Markov decision process (MDP). In each round, the seller determines an allocation and sets a payment for each bidder, while each bidder receives a private reward and submits a sealed bid to the seller. The state, which represents the underlying market, evolves according to an unknown transition kernel and the seller's allocation policy without episodic resets. We first extend the Vickrey-Clarke-Groves (VCG) mechanism to sequential auctions, thereby obtaining a dynamic counterpart that preserves the desired properties: efficiency, truthfulness, and individual rationality. We then focus on the online setting and develop a reinforcement learning algorithm for the seller to learn the underlying MDP and implement a mechanism that closely resembles the dynamic VCG mechanism. We show that the learned mechanism approximately satisfies efficiency, truthfulness, and individual rationality and achieves guaranteed performance in terms of various notions of regret.