Optimal item pricing in online combinatorial auctions
The article examines the pricing problem in combinatorial auctions under the following assumptions: given a set of indivisible items and a set of buyers with randomly drown monotone valuations over subset of items; a decision maker sets item prices and then the buyers make sequential purchasing decision, taking their favorite set among the remaining items. In this paper, the authors parametrize an instance \(d\), the size of the largest set a buyer may want. It is shown that there exist prices such that the expected (over the random valuations) welfare of the allocation they induce is at least a factor \(\frac{1}{1+d}\) times the expected optimal welfare in hindsight. The obtained estimate is more accurate compared to the existing ones. The article discusses additional results for the special case when buyers' valuations are known. For the entire collection see [Zbl 1492.90008].
- An O(\log \log m) Prophet Inequality for Subadditive Combinatorial Auctions
- Approximation algorithms for combinatorial auctions with complement-free bidders
- Combinatorial auctions via posted prices
- Combinatorial Walrasian equilibrium
- Comparison of threshold stop rules and maximum for independent nonnegative random variables
- Computing Walrasian equilibria: fast algorithms and structural properties
- scientific article; zbMATH DE number 1219592 (Why is no real title available?)
- Matroid prophet inequalities
- Multi-parameter mechanism design and sequential posted pricing
- Non-approximability results for optimization problems on bounded degree instances
- Online contention resolution schemes
- Online mechanism design (randomized rounding on the fly)
- Prophet inequalities made easy: stochastic optimization by pricing nonstochastic inputs
- Simple mechanisms for subadditive buyers via duality
- Understanding preferences: ``demand types, and the existence of equilibrium with indivisibilities
- Algorithmic pricing for the partial assignment
- Item Pricing for Combinatorial Public Projects
- New Results on the Online Pricing Problem
- Approximation algorithms and online mechanisms for item pricing
- COMPETITIVE ALGORITHMS FOR ONLINE PRICING
- Prices in a combinatorial auction
- Market pricing for matroid rank valuations
- Welfare maximization with production costs: a primal dual approach
- Combinatorial auctions via posted prices
- Dynamic and nonuniform pricing strategies for revenue maximization
- Estimating intermediate price transitions in online auctions
- Pricing Commodities, or How to Sell When Buyers Have Restricted Valuations
- Welfare and profit maximization with production costs
- A Dual Approach for Dynamic Pricing in Multidemand Markets
- Pricing commodities
- A constant factor prophet inequality for online combinatorial auctions
- Optimal item pricing in online combinatorial auctions
- Simple and optimal online contention resolution schemes for k-uniform matroids
- Online combinatorial assignment in independence systems
- Online combinatorial assignment in independence systems
- Optimal starting price for eBay-like online auctions
This page was built for publication: Optimal item pricing in online combinatorial auctions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2164686)
