Source-linked AI summary
Approximate Revenue Maximization with Multiple Items
Sergiu Hart, Noam Nisan
TL;DR
Selling multiple goods to one buyer is extremely difficult, while simple one-dimensional mechanisms do not generally maximize revenue. The paper analyzes separate selling and bundling, establishing revenue guarantees and identifying scope limits for bundling results.
Problem
Maximizing revenue from multiple goods is extremely difficult, and separate selling or bundling does not generally maximize revenue.
Method
The paper analyzes simple one-dimensional mechanisms, including selling goods separately at optimal one-good prices and bundling goods.
Results
50% of optimal revenue is guaranteed for two independent goods sold separately, while 73% is guaranteed for two independent and identically distributed goods sold separately.
Takeaways & Limitations
For two goods, separate selling provides a quantified approximation to optimal revenue despite the difficulty of the general multiple-goods problem.
Takeaways & Limitations
The paper notes that becoming close to optimal requires k to grow while F remains fixed.
Abstract
from arXiv · showhide
Maximizing the revenue from selling _more than one_ good (or item) to a single buyer is a notoriously difficult problem, in stark contrast to the one-good case. For two goods, we show that simple "one-dimensional" mechanisms, such as selling the goods separately, _guarantee_ at least 73% of the optimal revenue when the valuations of the two goods are independent and identically distributed, and at least $50\%$ when they are independent. For the case of $k>2$ independent goods, we show that selling them separately guarantees at least a $c/\log^2 k$ fraction of the optimal revenue; and, for independent and identically distributed goods, we show that selling them as one bundle guarantees at least a $c/\log k$ fraction of the optimal revenue. Additional results compare the revenues from the two simple mechanisms of selling the goods separately and bundled, identify situations where bundling is optimal, and extend the analysis to multiple buyers.
1 Introduction
Selling multiple goods to one additive buyer is substantially harder than the one-good pricing problem, and simple separate or bundled mechanisms need not be optimal. The paper nevertheless proves revenue guarantees for these mechanisms across independent and i.i.d. environments.
- Examples: 2.25 revenue from bundling two i.i.d. goods at price 3 exceeds the separate-selling revenue of 2 in Example 1.Each good takes values 1 and 2 with equal probability; the bundle sells with probability 3/4.
- Motivation: Two-good optimal mechanisms are difficult to characterize, and separate selling or bundling does not maximize revenue in general.The paper frames its central question as how much optimal revenue these simple mechanisms guarantee despite their general suboptimality.
- Guarantees: 50% of optimal revenue is guaranteed by separate selling for any two independent goods.The guarantee uses each good’s optimal one-good price and makes no distributional assumptions such as monotone hazard rate.
- Guarantees: 73% of optimal revenue is guaranteed by separate selling for any two independent and identically distributed goods.The mechanism sells each good at the one-good optimal price, equivalently allowing 0, 1, or 2 units at the optimal per-unit price.
- Many goods: For k independent goods, separate selling guarantees c/log^2 k of optimal revenue, while bundling i.i.d. goods guarantees c/log k.For general independent goods, bundling can fall to a 1/k fraction; for i.i.d. goods, its performance is not uniform over distributions, including cases below 57%.
2 Preliminaries
The paper formalizes revenue maximization for a risk-neutral monopolist selling multiple additive-valued goods and defines optimal, separate, bundled, and deterministic mechanisms. It characterizes incentive compatibility and establishes basic revenue and payment properties used later.
- Model: A monopolist sells k≥1 goods to one buyer, whose value for a set of goods is additive across items.
- Model: The seller maximizes expected revenue, while the buyer and seller have quasi-linear utilities and the seller knows only the distribution of valuations.
- Revenue benchmarks: Rev(X) is the supremum expected payment over incentive-compatible and individually rational mechanisms, and it cannot exceed the expected total valuation.
- Mechanism classes: Separate and bundled mechanisms reduce revenue optimization to one-dimensional problems, whereas deterministic mechanisms remain multidimensional.
- Incentive compatibility: Incentive compatibility is equivalent to convex buyer payoff with allocation vectors serving as subgradients.
- Payment properties: Without loss of generality for revenue maximization, mechanisms can be restricted to no positive transfers, and subdomain revenue cannot exceed overall optimal revenue.
3 Two Independent Goods
For two independent goods, the paper bounds the revenue of any incentive-compatible, individually rational mechanism by twice the sum of the optimal single-good revenues. The proof partitions revenue according to which valuation is higher and converts each part into a one-good mechanism.
- Theorem A: Rev(µ; X) ≤ 2Rev(Y) + 2Rev(Z) for every two-good valuation X=(Y,Z) with independent goods.
- Proof strategy: The proof splits revenue into the regions Y≥Z and Z≥Y, with nonnegative payments allowing the two regional revenues to be added.
- Proof strategy: Fixing the second value z yields a one-good mechanism for Y by preserving the first allocation and subtracting q2(y,z)·z from payment.
- Proof strategy: Independence permits conditioning on Z=z and taking expectations, while each resulting subdomain revenue is bounded by Rev(Y).
- Proof caveat: The auxiliary mechanism need not satisfy no positive transfers because its transformed payment sz may be negative.
4 The General Decomposition Result
The section develops a decomposition bound for revenue from two independent multidimensional groups of goods. This bound relates joint optimal revenue to separate and bundled revenues of each group.
- The framework permits arbitrary dependence among coordinates within Y and within Z, while requiring independence between the two vectors.The result is therefore broader than coordinate-wise independent goods.
- The decomposition result is built by partitioning valuation space and bounding each resulting term using marginal mechanisms and smaller-value lemmas.The marginal mechanism preserves incentive compatibility and individual rationality after accounting for allocations in the fixed group.
- Rev(Y, Z) ≤ Rev(Y) + Rev(Z) + BRev(Y) + BRev(Z) for independent multidimensional Y and Z.The one-dimensional case yields the corresponding two-good inequality.
- The proof uses only incentive compatibility, individual rationality, and no positive transfers rather than the full characterization of optimal one-good mechanisms.This supports generalization beyond posted-price characterizations.
- For independent groups, the marginal mechanism on one group is bounded by its optimal revenue, while the associated smaller-value term is bounded by its bundling revenue.The smaller-value argument applies to one-dimensional sums and extends to multidimensional groups.
5 Separate and Bundled Selling
This section compares separate selling and bundling through equal-revenue benchmarks and stochastic dominance. It gives bounds in both directions and identifies distributions where bundling is optimal.
- For two i.i.d.-ER goods, bundling is optimal, and the separate-to-optimal ratio bound is tight.The equal-revenue distribution has Rev(V) = 1 at every posted price p ≥ 1.
- For any two independent goods, bundling achieves at least approximately 0.78 times the bundled revenue benchmark used in the comparison.The stated bound is w + 1 times BRev(X1, X2), with w + 1 approximately 0.78.
- For any k independent goods, separate revenue is at most a constant-logarithmic factor above bundling revenue, with a c/log k-type comparison.For i.i.d. goods, the section gives a tighter logarithmic comparison between the two mechanisms.
6 k Independent Goods
For k independent goods, the decomposition theorem yields a polylogarithmic approximation guarantee for separate selling, while bundling can be much stronger for identically distributed goods.
- c/log^2 k is a lower-bound fraction of optimal revenue guaranteed by selling k independent goods separately.The proof combines the decomposition inequality with bounds comparing bundling and separate revenues.
- Padding a non-power-of-two instance with zero-value goods at most doubles k without adding revenue.This extends the power-of-two analysis to every k.
- c/log k is a lower-bound fraction of optimal revenue guaranteed by bundling k i.i.d. goods.The proof establishes the bound first for powers of two and then pads to nearby powers of two.
- Bundling may extract only a 1/k fraction of optimal revenue for independent goods, whereas identically distributed goods admit the tighter logarithmic bound.The section explicitly contrasts the general independent case with the i.i.d. case.
- For powers of two, the proof bounds Rk by 4(log2 k + 1)Bk, where Rk is optimal revenue and Bk is bundled revenue.The argument applies Theorem 7 inductively and bounds each term using the i.i.d. comparison.
7 Additional Results
The additional results sharpen two-good guarantees, characterize equal-revenue benchmarks, identify optimal bundling cases, and extend the separate-selling guarantee to multiple buyers.
- 50% and 73% are lower bounds on separate selling for two independent goods and two i.i.d. goods, respectively.These are guarantees relative to optimal revenue.
- 78% is an upper bound on the separate-selling guarantee for two independent goods.The bound is established using two i.i.d. equal-revenue goods.
- Bundling is optimal for two i.i.d.-F goods under the theorem’s density and support condition, including equal-revenue and sufficiently heavy-tailed Pareto cases.For f(x) = cx^-γ, the condition holds when γ ≥ 3/2.
- For n independent buyers and two independent goods, optimal separate selling guarantees at least 50% of optimal revenue under either dominant-strategy or Bayesian-Nash implementation.The result uses each good’s optimal one-good mechanism.
- Under dominant-strategy implementation, the 50% guarantee remains valid with dependent buyers; the proof does not require buyer independence.In Bayesian-Nash implementation, the proof does not extend to dependent buyers.
- When buyers satisfy the stated Crémer–McLean correlation condition, the paper reports GFOR(separate) = 1; otherwise, the guarantee is not known for neither-independent-nor-identified buyers.This comparison concerns the Bayesian-Nash case with dependent buyers.
8 Open Problems
The paper identifies unresolved questions about optimal mechanisms, deterministic guarantees, distributional conditions, and mechanism complexity in multi-good settings.
- Characterizing optimal mechanisms for multiple goods remains extremely difficult, even with only two goods.
- The paper asks when separate selling is optimal and seeks bounds for deterministic mechanisms, including distributions where they are optimal.
- The gap in the i.i.d. separate-selling guarantee is small but unresolved, while the correct independent-case bound is also unknown.
- The paper calls for simple mechanisms with stronger guarantees and useful measures of complexity, including tradeoffs between complexity and revenue.
- Open directions include non-independent goods and multiple buyers that are neither independent nor satisfy the specified condition.
A.1 Proof for Two I.I.D. Goods
The appendix proves the two i.i.d.-goods guarantee by reducing the two-dimensional mechanism to conditional one-dimensional mechanisms and bounding their combined revenue.
- Selling two i.i.d. goods separately yields at least e/(e+1) of the optimal revenue.
- For each fixed z, the proof constructs a one-good mechanism for Y conditional on Y ≥z while preserving incentive compatibility, individual rationality, and buyer payoff.
- Symmetry lets the proof analyze the regions Y ≥Z and Z >Y separately, then combine the resulting inequalities.
- The proof reduces the relevant affine expression to extreme nondecreasing functions ϕ = 1_[p,∞) and bounds the resulting quantity for every p.
- The auxiliary one-good lemma bounds revenue for IC and IR mechanisms on valuations supported above a lower endpoint.
A.2 Some Comments on Decomposition
The decomposition results yield revenue bounds and explain why the proof splits valuation space, while also extending beyond additive valuations and clarifying independence requirements.
- The preliminary bound Rev(Y, Z) ≤ Rev(Y) + E[Z] can fail to suffice because E[Z] may be infinite while Rev(Z) is finite.
- Splitting the domain into Y ≥Z and Y ≤Z allows the proof to bound the resulting expectation terms.
- Rev(Y) + Rev(Z) ≥ E[min{Y, Z}], so separate mechanisms guarantee the expected minimum for two independent goods.
- A mechanism achieving E[min{Y, Z}] posts independent random prices for the two goods.
- The decomposition extends to product alternatives with additive valuations, under assumptions supporting the relevant mechanism-design results.
- Without independence, the corresponding bounds use conditional revenues, and some independence-based inequalities can fail under full correlation.
A.3 Equal Revenue (ER) Goods
The appendix analyzes equal-revenue goods through stochastic domination and weighted-sum revenue bounds, showing that bundling scales as k log k while separate selling can be logarithmically worse.
- Rev(X) ≤r holds exactly when X is stochastically dominated by rV for an equal-revenue valuation V.
- For weighted sums of two independent equal-revenue goods, equalizing coefficients produces stochastic domination.
- For k i.i.d.-ER goods, bundling revenue satisfies c1k log k ≤ BRev(V1, ..., Vk) ≤ c2k log k.
- A sharper analysis shows Rev(Σ_i Vi)/(k log k) converges to 1 as k →∞.
- Separate selling may yield no more than a fraction of the order of 1/log k of the optimal revenue for i.i.d.-ER goods.
A.4 Separate vs. Bundled Selling
For independent goods, bundling can be much worse than separate selling as the number of goods grows, while for two i.i.d. goods it retains a two-thirds revenue guarantee that is tight.
- Independent goods: 1/k: bundling can achieve at most a (1/k + ε) fraction of optimal revenue for suitable independent goods.The construction has separate revenue k, while bundled revenue is bounded by approximately 1.
- Independent goods: 3k−2: for k independent goods, optimal revenue is at most (3k−2) times bundled revenue.The argument uses induction for powers of two and pads with zero-valued goods otherwise.
- Two i.i.d. goods: 1/3: for two i.i.d. goods, bundling revenue is at least (2/3) of separate revenue.The proof prices the bundle at p when α ≤ 2/3 and at 2p when α ≥ 2/3, where p is the optimal one-good price.
- Two i.i.d. goods: 2/3: the two-i.i.d.-goods bundling guarantee is tight.For values in {0,1} with probability 2/3 on value 1, separate revenue is 4/3 and bundled revenue is 8/9.
A.5 Many I.I.D. Goods
For many i.i.d. goods, bundling approaches the sum of expected values asymptotically, but fixed-k guarantees can remain substantially lower and depend on the distribution.
- Asymptotic bundling: kE[X1]: as k tends to infinity for i.i.d. goods, bundling revenue approaches k times the one-good expectation.For finite expectation and variance, pricing at (1−ε)kE[X1] makes the bundle almost surely sell; truncation handles infinite moments.
- Fixed-k guarantees: 57%: for every sufficiently large k, bundled selling can guarantee no more than 57% of optimal revenue for k i.i.d. goods.The corresponding lower bound recalled from Proposition 14(ii) is 1/4.
- Worst-case example: 0.569: a Bernoulli distribution with probability c/k of value 1 yields bundled-to-separate revenue approaching (1−e^-c)/c ≈ 0.569.For sufficiently large k, the optimal integral bundle price is either 1 or 2; higher prices yield less revenue.
- Worst-case example: m ≥ 4: higher integral bundle prices produce revenue bounded by c^m/(m−1)!, which is smaller than the limiting revenue at prices 1 or 2.The resulting selling probability is bounded using the remainder of the e^c series.
- Optimality conditions: Rev(X)=BRev(X): under the stated condition (9) for two i.i.d. goods, bundling is optimal.The proof transforms any incentive-compatible, individually rational mechanism into a bundled mechanism with at least as much revenue.