Optimal auctions maximize revenue with identical item values
Optimal Multi-Item Auctions with I.I.D. Values
Computer Science and Game Theory
Summary
This paper tackles the problem of designing auctions that maximize revenue when selling multiple items to buyers who value items independently but identically. The authors provide a precise method and efficient algorithm for the simplest case where item values come from just two possible values. They also show that finding the exact best auction is very hard when the value distribution is more complex or when there are many buyers or items. However, they identify conditions where exact or approximate solutions are still possible and efficient. All their auction designs ensure that buyers truthfully reveal their values and willingly participate.
What this means in practice
- •For online marketplace designers: Create multi-item selling mechanisms that guarantee truthful bidding and maximize revenue efficiently when item values follow simple distributions.
- •For digital advertising platforms: Develop auction formats to optimize revenue from selling multiple ad slots with independently valued impressions using approximation algorithms.
Authors
Boyu Liu, Zhengyang Liu, Zihe Wang
Abstract
We study revenue-maximizing multi-item auctions under dominant-strategy incentive compatibility (DSIC) and ex-post individual rationality. Buyers have additive valuations, and all item values are independent draws from a common finite distribution. For every two-point distribution and arbitrary numbers of buyers and items, we give an explicit deterministic mechanism that is optimal among all randomized mechanisms satisfying these requirements, together with a polynomial-time algorithm for computing the optimal expected revenue. For general finite-support distributions, computing the exact optimal revenue is $\#\mathrm P$-hard, both for a single buyer with an arbitrary number of items and for two items with an arbitrary number of buyers. For a single buyer, we also establish hardness of computing an optimal mechanism. Building on prior work, we also obtain exact and approximate algorithms under different parameter restrictions. Exact polynomial-time optimization is possible whenever any two of the buyer count, item count, and support size are fixed. When only the item count is fixed, a polynomial-time approximation scheme constructs a mechanism with expected revenue at least a $1-\varepsilon$ fraction of the optimum for every fixed $0<\varepsilon<1$. All these algorithms satisfy DSIC and ex-post individual rationality.