# Understanding Incentives: Mechanism Design becomes Algorithm Design

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 May 2013.

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

- [PreferenceNet: Encoding Human Preferences in Auction Design with Deep Learning](https://mlsanity.com/paper/2106.03215/) (2021)
- [Differentiable Economics for Randomized Affine Maximizer Auctions](https://mlsanity.com/paper/2202.02872/) (2022)
- [Social Theory Should Be a Structural Prior for Agentic AI: A Formal Framework for Multi-Agent Social Systems](https://mlsanity.com/paper/2605.07069/) (2026)
- [Mode Connectivity in Auction Design](https://mlsanity.com/paper/2305.11005/) (2023)
- [A Principle of Targeted Intervention for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2510.17697/) (2025)
- [Recommender Systems meet Mechanism Design](https://mlsanity.com/paper/2110.12558/) (2021)
- [Attaining Human`s Desirable Outcomes in Human-AI Interaction via Structural Causal Games](https://mlsanity.com/paper/2405.16588/) (2024)
- [How to Sell High-Dimensional Data Optimally](https://mlsanity.com/paper/2510.15214/) (2025)
- [A Robust Multi-Item Auction Design with Statistical Learning](https://mlsanity.com/paper/2302.00941/) (2023)
- [Refined Mechanism Design for Approximately Structured Priors via Active Regression](https://mlsanity.com/paper/2310.07874/) (2023)

## Abstract (arXiv)

We provide a computationally efficient black-box reduction from mechanism design to algorithm design in very general settings. Specifically, we give an approximation-preserving reduction from truthfully maximizing any objective under arbitrary feasibility constraints with arbitrary bidder types to (not necessarily truthfully) maximizing the same objective plus virtual welfare (under the same feasibility constraints). Our reduction is based on a fundamentally new approach: we describe a mechanism's behavior indirectly only in terms of the expected value it awards bidders for certain behavior, and never directly access the allocation rule at all. Applying our new approach to revenue, we exhibit settings where our reduction holds both ways. That is, we also provide an approximation-sensitive reduction from (non-truthfully) maximizing virtual welfare to (truthfully) maximizing revenue, and therefore the two problems are computationally equivalent. With this equivalence in hand, we show that both problems are NP-hard to approximate within any polynomial factor, even for a single monotone submodular bidder. We further demonstrate the applicability of our reduction by providing a truthful mechanism maximizing fractional max-min fairness. This is the first instance of a truthful mechanism that optimizes a non-linear objective.