TY - GEN
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:
© 2022, Springer Nature Switzerland AG.
PY - 2022
Y1 - 2022
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. We further show how to compute our prices in polynomial time. We provide additional results for the special case when buyers’ valuations are known (but a posted-price mechanism is still desired).
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. We further show how to compute our prices in polynomial time. We provide additional results for the special case when buyers’ valuations are known (but a posted-price mechanism is still desired).
KW - Combinatorial Auctions
KW - Online allocations
UR - http://www.scopus.com/inward/record.url?scp=85131916084&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85131916084&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-06901-7_10
DO - 10.1007/978-3-031-06901-7_10
M3 - Conference contribution
AN - SCOPUS:85131916084
SN - 9783031069000
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 126
EP - 139
BT - Integer Programming and Combinatorial Optimization - 23rd International Conference, IPCO 2022, Proceedings
A2 - Aardal, Karen
A2 - Sanità, Laura
PB - Springer Science and Business Media Deutschland GmbH
T2 - 23rd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2022
Y2 - 27 June 2022 through 29 June 2022
ER -