On the Power of Determinism in Multi-Item Auctions

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. We compare the revenue (REV) of the optimal truthful auction, which in general may be randomized or complicated, with the revenues of three simple deterministic auctions: selling all items separately (SREV), selling them as a single grand bundle (BREV), and choosing the better of the two. Our technical cornerstone is a general upper bound on the optimal multidimensional revenue, parameterized by freely chosen item-wise caps, and expressed in terms of optimal single-item, Myersonian revenues and basic statistics of the value distributions. We derive this inequality through Lagrangian duality for a nonlinear programming formulation of the worst-case approximation ratio of separate-selling. Combining this inequality with carefully chosen caps and a probabilistic analysis of the resulting terms, we obtain improved approximation guarantees for all three deterministic auctions, both for general independent values and for iid values. Notably, we prove that $REV\le 2.5\max \{SREV,BREV\}$, improving the long-standing $5.2$ factor of Ma and Simchi-Levi and the $6$ factor of Babaioff, Immorlica, Lucier, and Weinberg. We complement this upper bound with a construction establishing a lower bound of $2.19$, improving the bound of $2$ by Rubinstein. For two iid items, we determine the exact approximation ratio of selling separately. Our proof constructs tight Lagrangian dual certificates for the aforementioned programming formulation, when item values lie in the grid $\{0,1/K,2/K,\dots ,1\}$, for any discretization parameter $K$. Taking $K\to \infty$ yields the tight ratio $1+W(1/e)\approx 1.2785$ in the continuous-valued setting, where $W$ is the Lambert-W function, closing the $[1.278,1.368]$ gap left by Hart and Nisan.

arXiv commentImproved the upper bound on REV/max{SREV,BREV} from 3 to 2.5 for independent items, and added a lower bound of 2.19. For iid items, improved the upper bounds on REV/max{SREV,BREV} to 2.15 and on REV/BREV from 4.18 to 2.5. The improved upper bounds use a new capped revenue inequality obtained via a new Lagrangian dual construction