Optimal Item Pricing in Online Combinatorial Auctions

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

doi:10.1007/978-3-031-06901-7_10

Optimal Item Pricing in Online Combinatorial Auctions

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

^*Corresponding author for this work

Learning & Autonomous Control

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

2 Citations (Scopus)

26 Downloads (Pure)

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 language	English
Title of host publication	Integer Programming and Combinatorial Optimization
Subtitle of host publication	Proceedings of the 23rd International Conference, IPCO 2022
Editors	Karen Aardal, Laura Sanità
Publisher	Springer
Pages	126-139
ISBN (Electronic)	978-3-031-06901-7
ISBN (Print)	978-3-031-06900-0
DOIs	https://doi.org/10.1007/978-3-031-06901-7_10
Publication status	Published - 2022
Event	23rd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2022 - Eindhoven, Netherlands Duration: 27 Jun 2022 → 29 Jun 2022

Publication series

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

Conference

Conference	23rd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2022
Country/Territory	Netherlands
City	Eindhoven
Period	27/06/22 → 29/06/22

Bibliographical note

Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care
Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Keywords

Combinatorial Auctions
Online allocations

Access to Document

10.1007/978-3-031-06901-7_10

Correa2022_Chapter_OptimalItemPricingInOnlineCombFinal published version, 326 KB

Cite this

Correa, J., Cristi, A., Fielbaum, A., Pollner, T., & Weinberg, S. M. (2022). Optimal Item Pricing in Online Combinatorial Auctions. In K. Aardal, & L. Sanità (Eds.), Integer Programming and Combinatorial Optimization : Proceedings of the 23rd International Conference, IPCO 2022 (pp. 126-139). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13265 LNCS). Springer. https://doi.org/10.1007/978-3-031-06901-7_10

Correa, José ; Cristi, Andrés ; Fielbaum, Andrés et al. / Optimal Item Pricing in Online Combinatorial Auctions. Integer Programming and Combinatorial Optimization : Proceedings of the 23rd International Conference, IPCO 2022. editor / Karen Aardal ; Laura Sanità. Springer, 2022. pp. 126-139 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{b4332a02143a40f18e66a08f56d2fd48,

title = "Optimal Item Pricing in Online Combinatorial Auctions",

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{\"u}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{\textquoteright} valuations are known (but a posted-price mechanism is still desired).",

keywords = "Combinatorial Auctions, Online allocations",

author = "Jos{\'e} Correa and Andr{\'e}s Cristi and Andr{\'e}s Fielbaum and Tristan Pollner and Weinberg, {S. Matthew}",

note = "Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.; 23rd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2022 ; Conference date: 27-06-2022 Through 29-06-2022",

year = "2022",

doi = "10.1007/978-3-031-06901-7_10",

language = "English",

isbn = "978-3-031-06900-0",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "126--139",

editor = "Karen Aardal and Laura Sanit{\`a}",

booktitle = "Integer Programming and Combinatorial Optimization",

}

Correa, J, Cristi, A, Fielbaum, A, Pollner, T & Weinberg, SM 2022, Optimal Item Pricing in Online Combinatorial Auctions. in K Aardal & L Sanità (eds), Integer Programming and Combinatorial Optimization : Proceedings of the 23rd International Conference, IPCO 2022. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13265 LNCS, Springer, pp. 126-139, 23rd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2022, Eindhoven, Netherlands, 27/06/22. https://doi.org/10.1007/978-3-031-06901-7_10

Optimal Item Pricing in Online Combinatorial Auctions. / Correa, José; Cristi, Andrés; Fielbaum, Andrés et al.
Integer Programming and Combinatorial Optimization : Proceedings of the 23rd International Conference, IPCO 2022. ed. / Karen Aardal; Laura Sanità. Springer, 2022. p. 126-139 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13265 LNCS).

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

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 - Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

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

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 - 978-3-031-06900-0

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

A2 - Aardal, Karen

A2 - Sanità, Laura

PB - Springer

T2 - 23rd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2022

Y2 - 27 June 2022 through 29 June 2022

ER -

Correa J, Cristi A, Fielbaum A, Pollner T, Weinberg SM. Optimal Item Pricing in Online Combinatorial Auctions. In Aardal K, Sanità L, editors, Integer Programming and Combinatorial Optimization : Proceedings of the 23rd International Conference, IPCO 2022. Springer. 2022. p. 126-139. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-06901-7_10

Optimal Item Pricing in Online Combinatorial Auctions

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this