Optimal Item Pricing in Online Combinatorial Auctions

José Correa, Andrés Cristi, Andrés Fielbaum, Tristan Pollner, S. Matthew Weinberg

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

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

Original languageEnglish (US)
Title of host publicationInteger Programming and Combinatorial Optimization - 23rd International Conference, IPCO 2022, Proceedings
EditorsKaren Aardal, Laura Sanità
PublisherSpringer Science and Business Media Deutschland GmbH
Pages126-139
Number of pages14
ISBN (Print)9783031069000
DOIs
StatePublished - 2022
Event23rd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2022 - Eindhoven, Netherlands
Duration: Jun 27 2022Jun 29 2022

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13265 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference23rd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2022
Country/TerritoryNetherlands
CityEindhoven
Period6/27/226/29/22

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Keywords

  • Combinatorial Auctions
  • Online allocations

Fingerprint

Dive into the research topics of 'Optimal Item Pricing in Online Combinatorial Auctions'. Together they form a unique fingerprint.

Cite this