TY - JOUR

T1 - Optimal item pricing in online combinatorial auctions

AU - Correa, José

AU - Cristi, Andrés

AU - Fielbaum, Andrés

AU - Pollner, Tristan

AU - Weinberg, S. Matthew

N1 - Publisher Copyright:
© 2023, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society.

PY - 2023

Y1 - 2023

N2 - We consider 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 there exist prices 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. Moreover, we prove that this bound is tight. Thus, our result not only improves upon the 1 / (4 d- 2) bound of Dütting et al., but also settles the approximation that can be achieved by using item prices. The existence of these prices follows from the existence of a fixed point of a related mapping, and therefore, it is non-constructive. However, we show how to compute such a fixed point in polynomial time, even if we only have sample access to the valuation distributions. We provide additional results for the special case when buyers’ valuations are known (but a posted-price mechanism is still desired), and an improved impossibility result for the special case of prophet inequalities for bipartite matching.

AB - We consider 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 there exist prices 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. Moreover, we prove that this bound is tight. Thus, our result not only improves upon the 1 / (4 d- 2) bound of Dütting et al., but also settles the approximation that can be achieved by using item prices. The existence of these prices follows from the existence of a fixed point of a related mapping, and therefore, it is non-constructive. However, we show how to compute such a fixed point in polynomial time, even if we only have sample access to the valuation distributions. We provide additional results for the special case when buyers’ valuations are known (but a posted-price mechanism is still desired), and an improved impossibility result for the special case of prophet inequalities for bipartite matching.

UR - http://www.scopus.com/inward/record.url?scp=85175057859&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85175057859&partnerID=8YFLogxK

U2 - 10.1007/s10107-023-02027-2

DO - 10.1007/s10107-023-02027-2

M3 - Article

AN - SCOPUS:85175057859

SN - 0025-5610

JO - Mathematical Programming

JF - Mathematical Programming

ER -