DOI: 10.1145/2825814 Dennis Shasha
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).
All are invited to submit their solutions to
firstname.lastname@example.org; solutions to upstarts
and discussion will be posted at http://cs.nyu.edu/cs/
Dennis Shasha ( email@example.com) is a
professor of computer science in the Computer Science
Department of the Courant Institute at New York
University, New York, as well as the chronicler of his good
friend the omniheurist Dr. Ecco.
Copyright held by author.
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
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
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