None
Show that the factor of 1
2 in the prophet inequality cannot
be improved: for every constant c > 1
2 , there are distributions
G1, . . . , Gn such that every strategy, threshold or otherwise, has
expected value less than c · Eπ∼G[maxi πi].
(b) Prove that Theorem 6.4 does not hold with 50% replaced by
any larger constant factor.
Can the factor of 12 in the prophet inequality be improved for
the special case of i.i.d. distributions, with G1 = G2 = · · · =
Gn?
