Suppose you\'re designing strategies for selling items on a popular auction Web

Question

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,

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

2. Then buyers appear in sequence.

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

4. 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.

Consider the following two phase algorithm that a seller may follow:
1) Reject the first n/10 bids but keep track of the largest bid seen. Call that bid B*.
2) In the remaining bids accept the first bid that surpasses B* (if none surpass B* then accept the very last bid)

Using the given algorithm, What is an upper and/or lower bound on the probability?

Explanation / Answer

If you picked the first one you'd only have a 1/N chance, as you pointed out. If you instead rejected the first bid (whatever it was) and accepted the first bid that was higher, you would have a sum(i=1, n-1, 1/i) chance of winning. In general your only choice is to reject some fraction of the bids and then accept the first offer that tops all of them. For small n you can calculate this. For large n the value approaches a limit (as a ratio, not a fixed number). Find the limit and you're done.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.