OpenAlex ·
Improved Revenue Guarantees for Selling Separately and Bundling
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2609.28873
- Original
- Read it at the publisher
- Topics
Abstract
We study how much revenue a seller can lose by restricting attention to selling separately or grand bundling, in the setting of a single additive buyer with independent item values. Although revenue-optimal mechanisms can require lotteries and infinite menus, Babaioff, Immorlica, Lucier, and Weinberg showed that the better of these two simple formats always achieves a constant fraction of optimal revenue. We prove that $\mathrm{OPT} \le 3.52 \max\{\mathrm{SREV}, \mathrm{BREV}\}$, where $\mathrm{SREV}$ and $\mathrm{BREV}$ are the optimal revenues from selling separately and grand bundling, respectively. This improves the previous best-known approximation factor of $5.2$ due to Ma and Simchi-Levi and narrows the gap to the known lower bound of $2$.
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
Claim-Gated Source-Risk Auditing for Generative Search
Quantum interaction can superactivate cheating under parallel repetition
A Faster Algorithm for Fewer Vertex-Disjoint Paths Parameterized by Treewidth
Complexity Barriers to State Preparation in Quantum Approximate Optimization
On Kernels and Leaves: Searching for Bare and Lush Trees
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.