# Complexity of Mechanism Design

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Aug 2014.

## Built on by (most cited first, 30 of 33)

- [Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games](https://mlsanity.com/paper/2102.11494/) (2021)
- [Neural Auction: End-to-End Learning of Auction Mechanisms for E-Commerce Advertising](https://mlsanity.com/paper/2106.03593/) (2021)
- [Optimal-er Auctions through Attention](https://mlsanity.com/paper/2202.13110/) (2022)
- [Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?](https://mlsanity.com/paper/2112.13521/) (2021)
- [A Scalable Neural Network for DSIC Affine Maximizer Auction Design](https://mlsanity.com/paper/2305.12162/) (2023)
- [Differentiable Economics for Randomized Affine Maximizer Auctions](https://mlsanity.com/paper/2202.02872/) (2022)
- [A Context-Integrated Transformer-Based Neural Network for Auction Design](https://mlsanity.com/paper/2201.12489/) (2022)
- [Deep Learning for Two-Sided Matching](https://mlsanity.com/paper/2107.03427/) (2021)
- [GemNet: Menu-Based, Strategy-Proof Multi-Bidder Auctions Through Deep Learning](https://mlsanity.com/paper/2406.07428/) (2024)
- [Information Design in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2305.06807/) (2023)
- [Principal-Agent Reinforcement Learning: Orchestrating AI Agents with Contracts](https://mlsanity.com/paper/2407.18074/) (2024)
- [Benefits of Permutation-Equivariance in Auction Mechanisms](https://mlsanity.com/paper/2210.05579/) (2022)
- [Data Market Design through Deep Learning](https://mlsanity.com/paper/2310.20096/) (2023)
- [Modelling Cooperation in Network Games with Spatio-Temporal Complexity](https://mlsanity.com/paper/2102.06911/) (2021)
- [Mode Connectivity in Auction Design](https://mlsanity.com/paper/2305.11005/) (2023)
- [Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithms](https://mlsanity.com/paper/2411.00707/) (2024)
- [Distributed General-Purpose Agent Networks: Architecture, Key Mechanisms, and Prototypes](https://mlsanity.com/paper/2606.17368/) (2026)
- [Automated Mechanism Design for Classification with Partial Verification](https://mlsanity.com/paper/2104.05182/) (2021)
- [HCMD-zero: Learning Value Aligned Mechanisms from Data](https://mlsanity.com/paper/2202.10122/) (2022)
- [Carbon Market Simulation with Adaptive Mechanism Design](https://mlsanity.com/paper/2406.07875/) (2024)
- [An Interpretable Automated Mechanism Design Framework with Large Language Models](https://mlsanity.com/paper/2502.12203/) (2025)
- [Deep Incentive Design with Differentiable Equilibrium Blocks](https://mlsanity.com/paper/2603.07705/) (2026)
- [Optimal Automated Market Makers: Differentiable Economics and Strong Duality](https://mlsanity.com/paper/2402.09129/) (2024)
- [Incentive-Aware Multi-Fidelity Optimization for Generative Advertising in Large Language Models](https://mlsanity.com/paper/2604.06263/) (2026)
- [Discovering Cooperative Pipelines: Autoresearch for Sequential Social Dilemmas](https://mlsanity.com/paper/2605.30003/) (2026)
- [EdgeNet : Encoder-decoder generative Network for Auction Design in E-commerce Online Advertising](https://mlsanity.com/paper/2305.06158/) (2023)
- [Navigating Decision Landscapes: The Impact of Principals on Decision-Making Dynamics](https://mlsanity.com/paper/2312.16230/) (2023)
- [Deep Learning Meets Mechanism Design: Key Results and Some Novel Applications](https://mlsanity.com/paper/2401.05683/) (2024)
- [Decentralized Online Learning in General-Sum Stackelberg Games](https://mlsanity.com/paper/2405.03158/) (2024)
- [Learning Neural Strategy-Proof Matching Mechanism from Examples](https://mlsanity.com/paper/2410.19384/) (2024)

## Abstract (arXiv)

The aggregation of conflicting preferences is a central problem in multiagent systems. The key difficulty is that the agents may report their preferences insincerely. Mechanism design is the art of designing the rules of the game so that the agents are motivated to report their preferences truthfully and a (socially) desirable outcome is chosen. We propose an approach where a mechanism is automatically created for the preference aggregation setting at hand. This has several advantages, but the downside is that the mechanism design optimization problem needs to be solved anew each time. Focusing on settings where side payments are not possible, we show that the mechanism design problem is NP-complete for deterministic mechanisms. This holds both for dominant-strategy implementation and for Bayes-Nash implementation. We then show that if we allow randomized mechanisms, the mechanism design problem becomes tractable. In other words, the coordinator can tackle the computational complexity introduced by its uncertainty about the agents preferences BY making the agents face additional uncertainty.This comes at no loss, AND IN SOME cases at a gain, IN the(social) objective.