Posted price mechanisms for a random stream of customers

José Correa, Patricio Foncea, Ruben Hoeksma, Tim Oosterwijk, Tjark Vredeveld

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

26 Citations (Scopus)

Abstract

Posted price mechanisms constitute a widely used way of selling items to strategic consumers. Although suboptimal, the affractiveness of these mechanisms comes from their simplicity and easy implementation. In this paper, we investigate the performance of posted price mechanisms when customers arrive in an unknown random order. We compare the expected revenue of these mechanisms to the expected revenue of the optimal auction in two different settings. Namely, the nonadaptive se.ing in which all o.ers are sent to the customers beforehand, and the adaptive se.ing in which an o.er is made when a consumer arrives. For the nonadaptive case, we obtain a strategy achieving an expected revenue within at least a 11e fraction of that of the optimal auction. We also show that this bound is tight, even if the customers have i.i.d. valuations for the item. For the adaptive case, we exhibit a posted price mechanism that achieves a factor 0:745 of the optimal revenue, when the customers have i.i.d. valuations for the item. Furthermore, we prove that our results extend to the prophet inequality se.ing and in particular our result for i.i.d. random valuations resolves a problem posed by Hill and Kertz [13].

Original languageEnglish
Title of host publicationEC 2017 - Proceedings of the 2017 ACM Conference on Economics and Computation
PublisherAssociation for Computing Machinery (ACM)
Pages169-186
Number of pages18
ISBN (Electronic)9781450345279
DOIs
Publication statusPublished - 20 Jun 2017
Externally publishedYes
Event18th ACM Conference on Economics and Computation, EC 2017 - Cambridge, United States
Duration: 26 Jun 201730 Jun 2017
Conference number: 18
http://www.sigecom.org/ec17/

Publication series

NameEC 2017 - Proceedings of the 2017 ACM Conference on Economics and Computation

Conference

Conference18th ACM Conference on Economics and Computation, EC 2017
Abbreviated titleACM EC 2017
CountryUnited States
CityCambridge
Period26/06/1730/06/17
Internet address

Keywords

  • Mechanism design
  • Posted prices
  • Prophet inequality

Fingerprint Dive into the research topics of 'Posted price mechanisms for a random stream of customers'. Together they form a unique fingerprint.

  • Cite this

    Correa, J., Foncea, P., Hoeksma, R., Oosterwijk, T., & Vredeveld, T. (2017). Posted price mechanisms for a random stream of customers. In EC 2017 - Proceedings of the 2017 ACM Conference on Economics and Computation (pp. 169-186). (EC 2017 - Proceedings of the 2017 ACM Conference on Economics and Computation). Association for Computing Machinery (ACM). https://doi.org/10.1145/3033274.3085137