Communications of the ACM

Last byte

Upstart Puzzles: Auction Triplets

By Dennis Shasha
Communications of the ACM, November 2015, Vol. 58 No. 11, Page 136
10.1145/2825814
Comments

There are objects of four types and n people, each with a budget of $99. The objective of each one is to acquire three objects of the same type (any type) before anyone else does; for example, if player A acquires three type 1 objects before any other player acquires any three objects of any type, A wins. Assume each auction is resolved through a highest-bid method; that is, the highest bidder pays the amount he or she bids (Vickrey auctions are a possible variant.) Every bid must be an integral number of dollars. If there is a tie, the bidder (if any) who won the immediately preceding auction gets the item if that bidder is one of those who tied. In every other case, the tie ends in a draw, and nobody takes the item in that auction.

By symmetry, there cannot be a guaranteed winning strategy, but the general challenge is to work out probabilistically good strategies, given knowledge of the sequence of item types to be auctioned.

Warm-up. Suppose there are just two players and all items are of the same type. Is there an optimal bidding strategy?

Solution to this warm-up. The best strategy is to bid $33 every time. If you bid $33 and your opponent bids less, you will win, and the only way for your opponent to stop you is to bid $34 or more in the next auction. But if you keep bidding $33, the opponent will take a second item with $33 and spend $67. In that case, you win by bidding $33 thereafter.

Puzzle 1. Suppose again there are just two players and three items of type T1 and the rest of type T2. Assume player A gets the first item of type T1 for $12. Can A force a win?

Solution. Yes, by bidding any number divisible by three between $12 and $36 inclusive for the next item of type T1. If A wins again, then A bids $51 on the last T1 item. B must match to avoid losing, so B wins for, say, $52, but now A has $51, while B has only $50. A bets $17 each time for each element of T2. B cannot stop A. If B wins the second item for $13 or more, then A does not bid for the last T1 item but can win on T2 by bidding $29 (=(99−12)/3) from then on.

Puzzle 2. Suppose there are two players, A and B, but player A has $100, and player B has only $99. Suppose further there are items of only type 1. Can A force a win?

Solution. A starts with $34. If B ties, then A alternates randomly between $34 and $33. If A wins, then A bids $33 in the next bet. A will win on ties, so B must stop A by bidding $34. At that point, A bids $33 again. If B ties and takes a second item, then B has only $32, so A can continue to bid $33 and be sure to win.

Puzzle 3. Suppose there are several players and items of only type 1, and player A has two items and $m left, whereas each other player has at most one item and at most $2m−1 left. Can A force a win?

Solution. Yes. If A bets $m and someone else beats A, then that other player cannot have more than $m−1 left. If after a tie, A continues to bet $m or $m−1 then anyone who wins will have at most $m−1 left. Eventually each player but A has $m−1 left.

Now that you get the idea, here are the upstart questions for Auction Triplets.

Upstart 1. In a two-player bidding contest, if one player knows the sequence of items, but the other does not, what is the expected advantage of the player who knows? Assume each item in the sequence is generated uniformly at random across the four types.

Upstart 2. If there can be an arbitrary number of types and the sequence of the types of the objects to be auctioned is known beforehand, is there any bidding strategy (which may be randomized) that gives the best chance of winning?

Upstart 3. Now generalize the setting of Upstart 1 in which one player does not know the exact sequence of types but does know the distribution of types over some horizon of future items (such as half the next 20 items are T1).

Back to Top

Back to Top

The Digital Library is published by the Association for Computing Machinery. Copyright © 2015 ACM, Inc.

---

No entries found