PaperlayerView exact revision on arXiv

Source-linked AI summary

A Simple and Approximately Optimal Mechanism for an Additive Buyer

Moshe Babaioff, Nicole Immorlica, Brendan Lucier, S. Matthew Weinberg

arXiv:1405.6146v3cs.GT

TL;DR

Multi-item revenue optimization is difficult because optimal mechanisms can be highly complex. The paper compares separate selling and bundling, showing that the better option gives a 6-approximation for a single additive buyer with independent values. It also examines extensions to multiple buyers and correlated values.

  • Problem

    Multi-item optimal mechanisms can require randomization, infinite menus, non-monotonicity, or intractable computation, motivating simple approximation methods.

  • Method

    The paper takes the a priori better revenue from selling items separately at optimal prices and selling the grand bundle at an optimal price.

  • Results

    6-approximation: either separate selling or bundling achieves a factor-6 approximation to optimal revenue for one additive buyer with independent item values.

  • Takeaways & Limitations

    A simple deterministic mechanism provides a constant-factor revenue guarantee and remains computationally tractable, including with reasonable distribution access.

  • Takeaways & Limitations

    The paper’s broader extensions have weaker or different guarantees, including O(log n) bounds for multiple buyers and open questions for general subadditive valuations.

Abstract

from arXiv · show

We consider a monopolist seller with $n$ heterogeneous items, facing a single buyer. The buyer has a value for each item drawn independently according to (non-identical) distributions, and her value for a set of items is additive. The seller aims to maximize his revenue. We suggest using the a-priori better of two simple pricing methods: selling the items separately, each at its optimal price, and bundling together, in which the entire set of items is sold as one bundle at its optimal price. We show that for any distribution, this mechanism achieves a constant-factor approximation to the optimal revenue. Beyond its simplicity, this is the first computationally tractable mechanism to obtain a constant-factor approximation for this multi-parameter problem. We additionally discuss extensions to multiple buyers and to valuations that are correlated across items.

1 Introduction

Multi-item revenue optimization is substantially more complex than solving independent single-item problems, yet the better of selling separately and bundling together gives a simple constant-factor approximation under independent item values.

  • 1 Introduction: Optimal multi-item mechanisms can require randomization, infinite menus, non-monotonicity, or computationally intractable designs.These complexities motivate studying simple approximately optimal mechanisms.
  • 1.1 A Single Additive Buyer: Selling items separately can be suboptimal even for additive buyers, while bundling can be highly suboptimal in other instances.For a two-item example, bundling at price 3 yields expected revenue 9/4, exceeding separate-sale revenue 2; another construction gives bundling revenue O(1) versus separate-sale revenue n.
  • 1.2.1 Main Result: The a priori better of selling separately and bundling together guarantees a 6-approximation to optimal revenue for one additive buyer with independent item values.The formal theorem states Rev(D) ≤ 6 max{SRev(D), BRev(D)}.
  • 1.2.1 Main Result: The approach is deterministic, computationally tractable, and robust, extending constant-factor approximability beyond exact knowledge of the value distributions.The paper states that a constant-factor approximation can be found in polynomial time with reasonable access to the distributions.
  • 1.2.1 Main Result: Bundling handles instances where total value concentrates, while separate selling covers cases where rare high-value items drive revenue.The analysis uses a decomposition distinguishing concentrated core value from tail events.
  • 1.2.2 Additional results: Extensions show O(log n) guarantees for separate selling with multiple buyers, while the better of separate selling and bundling can require an Ω(log n) approximation in that setting.The paper also studies partition mechanisms and correlated values, where guarantees differ from the independent single-buyer case.

2 Complexity of Optimal Multi-Item Mechanisms

Known examples show that optimal multi-item mechanisms can be highly complex even for additive buyers, with complexity arising from non-monotonicity, computational difficulty, and correlation.

  • Examples and themes: Simple examples demonstrate that optimal mechanisms may be surprisingly complex even when the buyer is additive and the distributions are simple.This motivates seeking approximation guarantees without restricting distributions narrowly.
  • Revenue Non-Monotonicity: Revenue can be non-monotone: a stochastically better distribution can have strictly lower optimal revenue than the original distribution.Hart and Reny exhibit such distributions with i.i.d. marginals for two items.
  • Computational Intractability: For discrete product distributions with two-point supports, computing the optimal mechanism raises computational tractability concerns despite polynomial-size input descriptions.Each item distribution is specified by three rational numbers of polynomial bit complexity.
  • Infinite Gaps with Correlation: With correlated item values, the optimal revenue can be infinite while every mechanism with menu complexity C earns at most C.This creates potentially unbounded gaps between unrestricted mechanisms and bounded-menu mechanisms.
  • Examples and themes: In contrast, the paper’s approximately optimal maximum of separate selling and bundling is deterministic, revenue-monotone, and implementable in polynomial time.The text notes that its menu complexity is polynomially approximable, although exact separate selling technically has exponential menu complexity.

3 Related Work

Related work develops the simple-versus-optimal approximation agenda from single-item and unit-demand settings to additive buyers, while extending guarantees to broader buyer, correlation, and complexity settings.

  • Hartline and Roughgarden initiated the study of simple mechanisms through approximation to optimal revenue, first in single-dimensional settings.
  • For a single additive buyer, Hart and Nisan obtained an O(log^2 n) guarantee for separate selling and an O(log n) guarantee for bundling with i.i.d. items.
  • Li and Yao improved separate selling to O(log n), tight, and bundling for i.i.d. items to O(1); this work improves the guarantee to 6 without assumptions.
  • Subsequent work established constant-factor guarantees for broader valuation classes, correlated-feature models, and multiple buyers using posted prices with entry fees.
  • The approximation frontier remains open for stronger schemes and valuations: the existence of FPTAS/PTAS/QPTAS guarantees and constant-factor results for all subadditive valuations is unresolved.

4 Preliminaries

The preliminaries formalize additive buyers, incentive-compatible mechanisms, revenue benchmarks for optimal, separate, bundled, and partition mechanisms, and basic revenue-welfare bounds.

  • The model has n heterogeneous indivisible items and m additive, risk-neutral, quasi-linear buyers with independently sampled nonnegative values from known distributions.
  • The revelation principle permits restricting attention to direct Bayesian incentive-compatible mechanisms without loss of optimal revenue.
  • Rev(D), SRev(D), BRev(D), and PRev(D) denote optimal revenue, separate selling, grand-bundle selling, and partition mechanisms, respectively.
  • Separate selling and bundling are partition mechanisms, and every partition mechanism is dominant-strategy incentive compatible.
  • Rev(D) ≤ Val(D), while the preliminary bound Rev(D) ≤ n · m · SRev(D) relates optimal revenue to separate-selling revenue.

5 The Core-Tail Decomposition

The core-tail framework separates unusually high item values from bounded core values, decomposing optimal revenue into tail revenue and core welfare.

  • Here r_i is the optimal revenue from item i, r = Σ_i r_i equals SRev(D), and p_i is the probability that item i lies in the tail.
  • For each item, the tail consists of values above t_i r_i, while the core consists of values at or below that threshold.
  • The decomposition conditions on which items are in the tail, combining their tail distributions with core distributions for the remaining items.
  • Lemma 3 provides the tail-probability bound p_i ≤ 1/t_i for every item.
  • Lemma 6 bounds optimal revenue by tail revenue plus expected core welfare, rather than by the sum of tail and core revenues.

6 Main Result: Revenue Bounds for a Single Buyer

For a single buyer, the analysis uses a Core-Tail decomposition to show that simple selling mechanisms approximate optimal revenue. Selling separately alone gives a logarithmic bound, while choosing the better of separate selling and bundling yields a constant-factor guarantee.

  • Warm-up bound: (ln n + 3)SRev(D) ≥ Rev(D) for a single buyer, establishing a logarithmic warm-up bound for separate selling alone.The bound follows by combining tail-revenue and core-welfare estimates and is minimized at c = 1.
  • Warm-up bound: The tail bound is at most (1 + 1/c)SRev(D) when each cutoff is t_i = cn.The argument uses the fact that each item enters the tail with probability at most 1/(cn), so tail events often contain at most one item.
  • Main result: 6 · max{SRev(D), BRev(D)} ≥ Rev(D) for a single buyer and n items.Here, SRev sells items separately and BRev sells the grand bundle; the bound is attributed to Theorem 2.
  • Main result: The proof applies Core-Tail decomposition, separately bounding tail revenue and core welfare with cutoffs scaled inversely to each item's optimal separate-selling revenue.The choice t_i = cr/r_i gives every item the same absolute core-tail boundary, cr = cSRev(D).
  • Main result: Core welfare is controlled through variance bounds, allowing separate selling to handle low core welfare and bundling to extract revenue when core welfare is sufficiently concentrated.The core values have bounded support, which yields a variance bound used in the comparison between SRev and BRev.
  • Main result: The constant-factor analysis improved to 5.2, while an example shows the approximation ratio cannot be improved below 2; narrowing the gap remains open.The cited construction achieves max{SRev(D), BRev(D)} = (1/2 + o(1)) · Rev(D).

7 Revenue Bounds for Multiple Buyers

For multiple buyers with independently sampled valuations, the paper bounds the performance of separate selling and studies when bundling or partition pricing can match it. Separate selling gives a logarithmic approximation generally, while stronger constant-factor relationships require i.i.d. buyers or items.

  • 7.2 Comparing SRev(D), BRev(D), PRev(D) for multiple buyers: Without i.i.d. buyers or items, max{SRev(D), BRev(D)} can be only an Ω(ln n)-approximation to PRev(D), and this gap is tight.The lower bound is witnessed by a construction in which different buyer-item structures make separate selling and bundling ineffective together.
  • 7.1 Extension: (ln n + 6)SRev ≥Rev: Theorem 3 gives (2 + 2e^1/4 + ln 4 + ln n)SRev(D) ≥ Rev(D), hence separate selling is a logarithmic approximation for any number of buyers and items.The constant term is less than 6.
  • 7.1 Extension: (ln n + 6)SRev ≥Rev: The proof amplifies an initial revenue bound by repeatedly applying a core-tail decomposition until it reaches the desired logarithmic approximation.The amplification theorem improves a current bound parameter a using tail-revenue and core-welfare bounds.
  • 7.2 Comparing SRev(D), BRev(D), PRev(D) for multiple buyers: When either buyers or items are i.i.d., PRev(D) is at most a constant factor larger than max{SRev(D), BRev(D)}.This is stated separately for i.i.d. buyers and for i.i.d. items.
  • 7.4 A Concentration Result: The multiple-buyer extension identifies welfare concentration as the remaining obstacle: unless welfare is sufficiently concentrated, separate selling is a constant-factor approximation, but concentration alone does not make partition pricing constant-factor optimal.Proposition 8 shows that concentrated welfare can still leave PRev(D) far from Rev(D).

8 One Buyer with Correlated Values

For a single buyer with arbitrarily correlated item values, the paper compares separate, bundle, and partition pricing even though deterministic mechanisms may not approximate optimal revenue. Separate selling remains within a logarithmic factor of bundle and partition revenue, and this bound is tight.

  • 8 One Buyer with Correlated Values: The section studies these pricing relationships despite prior results showing that deterministic mechanisms have no non-zero approximation guarantee to optimal revenue under correlation.The comparison therefore concerns mechanisms of varying complexity rather than approximation to Rev(D).
  • 8 One Buyer with Correlated Values: For arbitrarily correlated values, BRev(D) ≤ 5 ln(n)SRev(D), and therefore PRev(D) ≤ 5 ln(n)SRev(D).The comparison concerns one buyer and n items.
  • 8 One Buyer with Correlated Values: The logarithmic comparison is tight: some correlated distribution satisfies max{SRev(D), BRev(D)} ≤ PRev(D)/Ω(ln n).Thus taking the better of separate and bundle revenue cannot improve the worst-case order.

A Summary of Known Results

The tables summarize known approximation gaps among revenue benchmarks for independent-item and correlated-item settings, including results for multiple buyers.

  • A Summary of Known Results: Table 1 reports upper and lower bounds comparing revenue benchmarks for one buyer with independently sampled item values.Top entries are universal approximation bounds; bottom entries exhibit distributions witnessing the bounds.
  • A Summary of Known Results: Table 3 concerns many buyers with independent item values and records the corresponding known results.

B Omitted Proofs from Section 4

The omitted proofs develop marginal-mechanism and sub-domain arguments, then apply them to bound optimal revenue using itemwise revenue and valuation terms.

  • B Omitted Proofs from Section 4: The marginal mechanism lemma bounds joint optimal revenue by one domain’s valuation plus conditional revenue from the other domain.Rev(D, D′) ≤ Val(D) + E_w←D[Rev(D′|v = w)].
  • B Omitted Proofs from Section 4: The constructed mechanism sells one item set using imaginary items, monetary substitutions, and rebates while preserving truthfulness on the conditioned sub-domain.Outside the sub-domain, revenue is non-negative but truthful reporting is not guaranteed.
  • B Omitted Proofs from Section 4: On a conditioned sub-domain, revenue is bounded by the corresponding conditional valuation plus the other domain’s optimal revenue.s · Rev(D × D′ | S) ≤ s · Val(D | S) + Rev(D′).
  • B Omitted Proofs from Section 4: For one buyer, partitioning types by favorite item yields Rev(D) ≤ n · SRev(D).The proof bounds each favorite-item region using single-item revenue and sums over all items.
  • B Omitted Proofs from Section 4: The same reduction extends to m buyers, giving Rev(D) ≤ n · m · SRev(D).A multi-buyer mechanism induces truthful single-buyer mechanisms by sampling make-believe buyers.

C Omitted Proofs from Section 5

These omitted proofs use stochastic dominance and sub-domain stitching to transfer revenue bounds between related distributions and decompose distributions into components.

  • C Omitted Proofs from Section 5: The taxation principle identifies a fixed menu with an equivalent truthful mechanism.
  • C Omitted Proofs from Section 5: For one item, stochastic dominance of every independent marginal implies weakly higher optimal revenue.If each marginal of D+ stochastically dominates the corresponding marginal of D, then Rev(D+) ≥ Rev(D).
  • C Omitted Proofs from Section 5: Sub-domain stitching combines revenue bounds over a partition of the distribution’s support.The proof applies the lemma because the component supports form a partition.

D Omitted Proofs from Section 6

The omitted proofs rely on a single-item posted-price approximation theorem, with deterministic or randomized prices depending on the version used.

  • D Omitted Proofs from Section 6: The analysis allows random prices for arbitrary distributions, while regular distributions permit deterministic prices in the relevant theorem.
  • D Omitted Proofs from Section 6: A posted-price mechanism achieves at least Rev(D)/2 for a single item with independently valued buyers.
  • D Omitted Proofs from Section 6: The randomized-price version additionally keeps the total sale probability at most one half and uses i.i.d. prices for i.i.d. buyers.
  • D Omitted Proofs from Section 6: The deterministic-price version achieves the same Rev(D)/2 guarantee, with identical prices for i.i.d. buyers.

E.1 Proof of Theorems 5 and 6

The proof partitions item sets into those whose revenue is well captured by separate selling and those whose revenue is well captured by bundling. This dichotomy lets either separate selling or grand bundling approximate the relevant optimal revenues.

  • An α-separable set satisfies SRev(DS) ≥ α·BRev(DS).
  • A collection of disjoint α-separable sets contributes at most a 1/α factor more revenue under separate selling than their bundled revenues.
  • A common buyer witnessing β-bundlability lets grand bundling capture at least β/4 of the summed bundle revenues.
  • For i.i.d. items, equal-sized sets share the same distribution, so either all such sets are separable or one buyer is bundling-good for all of them, yielding a (1/2048)-approximation.
  • The proof classifies every set that is not (1/1024)-separable as (1/16)-bundlable for some buyer, establishing the separable-or-bundlable dichotomy.

E.2 Analysis of Multi-buyer Lower Bounds

The multi-buyer lower-bound constructions show that separate selling and grand bundling can each miss substantial revenue. Partition mechanisms can combine the strengths of both approaches and achieve asymptotically higher revenue.

  • A second construction has SRev(D)=n and PRev(D)=Ω(n ln n), while grand-bundle revenue remains O(n).
  • For each small partition part with at most n^1/4 items, bundling revenue is at most 25 times the part size.
  • For larger parts, concentration bounds imply that grand-bundle revenue is also at most 25 times the part size.
  • For a construction with √n buyers and disjoint item groups, separate selling earns n while partition selling earns Ω(n log n).
  • In that construction, grand bundling earns O(√(n ln n)), so max{SRev(D), BRev(D)} is O(n) while partition revenue is Ω(n log n).

F.1 Proof of Theorem 8

The proof reduces the worst case for the bundling-to-separate-selling ratio to symmetric distributions whose total value is fixed. It then bounds that ratio by logarithmic concentration and marginal-revenue arguments.

  • A point-mass-in-sum distribution has a fixed total value p with probability one.
  • Any distribution can be transformed into a point-mass-in-sum distribution without decreasing BRev(D)/SRev(D).
  • Randomly permuting item values produces a symmetric distribution with the same bundling revenue and no larger separate-selling revenue.
  • For any symmetric point-mass-in-sum distribution, BRev(D) ≤ 5 ln(n) SRev(D).
  • The logarithmic bound follows by scaling SRev(D)=n, bounding each marginal’s revenue, and comparing total value p with the sum of marginal values.
  • A constructed distribution with independently activated item blocks has SRev(D)=n, PRev(D)=Ω(n ln n), and BRev(D)=O(n).

G Computational Considerations

The paper gives a polynomial-time implementation of the better-of-separate-selling-and-bundling idea using sample access and a direct test for a sufficiently good bundle price. The guarantee is probabilistic and depends on approximate item prices and sampling accuracy.

  • For one buyer, 6·max{SRev(D), BRev(D)} ≥ Rev(D), giving a constant-factor revenue guarantee.
  • Sample access alone can require very many samples for arbitrary distributions because rare values may be exponentially large.
  • If the separate-selling mechanism is not already a 6-approximation, a bundle price selling with probability at least 47/72 provides the needed guarantee.
  • The algorithm uses ln(1/δ)/ε^2 samples from each distribution to form samples of grand-bundle values.
  • With probability at least 1−δ, the algorithm obtains a 6α-approximation in time poly(ln(1/δ), 1/ε, n), for α ≥ 1+2ε.
  • It selects an empirical bundle price whose sale probability is at least 47/72−ε, then compares its revenue with the separate-selling revenue estimate.
Loading 1405.6146v3…