Online Learning for Dynamic Vickrey-Clarke-Groves Mechanism in Unknown Environments
This work addresses the challenge of dynamic mechanism design in unknown, non-episodic environments, which is incremental as it builds on existing VCG mechanisms by adapting them to sequential auctions using reinforcement learning.
The paper tackles the problem of designing online dynamic mechanisms for sequential auctions in unknown environments, where market conditions and bidder values change over time, by extending the VCG mechanism to sequential settings and developing a reinforcement learning algorithm that achieves approximate efficiency, truthfulness, and individual rationality with guaranteed regret performance.
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.