Proof of O'Neill's Theorem

• Now we want to prove O'Neill's Theorem.
• Reminder: the idea behind the technique is called "proof by induction."
• Basic idea:
  • The first step is easy.
  • The second step is easy, if you already know the first step.
  • The third step is easy, if you know the first and second step.
  • etc.
• An analogy:
  • Imagine you build a robot and program it to do two things: grab hold of a ladder, and get from one step to the next.
  • Clearly the robot can then climb a ladder of any height.
  • So you don't have to program it to climb a ladder of any particular height.
• Actual method:
  • Prove that the first step is true.
  • Prove that the current step follows if you can assume that all the previous steps are true.
  • Then all steps must be true.

• Theorem (O'Neill, as presented by Taylor):
  Suppose two players are bidding in the dollar auction and using the conservative convention, with stakes s and bankroll b. Construct "special numbers" by the following procedure: b, b - (s-1), b - 2(s-1), b - 3(s-1), etc. If the other player has just bid x, then your optimal strategy is to:
  • bid the smallest "special number" higher than x, if your old bid was at least the previous "special number"; player two will then pass
  • pass otherwise
• Proof:
  • We use proof by induction. First prove the optimal strategy works for x=b. Next, assume we have already proved that the strategy works for any bid player two makes higher than x, and prove that it will also work for x.
  • The first step is if x is the highest possible bid, so x=b. Of course we must pass. This is what the strategy tells us as well, since there is no special number higher than b.
  • Now suppose the induction hypothesis: that for any bid more than x, the optimal strategy is to bid the next special number if the previous bid was at least the previous special number, and pass otherwise.
  • Suppose the first special number after x is Sp.
  • If we bid anything higher than x but lower than Sp, player two can bid Sp.
  • In fact, since Sp is the next special number after whatever our new bid is, and since player two's old bid x is at least the previous special number, that is exactly what s/he will do, by the induction hypothesis.
  • When player two bids Sp, we will also look at the induction hypothesis, and it will tell us to bid the next special number (which is Sp+s-1) if our previous bid was at least Sp, and pass otherwise. Our previous bid was less than Sp, so we will pass. Thus player two wins with a bid of Sp.
  • This is not a good strategy for us. We lose our entire bid, which is larger than x. This is worse than if we had passed and lost our old bid, smaller than x.
  • If we bid Sp, player two will definitely pass, by the induction hypothesis again, because his previous bid was lower than Sp. So we will win with Sp.
  • • If Sp is no more than (s-1) higher than our previous bid, then by Lemma B it is better to bid Sp than to pass or bid higher than Sp. By the previous bullet it is also better to bid Sp than to bid something lower than Sp. So in this case we should bid Sp.
    • If Sp is more than (s-1) higher than our previous bid, then by Lemma A we should pass.
  • So we have proven that the optimal strategy described in the theorem is correct if player two has just bid x, given that it is correct for any bid higher than x.
  • This completes the induction step.
  • Thus the theorem is true for any bid x, since it is true for b and its truth for all bids higher than x implies its truth for x.
End of proof
• Corollary (O'Neill, as presented by Taylor):
  If player one starts, then the optimal bid for player one is the smallest special number. Player two will then pass.

  Proof:

  This is the special case of O'Neill's theorem when player two's previous bid was x=0; then we should bid the next special number after that. The next special number after 0 is the smallest special number.
  End of proof