Posted Price Mechanisms and Optimal Threshold Strategies for Random Arrivals

José Correa (), Patricio Foncea (), Ruben Hoeksma (), Tim Oosterwijk () and Tjark Vredeveld ()
Additional contact information
José Correa: Universidad de Chile, Departamento de Ingeniería Industrial, Santiago 8370456, Chile
Patricio Foncea: Massachusetts Institute of Technology, Operations Research Center, Cambridge, Massachusetts 02139
Ruben Hoeksma: University of Twente, Faculty of Electrical Engineering, Mathematics and Computer Science, 7500 AE Enschede, Netherlands
Tim Oosterwijk: Maastricht University, School of Business and Economics, 6200 MD Maastricht, Netherlands
Tjark Vredeveld: Maastricht University, School of Business and Economics, 6200 MD Maastricht, Netherlands

Mathematics of Operations Research, 2021, vol. 46, issue 4, 1452-1478

Abstract: The classic prophet inequality states that, when faced with a finite sequence of nonnegative independent random variables, a gambler who knows the distribution and is allowed to stop the sequence at any time, can obtain, in expectation, at least half as much reward as a prophet who knows the values of each random variable and can choose the largest one. In this work, we consider the situation in which the sequence comes in random order. We look at both a nonadaptive and an adaptive version of the problem. In the former case, the gambler sets a threshold for every random variable a priori, whereas, in the latter case, the thresholds are set when a random variable arrives. For the nonadaptive case, we obtain an algorithm achieving an expected reward within at least a 0.632 fraction of the expected maximum and prove that this constant is optimal. For the adaptive case with independent and identically distributed random variables, we obtain a tight 0.745-approximation, solving a problem posed by Hill and Kertz in 1982. We also apply these prophet inequalities to posted price mechanisms, and we prove the same tight bounds for both a nonadaptive and an adaptive posted price mechanism when buyers arrive in random order.

Keywords: optimal stopping; threshold rules; prophet inequality; posted price mechanisms; mechanism design; computational pricing and auctions; Primary: 91B25; secondary: 91B26; 68W25; Primary: finance: asset pricing; secondary: decision analysis: approximations (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2020.1105 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:46:y:2021:i:4:p:1452-1478

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().