I am having a difficulty on this problem (part a ) and would appreciate if someone can help.

Suppose you’re designing

strategies for selling items on a popular auction Web site. Unlike other

auction sites, this one uses a one-pass auction, in which each bid must be

immediately (and irrevocably) accepted or refused. Specifically,

• First, a seller puts up an item for sale.

• Then buyers appear in sequence.

• When buyer i appears, he or she makes a bid bi > 0.

• The seller must decide immediately whether to accept the bid or not.

If the seller accepts the bid, the item is sold and all future buyers are

turned away. If the seller rejects the bid, buyer i departs and the bid

is withdrawn; and only then does the seller see any future buyers.

Suppose an item is offered for sale, and there are n buyers, each with a

distinct bid. Suppose further that the buyers appear in a random order, and

that the seller knows the number n of buyers. We’d like to design a strategy

whereby the seller has a reasonable chance of accepting the highest of the n

bids. By a “strategy,” we mean a rule by which the seller decides whether to

accept each presented bid, based only on the value of n and the sequence of

bids seen so far.

For example, the seller could always accept the first bid presented. This

results in the seller accepting the highest of the n bids with probability only

1/n, since it requires the highest bid to be the first one presented.

(a) Give a strategy under which the seller accepts the highest of the n

bids with probability at least 1/4, regardless of the value of n. (For

simplicity, you are allowed to assume that n is an even number.) Prove

that your strategy achieves this probabilistic guarantee.