Abstract
We study anonymous posted price mechanisms for combinatorial auctions within a Bayesian framework. In these mechanisms, item prices are set upfront, and consumers approach the seller sequentially in an arbitrary order to purchase their preferred bundle of remaining items. While such mechanisms are transparent and inherently dominant strategy incentive compatible (DSIC), their efficiency in complex markets was previously unclear. We demonstrate that for fractionally subadditive (XOS) valuations—a broad class including all submodular functions—there exist prices that guarantee at least half of the optimal expected social welfare. Our approach is constructive and computationally efficient, providing a polynomial-time mechanism that requires only sample access to valuation distributions and demand query oracles. Furthermore, we extend these results to valuations with complements, where the approximation factor scales linearly with the level of complementarity.
Introduction
In market design, the ideal auction mechanism achieves three goals: economic efficiency (allocating goods to those who value them most), computational tractability, and simplicity for participants. Combinatorial auctions, where buyers seek bundles of items such as spectrum licenses or cloud computing resources, are notoriously difficult to design. The Vickrey-Clarke-Groves (VCG) mechanism, while theoretically optimal for truthfulness and efficiency, is often computationally prohibitive and complex for bidders to navigate.
This paper explores "posted price" mechanisms as a robust alternative. In this model, the seller sets a price for each item, and buyers arrive sequentially to pick their favorite available bundle. These mechanisms are inherently Dominant Strategy Incentive Compatible (DSIC) because buyers face a take-it-or-leave-it offer, removing any incentive for strategic manipulation. The central question is whether these simple, anonymous prices can approximate the social welfare of the optimal, yet often unattainable, allocation.
The Sequential Posted Price Mechanism
The authors operate within a Bayesian framework, where the seller knows the probability distribution of buyer valuations but not the specific realized values. The mechanism follows four distinct stages:
- Pricing: The seller determines a fixed price for every item in the inventory.
- Ordering: Buyers arrive in a sequence. Crucially, the authors prove their results hold even if this order is determined by an adversary.
- Realization: Buyers learn their private valuations for different bundles.
- Consumption: Each buyer, in turn, selects the bundle of remaining items that maximizes their utility (valuation minus price) and pays the posted prices.
The Price Computation Algorithm
The technical core of the paper is the method for determining these prices. Drawing inspiration from "prophet inequalities" in optimal stopping theory, the authors propose setting the price of an item to approximately half of its expected contribution to the optimal social welfare.
To ensure the mechanism is practical, the authors show that if one has "black-box" access to an algorithm capable of solving the underlying allocation problem (even approximately) and can sample from the valuation distributions, these prices can be computed in polynomial time. This makes the mechanism "truly polytime," as its complexity scales with the number of items ($m$) and buyers ($n$), rather than the exponential size of the buyers' potential preference sets.
Key Insights and Theoretical Results
Robustness to Arrival Order
A significant finding is that the 1/2-approximation guarantee for XOS valuations is independent of the arrival order. Whether buyers arrive randomly or in the worst possible sequence for the seller, the mechanism still captures at least 50% of the maximum possible social welfare. This sequentiality provides a stability that simultaneous Walrasian equilibrium models often lack in complex valuation spaces.
The "Half-Optimal" Balance
The choice to set prices at half the expected marginal contribution serves a dual purpose. It prevents prices from being so high that items remain unsold, while also ensuring they are high enough to prevent early buyers from "cannibalizing" items that would be more valuable to later participants.
Beyond Submodularity: Handling Complements
While the strongest results apply to complement-free (XOS) valuations, the authors extend their analysis to the Maximum over Positive Hypergraphs (MPH) hierarchy. This allows the mechanism to handle goods that are complements (where the value of a bundle is greater than the sum of individual items). In these cases, the efficiency guarantee degrades gracefully: for a complementarity level of $k$, the mechanism achieves a $1/4k$ approximation of the optimal welfare.
Conclusion and Future Work
This work provides the first computationally efficient, constant-factor DSIC mechanism for Bayesian submodular combinatorial auctions using simple posted prices. By bridging the gap between complex market theory and simple pricing strategies, it offers a blueprint for designing transparent and robust markets.
Future research directions include narrowing the gap for subadditive valuations, where currently only a logarithmic approximation is known. Additionally, exploring the impact of multiple identical items (multi-unit auctions) could potentially yield even higher approximation factors, further narrowing the gap between simple posted prices and the theoretical optimum.
Summary updated