# Automated Dynamic Mechanism Design

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 May 2021.

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

- [Principal-Agent Reward Shaping in MDPs](https://mlsanity.com/paper/2401.00298/) (2023)
- [Efficient Algorithms for Planning with Participation Constraints](https://mlsanity.com/paper/2205.07767/) (2022)
- [An Interpretable Automated Mechanism Design Framework with Large Language Models](https://mlsanity.com/paper/2502.12203/) (2025)
- [Belief-Driven Multi-Agent Collaboration via Approximate Perfect Bayesian Equilibrium for Social Simulation](https://mlsanity.com/paper/2603.24973/) (2026)
- [Stochastic Principal-Agent Problems: Efficient Computation and Learning](https://mlsanity.com/paper/2306.03832/) (2023)
- [Navigating Decision Landscapes: The Impact of Principals on Decision-Making Dynamics](https://mlsanity.com/paper/2312.16230/) (2023)
- [Learning Recommender Mechanisms for Bayesian Stochastic Games](https://mlsanity.com/paper/2505.22979/) (2025)
- [The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability](https://mlsanity.com/paper/2506.09940/) (2025)

## Abstract (arXiv)

We study Bayesian automated mechanism design in unstructured dynamic environments, where a principal repeatedly interacts with an agent, and takes actions based on the strategic agent's report of the current state of the world. Both the principal and the agent can have arbitrary and potentially different valuations for the actions taken, possibly also depending on the actual state of the world. Moreover, at any time, the state of the world may evolve arbitrarily depending on the action taken by the principal. The goal is to compute an optimal mechanism which maximizes the principal's utility in the face of the self-interested strategic agent. We give an efficient algorithm for computing optimal mechanisms, with or without payments, under different individual-rationality constraints, when the time horizon is constant. Our algorithm is based on a sophisticated linear program formulation, which can be customized in various ways to accommodate richer constraints. For environments with large time horizons, we show that the principal's optimal utility is hard to approximate within a certain constant factor, complementing our algorithmic result. We further consider a special case of the problem where the agent is myopic, and give a refined efficient algorithm whose time complexity scales linearly in the time horizon. Moreover, we show that memoryless mechanisms do not provide a good solution for our problem, in terms of both optimality and computational tractability. These results paint a relatively complete picture for automated dynamic mechanism design in unstructured environments. Finally, we present experimental results where our algorithms are applied to synthetic dynamic environments with different characteristics, which not only serve as a proof of concept for our algorithms, but also exhibit intriguing phenomena in dynamic mechanism design.