Title: Optimal Item Pricing in Online Combinatorial Auctions

Abstract: In this talk, I will present a result about a fundamental pricing problem in combinatorial auctions. We are given a set of indivisible items and a set of buyers with randomly drawn monotone valuations over subsets of items. A decision-maker sets item prices, and then the buyers make sequential purchasing decisions taking their favorite set among the remaining items. We parametrize an instance by d, the size of the largest set a buyer may want. Our main result asserts that prices exist such that the expected (over the random valuations) welfare of the allocation they induce is at least a factor 1/(d + 1) times the expected optimal welfare in hindsight. This result settles the approximation we can achieve by using item prices. I will present a sketch of our proof, which is based on constructing a map of which the optimal prices are a fixed point. Finally, I will discuss how to approximate this fixed point in polynomial time, using sample access to the valuations’ distributions.

Joint work with A. Fielbaum, T. Pollner, M. Weinberg, and J. Correa