Optimal item pricing in online combinatorial auctions (Q2164686)

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].