Bob and Alice are playing an auction game. In a round of the auction a single coin is going to be put up for auction and Bob makes a bid on that coin. Alice can then either outbid him or pass. If Alice outbids Bob, she wins the bid, Bob does not get to bid again (the auction is once-around). Additionally, it is an all-pay auction, any bid you make you must pay, even if you lose the bid. The first person to acquire three coins wins the game.
It is clear that Alice has a large advantage in this game, so Bob gets to start with extra money. Given that Alice starts with $100, what is the minimum amount of money that Bob needs to start with so that he has a winning strategy?
To be clear, only nonnegative integer bids are allowed, no fractions. In a given round, Bob bids $k (and immediately pays it) and Alice gets the choice of either paying $(k+1) for the coin or letting Bob have it. Bob is allowed to bid zero (and will be forced to if he runs out of money), and Alice may then take the coin for $1 (which she will probably do unless she is out of money).
On the forums, the actual puzzle had an infinite number of rounds of bidding, and a player won as soon as they had a three coin lead. That puzzle had a much more complicated answer, but if I am honest the answer to this one is actually sort of boring once you get it, I just found it fun to solve out.
No comments:
Post a Comment