8
$\begingroup$

Saw this on TV today:

A man is auctioning a real $20\$$ bill. There are a vast number of bidders. A person may make as many bids as he wants. The starting bid is $5\$$. No $2$ bids must be equal, and bids are in increments of $1\$$. The highest bidder wins. Bidding can go on indefinitely.

However, there is a catch. The second highest bidder must also pay his last bid, even though he gets nothing in return.

On the show, they were trying to analyse how our brain works. I'm asking a slightly different question. What is the optimal strategy?

Case I: All bidders play perfectly.

Case II: Bidders are humans, so some of them may deviate from the perfect strategy.

Is the best option not to bid at all? Or a bid till a certain amount and stop?

And lastly, has this Q been explored elsewhere?

Edit: Bidders are anonymous, and do not form contracts.

Improve this question
$\endgroup$
3
  • $\begingroup$ If bidders are allowed to cooperate with other bidders : Best Strategy is "One bidder goes for the lowest amount, nobody else bids, winner shares the profits with all bidders". If no way to cooperate with other bidders : Best Strategy is "Do not bid". $\endgroup$
    – Prem
    Commented May 16, 2015 at 11:40
  • 3
    $\begingroup$ I like this game, I think I'll move to London and make tons of money in the most crowded city squares. $\endgroup$
    – leoll2
    Commented May 16, 2015 at 11:46
  • $\begingroup$ @Prem Please add as an answer (with proper reasoning, of course) $\endgroup$
    – ghosts_in_the_code
    Commented May 16, 2015 at 15:53

6 Answers 6

Reset to default
9
$\begingroup$

Case I:

Let us suppose that each player can bid any integer equal to or above the current minimum bid. Then:

Without knowing the total bankroll that each player has to invest, we cannot calculte the optimal strategies. If we know that the bankroll of each player is b, the optimal strategy is for the first player to bid ($(b-1)$ mod 19)+1 and the subsequent players not to bid. (Irrespective of bankroll b, there is also a trivial Nash equilibrium in which the first player bids $20 and all other players drop.)

Barry O'Neill develops a simple formula for this strategy in a 1986 article in the Journal of Conflict Resolution.

If we play by the exact rules listed here--first player must bid \$5 and each bid must increase by an increment of one dollar--I do not know the optimal solution.

Case II: Playing against humans

I've never seen the auctioneer take a loss when this game is played in real life, so the optimal strategy is not to bid at all. (If the bidders may form binding contracts to collude, i.e., if we treat this as a cooperative game, then of course they can buy the \$20 bill for \$5 and share the profits.)

Has this been explored elsewhere?

This puzzle is known as the dollar auction and was first posed by Martin Shubik in a 1971 article in the journal of Conflict Resolution.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Assume bankroll is infinity. Players will bid any amount, as long as it is a better option than not bidding. $\endgroup$
    – ghosts_in_the_code
    Commented May 16, 2015 at 15:56
  • $\begingroup$ If we want an optimal strategy when all players play perfectly, I don't know how to interpret this other then as seeking a Nash equilibrium. If the bankroll is infinite, there's no way to use backward induction on the extended form game tree to determine Nash equilibrium strategies. I suspect that in this case there is no Nash equilibrium other than the trivial one where a leading player bids $20 and everyone else drops - though I don't have a proof of it. $\endgroup$
    – Corvus
    Commented May 16, 2015 at 18:20
  • 1
    $\begingroup$ Why does the majority of this answer need to be hidden? What does the spoiler markup achieve? $\endgroup$
    – jscs
    Commented May 16, 2015 at 18:29
  • $\begingroup$ @Corvus Why can't the leading player bid $19? $\endgroup$
    – ghosts_in_the_code
    Commented May 17, 2015 at 15:06
  • $\begingroup$ A proper answer would require a very long explanation of Nash equilibria in extended form games, the subgame perfection concept, and the use of subgame imperfect strategies as threats. I could try to write up a short version of that if people are interested. A short hint of the answer is laid out in O'Neill's paper: $\endgroup$
    – Corvus
    Commented May 17, 2015 at 19:39
1
$\begingroup$

Case I:

If no bid exists, bid 5$. Otherwise, do not bid. ("Fastest" bidder wins)
This should be is optimal under all reasonable metrics since there's no way to achieve a larger profit, nor a way to split the profit (unless bidders are allowed to split it after winning).

Case II:

A risk-less strategy is not to bid.

A riskier strategy is to bid 19\$ if no bid exists, and nothing otherwise. This can give you a profit of 1$ assuming no human bidders decide to screw you over for no profit for themselves.
(Was this riskier strategy ever attempted in a live game? Would be interesting to see the result!)

Improve this answer
$\endgroup$
4
  • $\begingroup$ The $19 bid for the first player should work. The others don't have any incentive to screw you, but if they did you would have an incentive to raise your bid, making them lose money. Of course, you never know with human nature... $\endgroup$
    – raven
    Commented May 16, 2015 at 14:09
  • 3
    $\begingroup$ Your case I is far from optimal. I respond to your strategy by bidding \$6; your strategy says you make no more bids, so you lose \$5 and I gain \$14. $\endgroup$
    – David Richerby
    Commented May 16, 2015 at 15:35
  • $\begingroup$ @JaimePardos By O'Neill's theorem, the $19 bid cannot possibly be a Nash equilibrium for any finite bankroll because b mod 19 will never equal 19. $\endgroup$
    – Corvus
    Commented May 16, 2015 at 18:24
  • $\begingroup$ Why does this answer need to be hidden? What does the spoiler markup achieve? $\endgroup$
    – jscs
    Commented May 16, 2015 at 18:29
1
$\begingroup$

Case I: All bidders play perfectly.

SubCase A : If bidders are allowed to cooperate with other bidders : Best Strategy is "One nominated bidder goes for the lowest amount, nobody else bids, winner shares the profits with all bidders". Guaranteed profit for all bidders.
SubCase B : If no way to cooperate with other bidders, and any number of people can bid at the same time : Best Strategy is "Do not bid". If you do bid, and somebody else also bids simultaneously, then you both lose money eventually.
SubCase C : If no way to cooperate with other bidders, but only one person at a time can bid (Example : there is always some order in which people can either bid or skip bidding in current state) : Best Strategy is "Do not bid, unless you are the first bidder". Nobody else will bid against you, because they know that you will both lose money. Guaranteed profit for one bidder who may choose to share the profit.
What SubCase C means is : If auctioneer goes around asking "B1, do you want to bid ?" "B2, do you want to bid ?" "B3, do you want to bid ?" "B4, do you want to bid ?", and back again, then only B1 should say "YES". If two more more people say "YES" , then they will all lose money.

Case II: Bidders are humans, so some of them may deviate from the perfect strategy.

For all three SubCases above, in case II : Let us say the best strategy involves bidding. What happens if somebody deviates from that strategy ? Two or more people will lose money.
So Best Strategy for all SubCases must be "Do not bid".

ANSWER EDIT: As per Question Edit: Bidders are anonymous, and do not form contracts. So SubCase A can be removed from the list, leaving only SubCase B & SubCase C.

Improve this answer
$\endgroup$
1
$\begingroup$

Once you bid, you lose. [note 1] Knowing this, nobody should bid. If someone does, at a level below $19, there is motivation for someone else to bid. (It isn't very much motivation, and should be resisted, but probably won't be.) Once there are bids of n and n+1, whether these are less than 20 or not, the n bidder stands to lose n unless they bid n+2. This of course puts the n+1 bidder in the same spot, so they bid n+3, forcing the n+2 bidder to move up to n+4. In real life this continues until people accept they are going to lose some money and stop bidding in order to stop the amount from increasing. It's a matter of luck which bidder will stop first.

[note 1:] In theory there is a small chance that nobody will bid after you. It would be wisest for nobody to bid after you. But somebody probably will. The auctioneer will goad them into it. "Come on lads, you're going to let him buy a twenty for 5? Nobody has 6? Nobody? What's your problem, just step up and say 6 and it's yours!"

Not only will the auctioneer make money (they do so once the bids are 10 and 11) they are likely to double their money because people will keep going until they get past 20 - either bidding 19 and thinking the other person won't bid 20, or bidding 20 and thinking the other person won't bid 21. But once you're going to lose 20 if you don't bid, you'll bid 22 and so on.

The only way to win is not to play.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Not quite. Please see the O'Neill paper referenced in my answer. If the players have a finite bankroll, there is a way for players to make money. This is of course predicated on accepting Nash equilibrium as the appropriate interpretation of playing optimally when all players play perfectly. This will only work if players can commit to playing subgame imperfect strategies in the extended form game. $\endgroup$
    – Corvus
    Commented May 16, 2015 at 18:29
  • $\begingroup$ well, we've been told all players have infinite bankrolls. What's that mod 19? $\endgroup$
    – Kate Gregory
    Commented May 16, 2015 at 18:57
  • $\begingroup$ Good point. With an infinite bankroll your answer is quite likely correct. The mod 19 comes from O'Neills theorem where you divide the bankroll minus one by the prize minus one and take the remainder to find the optimal leading bid. And I completely agree about how this plays out in practice with real humans. I've done this in a game theory class on occasion and always net more than the value of the prize (but never actually make the students pay). $\endgroup$
    – Corvus
    Commented May 16, 2015 at 19:07
  • 1
    $\begingroup$ And anyway, say I knew you had $500 in your pocket, so I worked out a starting bid (in this variant we have to start at 5, but pretend we don't) so that I end up bidding 500 and you can't bid 501, so I "win" and get 20 for 500. That's better than getting nothing for 499 like you, but neither of us has won. Right? Unless I know you have 11 or something else less than the prize (but then we wouldn't need to mod anything), there really isn't any way this turns out well. $\endgroup$
    – Kate Gregory
    Commented May 16, 2015 at 19:11
0
$\begingroup$

Let $P_n$ be the probability that a human player would rather bid $n+1$ than lose $n-1$. Let $Q_n$ be the probability that a human player who has nothing to lose would bid $n+1$. These values would vary with $n$, so we will have to carry out huge surveys to get these values.

Let $k$ be the number of players. Let $R_n$ be the probability of winning the auction by bidding $n$.

Now, we know that we do not win if the event in $P_n$ occurs. We also do not win if any of the other $k-2$ players decides to enter the auction. Therefore, none of the events mentioned should occur. $$R_n=(1-P_n)(1-Q_n)^{k-2}$$

If we bid $n$, our winning is $20-n$ if we win and our loss is $n$ if we lose. Hence we must bid $n$ only if $$Winnings\times Probability_{Winning}>Loss\times Probability_{Losing}$$ or $$(20-n)\times R_n>n\times (1-R_n)$$

P. S. I've not actually learnt these probability concepts, so please correct me where I'm wrong.

Improve this answer
$\endgroup$
1
  • $\begingroup$ @Prem Here's the new answer. $\endgroup$
    – ghosts_in_the_code
    Commented May 18, 2015 at 5:48
0
$\begingroup$

There are too many possible interpretations of the rules:

Case 1: You are not allowed to bid twice in a row

Perfect play: The best Option is not to bid at all, because bidding 5$ will lose you money.

Explanation: It is hard to put a starting point to analyse possible strategies because of infinite payrolls. But if every player plays a perfect strategy and can predict all other players, we have absolutely no chance involved and the outcome of each round can be predicted perfectly beforehand. Therefore there is no risky gamble, but always an expected Win/Loss.

In this scenario nobody will ever bid 21, because when you bid 21 you are guaranteed to loose at least 1\$ so whatever strategy would lead you to bid 21 eventually would never be taken in the first place, because not bidding at all is better than loosing.

This means you can always safely bet 20 without loosing or winning anything, because no one will ever bid 21 in perfect play. What about 19 ? If you bet 19, you can be sure that the guy who did bet 18 will now bet 20, because 20 is safe and will give him 0 loss (and nobody will ever bet 21, because nobody will use a loosing strategy leading him there) So betting 19 is a guaranteed loss.

This in case makes 18 to a perfectly safe bid, since no one will ever bet the sure loss of 19. And by induction we can follow this road downwards. Nobody will ever bet 17, since the next guy will pick 18 and you can't pick 19 because 19 is a sure loss. So all odd numbers are a guaranteed loss. So all perfect players will only ever bet even numbers.

So if the starting bid would be 4 or 6 (or any even number) the first one to bid would win. But so nobody will bid 5\$ since it is a guaranteed loss.

Case 2: One bidder can bid multiple times in a row and has to pay his last 2 bids if he wins

So if I bid 5\$ and then immediately overbid myself with 6\$ and no one else bids, I would get the 20 but would have to pay 5 and 6 (highest and second highest bid) so my net win would be 9\$.

In this case someone can always try to jump an odd number, by bidding twice in a row and get a winning even number. So the first bid would be 5+6 (since paying both bids is only 11 and you get 20 net win 9\$) next save bid is 7+8 and then 9+10. Nobody will bet 11, since 11+12 (or any other two bets in a row over 10) will result in a net loss. So the first one to bet 10 wins. So the question is how the bidding system actually works. But everyone will start bidding up to 10, or nobody will bid at all, depending on the number of your chances to get the two bets in a row. So with two people it is still attractive to try and get the bets 9+10 (if we assume chances 50/50 to get the 9\$ and 50/50 to get the 10\$, expected net results are 0,-9,1,10 so an expected winning of 0.5\$)

Case 3: One bidder can bid multiple times in a row, but whoever else is highest below him has to pay the extra

So if Geoffrey bids 5\$ and I bid 6,7 and 8 afterwards and no one else bids, I would get the 20\$ for 8 and Geoffrey would loose his 5\$ as second highest bidder.

This will also result in a race to the top, cut off depending on the chances of getting you bet in (so the number of people)

Case X: Humans involved with unpredictable bids

Don't bet at all, or try psychological tricks to intimidate them like at the poker-table. But this is too unpredictable, best to not bid at all... Or probably bid 5\$ and try to intimidate everyone away from bidding and if someone bids higher, let them destroy each other.

Improve this answer
$\endgroup$
7
  • $\begingroup$ It is not possible to intimidate people to leave right at the beginning. If they do not believe your explanation, they will use their own logic, which obviously says they should bid 6$. If they do believe that you are right in saying it is best not to bid, they trust you. In which case, what are you entering the bidding for? $\endgroup$
    – ghosts_in_the_code
    Commented May 18, 2015 at 15:26
  • $\begingroup$ In this scenario nobody will ever bid 21, because when you bid 21 you are guaranteed to loose at least 1$ so whatever strategy would lead you to bid 21 eventually would never be taken in the first place, because not bidding at all is better than loosing. Not true, at least if you are talking about Nash equilibrium. A Nash equilibrium strategy will certainly including bidding 21, as a threat to deter lower bids. Simple example: Suppose I big 19. f I promise not to bid 21, then I'm opening the door for you to bid 20 above me. By bidding 21, I might be able to deter a bid of 20. $\endgroup$
    – Corvus
    Commented May 18, 2015 at 15:33
  • $\begingroup$ @Corvus but that is the problem in this game, with an infinite payroll, there is no certain end to overbidding each other until the end of time... But we can conclude, that if you would bid 21 and you had perfect future vision, you would not have gone that path. You would never bet 19 in the first place, if you know I'm going to bet 20, because even if you then bet 21, it is never gonna get better, only worse $\endgroup$
    – Falco
    Commented May 18, 2015 at 16:10
  • $\begingroup$ @falco I think you're confusing Nash equilibrium with subgame perfect Nash equilibrium. There are many extensive form games in which we have Nash equilibria such that one player deters another by "threatening" a subgame imperfect action. This is the basic logic underlying O'Neill's theorem. BTW, we know that not playing at all is not a Nash equilibrium, because if everyone follows that strategy I can gain by unilaterally changing my own strategy to bid $1. $\endgroup$
    – Corvus
    Commented May 18, 2015 at 16:34
  • 1
    $\begingroup$ @Falco This "only bid even amounts" strategy is a very interesting one. As you say, it does seem to be a weak Nash equilibrium where everyone is kept out by threat. $\endgroup$
    – Corvus
    Commented May 21, 2015 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.