Improved bounds on simple auctions for selling multiple items
On the Power of Determinism in Multi-Item Auctions
Computer Science and Game TheoryDiscrete Mathematics
Summary
Figuring out how to sell multiple different items to one buyer for the most money can be very complicated. The authors studied three simple, straightforward ways of selling these items: selling each separately, selling all as one bundle, or picking the better of these two choices. They used math to find the worst-case performance of selling separately and improved previous estimates on how close these simple methods come to the best possible income. Their work gives better guarantees that these simple auctions earn at least a certain fraction of the ideal revenue.
What this means in practice
- •For online marketplace operators: Set pricing strategies for selling multiple products by choosing between simple bundling or separate selling with tighter guarantees on revenue.
- •For digital advertising platforms: Improve revenue forecasts when auctioning multiple ad slots by relying on simple deterministic auction formats with known revenue bounds.
Authors
Yiannis Giannakopoulos, Johannes Hahn
Abstract
We study the classical multi-item monopoly setting with a single additive buyer and $m$ heterogeneous items whose values are independent but not necessarily identically distributed. Optimal truthful auctions may be randomized and complicated. We analyze the approximation ratios of three simple deterministic auctions: selling all items separately, selling them as a single grand bundle, and choosing the better of the two. Our technical cornerstone is a nonlinear mathematical programming formulation of the worst-case approximation ratio of selling separately, in discrete auctions where values lie in the grid $\{0,1/K,2/K,\dots ,1\}$. For two iid items, we construct novel tight Lagrangian dual certificates that determine this ratio exactly for any discretization parameter $K$. Taking $K\to\infty$, we obtain the tight bound $1+W(1/e)\approx 1.278$ in the continuous-valued setting, where $W$ denotes the Lambert-W function, closing the $[1.278,1.368]$ gap from the work of Hart and Nisan [EC'12, JET 2017]. For $m\geq2$ independent items, a different dual construction gives an upper bound on the approximation ratio of selling separately in terms of basic statistics of the item values. Combining this bound with new inequalities relating optimal revenue (REV), separate-selling revenue (SREV), and grand-bundle revenue (BREV), we derive improved guarantees for all three auctions. Most notably, we prove \[REV\leq 3.5 \max\{SREV,BREV\},\] improving upon the $5.2$ factor of Ma and Simchi-Levi [AISTATS'21] and the $6$ factor of Babaioff, Immorlica, Lucier and Weinberg [FOCS'14, JACM 2020]. For iid items, we also prove $REV\leq 4.4534 BREV$.