Pessimism meets VCG: Learning Dynamic Mechanism Design via Offline Reinforcement Learning

  • 2022-05-05 06:44:26
  • Boxiang Lyu, Zhaoran Wang, Mladen Kolar, Zhuoran Yang
  • 1


Dynamic mechanism design has garnered significant attention from bothcomputer scientists and economists in recent years. By allowing agents tointeract with the seller over multiple rounds, where agents' reward functionsmay change with time and are state dependent, the framework is able to model arich class of real world problems. In these works, the interaction betweenagents and sellers are often assumed to follow a Markov Decision Process (MDP).We focus on the setting where the reward and transition functions of such anMDP are not known a priori, and we are attempting to recover the optimalmechanism using an a priori collected data set. In the setting where thefunction approximation is employed to handle large state spaces, with only mildassumptions on the expressiveness of the function class, we are able to designa dynamic mechanism using offline reinforcement learning algorithms. Moreover,learned mechanisms approximately have three key desiderata: efficiency,individual rationality, and truthfulness. Our algorithm is based on thepessimism principle and only requires a mild assumption on the coverage of theoffline data set. To the best of our knowledge, our work provides the firstoffline RL algorithm for dynamic mechanism design without assuming uniformcoverage.


Quick Read (beta)

loading the full paper ...