Designing an algorithm to guarantee accepting an outcome with at least 1/4 probability Here is a problem that I am stumped with.
There are n buyers in this auction, each with a distinct bid b_i > 0. The buyers appear in a random order and the seller must decide immediately whether to accept the current buyer’s bid or not. If he accepts, he makes a profit of b_i and the auction terminates. Otherwise, the bid is withdrawn and the seller may see the next buyer. Design a strategy (algorithm) that guarantees that the seller accepts the highest of the n bids with probability at least 1/4, regardless of n, which you may assume even for simplicity.
So far, I've considered four cases depending on whether the highest and second highest bids fall under the first and second halves of n.