Source-linked AI summary
Combinatorial Auctions via Posted Prices
Michal Feldman, Nick Gravin, Brendan Lucier
TL;DR
The paper studies whether simple anonymous posted prices can approximately implement efficient combinatorial-auction outcomes when valuations are privately known and drawn from known distributions. It constructs prices using allocation algorithms, distribution samples, and valuation oracles, obtaining constant-factor welfare guarantees and DSIC mechanisms for XOS and submodular valuations. The approach extends to complementarities, but its guarantee worsens with complementarity and constant approximation remains open for general subadditive valuations.
Problem
Whether anonymous posted prices can achieve approximately efficient outcomes for combinatorial auctions with incomplete information, where prices must be set without observing valuation realizations.
Method
The paper constructs posted prices from black-box allocation algorithms, samples from valuation distributions, and valuation and demand query access.
Results
For XOS valuations, the mechanism achieves at least a 1/2-approximation to optimal expected welfare and yields polynomial-time DSIC mechanisms, including for submodular valuations.
Takeaways & Limitations
Anonymous posted prices can provide simple, transparent, DSIC constant-factor mechanisms for Bayesian XOS and submodular combinatorial auctions.
Takeaways & Limitations
Constant approximation for subadditive valuations remains open, while guarantees for MPH-k valuations degrade with complementarity and become an Ω(m) fraction for general monotone valuations.
Abstract
from arXiv · showhide
We study anonymous posted price mechanisms for combinatorial auctions in a Bayesian framework. In a posted price mechanism, item prices are posted, then the consumers approach the seller sequentially in an arbitrary order, each purchasing her favorite bundle from among the unsold items at the posted prices. These mechanisms are simple, transparent and trivially dominant strategy incentive compatible (DSIC). We show that when agent preferences are fractionally subadditive (which includes all submodular functions), there always exist prices that, in expectation, obtain at least half of the optimal welfare. Our result is constructive: given black-box access to a combinatorial auction algorithm A, sample access to the prior distribution, and appropriate query access to the sampled valuations, one can compute, in polytime, prices that guarantee at least half of the expected welfare of A. As a corollary, we obtain the first polytime (in n and m) constant-factor DSIC mechanism for Bayesian submodular combinatorial auctions, given access to demand query oracles. Our results also extend to valuations with complements, where the approximation factor degrades linearly with the level of complementarity.
1 Introduction
The paper asks whether anonymous posted prices can achieve approximately efficient outcomes for combinatorial auctions with incomplete information. It gives constructive, polynomial-time mechanisms with welfare and incentive guarantees for XOS valuations and extensions to complementarities.
- Motivation: Anonymous posted prices offer simple, transparent, DSIC implementation, but their effectiveness under incomplete information is the central question.Agents sequentially purchase favorite bundles at common item prices; the mechanism is also weakly group strategyproof.
- Main guarantees: For XOS valuations, posted prices achieve at least a 1/2-approximation to optimal expected welfare.The guarantee applies to XOS valuations, which strictly include submodular valuations, and the factor is tight even for a single item.
- Construction: The construction computes prices in polynomial time from an allocation algorithm, valuation-distribution samples, valuation queries, and demand queries.Demand queries are needed only to simulate agents’ consumption behavior.
- Computational implications: The resulting mechanisms are polynomial in n and m and DSIC, yielding constant-factor mechanisms for Bayesian XOS and submodular combinatorial auctions.The paper emphasizes runtime independent of valuation type-space size and the stronger DSIC guarantee rather than BIC.
- Complementarities: For MPH-k valuations, the welfare guarantee degrades with complementarity, reaching an Ω(m) fraction of OPT for general monotone valuations, and this bound is tight.The paper also leaves constant approximation for general subadditive valuations open.
2 Preliminaries
The paper studies complement-free and complementary valuation classes, together with the oracle models used to represent valuations and compute allocations. XOS valuations generalize submodular valuations, while MPH-k captures complementarity levels across monotone valuations.
- Valuation Classes: The complement-free hierarchy is additive ⊂ gross substitutes ⊂ submodular ⊂ XOS ⊂ subadditive.
- Related mechanism access: A prior approach could combine its methodology with single-agent submodular maximization to obtain a constant-factor DSIC mechanism, but not within the posted-price paradigm.
- Valuation Classes: MPH is a hierarchy encompassing all monotone valuations, with its level representing the degree of complementarity.
- Computational model: The computational model provides value, demand, and XOS oracles for accessing valuations and their market-relevant choices.A demand oracle returns a utility-maximizing bundle at given prices; an XOS oracle returns an additive representative for a queried set.
- Computational model: Demand queries represent the basic buyer decision problem under item prices, while XOS queries can be simulated with polynomially many value queries for submodular functions.
3 Posted Prices for XOS Valuations
The paper constructs anonymous posted prices for XOS valuations by pricing items from expected welfare contributions under an allocation algorithm. The resulting mechanisms provide welfare guarantees for arbitrary arrival orders and can be computed from samples and valuation oracles.
- Theorem and computation: Theorem 3.1 guarantees that, for every ε > 0, polynomial-time-computed prices achieve the stated welfare approximation for any buyer arrival order.
- Theorem and computation: The construction assumes black-box access to a welfare-maximization algorithm A and an XOS query oracle for sampled valuations.
- Implications: Using an α-approximation algorithm A yields a posted-price approximation of α/2 up to an arbitrarily small additive error; direct implementation requires demand queries.
- Implications: For submodular valuations, the approach uses a 1 − 1/e allocation algorithm and simulates XOS queries with value queries, yielding polynomial-time prices.
- Implications: For gross substitutes, demand queries support both polynomial-time demand implementation and optimal allocation, enabling a value-query implementation of the direct mechanism.
- Proof strategy: The proof first establishes welfare under ideal prices and robustness to small perturbations, then computes sufficiently accurate empirical price estimates.
- Welfare analysis: The welfare analysis combines buyer-utility and expected-revenue bounds, allowing arbitrary tie-breaking among demanded bundles.
- Price computation: Prices are estimated by repeatedly sampling valuation profiles, running A, querying the relevant XOS representative, and averaging each item’s welfare contribution.
4 Posted Prices for General Valuations
The paper extends anonymous posted-price guarantees from XOS valuations to the MPH hierarchy, which captures valuations with bounded complementarity and ultimately all monotone valuations. Given algorithmic and oracle access, it computes prices achieving welfare guarantees whose approximation worsens with complementarity level.
- Guarantee: The mechanism achieves an O(k)-approximate dominant strategy incentive compatible mechanism for MPH-k valuations.The result is essentially tight because item prices can incur a loss linear in the number of items at each complementarity level k.
- MPH hierarchy: MPH-k valuations are maxima over positive hypergraph-k functions, with k bounding the largest hyperedge and therefore the complementarity level.MPH-1 captures XOS valuations, while MPH-m captures all monotone functions.
- Theorem 4.1: Theorem 4.1 assumes sample access to the Bayesian distribution, black-box access to a welfare-maximization algorithm, and an MPH-k query oracle.Under these assumptions, item prices can be computed in time POLY(m^k, n, 1/ε).
- Proof challenge: The proof must account for an item's contributions across every hyperedge in which it appears, complicating both price selection and welfare bounds.This is the main additional difficulty relative to the XOS analysis.
- Computational scope: The runtime has exponential dependence on k because an MPH-k oracle may return an explicit hypergraph representation of size O(m^k).The paper notes that restrictions on the complexity of the MPH representation could reduce this dependence.
5 Discussion and Open Problems
The discussion examines robustness to arrival-order assumptions and identifies open questions about valuation classes, arrival processes, item divisibility, and heterogeneous goods. It also records a logarithmic guarantee for subadditive valuations and leaves constant approximation open there.
- Arrival orders: The same guarantees extend from arbitrary arrival orders to adaptive adversaries that observe prior purchases and realized valuations.The adversary still chooses the next arrival sequentially after observing earlier outcomes.
- Valuation classes: The results imply a logarithmic approximation for subadditive valuations, while a constant approximation for subadditive valuations remains open.The implication follows from the constant approximation established for XOS valuations.
- Arrival orders: The paper asks whether random or mechanism-selected arrival orders improve approximability compared with the adversarial-order setting.It also asks whether constant approximation survives an adversary that observes all valuation realizations before selecting the order.
- Market structure: The paper assumes indivisible, heterogeneous items and proposes studying markets with multiple identical copies and at most one copy of each item wanted per buyer.The intended goal is to analyze efficiency as a function of the minimum number of item copies.
A Details of the proof of Theorem 3.1
The proof computes approximate ideal prices by averaging bounded samples from the valuation distribution and uses concentration bounds to control every item's price error. These approximate prices preserve the welfare guarantee up to an additive error.
- Price estimation: The algorithm estimates each ideal item price from t independent samples whose values lie in [0, 1].The empirical average is used as the computed price.
- Concentration guarantee: Hoeffding concentration and a union bound ensure |p′_j − p_j| < ε/2m for every item with probability at least 1 − ε/n.The per-item failure probability is bounded before applying the union bound over all items.
- Sample complexity: The required sample count is t = (log m + log n − log ε)4m^2/ε^2.This choice achieves the simultaneous price-accuracy guarantee.
- Welfare guarantee: With δ = ε/2m, the computed prices generate welfare at least 1/2 E_v∼F[SW(A(v))] − ε/2 with probability at least 1 − ε/n.The result follows by applying the welfare bound for prices close to the ideal vector.
B Proof of Theorem 4.1: MPH valuations
For MPH valuations, the proof constructs ideal prices by distributing hyperedge weights across their items, then estimates those prices from samples. A welfare analysis compares the resulting sequential consumption to the benchmark allocation and yields a 4k-factor guarantee.
- Ideal prices: For each allocation returned by algorithm A, the proof selects a supporting positive hypergraph representation whose value matches the buyer's value on that allocation.Hyperedge weights define the item-level contributions used to construct prices.
- Ideal prices: Each hyperedge's weight is divided uniformly among its items, and item j's total share is scaled down by α to form its ideal price.These prices are defined for full-information valuation profiles and then averaged in the Bayesian setting.
- Welfare analysis: The proof bounds the value lost when items already sold before buyer i's arrival are removed from the benchmark allocation.It uses an independently sampled profile for the other buyers to relate these losses to expected prices and welfare.
- Welfare guarantee: The analysis concludes that choosing α = 2 makes posted-price welfare within a factor 4k of algorithm A's expected welfare, up to additive error 2mδ.The factor reflects the complementarity level k in MPH-k valuations.
- Price computation: The computed MPH-k prices use t = (log m + log n − log ε)16m^2/ε^2 samples and achieve welfare at least 1/2 with probability at least 1 − ε/n.The prices are estimated using algorithm A together with the MPH-k query oracle.
C Lower bound for MPH
A unit-demand buyer arriving before a single-minded buyer creates a linear welfare gap for fixed item prices. Regardless of the price level, the posted-price outcome achieves at most 1 welfare while OPT is m−1.
- OPT is m−1 when the single-minded buyer receives all m identical items.
- If any item costs less than 1, the first unit-demand buyer buys it and the second buyer obtains zero value from the remainder, yielding welfare 1.
- If every item costs at least 1, neither buyer purchases, so the resulting welfare is 0.
- Thus, fixed item prices produce welfare at most 1 in either case, versus OPT of m−1.