TY - GEN
T1 - Posted Price Mechanisms for a Random Stream of Customers
AU - Correa, José R.
AU - Foncea, Patricio
AU - Hoeksma, Ruben
AU - Oosterwijk, Tim
AU - Vredeveld, Tjark
N1 - No data used
PY - 2017
Y1 - 2017
N2 - Posted price mechanisms constitute a widely used way of selling items to strategic consumers. Although suboptimal, the attractiveness 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 setting in which all offers are sent to the customers beforehand, and the adaptive setting in which an offer is made when a consumer arrives. For the nonadaptive case, we obtain a strategy achieving an expected revenue within at least a 1-1/e 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 setting and in particular our result for i.i.d. random valuations resolves a problem posed by Hill and Kertz.
AB - Posted price mechanisms constitute a widely used way of selling items to strategic consumers. Although suboptimal, the attractiveness 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 setting in which all offers are sent to the customers beforehand, and the adaptive setting in which an offer is made when a consumer arrives. For the nonadaptive case, we obtain a strategy achieving an expected revenue within at least a 1-1/e 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 setting and in particular our result for i.i.d. random valuations resolves a problem posed by Hill and Kertz.
UR - http://delivery.acm.org/10.1145/3090000/3085137/p169-
U2 - 10.1145/3033274.3085137
DO - 10.1145/3033274.3085137
M3 - Conference article in proceeding
SN - 978-1-4503-4527-9
SP - 169
EP - 186
BT - EC '17 Proceedings of the 2017 ACM Conference on Economics and Computation
PB - ACM New York
ER -