Prophet inequalities for cost of observation stopping problems

Comparisons are made between the expected gain of a prophet (an observer with complete foresight) and the maximal expected gain of a gambler (using only non-anticipating stopping times) observing a sequence of independent, uniformly bounded random variables where a non-negative fixed cost is charged for each observation. Sharp universal bounds are obtained under various restrictions on the cost and the length of the sequence. For example, it is shown for X1, X2, ... independent, [0, 1]-valued random variables that for all c >= 0 and all n >= 1 that E(max1 <= j <= n(Xj - jc)) - supt [set membership, variant] Tn E(Xt - tc) <= 1/e, where Tn is the collection of all stopping times t which are less than or equal to n almost surely.