Abstract: 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.
Recommendations
Cited in
(58)- Equivalence of auctions and posted prices
- Designing cost-sharing methods for Bayesian games
- Simple combinatorial auctions with budget constraints
- Strategyproof facility location in perturbation stable instances
- Learning in auctions: regret is hard, envy is easy
- Optimal item pricing in online combinatorial auctions
- Quality of local equilibria in discrete exchange economies
- Pricing multi-unit markets
- Prophet secretary through blind strategies
- Improved prophet inequalities for combinatorial welfare maximization with (approximately) subadditive agents
- From pricing to prophets, and back!
- Fair allocation of indivisible goods: beyond additive valuations
- Revenue maximization for market intermediation with correlated priors
- Designing cost-sharing methods for Bayesian games
- Clearing markets via bundles
- Iterative Combinatorial Auctions with Bidder-Determined Combinations
- Prophet inequalities made easy: stochastic optimization by pricing nonstochastic inputs
- Envy-free pricing in large markets: approximating revenue and welfare
- Polymatroid Prophet Inequalities
- Combinatorial Walrasian equilibrium
- Sequential posted price mechanisms with correlated valuations
- Prices in a combinatorial auction
- A simple and approximately optimal mechanism for a buyer with complements
- Market pricing for matroid rank valuations
- Max-min greedy matching
- Prophet matching with general arrivals
- Prophet inequalities for independent and identically distributed random variables from an unknown distribution
- Technical note -- Bifurcating constraints to improve approximation ratios for network revenue management with reusable resources
- scientific article; zbMATH DE number 7204414 (Why is no real title available?)
- Pricing social goods
- Tight revenue gaps among simple mechanisms
- Welfare maximization with production costs: a primal dual approach
- Welfare and profit maximization with production costs
- An O(\log \log m) Prophet Inequality for Subadditive Combinatorial Auctions
- scientific article; zbMATH DE number 7651221 (Why is no real title available?)
- scientific article; zbMATH DE number 7650074 (Why is no real title available?)
- Mechanism design for perturbation stable combinatorial auctions
- scientific article; zbMATH DE number 7765397 (Why is no real title available?)
- A Dual Approach for Dynamic Pricing in Multidemand Markets
- Walrasian pricing in multi-unit auctions
- Max-min greedy matching problem: hardness for the adversary and fractional variant
- Optimal prophet inequality with less than one sample
- A constant factor prophet inequality for online combinatorial auctions
- Multi-agent contracts
- Max-min greedy matching problem: hardness for the adversary and fractional variant
- A theory of simplicity in games and mechanism design
- Optimal item pricing in online combinatorial auctions
- The importance of knowing the arrival order in combinatorial Bayesian settings
- Prophet inequalities via the expected competitive ratio
- Prophet secretary for combinatorial auctions and matroids
- Order-competitive ratio
- Improved truthful mechanisms for combinatorial auctions with submodular bidders
- Non-adaptive matroid prophet inequalities
- Multi-agent contracts
- Nonbossy mechanisms: mechanism design robust to secondary goals
- Beating competitive ratio 4 for graphic matroid secretary
- q-partitioning valuations: exploring the space between subadditive and fractionally subadditive valuations
- Iterative Dutch combinatorial auctions
This page was built for publication: Combinatorial auctions via posted prices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5363025)
