One extra bidder can make a simple bundle auction match optimal selling

A simple auction against a demanding benchmark

Selling several goods creates a difficult pricing problem even when there is only one buyer. An optimal mechanism can involve menus of randomized offers rather than ordinary prices. Huang’s arXiv preprint, A Bulow–Klemperer Theorem for Bundling and Improved Approximation Bounds for Simple Auctions, asks how much of that complexity can be replaced by simple selling rules or additional competition.

The model assumes an additive buyer: the value of a collection is the sum of its item values. Those values are independent and nonnegative, and each item has finite optimal posted-price revenue. Independence does not require different items to have identical value distributions.

The benchmark is the highest expected revenue obtainable by a truthful, individually rational mechanism, including randomized offers. The paper compares it with selling each item at its own best price, selling everything at one best bundle price, and auctioning the whole bundle to two independent buyers drawn from the original buyer’s value distribution.

What one additional buyer achieves

The first main theorem applies when every item’s value distribution is regular. In auction theory, regularity means that the revenue curve—posted-price revenue expressed as a function of sale probability—is concave.

Under that assumption, Huang proves that a reserve-free second-price auction for the whole bundle, with two buyers, earns at least the optimal expected revenue obtainable from one buyer. The higher bidder receives everything and pays the other bidder’s total bundle value. The auction needs neither a reserve price nor knowledge of the value distributions.

The guarantee holds regardless of how many items are sold. The paper presents it as a multi-item counterpart to the classical Bulow–Klemperer theorem, which compares additional competition with optimal auction design for a single item. It answers a previously posed question about whether a constant amount of competition suffices for bundling independent regular items.

The same theorem places the two-buyer auction’s revenue at no more than twice the best one-buyer bundle revenue. Consequently, a single posted bundle price captures at least half the optimal one-buyer revenue under regularity. The factor of two is tight: the paper constructs independent, regular two-item examples whose optimal-to-bundle revenue ratio approaches two.

Better guarantees without regularity

For general independent item values, the paper proves a different bound: optimal revenue is at most separate-selling revenue plus π²/6 times bundle revenue.

It follows that choosing the better of separate selling and bundling gives an approximation factor of 1 + π²/6, which is less than 2.645. Equivalently, the chosen rule earns at least the optimal revenue divided by that factor.

The manuscript compares this with earlier factors of six and 5.2, as well as independent concurrent results giving factors of 3.52 and three. These are worst-case mathematical guarantees, not predictions that every seller will experience a particular revenue increase.

The new upper bound is accompanied by a stronger obstruction. Huang constructs a finite instance with independent, bounded item values in which prices for three disjoint bundles earn more than 2.11 times the better of separate selling and grand bundling. Because that three-bundle mechanism is itself feasible, the optimal mechanism earns at least as much. Thus a universal factor-two guarantee for the better of the two simpler rules is impossible. The paper places the best possible worst-case factor between 2.11 and 2.645.

How the proofs work

The regularity argument tracks value that a truthful mechanism does not collect: buyer utility and the value of items left unallocated. After subtracting utility from total value, Huang bounds the remaining variation by expected unallocated value. Independence allows one-item bounds to combine into a bound for the whole collection.

For irregular distributions, the paper measures a correction using the area needed to make each item’s revenue curve concave. A further refinement replaces the original variation measure with cumulative entropy. That stronger deduction produces the π²/6 coefficient without using the core–tail decompositions or duality arguments employed in earlier approaches.

Where the guarantees stop

The two-buyer exact-revenue guarantee depends on regularity and uses one original buyer as its benchmark. For general independent values, the paper constructs instances where even the better of optimal separate-item and bundle auctions needs a number of buyers growing logarithmically with the item count to match that benchmark exactly.

Closing the remaining approximation gap and finding simple formats that compete with optimal revenue from several original buyers remain open directions. The work is a theoretical preprint; its conclusions concern expected revenue within the stated model.