"Approximation algorithms"

Learning Multi-Item Auctions with (or without) Samples
We provide algorithms that learn simple auctions whose revenue is approximately optimal in multi-item multi-bidder settings, for a wide …
PDF DOI arXiv
Understanding Incentives: Mechanism Design Becomes Algorithm Design
We provide a computationally efficient black-box reduction from mechanism design to algorithm design in very general settings. …
PDF DOI arXiv
Extreme-Value Theorems for Optimal Multidimensional Pricing
We provide a Polynomial Time Approximation Scheme for the multi-dimensional unit-demand pricing problem, when the buyer’s values …
PDF DOI arXiv