PaperlayerView exact revision on arXiv

Source-linked AI summary

Simple Mechanisms for Subadditive Buyers via Duality

Yang Cai, Mingfei Zhao

arXiv:1611.06910v4cs.GTcs.DS

TL;DR

The paper addresses how to approximate optimal revenue with simple mechanisms for multiple buyers, including buyers with subadditive valuations. It extends a duality framework and analyzes simple posted-price mechanisms, obtaining constant-factor guarantees for XOS valuations and an O(log m) approximation for subadditive valuations.

  • Problem

    For multiple buyers, extending simple-mechanism revenue guarantees beyond valuation classes such as unit-demand and additive to general subadditive valuations remained an open problem.

    Source: §1 · p. 2

  • Method

    The authors extend the Cai-Devanur-Weinberg duality framework by relaxing valuations, choosing adaptive dual variables, and analyzing an upper bound alongside RSPM and ASPE mechanisms.

    Source: §1 · p. 3

  • Results

    A simple deterministic DSIC mechanism achieves a constant fraction of optimal BIC revenue for XOS valuations and at least Ω(1/log m) for subadditive valuations over independent items.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The paper’s guarantees apply to RSPM or ASPE mechanisms, both of which are deterministic and DSIC.

    Source: §1 · p. 3

    For general subadditive valuations, the approximation degrades to O(log m), which the authors attribute to the weaker supporting-price property available beyond XOS valuations.

    Source: §8 · p. 31

Abstract

from arXiv · show

We provide simple and approximately revenue-optimal mechanisms in the multi-item multi-bidder settings. We unify and improve all previous results, as well as generalize the results to broader cases. In particular, we prove that the better of the following two simple, deterministic and Dominant Strategy Incentive Compatible mechanisms, a sequential posted price mechanism or an anonymous sequential posted price mechanism with entry fee, achieves a constant fraction of the optimal revenue among all randomized, Bayesian Incentive Compatible mechanisms, when buyers' valuations are XOS over independent items. If the buyers' valuations are subadditive over independent items, the approximation factor degrades to $O(\log m)$, where $m$ is the number of items. We obtain our results by first extending the Cai-Devanur-Weinberg duality framework to derive an effective benchmark of the optimal revenue for subadditive bidders, and then analyzing this upper bound with new techniques.

1 Introduction

The paper addresses the challenge of designing simple, approximately revenue-optimal mechanisms for multiple buyers with subadditive valuations. It extends a duality framework and develops posted-price mechanisms and analyses that provide guarantees for XOS and subadditive valuations over independent items.

1 Introduction

  • Multiple buyers with subadditive valuations remained an open problem beyond the single-buyer results known for broader subadditive settings.Prior results covered sequential posted prices for unit-demand buyers, and separate sales or VCG with entry fees for additive buyers.Source: §1 · p. 2

1.2 Related Work

  • Earlier results established simple-mechanism approximations for unit-demand, additive, and matroid-rank valuations, while the cited multi-buyer subadditive results were limited.The paper positions its framework extension as unifying and strengthening those lines of work.Source: §1 · p. 2

1 Introduction

  • For XOS valuations over independent items, a simple deterministic DSIC mechanism achieves a constant fraction of optimal BIC revenue; for subadditive valuations, it achieves at least Ω(1/log m).The mechanisms considered are RSPM and ASPE.Source: §1 · pp. 2–3

1.1 Our Contributions

  • The paper extends the Cai-Devanur-Weinberg duality framework, relaxing valuations before deriving an analyzable revenue upper bound for subadditive bidders.For each allocation rule, it also chooses an adaptive dual so the resulting virtual welfare is easier to analyze.Source: §1.1 · p. 4
  • The analysis targets CORE, the difficult part of the prior SINGLE, TAIL, and CORE decomposition, with a new approach based on sequential posted prices and entry fees.The authors note that the supporting-price property used for XOS valuations weakens to Θ(log m)-supporting prices for general subadditive valuations, and the approximation degrades to O(log m).Source: §1.1 · pp. 4–5

2 Preliminaries

The paper considers revenue maximization with independent bidders and heterogeneous items, including subadditive valuations over independent items. It defines two sequential posted-price mechanisms that the paper analyzes.

2 Preliminaries

  • Each bidder’s type contains item-specific private information drawn independently across items, and the paper studies monotone, subadditive valuations with no externalities.XOS and constrained-additive valuations are also treated as classes over independent items.Source: §2 · p. 6
  • The copies setting represents each bidder-item pair as a single-dimensional agent, subject to matching constraints on bidders and items.The paper uses its optimal BIC revenue as OPTCOPIES-UD.Source: §2 · p. 8

2.1 Our Mechanisms

  • In the entry-fee mechanism, each bidder sees the available items before deciding whether to pay the fee and then chooses her favorite feasible bundle.The paper states that this mechanism is deterministic and DSIC.Source: §2.1 · p. 8
  • The RSPM visits bidders sequentially, offers personalized item prices, and limits each buyer to at most one item without an entry fee.The ASPE uses anonymous item prices and may charge a personalized entry fee; after paying it, a buyer may purchase any available bundle.Source: §2.1 · p. 9

3 Paper Organization

The paper first derives an upper bound for optimal revenue with subadditive bidders, then develops single-bidder bounds before presenting its main multi-buyer result.

3 Paper Organization

  • For subadditive bidders, the paper combines valuation relaxation and adaptive dual variables to bound optimal revenue by NON-FAVORITE and SINGLE.These terms are defined in Lemma 4, according to the section roadmap.Source: §3 · p. 9
  • For one subadditive bidder, optimal revenue is at most 24SREV and 16BREV.The section also introduces techniques for bounding SINGLE and NON-FAVORITE.Source: §3 · p. 9
  • For XOS or subadditive bidders, optimal revenue is upper bounded by a constant number of POSTREV or O(log m) POSTREV and APOSTENREV, respectively.The roadmap says SINGLE is bounded through OPTCOPIES-UD and NON-FAVORITE is decomposed into TAIL and CORE.Source: §3 · p. 9

4 Duality

The section formulates revenue optimization as a linear program and applies a partial Lagrangian to its Bayesian incentive constraints. The resulting dual yields virtual-welfare upper bounds on BIC revenue, with equality for the optimal dual and revenue-optimal mechanism.

4 Duality

  • The LP represents interim payments and exact-bundle allocation probabilities, with nonparticipation treated as a type so Bayesian IR becomes a BIC constraint.The partial Lagrangian is formed by lagrangifying the BIC constraints.Source: §4 · pp. 9–10
  • A dual solution has finite value exactly when each bidder’s dual variables form a valid flow over types, with source and sink nodes.Flow conservation holds at all nodes except the source and sink.Source: §4 · pp. 9–10
  • For any flow, a BIC mechanism’s revenue is at most its allocation’s virtual welfare; the optimal dual makes this bound equal optimal BIC revenue.The equality holds for the optimal dual variables and revenue-optimal BIC mechanism.Source: §4 · pp. 10–11

5 Canonical Flow and Properties of the Virtual Valuations

The section constructs flows through a parameterized partition of bidder types, then relaxes valuations to recover useful virtual-value properties. It adapts the dual benchmark to each mechanism and bounds it using revenues of simple mechanisms.

5 Canonical Flow and Properties of the Virtual Valuations

  • The flow is parameterized by item thresholds β and partitions types by affordability and favorite item, but subadditivity makes the favorite-item contribution depend on other items.That dependence prevents the direct conversion to the corresponding Myerson ironed virtual value used in the additive case.Source: §5 · pp. 11–12

5.1 Valuation Relaxation

  • For each β, the valuation relaxation preserves subadditivity and monotonicity, dominates original values, and provides a BIC mechanism with comparable revenue.The relaxed valuations also admit flows whose virtual values have properties similar to the additive case, yielding a benchmark for subadditive bidders.Source: §5.1 · p. 12

5.2 Virtual Valuation for the Relaxed Valuation

  • The chosen flow makes each item’s contribution to virtual value depend on that item’s coordinate, enabling an ironed-virtual-value expression for the relaxed valuation.The expression bounds the virtual valuation by the value of the bundle without the item plus its Myerson ironed virtual value.Source: §5.2 · p. 13

5.3 Upper Bound for the Revenue of Subadditive Buyers

  • The authors choose β separately for each mechanism, then upper-bound its revenue benchmark by revenues of simple mechanisms.The ASPE construction uses β to compute its parameters and entry fee; small random rebates handle discrete-distribution tie cases, and a deterministic rebate realization achieves at least the randomized mechanism’s expected revenue.Source: §5.3 · pp. 14–15

6 Warm Up: Single Bidder

For a single subadditive buyer, the section improves the approximation ratio from 338 to 40 and bounds optimal revenue using separate selling and grand bundling. The proof splits the revenue bound into single-item and non-favorite terms, then controls the latter through core and tail bounds.

6 Warm Up: Single Bidder

  • The warm-up improves the single-subadditive-buyer approximation ratio from 338 to 40.For one buyer, the proof sets β_j to 0 for all items.Source: §6 · p. 15
  • The optimal revenue is within a constant factor of the better of selling separately and grand bundling.The proof derives REV(M, v, D) ≤ 24 · SREV + 16 · BREV for any BIC mechanism M.Source: §6 · pp. 15, 16, 19
  • The proof bounds SINGLE(M) by 2 · SREV and NON-FAVORITE(M) by 5SREV + 4BREV.The single-item term is bounded through the copies setting; the non-favorite term is split into CORE(M) and TAIL(M).Source: §6 · pp. 16, 19
  • TAIL(M) is at most 2 · SREV, while CORE(M) is at most 3 · SREV + 4 · BREV.The core bound uses a concentration argument on a truncated valuation function.Source: §6 · pp. 16–17

7 Multiple Bidders

This section uses posted-price benchmarks to bound optimal BIC revenue for multiple bidders, analyzing tail and core components and giving bounds for XOS and subadditive valuations. It examines an anonymous sequential posted-price mechanism with entry fees for approximating the core benchmark, a constructed price sum as a proxy, and a limitation of a prior-analysis expression under general downward-closed feasibility.

7 Multiple Bidders

  • For multiple XOS bidders, REV(M,v,D) ≤ 236·POSTREV + 32·APOSTENREV; for subadditive bidders, it is at most O(log(m))·max{POSTREV, APOSTENREV}.The bounds hold for any BIC mechanism M; the supporting-price parameter is α = 1 for XOS valuations and α = O(log(m)) for general subadditive valuations.Source: §7 · p. 19

7.1 Analyzing TAIL(M, β) in the Multi-Bidder Case

  • TAIL(M, β) is bounded by 2/(1−b)·POSTREV for any BIC mechanism, via an RSPM analysis.Source: §7.1 · p. 20

7.2.1 Comparison between the Existing Methods and Our Approach

  • Prior CORE methods for constrained additive valuations rely on matroid OCRS; under general downward-closed feasibility, their bound can exceed optimal welfare, precluding a constant approximation.The comparison is restricted to constrained additive valuations because prior methods study special cases, while the authors' approach also applies to XOS and subadditive valuations.Source: §7.2.1 · p. 23

7.2 Analyzing CORE(M, β) in the Multi-Bidder Case

  • The CORE analysis replaces the original valuation with a dominated surrogate having small Lipschitz constants, enabling approximation through an ASPE or RSPM.The approach bounds the surrogate's Lipschitz constants using POSTREV and uses median-based entry fees to approximate CORE.Source: §7.2.1 · p. 23

7.2.2 Construction of \ CORE(M, β)

  • The constructed CORE surrogate preserves monotonicity, subadditivity, and no externalities, inherits α-supporting prices, and has total τ_i bounded by 4/(1−b)·POSTREV.Source: §7.2.2 · pp. 24–26
  • The analysis uses the sum of the constructed item prices as a proxy for CORE(M, β).The text states that approximating this proxy suffices to approximate the core benchmark.Source: §7.2.2 · p. 27

7.2.3 Design and Analysis of Our ASPE

  • In the ASPE, bidders accept the entry fee with probability at least 1/2, and its total revenue is comparable to CORE(M, β); combining ASPE and RSPM revenue bounds completes the proof of Theorem 4.Source: §7.2.3 · pp. 29–30

7.2.4 Bad Example for Chawla and Miller’s Approach

  • Θ(k log k) times optimal social welfare: with one bidder and general downward-closed feasibility, the expression used in Chawla and Miller’s analysis can be this large.The example has k^2 items and a feasibility constraint allowing the bidder to receive items from at most one of k disjoint sets.Source: §7.2.4 · pp. 30–31

8 Open Questions

The upper bound and SINGLE and TAIL analyses extend to subadditive valuations, but the CORE analysis relies on stronger supporting prices and limits the approximation. The section leaves open constant-factor mechanisms, constructive guarantees for asymmetric bidders, and polynomial-time computation.

8 Open Questions

  • Can simple mechanisms achieve a constant fraction of optimal revenue for multiple buyers with subadditive valuations over independent items?Source: §8 · p. 31
  • The upper bound applies to subadditive valuations, yielding a constant-factor approximation for one buyer and an O(log m)-approximation for multiple buyers.The SINGLE and TAIL analyses also extend to subadditive valuations.Source: §8 · p. 31
  • Only the CORE analysis fails to extend with constant-factor performance: XOS functions admit 1-supporting prices, while subadditive functions permit only Θ(log m)-supporting prices.The supporting-price dependence occurs in defining and comparing the proxy core and in lower-bounding ASPE revenue.Source: §8 · p. 31
  • Can sequential posted-price mechanisms achieve a constant fraction of optimal social welfare for subadditive bidders, extending the result of Feldman et al.?Source: §8 · p. 32
  • Selecting the right β is nonconstructive for asymmetric bidders; Appendix G gives a method for symmetric bidders, while the asymmetric case remains open.Source: §8 · p. 32
  • A polynomial-time algorithm for computing the simple approximately optimal mechanisms for constrained additive and XOS valuations remains an open question.Source: §8 · p. 32

A Improved Analysis for Constrained Additive Valuation

For constrained additive valuations, the paper applies its flow directly without relaxing valuations and derives improved revenue bounds. One stated bound compares BIC revenue with revenue from two posted-price mechanisms.

A Improved Analysis for Constrained Additive Valuation

B Proof of Theorem 1

The proof uses the dual objective to upper-bound mechanism revenue and, at optimal dual variables, to show that an optimal allocation maximizes virtual welfare. The additive recap describes a β-parameterized flow and its role in constructing a tighter revenue benchmark.

B Proof of Theorem 1

  • At optimal dual variables, strong duality implies that an optimal mechanism's allocation maximizes virtual welfare.The proof first establishes that the partial Lagrangian is at least the mechanism's revenue.Source: B Proof of Theorem 1 · p. 34

C Recap: Flow for Additive Valuations

  • For additive valuations, β partitions each bidder's types into a below-threshold region and one region per favorite item, with ties assigned to the smallest index.The below-threshold region has every item value below its β threshold; a favorite-item region maximizes value minus β.Source: C Recap: Flow for Additive Valuations · p. 34
  • The flow λ(β) adapts the framework of, and the figures provide a partial specification and a two-item additive example.Source: C Recap: Flow for Additive Valuations · p. 34, Figure 3 · p. 34, Figure 4 · p. 35
  • Replacing the favorite-item value with its Myerson ironed virtual value yields a structured upper bound that is at most 8 times optimal revenue for additive buyers.The paper uses this benchmark to compare simple mechanisms with optimal revenue and later overcomes difficulties applying the flow directly to subadditive valuations by relaxing valuations.Source: C Recap: Flow for Additive Valuations · p. 35

D Proof of Lemma 3

The lemma's flow routes probability across types that differ in one item's value and uses ironing when a marginal distribution is not regular. Its stated properties relate virtual values to Myerson's ironed values.

D Proof of Lemma 3

  • For a type with the largest value of item j, no flow enters except from the source; flow into lower-value types is passed down along item j.Source: D Proof of Lemma 3 · p. 36
  • When the marginal distribution F_ij is not regular, loops between types differing only in item j implement ironing of the virtual value function.Source: D Proof of Lemma 3 · p. 36
  • Lemma 34 states that for each β and bidder i, a flow exists whose virtual values are bounded by Myerson's ironed virtual values under its specified conditions.Source: D Proof of Lemma 3 · p. 36

E Analysis for the Single-Bidder Case

The single-bidder analysis works with a valuation restricted to items in C(t), then bounds its value by separating a core contribution from contributions of threshold items.

E Analysis for the Single-Bidder Case

  • The bound splits v(t, S) into a restricted-value term and a sum of single-item values for items in T(t).The restricted-value contribution is bounded by CORE(M); the remaining terms are then bounded using the threshold-region condition.Source: E Analysis for the Single-Bidder Case · p. 37
  • The proof’s monotonicity step uses that each type stays in one region R(β), allowing the restricted-value term to be bounded by the core.Source: E Analysis for the Single-Bidder Case · p. 37
  • The restricted valuation v′(t, S) = v(t, S ∩ C(t)) is monotone, subadditive, and has no externalities.The proof establishes monotonicity and subadditivity directly, and argues no externalities from the definition of C(t).Source: E Analysis for the Single-Bidder Case · pp. 37–38

F Missing Proofs for the Multi-Bidder Case

The multi-bidder proofs use restricted valuations that retain key valuation properties, and split non-favorite values into restricted and single-item contributions.

F Missing Proofs for the Multi-Bidder Case

  • The proof decomposes each non-favorite value into a restricted valuation on Ci(ti) and single-item values for items in Ti(ti).The restricted term is replaced using monotonicity when establishing the bound.Source: F Missing Proofs for the Multi-Bidder… · p. 38
  • For Xi(ti) = {j | Vi(tij) < xij}, the restricted valuation v̄i(ti, S) = vi(ti, S ∩ Xi(ti)) is monotone, subadditive, and has no externalities.The stated properties follow from restricting the bundle to Xi(ti).Source: F Missing Proofs for the Multi-Bidder… · p. 39
  • The proof also establishes that µi is τi-Lipschitz by bounding its change in terms of τi and the relevant set differences.The passage gives the bound using |X∆Y| + |X ∩ Y| − |H|.Source: F Missing Proofs for the Multi-Bidder… · p. 40

G Efficient Approximation for Symmetric Bidders

For symmetric bidders, the paper gives a polynomial-time construction of an RSPM and an ASPE, selecting the better mechanism to approximate optimal BIC revenue.

G Efficient Approximation for Symmetric Bidders

  • For symmetric bidders, the construction runs in polynomial time and the better of an RSPM and an ASPE achieves a constant fraction of optimal BIC revenue.The RSPM construction is independent of the given mechanism; the ASPE construction is adapted to symmetric bidders.Source: G Efficient Approximation for… · p. 41
  • The RSPM can approximate POSTREV by using a unit-demand revenue bound and the RSPM constructed in.The unit-demand optimum is at most 4OPTCOPIES-UD, yielding revenue at least POSTREV/24.Source: G Efficient Approximation for… · p. 41
  • For the ASPE, the construction computes ci, Qj, and τi, then uses τi to set the entry fee; sampling from type distributions requires only polynomially many samples.The initial construction depends on β, which depends on the mechanism M.Source: G Efficient Approximation for… · p. 41
  • Symmetry permits choosing β to meet Lemma 5’s requirements, and welfare maximization for v′ supplies the allocation rule used to compute Qj.The resulting ASPE or RSPM captures a constant fraction of CORE(M′, β), which is at least CORE(M*, β).Source: G Efficient Approximation for… · p. 41

H Proof of Lemma 2

The proof constructs a mechanism for transformed valuations through surrogate matching, then relates its incentives and revenue to those of the original mechanism.

H Proof of Lemma 2

  • The proof first establishes properties of v(β) and constructs a BIC mechanism M(β) from a BIC mechanism M for the original subadditive valuations.The passages state that the transformed valuations are monotone and subadditive.Source: H Proof of Lemma 2 · pp. 41–42

Phase 1: Surrogate Sale

  • In Phase 1, each buyer reports a type and is matched to a surrogate through VCG prices on a graph weighted by interim allocation value minus scaled interim payment.Replicas and independently sampled surrogates form the two sides of the graph; unmatched replicas are paired with random unmatched surrogates.Source: Phase 1: Surrogate Sale · p. 42

Phase 2: Surrogate Competition

  • In Phase 2, the mechanism runs M on the selected surrogate types and charges matched buyers the scaled payment plus their VCG price.Unmatched buyers receive nothing and pay nothing.Source: Phase 2: Surrogate Competition · pp. 42–43
  • When buyers report truthfully, each selected surrogate’s type is distributed as Di, supporting the BIC argument for M(β) under v(β).Truthful reports are critical to the distribution argument and to using VCG truthfulness in the incentive proof.Source: Phase 2: Surrogate Competition · p. 43
  • The revenue comparison accounts for imperfect VCG matchings by bounding prices from unmatched surrogates through a maximal same-type matching and augmenting paths.The proof first shows the expected size of the same-type matching is close to ℓ, then bounds prices of surrogates it matches but VCG does not.Source: Phase 2: Surrogate Competition · p. 44

Related papers

Loading 1611.06910v4…