A Bulow-Klemperer Theorem for Bundling and Improved Approximation Bounds for Simple Auctions

arXiv:2610.24973 · cs.GT, econ.TH · Submitted 2026-10-18 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "A Bulow-Klemperer Theorem for Bundling and Improved Approximation Bounds for Simple Auctions".

Jane: Here's the gist of the paper. Improved Approximation and Tight Competition for Simple Auctions studies simple auctions for one additive buyer whose values for m items are independent, proving tight approximation and competition guarantees under regularity and general independence For independent regular items, REV ≤ BSPA2 ≤ 2 BREV This establishes tight approximation and competition guarantees for bundling under regularity and answers an open question from Beyhaghi et al.

Tom: (EC 2025) For every product distribution D, REV(D) ≤ SREV(D) + π2/6 BREV(D) ≤ 1 + π2/6 max

SREV(D), BREV(D): This improves the previous approximation factors of 6 from Babaioff, Immorlica, Lucier, and Weinberg (FOCS 2014, JACM 2020) and 5.2 from Ma and Simchi-Levi (AISTATS 2021) This improves the previous lower bound of 2 from Rubinstein (ITCS 2016) The worst-case approximation factor is in

2.11, 2.645: Competition Complexity Bounds The paper analyzes the competition complexity required to match optimal revenue For every sufficiently large integer m, there is a product distribution D on m items satisfying max

SREVk(D), BREVk(D): < REV(D) for every integer 1 ≤ k ≤ c log m This shows that the dependence on the number of items is not inherent to simple auctions: a reserve-free grand-bundle auction needs only one additional bidder This construction involves a seed group whose gain over separate selling supplies the improvement beyond two The resulting ratio is greater than 2 + REVseed - SREVseed / c - ε max

SREV(D), BREV(D): Entropy Refinement An entropy refinement of the same argument gives a (1+π2/6)-approximation by the better of separate selling and bundling The new variation must still combine across independent coordinates, be unchanged by adding a constant, and be at most the mean of a nonnegative variable This leads to the improved bundle coefficient in Theorem 3.8 The paper obtains tight competition and approximation guarantees for bundling under regularity An immediate open problem is to close the approximation gap Another direction is to find simple auction formats that compete with optimal revenue from several original bidders The better of separate selling and bundling can require Ω(log m) bidders to match one buyer’s optimal revenue References

BCF+25: Hedyeh Beyhaghi, Linda Cai, Yiding Feng, Yingkai Li, and S.

Jane: Matthew Weinberg.

Tom: “Competition Complexity in Multi-Item Auctions: Beyond VCG and Regularity”

BILW20: Moshe Babaioff, Nicole Immorlica, Brendan Lucier, and S.

Title and authors: Tom: Let's talk about the title itself, "A Bulow-Klemperer Theorem for Bundling and Improved Approximation Bounds for Simple Auctions." It’s a really descriptive name that tells you exactly what the paper is trying to achieve.

Jane: That means they are taking those classic rules—separate selling versus bundling—and proving exactly how close they can get to the best possible revenue, or REV, under different conditions.

Lu: The authors are building on years of work in auction theory and mechanism design, focusing on that core question: how much revenue do you lose by sticking to a simple rule instead of finding the truly optimal one?

Meng: What I'm curious about is how they handle the complexity when we move away from perfectly regular item values. That sounds like where things usually get messy in real-world data, right?

Lalam: They address that by showing that even for any distribution D with independent items, there is a general relationship between REV and SREV and BREV using a specific constant factor >

The paper's summary: Tom: Their main finding is that they significantly improved the approximation factors from previous work. They showed that the previous bounds of six and five point two are now beaten by a factor of one plus pi over six, which is about one point five eight.

Jane: That’s a noticeable improvement compared to those bigger numbers before. So for any distribution D, their revenue bound is REV less than or equal to SREV plus some constant term involving that new fraction and BREV >

Lu: They also looked at the lower bound side of things too. They constructed a specific scenario with three disjoint bundles where the revenue earned from those bundles was greater than two point one one times the maximum of SREV and BREV, which is a bit better than the old lower bound of two that Rubinstein had established >

Meng: So they're demonstrating that bundling or separate selling is significantly better than what you might expect just by looking at the individual item values alone, even in complex scenarios.

Lalam: And on top of all that, they show that if you want to recover the exact optimal revenue by picking the better of separate selling and bundling, you need a specific number of extra bidders depending on how many items there are >

The paper's improvements: Tom: The improvements they highlight are twofold. First, they got a tighter approximation factor than before, moving it from six down to one plus pi over six for general independent items. That’s a solid reduction in the gap between simple mechanisms and the optimum.

Jane: And the second improvement is that they used an entropy refinement technique to get this better factor, which means they found a way to combine information from separate selling and bundling even when those two things don't align perfectly with each other >

Lu: That entropy refinement was key because it let them prove that the approximation factor of one plus pi over six is achievable for general independent item values by using a better measure than what was used before >

Meng: From an engineering standpoint, this means if we use these rules, we can expect a much smaller performance gap when dealing with real-world data distributions compared to the previous bounds they were hitting >

Lalam: And that refinement also gave them a better bundle coefficient in Theorem three point eight of the paper, which is important because it directly impacts how good the bundling rule performs against the separate selling rule >

Conclusion: Tom: So to wrap up this paper, "A Bulow-Klemperer Theorem for Bundling and Improved Approximation Bounds for Simple Auctions," it gives us tighter approximation guarantees under regularity. They’ve shown that the approximation factor is around one point five eight for general independent items and they found a better lower bound on the revenue ratio than previously thought >

Jane: And what this means practically is that we have a much clearer picture of how good these simple selling rules are at approximating the optimal revenue, especially when item values are distributed independently. It’s less of a gap and more of a quantifiable closeness to optimality >

Lu: The main implication for theory is showing that the dependence on the number of items isn't inherently tied to simple auctions, because they proved that a reserve-free grand-bundle auction needs only one additional bidder even under regularity >

Meng: For production, this means we can be more confident in using these rules for simple bundling or selling separately without worrying about falling into a huge revenue deficit compared to the best possible outcome >

Lalam: And just to put it all together, this paper shows that for one additive buyer with independent item values, the better of separate selling and bundling provides a solid guarantee on revenue approximation, even with these new bounds >

Yichen Huang

Harvard University

cs.GT, econ.TH

Submitted: 2026-10-18

Updated: 2026-11-03

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 91/100

The gist: Improved Approximation and Tight Competition for Simple Auctions studies simple auctions for one additive buyer whose values for m items are independent…

Key concepts

REV
This represents the revenue obtained from a specific simple auction mechanism under certain conditions. The paper analyzes how this revenue compares to optimal outcomes when items are bundled or sold separately.
BSPA2
This is a bound related to the buyer-sampling bound, which relates the auction's revenue to simulated bidders. It helps establish a lower limit on how much revenue can be expected from simple mechanisms.
BREV
This denotes the best possible revenue achievable through bundling or separate selling strategies for a given item distribution. The paper proves that REV is tightly approximated by BREV, showing the effectiveness of bundling.

Terminology

Summary

Improved Approximation and Tight Competition for Simple Auctions studies simple auctions for one additive buyer whose values for m items are independent, proving tight approximation and competition guarantees under regularity and general independence For independent regular items, REV ≤ BSPA2 ≤ 2 BREV This establishes tight approximation and competition guarantees for bundling under regularity and answers an open question from Beyhaghi et al. p. 0 (EC 2025) For every product distribution D, REV(D) ≤ SREV(D) + π2/6 BREV(D) ≤ 1 + π2/6 max[SREV(D), BREV(D)] This improves the previous approximation factors of 6 from Babaioff, Immorlica, Lucier, and Weinberg (FOCS 2014, JACM 2020) and 5. p. 02 from Ma and Simchi-Levi (AISTATS 2021) This improves the previous lower bound of 2 from Rubinstein (ITCS 2016) The worst-case approximation factor is in [2. p. 011, 2.645]

Competition Complexity Bounds

The paper analyzes the competition complexity required to match optimal revenue For every sufficiently large integer m, there is a product distribution D on m items satisfying max[SREVk(D), BREVk(D)] < REV(D) for every integer 1 ≤ k ≤ c log m This shows that the dependence on the number of items is not inherent to simple auctions: a reserve-free grand-bundle auction needs only one additional bidder This construction involves a seed group whose gain over separate selling supplies the improvement beyond two The resulting ratio is greater than 2 + REVseed - SREVseed / c - ε max[SREV(D), BREV(D)]

Entropy Refinement

An entropy refinement of the same argument gives a (1+π2/6)-approximation by the better of separate selling and bundling The new variation must still combine across independent coordinates, be unchanged by adding a constant, and be at most the mean of a nonnegative variable This leads to the improved bundle coefficient in Theorem 3.8

Conclusion

The paper obtains tight competition and approximation guarantees for bundling under regularity An immediate open problem is to close the approximation gap Another direction is to find simple auction formats that compete with optimal revenue from several original bidders The better of separate selling and bundling can require Ω(log m) bidders to match one buyer’s optimal revenue

References

[BCF+25] Hedyeh Beyhaghi, Linda Cai, Yiding Feng, Yingkai Li, and S. Matthew Weinberg. p. 0 p. 0 p. 0 p. 0 p. 0 “Competition Complexity in Multi-Item Auctions: Beyond VCG and Regularity”

[BILW20] Moshe Babaioff, Nicole Immorlica, Brendan Lucier, and S. Matthew Weinberg. “A Simple and Approximately Optimal Mechanism for an Additive Buyer”

[BK96] Jeremy Bulow and Paul Klemperer. “Auctions versus Negotiations”

[BLM13] St´ephane Boucheron, G´abor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence

[BW19] Hedyeh Beyhaghi and S. Matthew Weinberg. “Optimal (and Benchmark-Optimal) Competition Complexity for Additive Buyers over Independent Items”

[CDW16] Yang Cai, Nikhil R. Devanur, and S. Matthew Weinberg. “A Duality-Based Unified Approach to Bayesian Mechanism Design”

[CGJ+26] Yang Cai, Vineet Gupta, Yanchen Jiang, Christopher Liaw, Aranyak Mehta, Grigoris Velegkas, and Di Wang. Improved Revenue Guarantees for Selling Separately and Bundling

[Cha04] Djalil Chafa¨ı. “Entropies, Convexity, and Functional Inequalities: On Φ-Entropies and Φ-Sobolev Inequalities”

[Das15] Constantinos Daskalakis. “Multi-Item Auctions Defying Intuition? p. 1”

[DDT13] Constantinos Daskalakis, Alan Deckelbaum, and Christos Tzamos. “Mechanism Design via Optimal Transport”

[DDT14] Constantinos Daskalakis, Alan Deckelbaum, and Christos Tzamos. “The Complexity of Optimal Mechanism Design”

[DDT17] Constantinos Daskalakis, Alan Deckelbaum, and Christos Tzamos. “Strong Duality for a Multiple-Good Monopolist”

[EFF+17] Alon Eden, Michal Feldman, Ophir Friedler, Inbal Talgam-Cohen, and S. Matthew Weinberg. “The Competition Complexity of Auctions: A Bulow–Klemperer Result for Multi-Dimensional Bidders”

[FFR18] Michal Feldman, Ophir Friedler, and Aviad Rubinstein. “99% Revenue via Enhanced Competition”

[GH26] Yiannis Giannakopoulos and Johannes Hahn. On the Power of Determinism in MultiItem Auctions. p. 0 Version 2, October 1, 2026

[HN17] Sergiu Hart and Noam Nisan. “Approximate Revenue Maximization with Multiple Items”

[Kup16] Ron Kupfer. A Note on the Ratio of Revenues Between Selling in a Bundle and Separately

[Led99] Michel Ledoux. “Concentration of Measure and Logarithmic Sobolev Inequalities”

[LY13] Xinye Li and Andrew Chi-Chih Yao. “On Revenue Maximization for Selling Multiple Independently Distributed Items”

[MS21] Will Ma and David Simchi-Levi. “Reaping the Benefits of Bundling under High Production Costs”

[MV06] Alejandro M. Manelli and Daniel R. p. 4 Vincent. “Bundling as an Optimal Selling Mechanism for a Multiple-Good Monopolist”

[Mye81] Roger B. Myerson. “Optimal Auction Design”

[Roc87] Jean-Charles Rochet. “A Necessary and Sufficient Condition for Rationalizability in a Quasi-Linear Context”

[RTY12] Tim Roughgarden, Inbal Talgam-Cohen, and Qiqi Yan. “Supply-Limiting Mechanisms”

[Rub16] Aviad Rubinstein. “On the Computational Complexity of Optimal Simple Mechanisms”

arXiv: 1511.04741

--- Page 26 ---

A Basic Revenue Bounds A bundle sale implies that some item has value at least a 1/m fraction of the bundle price For the bidder-sampling bound, placing one real buyer among simulated bidders recovers a 1/k fraction of the auction’s revenue The union bound gives tPr[S ≥ t] ≤ Xm j=1 tPr[Vj ≥ t/m] ≤ m Xm j=1 REV(Fj) = m SREV(D) For the last inequality, take any k-bidder bundle auction

Proof of Theorem 6.1 Take a dominant-strategy truthful, ex-post individually rational scalar auction, and fix all Y values to a vector y The removed payments sum to at most maxi yi, because P i qi ≤ 1 Thus the original auction’s expected revenue, conditional on y, is at most REVh(X) + maxi yi

Proof of Theorem 5.4 Revenue at the seed price The exponential series implies e 1/2 7/50 > REVseed - SREVseed = (7/50) - (9/80) = 11/400

Proof of Theorem 5.4 Separate prices The second integral gives t Z ∞ t ν(x) dx ≤ η(t):= t 6 e−t + t 8 e−4t/3 + 4t 2/21 + 3/28 e−4t This proves the separateprice bound

Proof of Theorem B.1 For every m ≥ 2 and ε > 0, there is a product distribution D with bounded, atomless, regular marginals and BREV(D) > 0 such that REV(D) ≥ (2 − ε) BREV(D) The replacement tail lies below the original tail: Pr[Y ≥ y] ≤ 1/(1 + y) for every y ≥ 0

Proof of Theorem 5.3 A lower bound using three bundle prices This proves the three estimates in Theorem 5. p. 04: the revenue at the chosen seed price is greater than 7/50, shifted bundle prices earn at most c = 1/4, and the separate-price quantity t R ∞ t ν(x) dx is at most 9/80 for every price

Proof of Theorem 5.4 An Improved Seed This proves the separate revenue at most 9/80 + o(1), while its bundle revenue is strictly greater than 7/50 The completion lemma then gives a ratio arbitrarily close to 2 + REVseed - SREVseed / c > 2 + 11/400 = 2. p. 811

Proof of Theorem B.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Automated mechanism design for multi-item auctions: The improved system can determine if a simple selling rule (separate selling or grand bundling) is better than optimal revenue by calculating REV, SREV, and BREV for given item value distributions D.

  2. Tight approximation guarantee derivation: The system can prove the approximation factor of 1 plus pi over six is achievable for general independent item values by using an entropy refinement that replaces a simpler variation measure with a larger one.

  3. Competition complexity analysis: The AI system can calculate the required number of extra bidders, showing that for separate selling or bundling, Θ(log m) bidders are necessary to match one buyer's optimal revenue in the worst case.

  4. Lower bound construction for auction performance: The system can generate a finite product distribution D with rational values and probabilities that achieves a revenue ratio of 2 plus an improvement term (e.g., 2.11), demonstrating the impossibility of achieving a factor of two.

  5. Distribution synthesis for complex auctions: The system can synthesize item value distributions using compound-Poisson representations to create new, specific scenarios that test the limits of auction performance guarantees against simple rules.

Sources

Related papers