TY - JOUR

T1 - Posted Price Mechanisms and Optimal Threshold Strategies for Random Arrivals

AU - Correa, José

AU - Foncea, Patricio

AU - Hoeksma, Ruben

AU - Oosterwijk, Tim

AU - Vredeveld, Tjark

PY - 2021/3/11

Y1 - 2021/3/11

N2 - he 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.

AB - he 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.

KW - Optimal stopping

KW - Threshold rules

KW - Prophet inequality

KW - Posted Price Mechanisms

KW - Mechanism design

KW - Computational pricing and auctions

UR - https://doi.org/10.1287/moor.2020.1105

U2 - 10.1287/moor.2020.1105

DO - 10.1287/moor.2020.1105

M3 - Article

JO - Mathematics of operations research

JF - Mathematics of operations research

SN - 0364-765X

ER -