OpenAlex ·
On the Power of Determinism in Multi-Item Auctions
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2609.35711
- Original
- Read it at the publisher
- Topics
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)\approx1.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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
AI-based matching improves refugee employment in a double-blind randomized trial
Information Games: Strategic Crowding and Firm Repositioning in Language-Model Space
Representation Risk in Pretrained Image Encoders
Sharp Second-Best Welfare in Bilateral and Matching Markets
Fluctuations and multifractality in stochastic models of interface growth and population dynamics
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.