Online Learning for Dynamic Vickrey-Clarke-Groves Mechanism in Unknown Environments
Not on the map. Why?
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.
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
20 of 49 references.
References · 20
- 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 567
- 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 85
- 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
- 2020Dynamic Incentive-aware Learning: Robust Pricing in Contextual Auctionscited by 34
- 2016Oracle-Efficient Online Learning and Auction Designcited by 33
- 2020Optimal No-regret Learning in Repeated First-price Auctionscited by 33
- 2018Contextual Bandits with Cross-learningcited by 31
- 2020Fictitious play in zero-sum stochastic gamescited by 26
- 2016Learning Simple Auctionscited by 23
- 2021Independent Learning in Stochastic Gamescited by 22
- 2017Learning Multi-item Auctions with (or without) Samplescited by 18
- 2019Incentive-aware Contextual Pricing with Non-parametric Market Noisecited by 13
8 more
- 2020Reinforcement Learning in Non-Stationary Discrete-Time Linear-Quadratic Mean-Field Gamescited by 10
- 2022Learning Stationary Nash Equilibrium Policies in n-Player Stochastic Games with Independent Chainscited by 7
- 2020VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedbackcited by 6
- 2022Learning Dynamic Mechanisms in Unknown Environments: A Reinforcement Learning Approachcited by 5
- 2023Learning and Collusion in Multi-unit Auctionscited by 5
- 2019On Incentive Compatibility in Dynamic Mechanism Design With Exit Option in a Markovian Environmentcited by 4
- 2022Pessimism meets VCG: Learning Dynamic Mechanism Design via Offline Reinforcement Learningcited by 4
- 2023Learning in Repeated Multi-Unit Pay-As-Bid Auctionscited by 3
Built on by
Not cited yet.
Similar, not cited
Close in wording, no citation either way
- 2024Optimal Mechanism in a Dynamic Stochastic Knapsack Environment ↗
- 2024Deep Reinforcement Learning for Sequential Combinatorial Auctions
- 2024Auto-bidding in real-time auctions via Oracle Imitation Learning (OIL)
- 2024Approximating Auction Equilibria with Reinforcement Learning
- 2024Algorithmic Collusion And The Minimum Price Markov Game ↗
- 2021Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization
- 2024Understanding Iterative Combinatorial Auction Designs via Multi-Agent Reinforcement Learning
- 2026A3M: Adaptive, Adversarial and Multi-Objective Learning for Strategic Bidding in Repeated Auctions