Designing mechanisms to maximize revenue is a fundamental problem in mathematical economics and has various applications like online ad auctions and spectrum auctions. Unfortunately, optimal auctions for selling multiple items can be unreasonably complex and computationally intractable. In this talk, we consider a revenue-maximizing seller with n items facing a single unit-demand buyer. Our work shows that simple mechanisms can achieve almost optimal revenue. We approached the tradeoffs of simplicity formally through the lens of computation and menu size. Our main result provides a mechanism that gets a (1 − ε)-approximation to the optimal revenue in time quasi-polynomial in n and has quasi polynomial (symmetric) menu complexity.
I will also briefly discuss our work on welfare maximization in rich advertising auctions. Online ad auctions have evolved from allocating a few lines of text to richer formats that include images, sitelinks, etc. In our model, advertisers can be strategic both about their bid per click and the set of ad formats they are interested in (i.e, they are of multi-dimensional types). The advertisers are unit-demand and the seller's goal is to maximize welfare subject to a knapsack contraints. We provide a simple greedy-like allocation that is monotone (in both value and the set of formats) and guarantees a 1/3-approximation to the optimal welfare.
This talk is based on the following two works:
- Approximation Schemes for a Unit-Demand Buyer with Independent Items via Symmetries. Pravesh Kothari, Divyarthi Mohan, Ariel Schvartzman, Sahil Singla, Matt Weinberg (FOCS 2019).
- Simple Mechanisms for Welfare Maximization in Rich Advertising Auctions. Gagan Aggarwal, Kshipra Bhawalkar, Aranyak Mehta, Divyarthi Mohan, Alex Psomas (Neurips 2022).